Thread: Collections.binarySearch returns wrong index

  final static public Point diagPoint = new Point("308.540978536647", "204.89781897342627");
 
  /**
   * compare points by x,y
   */
  public static final Comparator<Point> pointComp = new Comparator<Point>()
  {
    public int compare(Point p1, Point p2)
    {
      if ((p1.compareToXY(diagPoint) == 0) || (p1.compareToXY(diagPoint) == 0))
      {
        App.diagnose("pointComp result " + p1.compareToXY(p2) + " when compare p1 " + p1 + " to p2 " + p2);
      }
      return p1.compareToXY(p2);    
    }
  };
 
  public Surface3d(Site site, TreeSet<ITriangle> unusedTriangles) throws UnexpectedException
  {
      TreeSet<Point> groundPoints = new TreeSet<Point>(pointComp);
 
      // A. for each point in unusedTriangles, save p into groundPoints
 
      for (ITriangle triangle: unusedTriangles)
      {
        Point[] points = triangle.getPoints();
        for (Point p: points)
        {
          boolean diag = (p.compareToXY(diagPoint) == 0);
          if (diag)
          {
            App.diagnose("checking diagPoint " + p.toXYString() + " in " + triangle);
          }
          if (! groundPoints.contains(p))
          {
            if (diag)
            {
              App.diagnose("add to groundPoints diagPoint " + p.toXYString());
            }
            groundPoints.add(p);
          }
        } // end for each point in triangle
      } // end for each triangle in roof
 
      // B. for each unusedTriangle get index of each point
      ArrayList<Point> sortedGroundPoints = new ArrayList<>(groundPoints);
 
      for (ITriangle triangle: unusedTriangles)
      {
        Point[] points = triangle.getPoints();
        for (Point p: points)
        {
          int index = Collections.binarySearch(sortedGroundPoints, p, pointComp);
 
          if (index < 0)
          {
            index = -index - 1;
            Point near = null;
            for (int nearIndex = index-10;nearIndex<= index;nearIndex++)
            {
              if (nearIndex >= 0)
              {
                near = sortedGroundPoints.get(nearIndex);
                App.diagnose("compare diag " + diagPoint.toXYString() + " to nearIndex " + nearIndex + " " + near.toXYString());
                if (near.compareToXY(diagPoint) == 0)
                {
                  break;
                }
                else
                {
                  near = null;
                }
              }
            }
            throw new UnexpectedException("In groundPoints, at index " + index + " can not find " + p + " from " + triangle + " near " + near); //$NON-NLS-1$
          }
          p = sortedGroundPoints.get(index);
          // groundTriangleIndexBuff.put(index); // save index into TriangleIndexBuff
          // more code saving p into vertexBuff, calculating normals, etc
        }
      }
  }

Output:
Surface3d.java(1916) add to groundPoints diagPoint -12445, X=308.540978536647, Y=204.89781897342627
Surface3d.java(88) pointComp result 1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16499, X=249.456506, Y=307.105268, Z=202.22098700393
Surface3d.java(88) pointComp result 1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16508, X=301.927425, Y=516.152892, Z=203
Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16211, X=314.0301017547257, Y=283.1977886190188, Z=204.22315265408673
Surface3d.java(88) pointComp result 1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16257, X=307.809813, Y=288.475484, Z=203.979338
Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16244, X=310.643037, Y=273.667287, Z=204
Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -15278, X=308.540913, Y=239.446042, Z=206.38019490565
Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -14617, X=308.5409603760091, Y=214.39787824126483, Z=0
Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -13111, X=308.5409671623528, Y=210.8478560735622, Z=0
Surface3d.java(88) pointComp result -1 when compare p1 -12445, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -13102, X=308.54097175030347, Y=208.44784106983346, Z=0
Surface3d.java(1910) checking diagPoint -12423, X=308.540978536647, Y=204.89781897342627 in Contour.ITriangle p1 -12423, p2 -12421, p3 -12422
Surface3d.java(88) pointComp result 1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16499, X=249.456506, Y=307.105268, Z=202.22098700393
Surface3d.java(88) pointComp result 1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16508, X=301.927425, Y=516.152892, Z=203
Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16211, X=314.0301017547257, Y=283.1977886190188, Z=204.22315265408673
Surface3d.java(88) pointComp result 1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16257, X=307.809813, Y=288.475484, Z=203.979338
Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -16244, X=310.643037, Y=273.667287, Z=204
Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -14617, X=308.5409603760091, Y=214.39787824126483, Z=0
Surface3d.java(88) pointComp result -1 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -13102, X=308.54097175030347, Y=208.44784106983346, Z=0
Surface3d.java(88) pointComp result 0 when compare p1 -12423, X=308.540978536647, Y=204.89781897342627, Z=0 to p2 -12445, X=308.540978536647, Y=204.89781897342627, Z=0
Surface3d.java(1976) compare diag -30818, X=308.540978536647, Y=204.89781897342627 to nearIndex 301 -11371, X=308.54100531484664, Y=190.8808392888774
Surface3d.java(1976) compare diag -30818, X=308.540978536647, Y=204.89781897342627 to nearIndex 302 -12439, X=308.540998, Y=194.716293
Surface3d.java(1976) compare diag -30818, X=308.540978536647, Y=204.89781897342627 to nearIndex 303 -12445, X=308.540978536647, Y=204.89781897342627

View3D.makeUnusedSurface unexpectedException
java.rmi.UnexpectedException: In groundPoints, at index 311 can not find -12445, X=308.540978536647, Y=204.89781897342627, Z=207.55448524554507914 from Contour.ITriangle p1 -12447, p2 -12445, p3 -12446 near -12445, X=308.540978536647, Y=204.89781897342627, Z=207.55448524554507914
at com.neighborhoodinnovations.ThreeD.Surface3d.<init >(Surface3d.java:1987)
... more printStackTrace output cut

Note that Point.pointCompXY returns the correct result. However Collections.binarySearch seems to be ignoring that result.

Also note that this code seems to work correctly 99.95 percent of the time. Only in this one data set (so far) am I experiencing a problem.

I am willing to share more code if needed. Any suggestions for further diagnostics?

I just want to point out, that this line:

if ((p1.compareToXY(diagPoint) == 0) || (p1.compareToXY(diagPoint) == 0))

does not look quite right since you are checking for the very same thing twice. I guess this is a typo and it might reveal other errors in your code somewhere, but I am not sure.


Other then that, it might also be, that your equals and hashCode methods are not synced, and thus your SortedCollection is not set up correctly.

You are correct, it should be

if ((p1.compareToXY(diagPoint) == 0) || (p2.compareToXY(diagPoint) == 0))

but that only means I got less diagnostics than what I wanted.

The equals and compareToXY code are synced. Since I am not using Hash* methods, why would I worry about hashCode?

Because the Object API clearly states that hashCode and equals must be synced (when equals returns true, hashCodes must be equal as well). If they are not the behavior of several standard classes is not well defined.
Furthermore the behavior of Comparators must also be synced with the equals method and return 0 when equals would return true.

The problem is in the data, where points are very close together, but the comparison method only was accurate to 6 decimal places. After upping the accuracy to 9 decimal places, everything sorted correctly and there were no problems.