Delaunay special constraints not being part of the triangulation

Hello, I'm trying to create a constrained delaunay triangulation of a set of points: in particular, I don't wont triangles to intersect a certain area. Matlab delaunayTriangulation allows me to set some constrains, the problem is that constraints must be part of the triangulation itself.

In my case, the black shape must not be part of the triangulation, I just don't want triangles to intersect its surface.

I could I do it?

Thanks, Alessandro.

Answer 1

[John D'Errico]

Trivial. At least if the triangles are not allowed to cross that internal boundary.

Simply create a polygon that describes the boundary, as a list of edges. Include those points in the set of points for your triangulation.

Set that list of edges from the polygon as constrained edges, and form a constrained triangulation.

No triangle will be able to CROSS one of those edges now, although there will be triangles INSIDE that constrained region. Now just delete any triangle from the tessellation that has all three vertices on the constraint polygon. What remains will have edges on the polygon, but none that can cross it.

You will not be able to insist that nothing even touch that region using constraints, while allowing edges to otherwise come arbitrarily close. The best you can do is to create a polygon as I suggested, but first move each vertex slightly outside. Thus, you must create a polygon that entirely contains your constraint domain yet lies some finite distance outside of the constraint region, then use the scheme I suggested above.

[Alessandro Masullo]

Thank you, I will try your solution!