Triangulate_MONO() failure

[GoogleCodeExporter]

Hello,
what input problems might cause Triangulate_MONO() to return 0?

(or, same thing, what requirements are there on input for triangulation to 
succeed?)

I'm going to append actual failing coordinates (polygon with holes) later today 
or tomorrow, as well as check whether partitioning fails or actual 
triangulation. Is there a format you prefer?

Thank you!

Original issue reported on code.google.com by motond...@gmail.com on 30 Apr 2014 at 3:54

[GoogleCodeExporter]

Hi,
Please upload the sample that fails. The most convenient format to use is that 
used by the test utility,
https://code.google.com/p/polypartition/source/browse/trunk/test/test.cpp
see
void WritePolyList(const char *filename, list<TPPLPoly> *polys);

Both partitioning and triangulation should succeed as long as input polygons 
are non-self-intersecting and are given in the correct vertex order 
(counter-clockwise for non-holes, clockwise for holes), as stated on the main 
project page.

Original comment by ivan.fra...@gmail.com on 30 Apr 2014 at 6:49

[GoogleCodeExporter]

Thanks for answering Ivan (and for developing the library). I will post data 
later today or tomorrow.

Those two requirements (non-self-intersecting and winding order) are satisfied 
in my data, so I wondered there could be more requirements. Maybe there's some 
numerical issue. We'll see after I post data.

Original comment by motond...@gmail.com on 30 Apr 2014 at 6:52

[GoogleCodeExporter]

Here's the data. I hope I got the format right.

While I'm quite sure the winding order is correct, I'm not that sure about 
self-intersections. I'm now working on a way to remove them; in the mean time I 
hope it's not too much time wasted on your side. Thank you in advance for 
helping.

Original comment by motond...@gmail.com on 30 Apr 2014 at 8:55

Attachments:

• failing_mono.txt

[GoogleCodeExporter]

Here's the same data after removal of self-intersections (not sure there were 
any, actually), performed using Clipper. Still fails.

Original comment by motond...@gmail.com on 1 May 2014 at 8:20

Attachments:

• failing_mono_clean.txt

[GoogleCodeExporter]

Hmm, this indeed looks like a bug. Good catch! For reference, I attached a 
minimized sample that triggers the bug. I haven't yet tracked down the root 
cause (it takes me some time as it's been a while since I did computational 
geometry), I plan to continue over the weekend.

Original comment by ivan.fra...@gmail.com on 1 May 2014 at 10:13

• Changed state: Accepted

Attachments:

• failing_mono_clean.txt

[GoogleCodeExporter]

The issue has been fixed in the most recent revision (submitted today).

The bug was in TPPLPartition::MonotonePartition where not all structures were 
correctly updated when new diagonals were added.

I verified that the new version works with failing_mono_clean.txt. The image 
with the result of triangulation is attached.

Original comment by ivan.fra...@gmail.com on 4 May 2014 at 10:27

• Changed state: Fixed

Attachments:

• test2.png

[GoogleCodeExporter]

Thank you very much Ivan, very quick.

Original comment by motond...@gmail.com on 4 May 2014 at 11:43