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?
Given k convex polygons. Let us assume we have the boundary of all polygons given in the form of n line segments. Each line segment has a reference to the polygon it belongs to and its interior side. Let us sort the vertices of the line segments by their x-coordinate. Now we start a line sweep from left to right.
During the sweep at most O(k) times a polygon starts and ends, as all polygons are convex. At such a start event we look through the sweep line status and determine how many other polygons surround us. Which takes O(n) time.
For n segments the line sweep gives you all intersections in O(n log n + k^2) time adding the handling of the start events we obtain O(n log n + k^2 + kn) time. Using the references of the line segments it should be possible to assign to every area (line segment) the number of currently covering polygons.