Doesn't check polygon winding order, direct equality comparison of floats

[fluffy-marmot]

There are some major issues that currently make this nonfunctional: First it doesn't do anything to check winding order of the input polygon; this is necessary to establish which angle is internal. Winding order could be determined by checking the sign of signed area of the polygon.

Even reversing the list given as an example in the readme file gives an incorrect result:

from triangulator.ear_clipping_method import triangulate vertices = [(1, 1), (4, 2), (3, 2), (2, 7), (3, 4), (7, 3), (8, 3), (9, 0)] print(triangulate(vertices)) [((9, 0), (1, 1), (4, 2)), ((3, 2), (2, 7), (3, 4)), ((4, 2), (3, 2), (3, 4)), ((9, 0), (4, 2), (3, 4)), ((9, 0), (3, 4), (7, 3)), ((9, 0), (7, 3), (8, 3))]

vertices.reverse() vertices [(9, 0), (8, 3), (7, 3), (3, 4), (2, 7), (3, 2), (4, 2), (1, 1)] print(triangulate(vertices)) [((8, 3), (7, 3), (3, 4)), ((8, 3), (3, 4), (2, 7)), ((3, 2), (4, 2), (1, 1)), ((2, 7), (3, 2), (1, 1))]

Second, the is_point_inside_triangle is using equality comparison for area, which would likely fail due to floating point errors. A better method might be checking signs of barycentric coordinates: https://en.wikipedia.org/wiki/Barycentric_coordinate_system

def is_point_inside_triangle(triangle: tuple, point: tuple) -> bool:
    A, B, C = triangle
    P = point

    def sign(p1, p2, p3):
        return (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1])

    d1 = sign(P, A, B)
    d2 = sign(P, B, C)
    d3 = sign(P, C, A)

    has_neg = (d1 < 0) or (d2 < 0) or (d3 < 0)
    has_pos = (d1 > 0) or (d2 > 0) or (d3 > 0)

    return not (has_neg and has_pos)

[joelibaceta]

Hi, thank you for your detailed feedback!

I really appreciate the time you’ve taken to point out these issues. You’re absolutely right regarding the winding order of the input polygon. I will work on implementing a check for the winding order based on the signed area to ensure that internal angles are correctly determined, as you suggested.

As for the issue with the is_point_inside_triangle function, you’re spot on about the potential floating point precision errors when comparing areas. I’ll look into replacing the current method with the use of barycentric coordinates, which should improve the robustness of the point-in-triangle test.

If you have any other suggestions or find additional issues, feel free to share them—your input is really valuable!