mapbox / earcut

The fastest and smallest JavaScript polygon triangulation library for your WebGL apps
ISC License
2.21k stars 207 forks source link

Triangulation result is different from expectation #170

Closed pockie closed 4 months ago

pockie commented 4 months ago

I have the following rectangle with an inner point which I add as a hole described in #166. In the first picture you see the result. But I expected the triangulation from the second image. My questions are: Is the result from earcut correct? Is there a way to get my expected result?

earcut([
  0, 0, // 0
  3000, 0, // 1
  3000, 2400, // 2
  0, 2400, // 3
  0, 0, // 4
  986, 1210, // 5
], [5])

image image

mourner commented 4 months ago

The result is expected and correct — the triangles cover and match the original shape exactly, and Earcut doesn't give any additional guarantees on triangulation shape. You might be looking for Constrained Delaunay Triangulation, which guarantees somewhat well-formed triangles, but there is no fast and robust JS library for performing such triangulation that I'm aware of.

pockie commented 4 months ago

Thanks for the fast reply. poly2tri.js works for me to solve this problem.