Thread Subject: Organise or sort 2d coordinates?

Hi all,

Has anyone produced a function that can help me sort a set of 2d points in a 'somewhat geometrically ordered' way?

The above is in quotation marks because I understand that if my points don't provide a convex hull, the problem of ordering them (without further info) is itself ill-defined.
Nevertheless, if you were to take the boundary points of some shape and then randomize those points, I think you could approximate the ordering that would return your closed contour using perhaps a combination of polar coordinates and nearest-neighbour computations.

My thoughts would be to centre the points near zero, then sort via their polar coordinates. From these sorted points, find a 'stable' location where the tangent to the points is least noisy. Start from this location, and try and use nearest-neighbour calculations to skip from one point to the next until you come back around to your starting point.

So my question is: has anyone tackled this problem and come up with something workable yet? My searches through the file exchange are at the moment coming up empty.

If there's truly nothing there, I'll take a shot at it for the kinds of shapes I'm trying to get a contour around, and maybe it can be generalised enough to stick up on the file exchange when it's done.

Cheers,
Sven.

On Nov 10, 11:20 pm, "Sven" <sven.holco...@gmail.deleteme.com> wrote:
> Hi all,
>
> Has anyone produced a function that can help me sort a set of 2d points in a 'somewhat geometrically ordered' way?
>
> The above is in quotation marks because I understand that if my points don't provide a convex hull, the problem of ordering them (without further info) is itself ill-defined.
> Nevertheless, if you were to take the boundary points of some shape and then randomize those points, I think you could approximate the ordering that would return your closed contour using perhaps a combination of polar coordinates and nearest-neighbour computations.
>
> My thoughts would be to centre the points near zero, then sort via their polar coordinates. From these sorted points, find a 'stable' location where the tangent to the points is least noisy. Start from this location, and try and use nearest-neighbour calculations to skip from one point to the next until you come back around to your starting point.
>
> So my question is: has anyone tackled this problem and come up with something workable yet? My searches through the file exchange are at the moment coming up empty.
>
> If there's truly nothing there, I'll take a shot at it for the kinds of shapes I'm trying to get a contour around, and maybe it can be generalised enough to stick up on the file exchange when it's done.
>
> Cheers,
> Sven.

--------------------------------------------------------------------------
It might depend on how scattered they are. If it looks like a shotgun
pattern, then it might be tough to pick any kind of order. If it's
basically some kind of somwhat noisy path around a well defined
perimeter of some shape, you might have a good algorithm. That's why
it would be nice to see an example.

John D'Errico posted a nice fitting routine here:
http://www.mathworks.com/matlabcentral/fileexchange/24443-slm-shape-language-modeling
Not sure if it works on closed contours though.

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <447cd29d-3596-4d86-9820-f03d5a413231@v37g2000vbb.googlegroups.com>...
> On Nov 10, 11:20?pm, "Sven" <sven.holco...@gmail.deleteme.com> wrote:
> > Hi all,
> >
> > Has anyone produced a function that can help me sort a set of 2d points in a 'somewhat geometrically ordered' way?
> >
> > The above is in quotation marks because I understand that if my points don't provide a convex hull, the problem of ordering them (without further info) is itself ill-defined.
> > Nevertheless, if you were to take the boundary points of some shape and then randomize those points, I think you could approximate the ordering that would return your closed contour using perhaps a combination of polar coordinates and nearest-neighbour computations.
> >
> > My thoughts would be to centre the points near zero, then sort via their polar coordinates. From these sorted points, find a 'stable' location where the tangent to the points is least noisy. Start from this location, and try and use nearest-neighbour calculations to skip from one point to the next until you come back around to your starting point.
> >
> > So my question is: has anyone tackled this problem and come up with something workable yet? My searches through the file exchange are at the moment coming up empty.
> >
> > If there's truly nothing there, I'll take a shot at it for the kinds of shapes I'm trying to get a contour around, and maybe it can be generalised enough to stick up on the file exchange when it's done.
> >
> > Cheers,
> > Sven.
>
> --------------------------------------------------------------------------
> It might depend on how scattered they are. If it looks like a shotgun
> pattern, then it might be tough to pick any kind of order. If it's
> basically some kind of somwhat noisy path around a well defined
> perimeter of some shape, you might have a good algorithm. That's why
> it would be nice to see an example.
>
> John D'Errico posted a nice fitting routine here:
> http://www.mathworks.com/matlabcentral/fileexchange/24443-slm-shape-language-modeling
> Not sure if it works on closed contours though.

Could use Djikstra's algorithm. Start at some point, maybe the center point. Then order the points in order of shortest distance to that central point.