2
$\begingroup$

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.

enter image description here

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.

$\endgroup$
7
  • $\begingroup$ Could you be more precise about what is a "shape"? If you close off the axes, your plot has eleven closed regions, not three. $\endgroup$ Jan 28, 2014 at 16:03
  • $\begingroup$ @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. $\endgroup$ Jan 28, 2014 at 17:24
  • 1
    $\begingroup$ Shape detection it a whole subfield of computer graphics, afaik. What have you read and tried? $\endgroup$
    – Raphael
    Jan 28, 2014 at 17:53
  • $\begingroup$ 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. $\endgroup$ Jan 29, 2014 at 11:13
  • $\begingroup$ 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. $\endgroup$
    – A.Schulz
    Jan 29, 2014 at 12:45

2 Answers 2

1
$\begingroup$
  • 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.

$\endgroup$
5
  • $\begingroup$ This seems to be a good approach. Actually I thought in that direction, but thanks for SOI and line/segment numbering. $\endgroup$ Feb 4, 2014 at 14:34
  • $\begingroup$ @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. $\endgroup$
    – Gangnus
    Feb 4, 2014 at 14:47
  • $\begingroup$ "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. $\endgroup$ Feb 4, 2014 at 15:47
  • $\begingroup$ @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? $\endgroup$
    – Gangnus
    Feb 4, 2014 at 15:55
  • $\begingroup$ @Omicron_Persei_11 Orientation explanation added $\endgroup$
    – Gangnus
    Feb 5, 2014 at 9:44
-2
$\begingroup$

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,

$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$ Jan 30, 2014 at 14:16
  • $\begingroup$ 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? $\endgroup$ Jan 30, 2014 at 15:01
  • $\begingroup$ @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. $\endgroup$ Jan 30, 2014 at 15:31
  • $\begingroup$ 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. $\endgroup$ Jan 30, 2014 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.