围绕中心对二维点进行排序会抛出比较异常

Question

我正在制作一个带有阴影的 2D 游戏，为了从灯光投射阴影，我绘制了可见性多边形。在我画它之前，我喜欢光线的交点，然后对这些点进行排序。我用这个算法 Sort points in clockwise order?

问题是我在游戏的某个时刻遇到了这个异常：

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!

我不知道为什么会这样。我检查了很多次错误，但我的代码与 post.

中的代码相同

这是我的比较器。

public class SortPoints implements Comparator<Point2D.Double>{

    private Point2D.Double center;
    public SortPoints(Point2D.Double _center){
        center = _center;
    }
    @Override
    public int compare(Point2D.Double o1, Point2D.Double o2) {

        if(o1.equals(o2)){//edited if statement
           return 0;
        }
        if (o1.x - center.x >= 0 && o2.x - center.x < 0)
            return 1;
        if (o1.x - center.x < 0 && o2.x - center.x >= 0)
            return -1;
        if (o1.x - center.x == 0 && o2.x - center.x == 0) {
            if (o1.y - center.y >= 0 || o2.y - center.y >= 0)
                if (o1.y > o2.y)
                    return 1;
                else return -1;
            if (o2.y > o1.y)
                return 1;
            else return -1;
        }

        // compute the cross product of vectors (center -> a) x (center -> b)
        double det = (o1.x - center.x) * (o2.y - center.y) - (o2.x - center.x) * (o1.y - center.y);
        if (det < 0)
            return 1;
        if (det > 0)
            return -1;

        // points a and b are on the same line from the center
        // check which point is closer to the center
        double d1 = (o1.x - center.x) * (o1.x - center.x) + (o1.y - center.y) * (o1.y - center.y);
        double d2 = (o2.x - center.x) * (o2.x - center.x) + (o2.y - center.y) * (o2.y - center.y);
        if(d1 > d2)
            return 1;
        else return -1;
    }
}

编辑： 我没有处理两点相等的部分。所以我在比较方法的开头添加了这个：

if(o1.equals(o2)){
   return 0;
}

Answer 1

你的方法没有处理点数相等的情况。 Comparator 的 compare 方法可以 return 正数或负数，具体取决于参数之间的关系——如果参数相等，则为零。

围绕中心对二维点进行排序会抛出比较异常

Sorting 2D points around center throws comparison exception

java

algorithm

math

geometry

computational-geometry