The produced triangulation is wrong

[DaivaMarcinkeviciute]

When i make the triangulation for the following polygon (orange in the image), an invalid result is calculated (blue in the image):

import matplotlib.pyplot as plt
import geopandas as gpd
import shapely as shp

polygon = ((-0.2576266 , -3.63984984),
       ( 1.9325525 , -3.432218  ),
       ( 1.63998022, -0.3460551 ),
       ( 2.13774843, -0.29886602),
       ( 2.47750979, -3.88279714),
       ( 0.28733069, -4.09042898),
       ( 0.41002229, -5.38462632),
       ( 1.50511132, -5.28081045),
       ( 1.91093738, -9.56161706),
       ( 1.41316917, -9.60880614),
       ( 1.05453219, -5.82576774),
       (-0.04055685, -5.92958361),
       (-0.2576266 , -3.63984984)
    )

triangles = triangulate(polygon)

fig, ax = plt.subplots (figsize = (200,200))
gpd.GeoSeries(shp.geometry.Polygon(polygon)).plot(ax = ax, alpha = 0.3, color = 'orange')
for t in triangles:
    gpd.GeoSeries(shp.geometry.Polygon(t)).boundary.plot(ax = ax, color = 'blue', linewidth=2)
plt.show()
plt.clf()

print(triangles)

console:

[((1.9325525, -3.432218), (1.63998022, -0.3460551), (2.13774843, -0.29886602)), ((1.9325525, -3.432218), (2.13774843, -0.29886602), (2.47750979, -3.88279714)), ((-0.2576266, -3.63984984), (1.9325525, -3.432218), (2.47750979, -3.88279714)), ((-0.2576266, -3.63984984), (2.47750979, -3.88279714), (0.28733069, -4.09042898)), ((-0.2576266, -3.63984984), (0.28733069, -4.09042898), (0.41002229, -5.38462632)), ((1.50511132, -5.28081045), (1.91093738, -9.56161706), (1.41316917, -9.60880614)), ((0.41002229, -5.38462632), (1.50511132, -5.28081045), (1.41316917, -9.60880614)), ((-0.2576266, -3.63984984), (0.41002229, -5.38462632), (1.41316917, -9.60880614)), ((1.05453219, -5.82576774), (-0.04055685, -5.92958361), (-0.2576266, -3.63984984))]

image:

[joelibaceta]

Hi, thank you for providing such a detailed report along with the example and visualization!

I see the issue you’re describing with the incorrect triangulation result. I’m currently working on improving the triangulation logic, particularly with respect to handling winding order and floating point precision, based on feedback from another issue. It’s possible that the problem you’re seeing here is related, so I will make sure to consider this case as well while addressing the improvements.

I’ll keep you posted on the progress, and feel free to share any further insights or issues you come across in the meantime. Your input is incredibly helpful in making this tool more robust!

Thanks again for your contribution.