Find midpoints of alphashape's defining spheres

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.

Answer 1

[John D'Errico]

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.

[Johannes Korsawe]

Humm. I hate to do the work by myself.

Do i have to start from the triangulation points of the alphashape? I would like to maintain any helpful information from during the calculation of the alphashape. Is there no possibility to mark onto the actual boundary triangles of the Delaunay triangulation about HOW there has been decided to keep 'em?

Hmm, it looks like i have to dive deeper into the actual alphashape algorithm. (I once got one from you, John, i will start with that.)

[Johannes Korsawe]

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 :-) ).