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

Question

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

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

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

我不知道为什么会这样。我检查了很多次错误，但我的代码与那篇文章中的代码完全相同。

这是我的比较器。

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 方法可以根据参数之间的关系返回正数或负数——如果参数相等则返回零。