Crash when trying to triangulate

[GoogleCodeExporter]

Hello,

Poly2tri chrashes (AccessViolation) when trying to triangulate the following 
polyline (see attached file). We solved the issue by inserting the following 
code to sweep.cc Sweep::EdgeEvent() - line 107

>> if(!triangle)
>> {
>>   printf( "p2tri: triangle is null\n" );
>>   return;
>> }

The triangulation the works but uses additional points outside the input 
polyline. Would you please check?! We are using the recent repo source code on 
a win7-machine.

Thanks!

Ricardo

Original issue reported on code.google.com by ricardos...@gmail.com on 10 Jul 2013 at 11:16

Attachments:

• polyline.txt

[GoogleCodeExporter]

Running supplied pointset at 
http://javascript.poly2tri.googlecode.com/hg/index.html works fine.

Also no problems triangulating the polyline with the Java branch that I 
maintain.

So hard for me to help with this since I don't have a setup to run c++ code :/.

There are two exterior points used during triangulation but they and the 
external triangles will be remove after a successful triangulation.

Original comment by thahlen@gmail.com on 10 Jul 2013 at 12:23

[GoogleCodeExporter]

Hi,

after adding the code above to the c++ version, our example works but the 
exterior points and external triangles are not removed automatically 
afterwards. We do this currently ourselves after the triangulation, but it 
would be nice if this can be done inside p2t.

We have another polyline that crashes p2t c++ but works in the jave version 
(see attached file). This time an stack overflow occurs...

Thahlen, could you shortly summarize how the c++ and java differ? Are the 
source code changes of both not synchronized from time to time?

Thanks in advance,
Ricardo

Original comment by ricardos...@gmail.com on 10 Jul 2013 at 1:13

[GoogleCodeExporter]

Sorry forgot the test data..

Original comment by ricardos...@gmail.com on 10 Jul 2013 at 1:38

Attachments:

• polyline1.txt

[GoogleCodeExporter]

Well triangle should never be null where you add your code.
Can't really tell what will happen to the triangulation datastructure when 
aborting the triangulation process with that return.

There shouldn't be any major differences between the core triangulation code in 
the Java or C++ code that I could think of. The C++ version was ported from the 
Java version, but the class structure is somewhat different.

It sound like you have some kind of precision issue. Is your polyline dump 
exactly the values you are using or are they rounded to three decimals just 
when dumping?

The polyline looks like some result of an intersection cut since there are so 
many points on same "straight" lines. If you use double precision and cut 
multiple edges with one line and get multiple intersection points on that line 
and use 15 decimals you can get float issues when triangulating. 

If this is what you do try rounding points to 12 decimals or less before 
triangulation. Also the Epsilon value used in the lib is optimized for data in 
the range -1 to 1. If the lib uses epsilon 1e-13 and your points are in the 
range -1000 to 1000 an epsilon of 1e-10 would be better.

Well thats what I could think of right now.

Original comment by thahlen@gmail.com on 10 Jul 2013 at 9:30

[GoogleCodeExporter]

Did you manage to solve this issue?

Original comment by thahlen@gmail.com on 20 Jul 2013 at 11:11

[GoogleCodeExporter]

Yes after several tests and debugging p2t works fine.

We have implemented a routine that filters all non-collinear unique points and 
transforms them in the range of -1 to 1. Now p2t does not crash anymore and the 
results are good. 

Thanks for your help.

Original comment by ricardos...@gmail.com on 23 Jul 2013 at 11:22

[GoogleCodeExporter]

Great!

Original comment by thahlen@gmail.com on 23 Jul 2013 at 11:27

• Changed state: WontFix