Re: Concave hull 3D

Posted by ctrueden on Aug 09, 2007; 2:23pm
URL: http://imagej.273.s1.nabble.com/Concave-hull-3D-tp3698649p3698654.html

Hi Eddie,

Googling for "concave hull" there is quite a bit of information about
this idea. One informative writeup is here:
http://ubicomp.algoritmi.uminho.pt/local/concavehull.html

It appears that the algorithm essentially works based on density and
proximity. Unfortunately the link to the online version of their
algorithm seems nonfunctional, but you could try emailing them. It is
probably worth starting from some existing code, as this problem is
certainly nontrivial.

-Curtis

On 8/9/07, Eddie Iannuccelli <[hidden email]> wrote:

> I agree with you but I was wondering if the problem coud be solved by
> using some "biological" constraints on angles and distances between 2
> surface points. My objects are always more continous and curved than
> your cube example, concave regions are generally made by several points
> in a progressive curve so this kind of ambiguous case are not so much
> encountered. I know some plugins can get isosurface from an imagestack.
> Could that isosurface approach resolve my problem ?
>
> Regards
>
> Johannes Schindelin a écrit :
> > Hi,
> >
> > On Thu, 9 Aug 2007, Eddie Iannuccelli wrote:
> >
> >
> >> I am currently using QuickHull3D java lib to build a 3D shape from a surface
> >> Point3f list. My biological objects (cell nucleus) are not always convex and
> >> QuickHull3D always returns convex shapes so now  I am looking for a way to
> >> produce concave 3D shapes from surface points (no image available, only
> >> surface points list).
> >>
> >
> > This is not a well defined problem.  Imagine a cube.  Put points onto all
> > 8 of its corners.  Now put a 9th point into its center.
> >
> > The convex hull is well defined.  But what should a concave hull do?
> >
> > Should it produce the cube? (Volume 1 for dimensions 1x1x1)
> >
> > Or should it produce a cube with one "dent", i.e. replace one side by the
> > four triangles built by the four corners and the cube's center?  (Volume
> > 5/6 for dimensions 1x1x1)
> >
> > Or should it just produce the triangles built by any two adjacent corners
> > and the cube's center (Volume 0 for any dimension)?
> >
> > It is highly ambiguous.
> >
> > Ciao,
> > Dscho
> >
> >
>
> --
> ******************************************
> Eddie Iannuccelli
> Laboratoire de génétique cellulaire
> INRA - Castanet Tolosan
> Tel: [phone] / Fax: [phone]
>