[Solved]: detect closed shapes formed by points

Problem Detail: 

I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the curves lie close to each other).

Now I need to find the (possibly approximate) centers of the closed shapes. Alternatively, it's good to "recognize" the closed shapes and to fill them. I don't know what is easier given the coordinates of points forming the shapes.

A possible example with 3 closed shapes to detect is given below.

Points can be also added along the image's borders, thus, closing all open shapes. Then all "regions" in the figure will be closed, but the question persists.

Asked By : Omicron_Persei_11

Answered By : Gangnus

• 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.

Edit: 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20039