Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!i20g2000prf.googlegroups.com!not-for-mail
From: ImageAnalyst <imageanalyst@mailinator.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: sorting, 2D vector, puzzle piece shaped
Date: Fri, 14 Nov 2008 19:13:45 -0800 (PST)
Organization: http://groups.google.com
Lines: 64
Message-ID: <f6737b12-4c51-4e93-86a0-b54c1fc6887a@i20g2000prf.googlegroups.com>
References: <gfk6hl$snc$1@fred.mathworks.com> <cfb67021-f6d7-4853-b3bb-52e1211a087a@a3g2000prm.googlegroups.com> 
	<gfkd60$q5a$1@fred.mathworks.com>
NNTP-Posting-Host: 75.186.70.56
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1226718826 15418 127.0.0.1 (15 Nov 2008 03:13:46 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 15 Nov 2008 03:13:46 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: i20g2000prf.googlegroups.com; posting-host=75.186.70.56; 
	posting-account=0rLUzAkAAABojYSRC64DkTbtiSCX77HH
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET 
	CLR 1.1.4322; .NET CLR 2.0.50727; .NET CLR 3.0.04506.648; .NET CLR 
	3.5.21022),gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:500942

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