# vtkDelaunay2D failed to triangulate some special concav polygons

**URL:** <https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811>\
**Category:** Development\
**Tags:** code\
**Created:** [November 14, 2022, 3:18am UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811 "2022-11-14T03:18:14Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Robinhwd](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/r/eb9ed0/32.png) [@Robinhwd](https://discourse.vtk.org/u/Robinhwd)\
**Post date:** [November 14, 2022, 3:18am UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/1 "2022-11-14T03:18:14Z")

</div>

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.

 ![One of the polygon](https://discourse.vtk.org/uploads/default/original/2X/f/fc20e3940da9075d06625daf476968765efb4615.png)  
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!

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [November 14, 2022, 12:09pm UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/2 "2022-11-14T12:09:45Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Robinhwd](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/r/eb9ed0/32.png) [@Robinhwd](https://discourse.vtk.org/u/Robinhwd)\
**Post date:** [November 14, 2022, 2:17pm UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/3 "2022-11-14T14:17:17Z")

</div>

I updated the model file which contains only one polygon (School\_building\_simple.obj) and a sample code (VTKTriangle.cpp) here:  
[https://gitlab.kitware.com/vtk/vtk/-/issues/18715](https://gitlab.kitware.com/vtk/vtk/-/issues/18715)

Thank you!

---

<div class="post-metadata">

**Author:** ![amaclean](https://discourse.vtk.org/user_avatar/discourse.vtk.org/amaclean/32/224_2.png) [@amaclean](https://discourse.vtk.org/u/amaclean)\
**Post date:** [November 14, 2022, 8:27pm UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/4 "2022-11-14T20:27:29Z")

</div>

Have you tried using different values for Alpha and Tolerance?

---

<div class="post-metadata">

**Author:** ![Robinhwd](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/r/eb9ed0/32.png) [@Robinhwd](https://discourse.vtk.org/u/Robinhwd)\
**Post date:** [November 15, 2022, 2:33am UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/5 "2022-11-15T02:33:49Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![amaclean](https://discourse.vtk.org/user_avatar/discourse.vtk.org/amaclean/32/224_2.png) [@amaclean](https://discourse.vtk.org/u/amaclean)\
**Post date:** [November 15, 2022, 4:36am UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/6 "2022-11-15T04:36:45Z")

</div>

That’s good to know.

---

<div class="post-metadata">

**Author:** ![amaclean](https://discourse.vtk.org/user_avatar/discourse.vtk.org/amaclean/32/224_2.png) [@amaclean](https://discourse.vtk.org/u/amaclean)\
**Post date:** [November 15, 2022, 6:09am UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/7 "2022-11-15T06:09:43Z")

</div>

Is this what you are expecting to see?

 ![School_building_2face](https://discourse.vtk.org/uploads/default/original/2X/d/d344e9580890eb26878cdeeb732b6f2a79836b27.png)  
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.

---

<div class="post-metadata">

**Author:** ![Robinhwd](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/r/eb9ed0/32.png) [@Robinhwd](https://discourse.vtk.org/u/Robinhwd)\
**Post date:** [November 15, 2022, 2:02pm UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/9 "2022-11-15T14:02:26Z")

</div>

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:  
[https://gitlab.kitware.com/vtk/vtk/-/issues/18715](https://gitlab.kitware.com/vtk/vtk/-/issues/18715)

---

<div class="post-metadata">

**Author:** ![amaclean](https://discourse.vtk.org/user_avatar/discourse.vtk.org/amaclean/32/224_2.png) [@amaclean](https://discourse.vtk.org/u/amaclean)\
**Post date:** [November 15, 2022, 9:04pm UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/10 "2022-11-15T21:04:10Z")

</div>

Delaunay triangulations work best on planar convex sets of points; for some examples start here: [vtkDelaunay2D](https://vtk.org/doc/nightly/html/classvtkDelaunay2D.html).

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](https://kitware.github.io/vtk-examples/site/Cxx/GeometricObjects/Cube/)

---

<div class="post-metadata">

**Author:** ![Robinhwd](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/r/eb9ed0/32.png) [@Robinhwd](https://discourse.vtk.org/u/Robinhwd)\
**Post date:** [November 21, 2022, 1:39pm UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/11 "2022-11-21T13:39:57Z")

</div>

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:  
[https://gitlab.kitware.com/vtk/vtk/-/issues/18715](https://gitlab.kitware.com/vtk/vtk/-/issues/18715)

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

---

<div class="post-metadata">

**Author:** ![will.schroeder](https://discourse.vtk.org/user_avatar/discourse.vtk.org/will.schroeder/32/233_2.png) [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)\
**Post date:** [November 21, 2022, 1:57pm UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/12 "2022-11-21T13:57:39Z")

</div>

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:

 ![image.png](https://discourse.vtk.org/uploads/default/original/2X/a/a2201dae2d7618e6f4052b4b69c92515b0cd05d5.png)

---

<div class="post-metadata">

**Author:** ![Robinhwd](https://discourse.vtk.org/letter_avatar_proxy/v4/letter/r/eb9ed0/32.png) [@Robinhwd](https://discourse.vtk.org/u/Robinhwd)\
**Post date:** [November 22, 2022, 1:44am UTC](https://discourse.vtk.org/t/vtkdelaunay2d-failed-to-triangulate-some-special-concav-polygons/9811/13 "2022-11-22T01:44:04Z")

</div>

Sorry for the confusion.  
I’ve updated the source data (VTKTriangle.cpp) and result here:  
[https://gitlab.kitware.com/vtk/vtk/-/issues/18715](https://gitlab.kitware.com/vtk/vtk/-/issues/18715)

By using the sample code, I reproduced this issue:

 ![Sample_code](https://discourse.vtk.org/uploads/default/original/2X/6/62ab5afc9c196b358366d46d86ef03d78cd41a14.png)