math - 如何组合复杂的多边形？

Question

给定两个多边形:

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))

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

Dave's example使用 SQL Server 生成联合，但我需要在代码中完成相同的任务。我正在寻找任何能够公开实际数学的语言的数学公式或代码示例。我正在尝试制作将国家动态地组合成区域的 map 。我在这里问了一个相关问题:Grouping geographical shapes

Answer 1

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

<小时/>

第 1 步:创建描述多边形的图形。

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

我们应该找到交叉点。迭代两个多边形中的所有多边形边 [O(n*m)] 并找到所有交点。

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

• 如果发现任何交叉点，则将它们按长度排序到起始点，然后将所有交叉点相加顶点(起点、终点和交点)并连接它们(已经在排序顺序)到边缘。

第2步.检查构造图

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

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

第 3 步:找到左下顶点。

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

第 4 步:构建公共(public)轮廓。

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

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

我计算两个向量:当前边缘的向量 1 和每个下一个未访问边缘的向量 2(如图所示)。

对于我计算的向量:

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

结果我得到了一条具有最大角度的边(以及相应的下一个顶点)。

我将每个传递的顶点添加到结果列表中。结果列表是并集多边形。

备注

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