[geos-devel] QD (Quad-Double) Approach to Robustness

[strk at refractions.net]

On Wed, Jun 14, 2006 at 11:16:09AM -0700, Martin Davis wrote:
> > Ok, but equality is actually used in JTS too.
> > Does Java have an automatic approximate equality ?
> 
> I've been working under the assumption that Java uses a single FP model,
> so that it's safe to compare FP numbers.
> 
> In any case, I'm not sure that JTS uses FP equals for anything other
> than checking whether two points are *exactly* the same.  So this should
> be portable, I assume. 

As far as you mean memory address comparison that would be portable
(pointers are integer values). Unfortunately we don't have garbage
collection for free in the C++ world, so in some places your identity
checks might have become value comparisons. 

BTW, a quick grep on JTS sources for equals2D shows this is not true:

  ./algorithm/CGAlgorithms.java:197:    } while (ring[iPrev].equals2D(hiPt) && iPrev != hiIndex);
  ./algorithm/CGAlgorithms.java:203:    } while (ring[iNext].equals2D(hiPt) && iNext != hiIndex);
  ./algorithm/CGAlgorithms.java:214:    if (prev.equals2D(hiPt) || next.equals2D(hiPt) || prev.equals2D(next))
  ./algorithm/LineIntersector.java:284:      if (intPt[i].equals2D(pt)) {
  ./algorithm/LineIntersector.java:311:      if (! (   intPt[i].equals2D(inputLines[inputLineIndex][0])
  ./algorithm/LineIntersector.java:312:             || intPt[i].equals2D(inputLines[inputLineIndex][1]) )) {
  ./geom/Coordinate.java:134:  public boolean equals2D(Coordinate other) {
  ./geom/Coordinate.java:159:    return equals2D((Coordinate) other);
  ./geom/CoordinateList.java:141:        if (last.equals2D(coord)) return;
  ./geom/LineString.java:146:    return getCoordinateN(0).equals2D(getCoordinateN(getNumPoints() - 1));
  ./geomgraph/Edge.java:193:        if (intPt.equals2D(nextPt)) {
  ./geomgraph/Edge.java:234:      if (! pts[i].equals2D(e.pts[i])) {
  ./geomgraph/Edge.java:237:      if (! pts[i].equals2D(e.pts[--iRev])) {
  ./geomgraph/Edge.java:253:      if (! pts[i].equals2D(e.pts[i])) {
  ./geomgraph/EdgeIntersectionList.java:145:    boolean useIntPt1 = ei1.dist > 0.0 || ! ei1.coord.equals2D(lastSegStartPt);
  ./noding/SegmentNode.java:57:    isInterior = ! coord.equals2D(segString.getCoordinate(segmentIndex));
  ./noding/SegmentNode.java:81:    if (coord.equals2D(other.coord)) return 0;
  ./noding/SegmentNodeList.java:69:      Assert.isTrue(ei.coord.equals2D(intPt), "Found equal nodes with different coordinates");
  ./noding/SegmentNodeList.java:70://      if (! ei.coord.equals2D(intPt))
  ./noding/SegmentNodeList.java:126:      if (p0.equals2D(p2)) {
  ./noding/SegmentNodeList.java:159:    if (! ei0.coord.equals2D(ei1.coord)) return false;
  ./noding/SegmentNodeList.java:212:    if (! pt0.equals2D(edgePts[0]))
  ./noding/SegmentNodeList.java:218:    if (! ptn.equals2D(edgePts[edgePts.length - 1]))
  ./noding/SegmentNodeList.java:238:    boolean useIntPt1 = ei1.isInterior() || ! ei1.coord.equals2D(lastSegStartPt);
  ./noding/SegmentString.java:157:        if (intPt.equals2D(nextPt)) {
  ./noding/SegmentPointComparator.java:30:    if (p0.equals2D(p1)) return 0;

--strk;