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

问题描述

林寻找一些很容易（我知道多边形的工会不是一件容易操作，但也许有人会用relativly容易一点我在正确的方向上）在合并两个相交的多边形算法。多边形可能是凹无孔，也输出面不应该有它的漏洞。多边形psented逆时针的方式重新$ P $。我的意思是psented上的图片$ P $。正如你可以看到即使是在多边形我不需要它在输出工会的孔。输入多边形是肯定的无孔。我觉得无孔应该是比较容易做，但我仍然不有一个想法。

解决方案

1. 删除它趴在其它多边形内部的多边形的所有顶点：<一href="http://paulbourke.net/geometry/insidepoly/">http://paulbourke.net/geometry/insidepoly/
2. 在挑选一个是保证在工会多边形的出发点（极端的人会工作）
3. 通过逆时针时尚多边形的边跟踪。这些都是在你的工会点数。跟踪，直到到达一个交叉点（注意，边沿可以与其它多边形的多个边相交的）。
4. 找到第一个路口（如果有多个）。这是你的联盟的一个点。
5. 回到与其他多边形步骤3。第二点应该是使与previous边最大角度的位置。

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. Remove all the vertices of the polygons which lie inside the other polygon: http://paulbourke.net/geometry/insidepoly/
2. Pick a starting point that is guaranteed to be in the union polygon (one of the extremes would work)
3. Trace through the polygon's edges in counter-clockwise fashion. These are points in your union. Trace until you hit an intersection (note that an edge may intersect with more than one edge of the other polygon).
4. Find the first intersection (if there are more than one). This is a point in your Union.
5. Go back to step 3 with the other polygon. The next point should be the point that makes the greatest angle with the previous edge.

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