geometry - Multiple convex polygon intersection

Question

I have multiple convex polygons that intersect. I want to find the areas, where many of them intersect. In an image, one could think of it as a "peak". I am searching for the local peaks.

I have the software to intersect two polygons. Now I am thinking about how to compute the peaks, without computing all possible intersections (exponential time!).

Does somebody have a hint?

Answer 1

给定 k 个凸多边形。让我们假设我们有以 n 条线段的形式给出的所有多边形的边界。每条线段都有一个对其所属多边形及其内侧的参考。让我们按照 x 坐标对线段的顶点进行排序。现在我们开始从左到右的线扫描。

在扫描过程中，多边形开始和结束最多为 O(k) 次，因为所有多边形都是凸的。在这样的开始事件中，我们查看扫描线状态并确定我们周围有多少其他多边形。这需要 O(n) 时间。

对于 n 段，线扫描为您提供 O(n log n + k^2) 时间内的所有交点，加上我们获得 O(n log n + k^2 + kn) 时间的开始事件的处理。使用线段的参考应该可以为每个区域（线段）分配当前覆盖多边形的数量。