多边形内多边形内多边形 [英] 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?

推荐答案

将你的多边形放入某种 空间查找结构，例如基于最小边界矩形的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-tree 来告诉您一个多边形是否在另一个多边形内(它基于最小边界矩形，因此它只能给您一个近似值).您可以使用 R-tree 廉价地识别 候选包含，然后以昂贵的方式进行验证(检查一个多边形中的一个点是否在另一个多边形内).

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屋！