多边形内部多边形内的多边形

Question

我有许多简单的多边形,它们彼此不相交,但有些多边形可能嵌入到其他多边形中.

例如:

+--------------------------------------------+
|                                            |
|   +----------------+          +--------+   |
|   |                |         /         |   |
|   |   +--------+   |        /          |   |
|   |   |        |   |       /  +----(2)-+   |
|   |   |        |   |      /   |            |
|   |   +----(3)-+   |     /    |   +---+    |
|   |                |    +-----+   |   |    |
|   +------------(2)-+              +(2)+    |
|                                            |
+----------------------------------------(1)-+

如何找出所有多边形的"深度"？换句话说,如何找出多边形包含多少个多边形？"深度"是括号中的数字.

我可以计算多边形点在所有其他多边形内部的次数,但这具有二次复杂性.如何更快地计算这些深度？

Answer 1

将多边形放入某种空间查找结构中，例如基于多边形最小外接矩形的R 树。然后您应该能够在 O( n log n ) 中计算出您所追求的包含关系。（除非您处于病态情况，其中多边形的许多最小边界矩形重叠，根据您的描述，这似乎不太可能。）

编辑添加：当然，您不依赖 R 树来告诉您一个多边形是否在另一个多边形内部（它基于最小边界矩形，因此它只能给您一个近似值）。您可以使用 R 树来廉价地识别候选包含物，然后以昂贵的方式对其进行验证（检查一个多边形中的点是否在另一个多边形内部）。