如何在一堆多边形中找出相互嵌套的多边形？

Question

现在我有一堆多边形，知道每个多边形的坐标点。
然后我要找出哪几个多边形相互之间嵌套，也就是说组成了一个有孔洞的图形。有谁能提供一个好的算法么？谢谢了。。

Answer 1

matlab的话可以分别把每个多边形fill之后"与运算",结果不为0就是有交集

Answer 2

https://skydrive.live.com/embed?cid=0BC86E4BC0BB5698&resid=BC86E4BC0BB5698%21679&authkey=AMyQfZEIxkZ7dJQ
看这张图吧。这里边有三个多边形。
但是在数据结构中，这三个多边形是随机顺序储存在一个vector里的，也就是他们相互之间并没有建立拓扑关系，然后现在我要找出哪些多边形是相互嵌套的。
比如说这个最外边的black多边形便是内嵌了red多边形。red多边形内嵌了blue多边形。
多层嵌套是不允许的，比如说blue多边形虽然也在black多边形内部，但是他们之间隔着red多边形，所以在考虑black多边形的内嵌的时候，要将blue排除在外。在整个vector里找出所有类似black与red这样相互嵌套的多边形（有可能会有一个多边形内部嵌套多个小多边形的情况，就是一个图形里有多个洞）。这些多边形没有边界相互交叉的情况。
不知道我说明白没。现在我所采用的算法是是多层迭代，比如读取vector里边的第一个多边形A，然后迭代vector中的其他多边形B,C,D,E....，检查这些多边形有没有在A内部的，如果在A内部就和A绑定。当找出所有在A内部的多边形后，再迭代A中所有的多边形，检查有没有相互嵌套的情况出现，如果有，就把被嵌套的多边形删除。用这样的方法迭代整个vector来确定相互之间的嵌套关系。
但现在的问题是我这个算法效率好像很低。
这种东西应该有比较成熟的公开算法吧。所以想在这里讨教一下。多谢了！

Answer 3

我现在是要在VC实现这个。显然和MATLAB离的很远啊。

Answer 4

VC里关于拓扑图形的比较成熟的公开算法没听过，关注一下。
如果不排斥，VC+matlab结合的话倒是有可能解决，不过效率肯定不如纯VC的。

Answer 5

貌似一个多边形A的所有顶点都在另一个多边形B内，那么这个多边形A就应该在多边形B内部吧？那么问题就归结为判断A的各个定点是否在B内，我用的是搜狐的浏览器，我看这个网页的时侯，下面就提示：点在多边形内的快速算法。如果判断点是否在多边形内的算法够效率，那么整个算法的效率就应该上去了吧？

Answer 6

http://wenku.baidu.com/view/8253c47c5acfa1c7aa00cc24.html
看看这篇文章。

Answer 7

因为对于n个多边形，每个多边形都要与另外n-1个多边形检查是否嵌套----------------------------------------------------------
这个应该可以优化吧？如果A嵌入在B内，B又嵌入在C内，那么A与C就不用比较了，必然是A嵌入在C内。

Answer 8

每一个多边形的坐标，先做范围矩形，[min_X,max_X,min_Y,max_Y];
当两个多边形的这个矩形范围内嵌时，才检查是否内嵌；矩形是否内嵌的检查就容易了，直接比较X Y的大小就行；