# detect closed shapes formed by points

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.

• Could you be more precise about what is a "shape"? If you close off the axes, your plot has eleven closed regions, not three. – David Richerby Jan 28 '14 at 16:03
• @DavidRicherby Under closed shape I mean an area encircled by a closed contour. But only "simple" closed shapes which consist of one closed contour should be considered. I've also added a postscriptum to the question. – Omicron_Persei_11 Jan 28 '14 at 17:24
• Shape detection it a whole subfield of computer graphics, afaik. What have you read and tried? – Raphael Jan 28 '14 at 17:53
• OK, not so much. I'm even not a computer science major. But the question seems to be interesting, if it has an answer. Currently I have not so many ideas. May be be map the figure to an array, marking the white spaces with zeros, and lines with 1s. But then we need to somehow interpolate the lines between the points. – Omicron_Persei_11 Jan 29 '14 at 11:13
• Look up "sweep-line algorithm". Basically you want to determine the cells of an arrangement of piecewise linear curves. This can be done best with a sweepline algorithm. – A.Schulz Jan 29 '14 at 12:45

## 2 Answers

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

• This seems to be a good approach. Actually I thought in that direction, but thanks for SOI and line/segment numbering. – Omicron_Persei_11 Feb 4 '14 at 14:34
• @Omicron_Persei_11 numbered are intersections, not segments. And very important is the orientation of intersections, without it you'll have tree recursion instead of cycles later. – Gangnus Feb 4 '14 at 14:47
• "the sign of the left movement on the intersecting curve" - what is it? I didn't quite understand... And "For the right attempt, make only left turns, for the left attempt, make only the right turns." Sorry for being such a noob. But may be it will be helpful for other people too. – Omicron_Persei_11 Feb 4 '14 at 15:47
• @Omicron_Persei_11 if one closed contour has adjacent segments a,b, and the other one has adjacent a,b, too, these contours are the same. How can they differ? – Gangnus Feb 4 '14 at 15:55
• @Omicron_Persei_11 Orientation explanation added – Gangnus Feb 5 '14 at 9:44

Here you go:

1) Do not draw the axis

2) Do not draw the plots with * but plot it with - .

3) Also plot $y=-0.02$, $x=-0.02$, $x=0.08$ plots. Plot the upper boundary as well.

4) Now take a screen capture. The bigger the plot, the more accurate the result will be.

5) Normalize the image to $0-1$. (Make it logical as in $logical(I)$)

6) Apply connected component labeling (supposedly in matlab using bwlabel etc.) - If you are not familiar with this part, I could elaborate.

Now you have closed shapes as connected binary regions. You can compute the region properties with : http://www.mathworks.com/help/images/ref/regionprops.html

Center and area are just 2 properties of these regions.

7) If you want to paint those regions on the image you could as well do so, since you have every point in the region.

If you don't have the image processing toolbox, then let me put it this way (exactly the same operation):

Sufficiently discretize your grid (adjust grid resolution so that the accuracy is sufficient for you). Each discrete point (a.k.a pixel) will be a node in your grid. Then for all grid locations other than the actual data points, form a connectivity graph (adjacency graph). This will connect the neighboring nodes (Use 4 or 8 connectivity) Then apply Tarjan's strongly connected components analysis to it: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm .

At this point, you will end up a component label per each node. This is the same as obtaining the connected components from the image. After that, you could retrieve each discretized point on the grid separately to compute the centroid, area or you can visualize these by label coloring.

Hope this helps. Cheers,

• Usage of Image Processing Toolbox is not desirable. It is an additional toolbox, and the speed is also important. It is desirable to solve the problem based on the given coordinates of points (possibly adding some auxiliary points, if it is needed for the solution) – Omicron_Persei_11 Jan 30 '14 at 14:16
• Check the updated answer. It is pretty much the same thing even if you don't use the image processing toolbox. What counts more is the idea. By the way, if you write "Points can be also added along the image's borders", I automatically assume that you are familiar with image representation and might have the image processing toolbox, as it is not explicitly stated. Moreover, how else will you "Fill" it, if you don't think about images? – Tolga Birdal Jan 30 '14 at 15:01
• @tbirdal There is also a considerable whitespace between several points, and it also may vary. In fact, you see parametric curves, i.e. the coordinates are functions of some implicit parameter. Therefore, the Tarjan alg may connect 2 regions together, because of too much whitespace at some regions' borders. About fill: MATLAB has function patch to fill polygons. ANd fill is only a suggestion, it is not strictly required. – Omicron_Persei_11 Jan 30 '14 at 15:31
• If you discretize your grid adequately, you will always have enough white space. Think about scaling the points in order to make the white space sufficient. This scaling can easily be computed automatically. – Tolga Birdal Jan 30 '14 at 15:41