[ REQ 5499]: Problem with poly2tri routine

[SVLAD at delphi.com]

Hi,

I recently downloaded the geom_utils and I have found a problem
with the poly2tri function, but I am not quite sure how it
should be fixed.

The error can be duplicated by running the program "func_test"
with the following simple planar, concave, non-intersecting
polygon:

Vertex 0: 1 1 0
Vertex 1: 2 5 0
Vertex 2: 6 6 0
Vertex 3: 5 3 0
Vertex 4: 8 1 0

The program will core dump because in the routine
"point_in_triangle" the test_point is equal to the first vertex
of the triangle passed in.  This causes the calculation  of the
denominator to result in zero which is later used in divisions
causing a divide by zero exception.

I tried trapping this condition and either return TRUE or
FALSE.  Returning TRUE will fix the problem for some polygons,
but there are others that will result in an infinite loop.
Returning FALSE seems to always result in an infinite loop.
Here is a polygon that never seems to work no matter what you
return:

Vertex  0: 1 0 0
Vertex  1: 1 1 0
Vertex  2: 3 2 0
Vertex  3: 1 5 0
Vertex  4: 2 8 0
Vertex  5: 8 8 0
Vertex  6: 9 5 0
Vertex  7: 7 3 0
Vertex  8: 6 5 0
Vertex  9: 4 5 0
Vertex 10: 5 2 0
Vertex 11: 7 0 0

I am rather unfamiliar with these algorithms and I appreciate
any help you could provide.  Thanks.


Rick Harding
svlad at delphi.com