Thread Subject: sorting, 2D vector, puzzle piece shaped

I have a nx2 vector, which includes the XY coordinates of the n points.

When plotted, these points create a shape looking like a puzzle piece.
Now, I need to sort this vector, such that by connecting two consequent points in the vector, I would get the permieter of the shape. i.e. consequent points in the vector, correspond to adjacent point in the graph.

I have tried:
1- a. calculating the centroid, b. choosing one point in the vector c. sorting based on the angle between two lines, one passing through centroid and b.point, other line passing through centroid and any point on the vector ...

2- a. dividing the shape into 4 quadrants, b. sorting each quadrant based on X or Y c. connecting them together

none of the methods, accomplish sorting the whole shape ...

I am out of algorithms,
any help would be really appreciated ...

Thanks a lot
-Mah

On Nov 14, 10:47=A0am, "Mahdieh" <mahdieh.emr...@capitalhealth.ca>
wrote:
> I have a nx2 vector, which includes the XY coordinates of the n points.
>
> When plotted, these points create a shape looking like a puzzle piece.
> Now, I need to sort this vector, such that by connecting two consequent p=
oints in the vector, I would get the permieter of the shape. i.e. consequen=
t points in the vector, correspond to adjacent point in the graph.
>
> I have tried:
> 1- =A0a. calculating the centroid, b. choosing one point in the vector c.=
 sorting based on the angle between two lines, one passing through centroid=
 and b.point, other line passing through centroid and any point on the vect=
or ...
>
> 2- a. dividing the shape into 4 quadrants, b. sorting each quadrant based=
 on X or Y c. connecting them together
>
> none of the methods, accomplish sorting the whole shape ...
>
> I am out of algorithms,
> any help would be really appreciated ...
>
> Thanks a lot
> -Mah

----------------------------------------------------------
Mah:
Not sure why you're having such difficulty. Just add a pair of
elements at the end of the array that are the same as the first
coordinate of the array (so you'll get a closed curve), and use the
plot command. It's quite capable of plotting a closed curve such as a
jigsaw puzzle piece. Why do you need to do sorting????
Regards,
ImageAnalyst

Mahdieh wrote:
> I have a nx2 vector, which includes the XY coordinates of the n points.
>
> When plotted, these points create a shape looking like a puzzle piece.
> Now, I need to sort this vector, such that by connecting two consequent points in the
> vector, I would get the permieter of the shape. i.e. consequent points in the vector,
> correspond to adjacent point in the graph.

In theory, this should work:

xm = mean(XY,1); ym = mean(XY,2);
t = complex(xm, ym) + sort(complex(XY(:,1) - xm, XY(:,2) - ym)));
plot(real(t[1:end 1]), imag(t[1:end 1]))

This is just another way of expressing a centroid method like you mentioned.

--
.signature note: I am now avoiding replying to unclear or ambiguous postings.
Please review questions before posting them. Be specific. Use examples of what you mean,
of what you don't mean. Specify boundary conditions, and data classes and value
relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <cfb67021-f6d7-4853-b3bb-52e1211a087a@a3g2000prm.googlegroups.com>...
> On Nov 14, 10:47=A0am, "Mahdieh" <mahdieh.emr...@capitalhealth.ca>
> wrote:
> > I have a nx2 vector, which includes the XY coordinates of the n points.
> >
> > When plotted, these points create a shape looking like a puzzle piece.
> > Now, I need to sort this vector, such that by connecting two consequent p=
> oints in the vector, I would get the permieter of the shape. i.e. consequen=
> t points in the vector, correspond to adjacent point in the graph.
> >
> > I have tried:

(Snip)

> ----------------------------------------------------------
> Mah:
> Not sure why you're having such difficulty. Just add a pair of
> elements at the end of the array that are the same as the first
> coordinate of the array (so you'll get a closed curve), and use the
> plot command. It's quite capable of plotting a closed curve such as a
> jigsaw puzzle piece. Why do you need to do sorting????
> Regards,
> ImageAnalyst

Because, I predict the points are scattered. The OP does
not have a polygon, only a list of scattered points, in no
specific order.

The simplest solution is to use one of the traveling salesman
codes that Joseph Kirk has posted to the file exchange. In
fact, he has codes that assume the start and end points
must be the same, as required for a closed polygon. The
TSP code will produce a polygon as the OP desires.

HTH,
John

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <cfb67021-f6d7-4853-b3bb-52e1211a087a@a3g2000prm.googlegroups.com>...
> On Nov 14, 10:47=A0am, "Mahdieh" <mahdieh.emr...@capitalhealth.ca>
> wrote:
> > I have a nx2 vector, which includes the XY coordinates of the n points.
> >
> > When plotted, these points create a shape looking like a puzzle piece.
> > Now, I need to sort this vector, such that by connecting two consequent p=
> oints in the vector, I would get the permieter of the shape. i.e. consequen=
> t points in the vector, correspond to adjacent point in the graph.
> >
> > I have tried:
> > 1- =A0a. calculating the centroid, b. choosing one point in the vector c.=
> sorting based on the angle between two lines, one passing through centroid=
> and b.point, other line passing through centroid and any point on the vect=
> or ...
> >
> > 2- a. dividing the shape into 4 quadrants, b. sorting each quadrant based=
> on X or Y c. connecting them together
> >
> > none of the methods, accomplish sorting the whole shape ...
> >
> > I am out of algorithms,
> > any help would be really appreciated ...
> >
> > Thanks a lot
> > -Mah
>
> ----------------------------------------------------------
> Mah:
> Not sure why you're having such difficulty. Just add a pair of
> elements at the end of the array that are the same as the first
> coordinate of the array (so you'll get a closed curve), and use the
> plot command. It's quite capable of plotting a closed curve such as a
> jigsaw puzzle piece. Why do you need to do sorting????
> Regards,
> ImageAnalyst

well, I need them sorted for my further analysis. I know that I get a perfect plot by just using the plot function. but what I need , is that the vector is sorted, in such way that the 1st and 2nd elements correspond to 2 consequent points on the graph ... and so on for the rest of my vector ...

any help is really appreciated.
Thanks,

"Mahdieh" <mahdieh.emrani@capitalhealth.ca> wrote in message <gfk6hl$snc$1@fred.mathworks.com>...
> I have a nx2 vector, which includes the XY coordinates of the n points.
>
> When plotted, these points create a shape looking like a puzzle piece.
> Now, I need to sort this vector, such that by connecting two consequent points in the vector, I would get the permieter of the shape. i.e. consequent points in the vector, correspond to adjacent point in the graph.
>
> I have tried:
> 1- a. calculating the centroid, b. choosing one point in the vector c. sorting based on the angle between two lines, one passing through centroid and b.point, other line passing through centroid and any point on the vector ...
>
> 2- a. dividing the shape into 4 quadrants, b. sorting each quadrant based on X or Y c. connecting them together
>
> none of the methods, accomplish sorting the whole shape ...
>
> I am out of algorithms,
> any help would be really appreciated ...
>
> Thanks a lot
> -Mah


one important note, is that when plotted (used plot function) these points create a shape which looks like the "outline" of a puzzle piece, so it is sort of a curvature ....

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gfkd60$q5a$1@fred.mathworks.com>...
> ImageAnalyst <imageanalyst@mailinator.com> wrote in message <cfb67021-f6d7-4853-b3bb-52e1211a087a@a3g2000prm.googlegroups.com>...
> > On Nov 14, 10:47=A0am, "Mahdieh" <mahdieh.emr...@capitalhealth.ca>
> > wrote:
> > > I have a nx2 vector, which includes the XY coordinates of the n points.
> > >
> > > When plotted, these points create a shape looking like a puzzle piece.
> > > Now, I need to sort this vector, such that by connecting two consequent p=
> > oints in the vector, I would get the permieter of the shape. i.e. consequen=
> > t points in the vector, correspond to adjacent point in the graph.
> > >
> > > I have tried:
>
> (Snip)
>
> > ----------------------------------------------------------
> > Mah:
> > Not sure why you're having such difficulty. Just add a pair of
> > elements at the end of the array that are the same as the first
> > coordinate of the array (so you'll get a closed curve), and use the
> > plot command. It's quite capable of plotting a closed curve such as a
> > jigsaw puzzle piece. Why do you need to do sorting????
> > Regards,
> > ImageAnalyst
>
> Because, I predict the points are scattered. The OP does
> not have a polygon, only a list of scattered points, in no
> specific order.
>
> The simplest solution is to use one of the traveling salesman
> codes that Joseph Kirk has posted to the file exchange. In
> fact, he has codes that assume the start and end points
> must be the same, as required for a closed polygon. The
> TSP code will produce a polygon as the OP desires.
>
> HTH,
> John

Thanks John, you got it right and the solution seems to be the answer... I have donwloaded the TSP code and from the description it is promising to solve my problem.
Thanks again for the advice,
-Mah

"Mahdieh" <mahdieh.emrani@capitalhealth.ca> wrote in message <gfk6hl$snc$1@fred.mathworks.com>...
> I have a nx2 vector, which includes the XY coordinates of the n points.
> ........ (snip)
> -Mah

  As John has indicated, this could be considered a "traveling salesman problem" which is known to be NP-hard (that is, takes a truly enormous number of steps for large n.) For a discussion see, for example,

 http://en.wikipedia.org/wiki/Traveling_salesman_problem

  However, in your particular case you presumably have the advantage of knowing that your points probably lie on a reasonably smooth curve. (I assume the "puzzle piece" outline is reasonably smooth.) You might try an algorithm that takes advantage of that fact and proceeds along the following lines.

  Having once determined that your n_th point is to be A and the n+1_st point be B, choose as the n+2_nd point C one that combines in some manner the closeness of C to B and the smallness of the bend in angle ABC. That is, it tries to avoid choosing nearby points that are in a backwards direction. Perhaps that could be as simple as ensuring that C is closer to B than to A. In other words, you are restricting yourself to triplets of points that are not only close together but do not have excessively sharp bends in their connecting line segments.

  Hopefully you could work your way sequentially from some initial point through all the points in the array and back eventually to that same initial point. This sounds like an algorithm of order n^2 but necessarily combined with some kind of check for final overall validity. That might cause it to end up order n^3 if you have to keep restarting with different initial points. (Or it might not work at all!) There is no denying that you have posed a difficult task here.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gfkkr6$a33$1@fred.mathworks.com>...
> "Mahdieh" <mahdieh.emrani@capitalhealth.ca> wrote in message <gfk6hl$snc$1@fred.mathworks.com>...
> > I have a nx2 vector, which includes the XY coordinates of the n points.
> > ........ (snip)
> > -Mah
>
> As John has indicated, this could be considered a "traveling salesman problem" which is known to be NP-hard (that is, takes a truly enormous number of steps for large n.) For a discussion see, for example,
>
> http://en.wikipedia.org/wiki/Traveling_salesman_problem
>
> However, in your particular case you presumably have the advantage of knowing that your points probably lie on a reasonably smooth curve. (I assume the "puzzle piece" outline is reasonably smooth.) You might try an algorithm that takes advantage of that fact and proceeds along the following lines.
>
> Having once determined that your n_th point is to be A and the n+1_st point be B, choose as the n+2_nd point C one that combines in some manner the closeness of C to B and the smallness of the bend in angle ABC. That is, it tries to avoid choosing nearby points that are in a backwards direction. Perhaps that could be as simple as ensuring that C is closer to B than to A. In other words, you are restricting yourself to triplets of points that are not only close together but do not have excessively sharp bends in their connecting line segments.
>
> Hopefully you could work your way sequentially from some initial point through all the points in the array and back eventually to that same initial point. This sounds like an algorithm of order n^2 but necessarily combined with some kind of check for final overall validity. That might cause it to end up order n^3 if you have to keep restarting with different initial points. (Or it might not work at all!) There is no denying that you have posed a difficult task here.
>
> Roger Stafford

I have tried the TSP code, provided by Joseph Kirk and large data it takes very very long to sort them, as you stated ...
I have 1000 points on each curve and I need to analyze 18 curves at a time ...
So, I will try to combine the simple sorting solutions, such as the angle and centroid, with the TSP problem. i.e. first sort the points with the simple solution, then evaluate the points by some heuristic funny algorithms, and for the parts that the algorithm has failed, I will try to use the TSP code ....

Meanwhile, if someone come up with something, let me know ...
Thanks,
-Mahdieh
 
 

"Mahdieh" <mahdieh.emrani@capitalhealth.ca> wrote in message <gfknui$lf9$1@fred.mathworks.com>...

> I have tried the TSP code, provided by Joseph Kirk and large data it takes very very long to sort them, as you stated ...
> I have 1000 points on each curve and I need to analyze 18 curves at a time ...
> So, I will try to combine the simple sorting solutions, such as the angle and centroid, with the TSP problem. i.e. first sort the points with the simple solution, then evaluate the points by some heuristic funny algorithms, and for the parts that the algorithm has failed, I will try to use the TSP code ....
>
> Meanwhile, if someone come up with something, let me know ...

Oh. You did not tell us it was that large of a problem.
The TSP is truly nasty for large sets of points.

However, you might be willing to solve the TSP for say
every 5th point from your set, then add the rest of the
points back in.

John

On Nov 14, 12:40=A0pm, "John D'Errico" <woodch...@rochester.rr.com>
wrote:
> ImageAnalyst <imageanal...@mailinator.com> wrote in message <cfb67021-f6d=
7-4853-b3bb-52e1211a0...@a3g2000prm.googlegroups.com>...
> > On Nov 14, 10:47=3DA0am, "Mahdieh" <mahdieh.emr...@capitalhealth.ca>
> > wrote:
> > > I have a nx2 vector, which includes the XY coordinates of the n point=
s.
>
> > > When plotted, these points create a shape looking like a puzzle piece=
.
> > > Now, I need to sort this vector, such that by connecting two conseque=
nt p=3D
> > oints in the vector, I would get the permieter of the shape. i.e. conse=
quen=3D
> > t points in the vector, correspond to adjacent point in the graph.
>
> > > I have tried:
>
> (Snip)
>
> > ----------------------------------------------------------
> > Mah:
> > Not sure why you're having such difficulty. =A0Just add a pair of
> > elements at the end of the array that are the same as the first
> > coordinate of the array (so you'll get a closed curve), and use the
> > plot command. =A0It's quite capable of plotting a closed curve such as =
a
> > jigsaw puzzle piece. =A0Why do you need to do sorting????
> > Regards,
> > ImageAnalyst
>
> Because, I predict the points are scattered. The OP does
> not have a polygon, only a list of scattered points, in no
> specific order.
>
> The simplest solution is to use one of the traveling salesman
> codes that Joseph Kirk has posted to the file exchange. In
> fact, he has codes that assume the start and end points
> must be the same, as required for a closed polygon. The
> TSP code will produce a polygon as the OP desires.
>
> HTH,
> John

-----------------------------------------
John, I think you're right - I didn't think of it that way. Well for
a random cluster of points there are numerous ways that you could
possibly draw enclosing perimeters. If each point is not necessarily
required to be on the perimeter, the simplest way (if you have the
image processing toolkit) is to just pass them in to poly2mask or
roipoly, and then pass the result into the convex hull. Just two
lines. But the piece is all convex - no bays, nooks, and crannies.
If you want concave as well as convex portions on the perimeter, then
you might take a look at a little known (I think) method called "alpha
shapes." Google it or go here:
http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html
The alpha parameter is how much the perimeter "hugs" the points.
Makes an outline kind of like if you put the points into heat-shrink
wrap or vacuum-pack plastic film. The alpha is like how much heat or
vacuum you apply to the plastic wrap. I'm personally not familiar
with the method but the demo images look cool.
Regards,
ImageAnalyst

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <f6737b12-4c51-4e93-86a0-b54c1fc6887a@i20g2000prf.googlegroups.com>...
> -----------------------------------------
> John, I think you're right - I didn't think of it that way. Well for
> a random cluster of points there are numerous ways that you could
> possibly draw enclosing perimeters. If each point is not necessarily
> required to be on the perimeter, the simplest way (if you have the
> image processing toolkit) is to just pass them in to poly2mask or
> roipoly, and then pass the result into the convex hull. Just two
> lines. But the piece is all convex - no bays, nooks, and crannies.
> If you want concave as well as convex portions on the perimeter, then
> you might take a look at a little known (I think) method called "alpha
> shapes." Google it or go here:
> http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html
> The alpha parameter is how much the perimeter "hugs" the points.
> Makes an outline kind of like if you put the points into heat-shrink
> wrap or vacuum-pack plastic film. The alpha is like how much heat or
> vacuum you apply to the plastic wrap. I'm personally not familiar
> with the method but the demo images look cool.
> Regards,
> ImageAnalyst

You are correct that an alpha shape is an option here.
It can give a triangulation of the "puzzle piece", then
you would extract the boundary of that triangulation
to yield the circuit of the points.

Beware - there are subtly different versions of alpha
shape however. Some require the alpha ball to ride
around only on the perimeter of the object, others
allow it to also erode from within. The link posted
above is the latter kind of alpha shape, but you need
the former style of alpha shape.

Finally, a problem with an alpha shape here is it will
not always yield a circuit of the points, as a TSP will
do. I would often expect to see some subset of the
points that remain inside the interior of the alpha
shape.

John

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gflftd$1hf$1@fred.mathworks.com>...
> ImageAnalyst <imageanalyst@mailinator.com> wrote in message <f6737b12-4c51-4e93-86a0-b54c1fc6887a@i20g2000prf.googlegroups.com>...
> > -----------------------------------------
> > John, I think you're right - I didn't think of it that way. Well for
> > a random cluster of points there are numerous ways that you could
> > possibly draw enclosing perimeters. If each point is not necessarily
> > required to be on the perimeter, the simplest way (if you have the
> > image processing toolkit) is to just pass them in to poly2mask or
> > roipoly, and then pass the result into the convex hull. Just two
> > lines. But the piece is all convex - no bays, nooks, and crannies.
> > If you want concave as well as convex portions on the perimeter, then
> > you might take a look at a little known (I think) method called "alpha
> > shapes." Google it or go here:
> > http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html
> > The alpha parameter is how much the perimeter "hugs" the points.
> > Makes an outline kind of like if you put the points into heat-shrink
> > wrap or vacuum-pack plastic film. The alpha is like how much heat or
> > vacuum you apply to the plastic wrap. I'm personally not familiar
> > with the method but the demo images look cool.
> > Regards,
> > ImageAnalyst
>
> You are correct that an alpha shape is an option here.
> It can give a triangulation of the "puzzle piece", then
> you would extract the boundary of that triangulation
> to yield the circuit of the points.
>
> Beware - there are subtly different versions of alpha
> shape however. Some require the alpha ball to ride
> around only on the perimeter of the object, others
> allow it to also erode from within. The link posted
> above is the latter kind of alpha shape, but you need
> the former style of alpha shape.
>
> Finally, a problem with an alpha shape here is it will
> not always yield a circuit of the points, as a TSP will
> do. I would often expect to see some subset of the
> points that remain inside the interior of the alpha
> shape.
>
> John

It seems that I am getting fairly good results from my combination code, using TSP and the theta ...
However I have looked into the alpha shape a bit. So far I can not work with the Demo ... I will try my best to get that too and compare the results to each other ...

Thanks a lot to John and Image Analyst :)
-mah

I tried this and it seems like there should be a simpler way. The traveling salesman assumes you can go between any two cities, not just along the contour. This means calculation takes a long time and the result doesn't give a closed contour route. A possible solution is to drop a high weight function in the middle of the contour.

"Bogdan Dzyubak" <illan7@gmail.com> wrote in message <jfs1si$1tj$1@newscl01ah.mathworks.com>...
>
>A possible solution is to drop a high weight function in the middle of the contour.

Only if the points are approximately the boundary of a convex shape.