多边形内多边形 多边形内多边形 [英] Polygon inside polygon inside polygon
问题描述
我有许多不相交的简单多边形,但有些多边形可能嵌入到其他多边形中.
I have number of simple polygons which do not intersect each other but some polygons may be embedded into others.
例如:
+--------------------------------------------+
| |
| +----------------+ +--------+ |
| | | / | |
| | +--------+ | / | |
| | | | | / +----(2)-+ |
| | | | | / | |
| | +----(3)-+ | / | +---+ |
| | | +-----+ | | |
| +------------(2)-+ +(2)+ |
| |
+----------------------------------------(1)-+
如何找出所有多边形的深度"?换句话说,如何找出一个多边形包含多少个多边形?深度"是括号中的数字.
How to find out the "depth" of all the polygons? In other words, how to find out by how many polygons a polygon is encompassed by? The "depth" are the numbers in parentheses.
我可以计算一个多边形的一个点在所有其他多边形内的次数,但这具有二次复杂性.如何更快地计算这些深度?
I could count how many times a point of a polygon is inside of all the other polygons but this has quadratic complexity. How to compute those depths faster?
推荐答案
将多边形放入某种spatial查找结构,例如基于最小边界矩形的R-tree对于多边形.然后你应该能够在 O(n log n) 中计算你所追求的包含关系.(除非您处于病理情况,其中多边形的许多最小边界矩形重叠,根据您的描述,这似乎不太可能.)
Put your polygons into some kind of spatial lookup structure, for example an R-tree based on the minimum bounding rectangles for the polygons. Then you should be able to compute the containment relation that you're after in O(n log n). (Unless you're in a pathological case where many of the minimum bounding rectangles for your polygons overlap, which seems unlikely based on your description.)
编辑添加:当然,您不依赖于 R 树来告诉您一个多边形是否在另一个多边形内(它基于最小边界矩形,因此它只能给您一个近似值).您可以使用 R 树廉价地识别候选夹杂物,然后以昂贵的方式进行验证(检查一个多边形中的一个点是否在另一个多边形内).
Edited to add: of course, you don't rely on the R-tree to tell you if one polygon is inside another (it's based on minimum bounding rectangles so it can only give you an approximation). You use the R-tree to cheaply identify candidate inclusions which you then verify in the expensive way (checking that a point in one polygon is inside the other).
这篇关于多边形内多边形 多边形内多边形的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!