search

lionfish0 / earclip

Polygon to triangle library
MIT License
5 stars 1 forks source link

wrong triangulation #1

Open GliderGeek opened 5 years ago

GliderGeek commented 5 years ago

I think there is a mistake in the algorithm. The following points produce invalid triangles:

import earclip

"""
                p3
                  xxxxxxxxxxxx   p2
                  x         x
                  x        x
                  x       x
        p5 xxxxxxxx p4   x
            x           x
             x         x
              x       x
               x     x
                x   x
                 x x
                  x
                p1
"""

pts = [[ 1.0, 0.0],
           [ 2,   2],
           [ 1,  2],
           [ 1,   1],
           [  0,   1]]

res = earclip.triangulate(pts)
print(res)

# resulting triangles:
# p1, p2, p3
# p5, p1, p3 -> spans outside area
# p3, p4, p5 -> not inside shape

It seems that the algorithm only checks if points lie inside the proposed ear (not on it) In this example: ear (p1, p2, p3) is not rejected, while p4 lies on top of one each edges

lionfish0 commented 5 years ago

Thanks for the spot! Will fix soon. Feel free to make a pull-request :)

GliderGeek commented 5 years ago

Unfortunately dont have the time to make a PR right now, but it should be quite trivial to implement. You can use my example as a test case.

On Mon, 28 Jan 2019 at 12:03, Mike Smith notifications@github.com wrote:

Thanks for the spot! Will fix soon. Feel free to make a pull-request :)

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/lionfish0/earclip/issues/1#issuecomment-458086617, or mute the thread https://github.com/notifications/unsubscribe-auth/APXOicFargCDhT0pkdjm3nF2dc2TMQGWks5vHtjlgaJpZM4ZPaZR .