如何组合复杂的多边形？
gre*_*ade 74 math union geometry
给出两个多边形:
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的例子使用SQL服务器来生成联合,但我需要在代码中完成相同的操作.我正在寻找任何暴露实际数学的语言的数学公式或代码示例.我正在尝试制作将国家动态组合到地区的地图.我在这里问了一个相关的问题:分组地理形状
xtm*_*tmq 58
这个问题问得好.我前段时间在c#上实现了相同的算法.算法构造两个多边形的公共轮廓(即构造一个没有孔的联合).这里是.
步骤1.创建描述多边形的图形.
输入:第一个多边形(n个点),第二个多边形(m个点).输出:图表.顶点 - 多边形交点.
我们应该找到交叉点.遍历两个多边形[O(n*m)]中的所有多边形边并找到任何交点.
如果未找到交点,只需添加顶点并将它们连接到边.
如果找到任何交叉点,则按长度对它们的起点进行排序,添加所有顶点(开始,结束和交叉点)并将它们(已按排序顺序)连接到边缘.
第2步.检查构造的图形
如果在构建图形时我们没有找到任何交叉点,则我们具有以下条件之一:
- Polygon1包含polygon2 - 返回polygon1
- Polygon2包含polygon1 - 返回polygon2
- Polygon1和polygon2不相交.返回polygon1和polygon2.
第3步.找到左下角的顶点.
找到最小x和y坐标(minx,miny).然后找到(minx,miny)和多边形点之间的最小距离.这一点将是左下角.
步骤4.构建共同的轮廓.
我们开始从左下角遍历图形并继续直到我们回到它.在开始时,我们将所有边标记为未访问.在每次迭代中,您应该选择下一个点并将其标记为已访问.
要选择下一个点,请选择逆时针方向具有最大内角的边.
我计算了两个向量:当前边缘的vector1和每个下一个未访问边缘的vector2(如图所示).
对于我计算的向量:
- 标量积(点积).它返回与矢量之间的角度相关的值.
- 矢量产品(交叉产品).它返回一个新的向量.如果此向量的z坐标为正,则标量乘积在逆时针方向上给出直角.否则(z坐标为负),我计算得到矢量之间的角度为360°角度与标量积.
结果,我得到一个具有最大角度的边(和一个对应的下一个顶点).
我添加到每个传递顶点的结果列表.结果列表是联合多边形.
备注
- 该算法允许我们合并多个多边形 - 以迭代方式应用多边形对.
- 如果您的路径由许多贝塞尔曲线和线组成,则应首先展平此路径.
- 我认为应该提到的是,为了比较标量积,应该在计算它们的标量积之前对矢量进行归一化(即,将矢量坐标除以它的长度).无论如何,谢谢你的回答. (2认同)
- ...要执行“（a）计算孔”，请查找“步骤4。构造公共轮廓”从未访问过的点。使用这些点之一来“开始”孔。执行类似的“轮廓”算法，排除主要输出多边形已经使用的任何点。所得的多边形为“孔”。重复直到所有点都包含在某个多边形或孔中。 (2认同)
这是一个具有挑战性但很容易理解的主题,通常名为"多边形上的正则化布尔运算".您可以查看 这个MathOverflow答案,其中包括下图(来自Alan Murta的剪辑库),粉红色联合OP的组合:
- 这个人真的写了这本书;) (2认同)