[Plib-devel] sgPointInTriangle2

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

Gentlemen,

	A couple of months ago I put out a new algorithm for calculating
whether a point is in a triangle in two dimensions.  This algorithm is
robust and is a good bit faster than the one currently in the SG library.
At the time I listed the number of multiplications and so on and noted that
it avoided some square root taking.  The reaction at the time was that this
was a new and unheard-of algorithm and that we would do well to play it safe
with the SG library.

	Since then I have put it and the present algorithm through some
rather stringent tests.  Under all reasonable circumstances, they give
identical results.  The new algorithm handles degenerate triangles slightly
better than the present algorithm, which includes my good friend "NaN" (Not
a Number) in its calculations under these circumstances.  I have just given
them Steve Baker's test of "Given a grid of triangles, will the point fall
into exactly one of the triangles".  For a reasonable grid (no exceptionally
elongated triangles, although two of the 50 triangles were degenerate) I
checked some 16,000,000 points and found no multiple-triangle hits.  With
some extremely elongated triangles (an aspect ratio of 1000 or so) I am
getting about 50 double hits (where the point is flagged as being in two
triangles) when checking 10,000,000 points.  Again, both the present
algorithm and the new algorithm give identical results.

	Based on these results, I would like to offer the new
"sgPointInTriangle2" function for the SG library.  It behaves at least no
worse than the present algorithm and does it considerably faster.

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