vtkDelaunay2D generates redundant triangles

Hello !
I am using vtkDelaunay2D to generate a polygon with holes, Here’s what I want

I based on VTK examples https://examples.vtk.org/site/Cxx/Filtering/ConstrainedDelaunay2D/ to setting up the parameters, most of the triangle is what I want effect, but also can generate some redundant triangles, the following figure:

My question is:

  1. Why are there redundant triangles
  2. How can I adjust it to get a more accurate effect


It’s likely you defined one boundary for the central hole, right? So, you can extend the boundary polyline to achieve the desired output. Just add two additional boundaries connecting the points belonging to the red outlines shown below:

A possible implementation based on that example:


  // Create a cell array to store the boundary polygon in
  vtkNew<vtkCellArray> aCellArray;

  // Define the polygonal hole with a clockwise polygon for the central boundary
  vtkNew<vtkPolygon> aPolygon;

  // Define the polygonal hole with a clockwise polygon for the rightmost boundary
  vtkNew<vtkPolygon> aPolygon2;

  // Define the polygonal hole with a clockwise polygon for the leftmost boundary
  vtkNew<vtkPolygon> aPolygon3;

The rest of the example goes unchanged.

kind regards,


Thanks for your reply Paulo, I think you misunderstood me . You are right, I defined the inner and outer boundaries for a polygon with holes, but the red area you drew is not what I wanted, the first image is what I wanted

I know! Please, reread what I posted above carefully.

Yeah, you’re right. I can treat the extra triangles as holes. However, this is not universal, and depending on the width and height of the polygon, or other dimensions, it may not generate extra triangles. I’m actually going to generate a perforated polygon based on two or more sets of boundaries. However, the results generated by vtkDelaunay2D are sometimes unstable, which makes me very confused. Is there any other better method recommended?

That is not vtkDelauney2D fault. There is no way for the triangulation algorithm to guess what is hole and what is not based on so few control points. Perhaps you could increase the density of the points along the lines and in the inside areas to have very small triangles. Setting an upper size threshold for the triangles may give you the wanted result automatically. After that first step, optimize the mesh to get back to low poly count. But even this is not quite stable depending on the shapes you have.

You may also try working with the winding order of the boundaries: