无孔多边形联合 [英] polygon union without holes

问题描述

我正在寻找一些相当简单的(我知道多边形联合不是一个简单的操作，但也许有人可以用一个相对简单的方法为我指出正确的方向)合并两个相交多边形的算法.多边形可以是没有孔的凹面，并且输出多边形中不应有孔.多边形以逆时针方式表示.我的意思是在图片上呈现.正如您所看到的，即使多边形联合中有一个洞，我在输出中也不需要它.输入多边形肯定没有孔.我认为没有漏洞应该更容易做，但我仍然不知道.

Im looking for some fairly easy (I know polygon union is NOT an easy operation but maybe someone could point me in the right direction with a relativly easy one) algorithm on merging two intersecting polygons. Polygons could be concave without holes and also output polygon should not have holes in it. Polygons are represented in counter-clockwise manner. What I mean is presented on a picture. As you can see even if there is a hole in union of polygons I dont need it in the output. Input polygons are for sure without holes. I think without holes it should be easier to do but still I dont have an idea.

推荐答案

1. 删除位于另一个多边形内的多边形的所有顶点:http://paulbourke.net/geometry/insidepoly/
2. 选择一个保证在联合多边形中的起点(极端情况之一可行)
3. 以逆时针方向跟踪多边形的边缘.这些是您工会中的要点.跟踪直到遇到交叉点(请注意，一条边可能与另一个多边形的不止一条边相交).
4. 找到第一个交叉点(如果有多个).这是您联盟中的一个要点.
5. 使用另一个多边形返回第 3 步.下一个点应该是与前一个边缘形成最大角度的点.

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