Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Delaunay Triangulation of a concave hull

Subject: Delaunay Triangulation of a concave hull

From: Liana

Date: 12 Apr, 2011 04:39:05

Message: 1 of 7

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!

Subject: Delaunay Triangulation of a concave hull

From: John D'Errico

Date: 12 Apr, 2011 11:22:04

Message: 2 of 7

"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

Subject: Delaunay Triangulation of a concave hull

From: Liana

Date: 12 Apr, 2011 17:32:04

Message: 3 of 7

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

Subject: Delaunay Triangulation of a concave hull

From: Etienne Rousee

Date: 12 Apr, 2011 17:53:19

Message: 4 of 7

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

Subject: Delaunay Triangulation of a concave hull

From: Liana

Date: 12 Apr, 2011 20:39:05

Message: 5 of 7

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

Subject: Delaunay Triangulation of a concave hull

From: John D'Errico

Date: 12 Apr, 2011 21:30:19

Message: 6 of 7

"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

Subject: Delaunay Triangulation of a concave hull

From: Liana

Date: 14 Apr, 2011 18:27:05

Message: 7 of 7

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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us