0
$\begingroup$

I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue.

The algorithm starts by creating a bounding triangle that it then splits recursively as new points are inserted. Then the 3 extra points are deleted. This yields these kind of meshes before deleting the point:

enter image description here

There's 2 edges in there, which are 100% delaunay, flipping them would make the triangulation non delaunay.

But when I take these points out, I will delete the edges, creating a non convex triangulation.

I could just grab the convex hull of the result and try to add the missing edges but that's very inelegant. I am wondering if there is a better way. For what is worth I implemented the algorithm described here.

enter image description here

$\endgroup$
1
  • $\begingroup$ As I noted in this answer an earlier question from you, it is not enough to construct a triangle that only contains the point set, the triangle should be large enough to be outside any circle defined by the points in the input set. As such a triangle is unreasonably large, you can treat the vertices symbolically, as explained in the answer. Does this previous answer solve your problem? If not, can you specify why it doesn't? $\endgroup$
    – Discrete lizard
    Commented Sep 8, 2023 at 9:24

1 Answer 1

0
$\begingroup$

I went about this problem as follows:

Find the centroid of the point set as well as the largest distance from the centroid to any of the points.

This yields a circle, compute a triangle that fully contains the circle (and thus fully contains the point set).

When testing for the Delaunay criterion to decide if an edge needs to be flipped, check if the point opposite to the edge is one of the 3 new points, if it is, ignore the test and return that the point is not in the circumcircle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.