如何组合复杂的多边形? [英] How do I combine complex polygons?

问题描述

给定两个多边形:

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

如何计算并集(组合多边形)?

How can I calculate the union (combined polygon)?

Dave 的示例 使用 SQL 服务器来生成联合，但我需要在代码中完成相同的操作.我正在寻找任何公开实际数学的语言的数学公式或代码示例.我正在尝试制作将国家动态组合成区域的地图.我在这里问了一个相关的问题:地理形状分组

Dave's example uses SQL server to produce the union, but I need to accomplish the same in code. I'm looking for a mathematical formula or code example in any language that exposes the actual math. I am attempting to produce maps that combine countries dynamically into regions. I asked a related question here: Grouping geographical shapes

推荐答案

这是一个很好的问题.前段时间我在 c# 上实现了相同的算法.该算法构造两个多边形的公共轮廓(即构造一个没有孔的联合).在这里.

This is a very good question. I implemented the same algorithm on c# some time ago. The Algorithm constructs a common contour of two polygons (i.e. Constructs a union without holes). Here it is.

输入:第一个多边形(n 个点)，第二个多边形(m 个点).输出:图形.顶点 - 交点的多边形点.

Input: first polygon (n points), second polygon (m points). Output: graph. Vertex - polygon point of intersection point.

我们应该找到交叉点.遍历两个多边形 [O(n*m)] 中的所有多边形边并找到任何交点.

We should find intersections. Iterate through all polygon sides in both polygons [O(n*m)] and find any intersections.

• 如果没有找到交点，只需添加顶点并连接它们到边缘.

• If an intersection is not found, simply add vertices and connect them to the edge.

如果找到任何交叉点，将它们按长度排序到它们的起点，添加所有顶点(开始、结束和交叉点)并连接它们(已经在排序顺序)到边缘.

If any intersections are found, sort them by length to their start point, add all vertexes (start, end and intersections) and connect them (already in sorted order) to the edge.

如果我们在建图时没有找到任何交点，我们有以下情况之一:

If we did not find any intersection points when graph was built, we have one of the following conditions:

1. 多边形 1 包含多边形 2 - 返回多边形 1
2. 多边形 2 包含多边形 1 - 返回多边形 2
3. 多边形 1 和多边形 2 不相交.返回多边形 1 和多边形 2.

步骤 3. 找到左下角的顶点.

找到最小的 x 和 y 坐标(minx，miny).然后找到 (minx, miny) 和多边形点之间的最小距离.该点将是左下角的点.

Step 3. Find left-bottom vertex.

Find the minimum x and y coordinates (minx, miny). Then find the minimum distance between (minx, miny) and the polygon's points. This point will be the left-bottom point.

我们从左下角开始遍历图形并继续直到我们回到它.一开始，我们将所有边标记为未访问.在每次迭代中，您应该选择下一个点并将其标记为已访问.

We start to traverse the graph from the left-bottom point and continue until we get back into it. At the beginning we mark all edges as unvisited. On every iteration you should select the next point and mark it as visited.

要选择下一个点，请选择逆时针方向具有最大内角的边.

To choose the next point, choose an edge with a maximum internal angle in counter-clockwise direction.

我计算了两个向量:vector1 用于当前边，vector2 用于每个下一个未访问的边(如图所示).

I calculate two vectors: vector1 for current edge and vector2 for each next unvisited edge (as presented in the picture).

对于我计算的向量:

1. 标量积(点积).它返回一个与向量之间的角度相关的值.
2. 矢量积(叉积).它返回一个新的向量.如果这个 z 坐标向量是正的，标量积给了我直角逆时针方向.否则(z 坐标为负)，我计算向量之间的角度为 360 - 来自标量的角度产品.

结果我得到了最大角度的边(和对应的下一个顶点).

As a result I get an edge (and a correspond next vertex) with the maximum angle.

我将每个通过的顶点添加到结果列表中.结果列表是联合多边形.

I add to result list each passed vertex. Result list is the union polygon.

1. 该算法允许我们合并多个多边形 - 以迭代应用多边形对.
2. 如果您的路径由许多贝塞尔曲线和直线组成，您应该先将这条路径展平.

这篇关于如何组合复杂的多边形?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！