Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: sorting, 2D vector, puzzle piece shaped
Date: Sat, 15 Nov 2008 03:33:01 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 40
Message-ID: <gflftd$1hf$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>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
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 1226719981 1583 172.30.248.37 (15 Nov 2008 03:33:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 15 Nov 2008 03:33:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:500945


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