search

jhasse / poly2tri

2D constrained Delaunay triangulation library
BSD 3-Clause "New" or "Revised" License
429 stars 89 forks source link

Simple polygon triangles error! #8

Closed sheiling closed 2 years ago

sheiling commented 4 years ago

When I using "poly2tri" to triangles my polygons, amlost of them can work fines! But, this polygon works invalid.

  1. The polygon image: 传入ID所对应三角面剖分轮廓图
  2. triangles.dat using the demo format

triangles.zip

  1. Tringle result: 捕获

Can your help me,thanks!

praveenagrawal commented 4 years ago

Hi Even I am facing a similar error while trying to triangulate a 2D contour in the shape of letter 'D'. The error I am facing is exactly like the above example where two points are wrongly generated on the bottom left and bottom right.

sheiling commented 4 years ago

Hi,when I searched some tips about this problem,but not got a direct answer. So I using " ear cut " make the polygon triangle right!

---Original--- From: "Praveen Agrawal"<notifications@github.com> Date: Mon, Oct 21, 2019 20:51 PM To: "jhasse/poly2tri"<poly2tri@noreply.github.com>; Cc: "sheiling"<863583026@qq.com>;"Author"<author@noreply.github.com>; Subject: Re: [jhasse/poly2tri] Simple polygon triangles error! (#8)

Hi Even I am facing a similar error while trying to triangulate a 2D contour in the shape of letter 'D'. The error I am facing is exactly like the above example where two points are wrongly generated on the bottom left and bottom right.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub, or unsubscribe.

Myszkoj commented 2 years ago

Hello, I have found out that sometimes generated triangles use head and tail points from the SweepContext. Any idea why?

pierre-dejoue commented 2 years ago

Hello,

I investigated this issue. It turns out that the input polygon isn't simple, which is a requirement of the input of poly2tri (see README for more information.)

More precisely, the following edges taken from the original input are self-intersecting:

628 511
628 508
632 508
610 509

This can be seen by zooming in on that area:

./p2t.exe ./testbed/data/triangles-issue-8.dat 620 510 40 non-simple-polygon

pierre-dejoue commented 2 years ago

In addition to my previous post, if we move one of the points to make the polygon simple, then the triangulation works properly.

Moving point 628 508 to 628 509: make-it-simple

Whole solution with the patched polygon: full-polygon-with-patch