MATLAB Answers

Find midpoints of alphashape's defining spheres

1 view (last 30 days)
Johannes Korsawe
Johannes Korsawe on 16 Oct 2015
Commented: Johannes Korsawe on 19 Oct 2015
Hi there,
if i compute a 3d-alphashape on a pointcloud...is it possible to find the midpoints of those spheres, which are defining for this shape.
I mean, for each triangle of the triangulation of this alphashape it is definitive, that a sphere of radius alpha will not go through this triangle. So there may be an corresponding "extreme" sphere for each triangle, which just touches the sides of the triangle, but does not go through it.
I need the midpoints of those spheres.

Answers (1)

John D'Errico
John D'Errico on 16 Oct 2015
Those spheres are implicit spheres. They are never explicitly generated in the alpha shape algorithm. Sorry, but you will need to do the work here.
  2 Comments
Johannes Korsawe
Johannes Korsawe on 19 Oct 2015
Let me see, if i got it right after thinking it over:
Assume [vertices,tri] is a triangulation of the alphashape in 3d. Then each triangle T is an outer facet of a tetrahedron TE of the former Delaunay-triangulation. For this tetrahedron TE it holds, that the circumscribed sphere (passing through all four vertices) has a radius which is smaller than ALPHA.
And now my assumption: When i think of a sphere S of radius ALPHA, coming from the outside, which just comes near T and tries to invade TE, the sphere S will come into contact with three vertices of T (and therefore of TE), but not with the fourth vertex (of TE). So i may assume, that the center of S is just ALPHA away from the three vertices of T. There are only two possible solutions (taking the non-degenerate cases only) and i will take that one, which lies in the "outside" direction.
Am I right here?
(Take this as an extra-question to make me accept the first answer :-) ).

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!