Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-8583

Make GeoUtils#orientation method more stable

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Resolved
    • Priority: Major
    • Resolution: Not A Problem
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: core/other
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      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.

        Attachments

        1. LUCENE-8583.patch
          4 kB
          Ignacio Vera

          Activity

            People

            • Assignee:
              ivera Ignacio Vera
              Reporter:
              ivera Ignacio Vera
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: