vtkDelaunay2D failed to triangulate some special concav polygons

Hi vtkers,
I was trying to triangulate a mesh which includes two special concav polygons.
The triangulation was perfect by using VTK 5.10 (vtkDelaunay2D), however when I update VTK to 9.2, it failed.

Some triangles are missing as you can see from the picture above.

It seems that the new vtkDelaunay2D has different behaviour on triangulation.
Just wonder if there is any walkaround or some other algrithms which can replace vtkDelaunay2D?

(BTW, I also tried vtkTriangleFilter, since it doesn’t have the API (SetSourceInput) to specify constrained edges and loops, so it doesn’t work for some models too.)

Thank you in advance!

Can you send the data? and a simple python/c++ would be helpful.

I updated the model file which contains only one polygon (School_building_simple.obj) and a sample code (VTKTriangle.cpp) here:

Thank you!

Have you tried using different values for Alpha and Tolerance?

Yes, I tried different values for Alpha [-20, 20] and Tolerance [0.00001, 0.00000000001], didn’t work.

That’s good to know.

Is this what you are expecting to see?

An L-shaped object roughly in the Y-Z plane (lower right) and a planar object with a slot in the X-Z plane (upper left)?
If this is the case I would extract the two objects and individually apply the Delauny2d transform to each one as they lie in different planes Y-Z and X-Z respectively.

Yes, that’s what I expected.
I also tried to save these two polygons in seperated files and triangulated them individually, got the same results.

I updated the model file which contains only one polygon (School_building_simple.obj) and a sample code (VTKTriangle.cpp) here:

Delaunay triangulations work best on planar convex sets of points; for some examples start here: vtkDelaunay2D.

I really think that you need to go back and re-examine the original code and produce a simple example showing the issue.

Regarding the code above:

  1. You can use a for loop at line 45.
  2. In line 77 why are you setting source data to the same source as the input data? This is generally used to set a boundary of some sort. It is used to specify constrained edges and loops, perhaps this is what you are missing from the original code.

In looking at the object you need to add a set of points within the boundaries of the object for the triangulation to work.

If you know the goemetry and topology then you can manually build the objects as done here: Cube

Thank you! Andrew.
I took your suggestions remove SetSourceData(), the result seems even worse. we need the source data as the boundary to constain this triangulation.
I updated sample code and the results in the issue statement:

These is a warning when dealing with the edge between vertex 4 and 5:
“Warning: In vtkDelaunay2D.cxx, line 1419
vtkDelaunay2D (0000022A73EB5770): Edge not recovered, polygon fill suspect”
I think this maybe an issue of vtkDelaunay2D

I’m confused, when I write a simple python script with the points/polygons you provided I see bad polygons. Also, as Andrew mentioned, the polygons are in different planes so hopefully being tessellated separately, using a transform or best fitting plane.

Example of first polygon:

Sorry for the confusion.
I’ve updated the source data (VTKTriangle.cpp) and result here:

By using the sample code, I reproduced this issue: