Polygon decomposition algorithm

Question

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

For example, the input will consist of 4 polygons representing circles, as shown below

and the output will be all polygons representing different areas displayed in different colors.

I can write my own implementation using polygon operations, but the algorithm is likely to be slow and time consuming. I am wondering if there is an optimized algorithm there for this kind of problem.

Answer 1

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

First you need to present your polygons as a doubly linked list of edges , different faces corresponding to the interiors of different polygons.

Then use the Bentley-Ottmann algorithm to find all the intersections of the segments and rebuild the list of edges. See: Computing an Overlay of Two Units or Introducing a Unit and a Map Overlay .

Finally, go around each cycle in the list of edges and collect graphs of this half-limit of the cycle. Each set of faces will represent a separate overlapping area.

See also: Formal overlay using a double-join list .

Answer 2

I do not think it is so difficult. I answered a similar question on a friendly site and it was checked by a small community: https://cs.stackexchange.com/questions/20039/detect-closed-shapes-formed-by-points/20247#20247

• Let's look at a more common question: let curves be taken instead of polygons. And let them get out of the picture frame, but we will only count for simple polygons that completely belong to the image.
• find all intersections by checking all pairs of segments belonging to different curves. Of course, filter them out before actually checking for an intersection.
• The number of all curves 1..n. Set them to some order of segments.
• For each point, create a sequence of SOI intersections, therefore: if it starts at the boundary end, SOI [1] is NULL. If not, SOI [1] = (the number of the first curve with which it intersects, the sign of the left movement on the intersecting curve). Continue to write in the SDI each intersection — the number of curves, if any, or 0 if it is an intersection with a border.
• Obviously, you are looking for only simple boundary areas within which there are no curves.
• Pieces of curves between two adjacent non-point intersection points will be called segments.
• Availability of SOI for each curve:
  • for curve segment 1, starting from the first point of the segment, make 2 attempts to draw a polygon of segments. This is 2 because you can go two sides along the first intersecting curve.
  • For a correct attempt, make only left turns; for a left attempt, make only correct turns.
  • If you reach a point without a segment in the right direction, the attempt will fail. If you return to curve 1, it will be successful. 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 already found ones. Two identical adjacent segments are enough to consider equal areas.

How to find the intersection orientation.

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

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

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

(of course, it could be written easier, but this is a good trick to remember)

Of course, if you change all the rights to the left, nothing will change in the algorithm as a whole.