CODEWITHSUNDEEP
javaalgorithmmathgeometrycomputational-geometry
Nikolai Nikolov
Nikolai Nikolov

Reputation: 458

Sorting 2D points around center throws comparison exception

I am making a 2D game with shadows and in order to cast shadows from lights i draw visibility polygon. Before i draw it i fond intersection points of rays and then sort these points. I use this algorithm Sort points in clockwise order?

The problem is that i get this exception at some point of the game : 

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

I have no idea why this is happening. I checked a lot of times for mistakes, but my code is identical to the code in that post.

This is my comparator.

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;
    }
}

Edit: I didn't handle the part where the two points are equal. So i added this at the beggining of the compare method:

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

Upvotes: 1

Views: 182

Answers (1)

martinez314
martinez314

Reputation: 12332

Your method is not handling the case where the points are equal. The compare method of Comparator can return a positive or negative number depending on the relationship between the arguments -- or zero if the arguments are equal.

Upvotes: 1

Related Questions