Thread Subject:

Delaunay Triangulation of a concave hull

Hello,

please help me to solve the following problem:

I have a points cloud that corresponds to the concave hull. I need to make Delaunay Triangulation of that hull, but it seems to be working only for convex hulls. Give me please some idea of how to get DT for concave hulls. Moreover, I will need to check if a certain new point is inside the concave hull. I know how to do it for the convex hull, however I have no idea for the concave hull.

Thanks a lot!

"Liana" wrote in message <io0l19$9f0$1@fred.mathworks.com>...
> Hello,
>
> please help me to solve the following problem:
>
> I have a points cloud that corresponds to the concave hull. I need to make Delaunay Triangulation of that hull, but it seems to be working only for convex hulls. Give me please some idea of how to get DT for concave hulls. Moreover, I will need to check if a certain new point is inside the concave hull. I know how to do it for the convex hull, however I have no idea for the concave hull.
>
> Thanks a lot!

Oh, it still works. It just does not do what you wish for
it to do. These are obviously different things. Given a
random, scattered set of points from a domain, how
could MATLAB possibly know that the set represents a
concave domain or a convex one? For example,

xy = [0 0;0 1;1 0;1 1;.5 .5];
plot(xy(:,1),xy(:,2),'r*')

Is the true domain the convex unit square? Or should
MATLAB be intelligent enough to read your mind, and
know that you really wanted some concave portion of
that unit square? This is true for ANY scattered set of
points.

The mind reading toolbox is still in testing at TMW.

A delaunay tessellation ALWAYS produces a convex
result. This is the only unambiguous solution, as it
must be.

John

Thank you, John. I agree with you. I know that DT is ment for convex hulls. I just though there might be some tricks and indirect solutions.

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <io1cks$t11$1@fred.mathworks.com>...
> "Liana" wrote in message <io0l19$9f0$1@fred.mathworks.com>...
> > Hello,
> >
> > please help me to solve the following problem:
> >
> > I have a points cloud that corresponds to the concave hull. I need to make Delaunay Triangulation of that hull, but it seems to be working only for convex hulls. Give me please some idea of how to get DT for concave hulls. Moreover, I will need to check if a certain new point is inside the concave hull. I know how to do it for the convex hull, however I have no idea for the concave hull.
> >
> > Thanks a lot!
>
> Oh, it still works. It just does not do what you wish for
> it to do. These are obviously different things. Given a
> random, scattered set of points from a domain, how
> could MATLAB possibly know that the set represents a
> concave domain or a convex one? For example,
>
> xy = [0 0;0 1;1 0;1 1;.5 .5];
> plot(xy(:,1),xy(:,2),'r*')
>
> Is the true domain the convex unit square? Or should
> MATLAB be intelligent enough to read your mind, and
> know that you really wanted some concave portion of
> that unit square? This is true for ANY scattered set of
> points.
>
> The mind reading toolbox is still in testing at TMW.
>
> A delaunay tessellation ALWAYS produces a convex
> result. This is the only unambiguous solution, as it
> must be.
>
> John

Le 12/04/2011 13:22, John D'Errico a écrit :
> Oh, it still works. It just does not do what you wish for
> it to do. These are obviously different things. Given a
> random, scattered set of points from a domain, how
> could MATLAB possibly know that the set represents a
> concave domain or a convex one? For example,
>
> xy = [0 0;0 1;1 0;1 1;.5 .5];
> plot(xy(:,1),xy(:,2),'r*')
>
> Is the true domain the convex unit square? Or should
> MATLAB be intelligent enough to read your mind, and
> know that you really wanted some concave portion of
> that unit square? This is true for ANY scattered set of
> points.
>
> The mind reading toolbox is still in testing at TMW.
>
> A delaunay tessellation ALWAYS produces a convex
> result. This is the only unambiguous solution, as it
> must be.

Yes, but let S a set of points. Let its convex hull H.
We can look for a point M of S-H (in S, not in H) so that:
a polygon P build on S'=HU{M} (union) contains all S,
is concav, have a minimal area, and do not cross itself.
Then we can iterate on S'. We must bound the number
of iterations (how ?).
Do this satisfy the OP ?

Or an other idea: delete from the DT the triangle of
maximal area among the triangles of which an edge is
on the convex hull, and perhaps iterate.

--

Etienne

Thanks, Etienne.

I found out that in my particular case I can check if the planes that belong to the convex hull are producing 90 degrees angles with any of XYZ planes. If the angle between the plane and any of XYZ planes is 90 degrees, then the plane belongs to the concave hull. Otherwise, it belongs to the convex hull. But it works only for my case. Hope I've clearly described my idea.

Etienne Rousee <etienne@rousee.org> wrote in message <io23g8$1gps$1@talisker.lacave.net>...
> Le 12/04/2011 13:22, John D'Errico a écrit :
> > Oh, it still works. It just does not do what you wish for
> > it to do. These are obviously different things. Given a
> > random, scattered set of points from a domain, how
> > could MATLAB possibly know that the set represents a
> > concave domain or a convex one? For example,
> >
> > xy = [0 0;0 1;1 0;1 1;.5 .5];
> > plot(xy(:,1),xy(:,2),'r*')
> >
> > Is the true domain the convex unit square? Or should
> > MATLAB be intelligent enough to read your mind, and
> > know that you really wanted some concave portion of
> > that unit square? This is true for ANY scattered set of
> > points.
> >
> > The mind reading toolbox is still in testing at TMW.
> >
> > A delaunay tessellation ALWAYS produces a convex
> > result. This is the only unambiguous solution, as it
> > must be.
>
> Yes, but let S a set of points. Let its convex hull H.
> We can look for a point M of S-H (in S, not in H) so that:
> a polygon P build on S'=HU{M} (union) contains all S,
> is concav, have a minimal area, and do not cross itself.
> Then we can iterate on S'. We must bound the number
> of iterations (how ?).
> Do this satisfy the OP ?
>
> Or an other idea: delete from the DT the triangle of
> maximal area among the triangles of which an edge is
> on the convex hull, and perhaps iterate.
>
> --
>
> Etienne

"Liana" wrote in message <io22ak$3in$1@fred.mathworks.com>...
> Thank you, John. I agree with you. I know that DT is ment for convex hulls. I just though there might be some tricks and indirect solutions.
>

You can try an alpha shape.

An alpha shape is an erosion of a delaunay tessellation.
Imagine a ball of radius alpha used as a probe. The ball
"rolls' around the perimeter of the point set. If the alpha
ball can touch an interior point of the tessellation, without
passing over any points, then delete those simplexes which
the ball crossed to do so.

There is an alpha shape tool on the FEX that works in 2-d.
I also have an alpha shape tool that I have not posted on
the FEX, but it works in any number of dimensions.

John

John, I've been searching for 3D alpha shape function, however I haven't found any. If you can share your function, then it would be brilliant. Thanks.

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <io2g9b$41p$1@fred.mathworks.com>...
> "Liana" wrote in message <io22ak$3in$1@fred.mathworks.com>...
> > Thank you, John. I agree with you. I know that DT is ment for convex hulls. I just though there might be some tricks and indirect solutions.
> >
>
> You can try an alpha shape.
>
> An alpha shape is an erosion of a delaunay tessellation.
> Imagine a ball of radius alpha used as a probe. The ball
> "rolls' around the perimeter of the point set. If the alpha
> ball can touch an interior point of the tessellation, without
> passing over any points, then delete those simplexes which
> the ball crossed to do so.
>
> There is an alpha shape tool on the FEX that works in 2-d.
> I also have an alpha shape tool that I have not posted on
> the FEX, but it works in any number of dimensions.
>
> John