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