Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: sorting, 2D vector, puzzle piece shaped
Date: Fri, 14 Nov 2008 19:51:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 17
Message-ID: <gfkkr6$a33$1@fred.mathworks.com>
References: <gfk6hl$snc$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1226692262 10339 172.30.248.38 (14 Nov 2008 19:51:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 14 Nov 2008 19:51:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:500895


"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