Path: news.mathworks.com!not-for-mail
From: "Mahdieh" <mahdieh.emrani@capitalhealth.ca>
Newsgroups: comp.soft-sys.matlab
Subject: Re: sorting, 2D vector, puzzle piece shaped
Date: Mon, 17 Nov 2008 16:36:02 +0000 (UTC)
Organization: Glenrose Research Building
Lines: 47
Message-ID: <gfs6hi$m3u$1@fred.mathworks.com>
References: <gfk6hl$snc$1@fred.mathworks.com> <cfb67021-f6d7-4853-b3bb-52e1211a087a@a3g2000prm.googlegroups.com> <f6737b12-4c51-4e93-86a0-b54c1fc6887a@i20g2000prf.googlegroups.com> <gflftd$1hf$1@fred.mathworks.com>
Reply-To: "Mahdieh" <mahdieh.emrani@capitalhealth.ca>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1226939762 22654 172.30.248.37 (17 Nov 2008 16:36:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 17 Nov 2008 16:36:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1449772
Xref: news.mathworks.com comp.soft-sys.matlab:501236


"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