[Plib-devel] RE: sgPointInTriangle2

[Fay J. F C. AAC/W. <joh...@eg...>]

For an additional note:  I modified the algorithm slightly so that all
subtractions are done relative to the corner of the triangle nearest the
point being tested.  This makes the algorithm considerably more robust in
cases where one corner of the triangle has coordinates greater than the
others by several orders of magnitude.

I have noticed that the existing algorithm gives significantly different
results when in MSVC debug mode than it does in MSVC release mode for
degenerate triangles.  In the case of degenerate triangles, many
"reasonable" cases (all coordinates the same order of magnitude and the
point is clearly off the line segment created by the degenerate triangle)
give false positives.

In release mode, I ran a case (with "stretched" triangles with one corner
having coordinates three orders of magnitude larger than the other corners)
and found out of 29,000,000 points tested there were 218 cases in which the
two algorithms disagreed.  From a brief inspection it appears that all
involve the "stretched" triangles.  An in-depth analysis of two of them
shows that the new algorithm gives correct answers where the existing
algorithm does not.

The bottom line is that I have tested the new algorithm rather severely and
I think it should go into the SG library.

John F. Fay
joh...@eg...