6

Does anyone know a relatively fast algorithm for decomposing a set of polygons into their distinct overlapping and non-overlapping regions, i.e. Given a set of n polygons, find all the distinct regions among them?

For instance, the input would be 4 polygons representing circles as shown below

and the output will be all polygons representing the distinct regions shown in the different colours.

I can write my own implementation using polygon operations but the algorithm will probably be slow and time consuming. I'm wondering if there's any optimised algorithm out there for this sort of problem.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Hamza Juzer
  • 65
  • 6
  • You will probably want some kind of sweep line algorithm, but it's non-standard and probably highly non-trivial to implement efficiently (polylog linear) – Niklas B. Feb 15 '14 at 16:09
  • Every algorithm is "relatively fast" - except, maybe, the slowest one, but this consists of an infinite loop anyhow. Seriously: *Robustly* computing the intersection of polygons is difficult enough (threoretically, it's easy, but given the limited precision of floating point operations, and the "border case hell" of points/lines being (nearly) coincident, I'd be wary of implementing this on my own). I assume that when you ask for a "relatively fast" algorithm, you want to rule out the obvious one of doing pairwise tests of all polygons and their intersections? How many polygons do you have? – Marco13 Feb 15 '14 at 16:40
  • @Marco13 Im developing a program which accepts 2-8 polygons, but yes, I would rather not test all possible combinations if thats possible. – Hamza Juzer Feb 15 '14 at 16:51
  • For so few polygons, any attempt to write a "non-brute-force" algorithm will not be worth the effort. But if you want to do so: In the worst case, *every* polygon intersects *every* other polygon (and every intersection of pairs of other polygons) anyhow (like in your example!). The only possible optimization that I can currently think of is some sort of http://en.wikipedia.org/wiki/Bounding_volume_hierarchy to quickly rule out polygons that certainly do *not* intersect. Might this be a feasible approach for your application case? – Marco13 Feb 15 '14 at 16:57
  • Thank you for asking a question for which I had already the answer :-) +1. – Gangnus Feb 15 '14 at 19:29
  • The objects shown above are ellipses, not circles. The intersection of two curved surfaces (either ellipses or circles) is not a polygon. – Tyler Durden Feb 15 '14 at 22:07

2 Answers2

1

I don't think it is SO difficult. I have answered the similar question on the friendly site and it was checked by a smaller community: https://cs.stackexchange.com/questions/20039/detect-closed-shapes-formed-by-points/20247#20247

  • Let's look for a more common question - let's take curves instead of polygons. And let's allow them to go out of the picture border, but we'll count only for simple polygons that wholly belong to the picture.
  • find all intersections by checking all pairs of segments, belonging to different curves. Of course, filter them before real check for intersection.
  • Number all curves 1..n. Set some order of segments in them.
  • For every point create a sequence of intersections SOI, so: if it starts from the border end, SOI[1] is null. If not, SOI[1]= (number of the first curve it is intersecting with, the sign of the left movement on the intersecting curve). Go on, writing down into SOI every intersection - number of curve if there is some, or 0 if it is the intersection with the border.
  • Obviously, you are looking only for simple bordered areas, that have no curves inside.
  • Pieces of curves between two adjacent non-null intersection points we'll call segments.
  • Having SOI for each curve:
    • for segment of the curve 1, starting from the first point of the segment, make 2 attempts to draw a polygon of segments. It is 2 because you can go to 2 sides along the first intersecting curve.
    • For the right attempt, make only left turns, for the left attempt, make only the right turns.
    • If you arrive at point with no segment in the correct direction, the attempt fails. If you return to the curve 1, it success. You have a closed area.
    • Remember all successful attempts
    • Repeat this for all segments of curve 1
    • Repeat this for all other curves, checking all found areas against the already found ones. Two same adjacent segments is enough to consider areas equal.

How to find the orientation of the intersection.

When segment p(p1,p2) crosses segment q(q1,q2), we can count the vector multiplication of vectors pXq. We are interested in only sign of its Z coordinate - that is out of our plane. If it is +, q crosses p from left to right. If it is -, the q crosses p from right to left.

The Z coordinate of the vector multiplication is counted here as a determinant of matrix: 

0         0          1
p2x-p1x   p2y-p1y    0
q2x-q1x   q2y-q1y    0

(of course, it could be written more simply, but it is a good memorization trick)

Of course, if you'll change all rights for lefts, nothing really changes in the algorithm as a whole.

Community
  • 1
  • 1
Gangnus
  • 24,044
  • 16
  • 90
  • 149
  • "Checkig all pairs of segments" is not very efficient though. Computig the intersection of polygons can be done in polylog linear time, so actually computing all pairwise intersections might be better – Niklas B. Feb 15 '14 at 19:51
  • @NiklasB. Of course, you could greatly improve the time of finding the intersections by using different filters. But that part is the less important one. I even don't know, maybe the questionner already has the intersection points. – Gangnus Feb 15 '14 at 19:55
  • @NiklasB. Our task is to give a useful thought, the concrete work is on the author of the question himself. – Gangnus Feb 15 '14 at 19:59
  • Does that algorithm handle cases where several polygons share a segment or a part of a segment? – Anton Feb 15 '14 at 21:05
  • @user3290797 yes. But if they can't have part of segment. The polygons generation is limited so, that if they share 2 adjacent segments, the polygons are equal. – Gangnus Feb 15 '14 at 21:10
1

Your problem in called the map overlay problem. It can be solved in O(n*log(n)+k*log(k)) time, where n is the number of segments and k is the number of segment intersections.

First you need to represent your polygons as a doubly connected edge list, different faces corresponding to the interiors of different polygons.

Then use the Bentley–Ottmann algorithm to find all segment intersections and rebuild the edge list. See: Computing the Overlay of Two Subdivisions or Subdivision representation and map overlay.

Finally, walk around each cycle in the edge list and collect faces of that cycle's half-edges. Every set of the faces will represent a distinct overlapping region.

See also: Shapefile Overlay Using a Doubly-Connected Edge List.

Anton
  • 3,113
  • 14
  • 12