[jira] [Created] (LUCENE-8583) Make GeoUtils#orientation method more stable

["Ignacio Vera (JIRA)" <ji...@apache.org>]

Ignacio Vera created LUCENE-8583:
------------------------------------

             Summary: Make GeoUtils#orientation method more stable
                 Key: LUCENE-8583
                 URL: https://issues.apache.org/jira/browse/LUCENE-8583
             Project: Lucene - Core
          Issue Type: Improvement
          Components: core/other
            Reporter: Ignacio Vera


The method GeoUtils#orient is problematic when called with points that are almost collinear but not quite. In that case the sign of the determinant is not reliable, so for example calling the method with points (a, b, c) and with (c, b, a) gives the same orientation. 

There is a complex implementation described here (https://www.cs.cmu.edu/~quake/robust.html) where the method becomes more reliable. I have been playing with such implementation and still is not 100% reliable.

My proposal is not to be fully precise and define a precision constant for this method. Therefore whenever the value of determinant is small to that precision, we consider the points to be collinear. In this case the results of the method are reliable.




--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org