Simple polygons fail triangulation

[GoogleCodeExporter]

What steps will reproduce the problem?
----------

Using c++ latest source, attempt to triangulate two simple polygons. It appears 
that when two edges get near (not even very near) to collinear, strange results 
occur. 

Error Case 1:

(-10, -10.6426)
(-28.3133, -5.98394)
(19.8795, 21.6466)
(18.4337, -5.02008)

In EdgeEvent this causes "triangle->NeighborCCW(point);" to return NULL

Error Case 2:

(-4.61211, -11.3371)
(-44.477, -3.90043)
(25.2674, 20.9521)
(23.8216, -5.71459)

In NextFlipPoint this causes "Orientation o2d = Orient2d(eq, op, ep);" to 
return COLLINEAR as op == ep

What version of the product are you using? On what operating system?
---------

Latest source (as at 2010/12/16), Windows XP, VS2005.

Please provide any additional information below.
----------
My reported points start out as floats, so hopefully you can reproduce this on 
different hardware.

Sorry I couldn't run these through the testbed. I tried to get it building but 
couldn't get Python25 to run the waf configure:

C:\DEV\poly2tri>python waf configure
  set_options
  init called
  calling the configuration
Checking for program g++,c++             : ok C:\GCC\g++.exe
 error: Could not determine the compiler type

Original issue reported on code.google.com by roond...@gmail.com on 16 Dec 2010 at 8:48

Attachments:

• p2t_errorcase1.png
• p2t_errorcase2.png

[GoogleCodeExporter]

This must be the result of some bug. They are simple polygons and there is no 
issues triangulation them with the Java version.

Original comment by thahlen@gmail.com on 16 Dec 2010 at 3:59

[GoogleCodeExporter]

C++ has no problem triangulating. See attached screenshots.

Original comment by mason.gr...@gmail.com on 16 Dec 2010 at 5:10

• Changed state: Invalid

Attachments:

• poly1.png
• poly2.png

[GoogleCodeExporter]

Thank you both for verifying this for me. I'll have to go over my code again.

Original comment by roond...@gmail.com on 17 Dec 2010 at 1:42

[GoogleCodeExporter]

Ok, I'm officially an idiot. Turns out to get it to compile for MSVC I added 
the following:

#ifndef M_PI
#define M_PI 3.1415926535897932384626433832795
#endif

#ifndef M_PI_2
#define M_PI_2 6.283185307179586476925286766558
#endif

And clearly M_PI_2 is meant to be PI / 2 not PI * 2. Sorry for wasting your 
time!

Original comment by roond...@gmail.com on 17 Dec 2010 at 2:46

[GoogleCodeExporter]

np. I know of one more that did this error. There should probably be a comment 
or something about this in the code.

I usually name such fields PI_DIV_2 to avoid confusion.

Original comment by thahlen@gmail.com on 17 Dec 2010 at 5:30

[GoogleCodeExporter]

OK, I'll change M_PI_2 to PI_DIV_2 to avoid confusion.... thanks for the catch!

/Mason

Original comment by mason.gr...@gmail.com on 17 Dec 2010 at 6:58