Orientation.Index problem with COLLINEARity

[FObermaier]

The following unit test fails:

  public void testCollinear() {
    Coordinate p0 = new Coordinate(0, 100);
    Coordinate p1 = new Coordinate(1, 102.1082);
    Coordinate p2 = new Coordinate(3, 106.3246);

    assertEquals(Orientation.COLLINEAR, Orientation.index(p0, p1, p2));
  }

I'm aware that this is due to floating point arithmetic, so would it be acceptable to add the following overload of Orientation.index:

  /**
   * Returns the orientation index of the direction of the point <code>q</code> relative to
   * a directed infinite line specified by <code>p1-p2</code>.
   * The index indicates whether the point lies to the {@link #LEFT} or {@link #RIGHT}
   * of the line, or lies on it {@link #COLLINEAR}.
   * The index also indicates the orientation of the triangle formed by the three points
   * ( {@link #COUNTERCLOCKWISE}, {@link #CLOCKWISE}, or {@link #STRAIGHT} )
   * 
   * @param p1 the origin point of the line vector
   * @param p2 the final point of the line vector
   * @param q the point to compute the direction to
   * @param eps a threshold value for the determinat to be meaningful
   * 
   * @return -1 ( {@link #CLOCKWISE} or {@link #RIGHT} ) if q is clockwise (right) from p1-p2;
   *         1 ( {@link #COUNTERCLOCKWISE} or {@link #LEFT} ) if q is counter-clockwise (left) from p1-p2;
   *         0 ( {@link #COLLINEAR} or {@link #STRAIGHT} ) if q is collinear with p1-p2
   */
  public static int index(Coordinate p1, Coordinate p2, Coordinate q, double eps)

[dr-jts]

It's worth noting that this could be due to either:

• robustness failure in the DD determinant computation
• imprecise conversion of the decimal values to DD floating point values

Either way the effect is the same.

Do you need to define what the epsilon value applies to? Is it the value of the determinant, or the ordinate values? That can affect the size of the provided value. The method doc should discuss this, I think.

What is the algorithm you are suggesting be used to evaluate the fuzzy index value?

How are you intending to use this method in computation?

I do think something like this will be needed. I've been thinking about developing spatial predicates which will allow a tolerance value. Although I was thinking more along the lines of adding some snapping, rather than a tolerance on the basic predicates.

[FObermaier]

The problem first arises in CGAlgorithmsDD.orientationIndexFilter:

jts/modules/core/src/main/java/org/locationtech/jts/algorithm/CGAlgorithmsDD.java

Lines 142 to 144 in c2702c0

	double detleft = (pax - pcx) * (pby - pcy);
	double detright = (pay - pcy) * (pbx - pcx);
	double det = detleft - detright;

detLeft = 12.649200000000022,
detRight = 12.649200000000008, making
det = 1.4210854715202004E-14 instead of 0.

This continues into the DD computation in CGAlgorithmsDD.orientationIndex just with a lot more decimal places.
I don't see how snapping will help, but if it does, I'm fine with it. Perhaps a hard coded threshold for collinearity would do, too.

[dr-jts]

A related issue: libgeos/geos#1207