2011-01-10 256 views
0

如何从包含共线边的多边形中提取简单多边形? 对于以下非常简单的情况,边缘2-3和6-0是共线的。我想分开这个0,1,2和3,4,5,6。从具有共线边的多边形中提取多边形

我可以比较每条边的共线性对其他边,但这是一个缓慢的O(n^2)方法。有更快的方法吗?

alt text

回答

2

查找外接圆。计算边界圆与每条边所在的直线之间的上/右交点。这是O(n)。现在按照它的角度元组和它与边界圆相交的角度位置对每个边进行排序。这是O(nlogn),并将共线排列在您的排序列表中。

如果你不可能有很多平行但非共线的边缘,那么你可以跳过边界圆的东西,只是按角度排序。如果有很多平行的非共线角度,那么只是使用角度仍然“有效”,它只是不会为您提高效率。

+0

您可以通过将每一行转换为斜坡相交形式来做同样的事情。请注意,无论采用哪种方式,您都可以使用散列集而不是排序。 – 2011-01-10 08:05:24

0

你能找到1-2和6-0的交点吗?如果是这样,您可以生成边和顶点的图形。然后,找到所有不重叠的多边形很简单。