许多（多于两个）多边形没有孔的联合 [英] Union of many (more than two) polygons without holes

问题描述

我创建没有孔的多边形的联合。输入多边形没有孔，也应该是输出。我已经有了用于找到两个多边形的工作算法。但是如果有两个以上的话就有问题了。作为一个联合不应该是不相交的多边形，当我尝试逐一计算它们的总和时，在这种情况下我有一个问题：

然后多边形1遇到多边形2的联合是不相交的（所以我的算法不计算和）。在第二个循环中，它与第3个和第4个多边形结合，但输出不是第2个多边形。
那么，有没有人知道这样做的快速和准确的算法？
可能一个好主意是首先用交叉点对多边形进行排序，但我不能想到任何快速算法，也不太清楚我不知道它们应该如何排序。

您可以应用2种算法中的任何一种从这个问题无孔多边形联合直接与n个多边形。

希望它有帮助

Im creating union of polygons without holes. Input polygons are without holes and also output one should be. I already have working algorithm for finding it for two polygons. But in case of more than two there is a problem. As an union shouldn't be disjoint polygon, when I try to compute sum of them one by one I have a problem in such case:

Then polygon 1 meets polygon 2 the union is disjoint (so my algorithm does not compute sum). In second loop ofc it makes union with 3rd and 4th polygon, but output is wihout 2nd polygon. So does any one know kind of fast and accurate algorithm of doing it? Probably a good idea would be to sort polygons by intersections first, but I cant think of any fast algorithms for that and also not quite Im not sure how they should be sorted.

解决方案

You shouldn't look at the polygons one by one.

You can apply any of the 2 algorithms from this question polygon union without holes directly with n polygons.

hope it helps

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