Sorting 2D points around center throws comparison exception

Question

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

At which line does the error occur? Does the stack trace show it? — DSlomer64, Sep 23 '15 at 18:53
Did you break on the exception in you IDE, and see what code is throwing the exception? Is there a comment in the code why it threw the exception or can you deduce the reason yourself? — mvd, Sep 23 '15 at 18:55
No the stack trace doesnt. It just shows the part of the code where i create the comparator.It points at this line -> Collections.sort(intersectionPoints, new SortPoints(lightSource)); And after that it goes in the arrays and collections in java. — Nikolai Nikolov, Sep 23 '15 at 18:59
It is really hard to debug because the game runs at 60fps and it doesnt appear right away it just happens at some point. And it happens more often when there are a lot of objects around. — Nikolai Nikolov, Sep 23 '15 at 19:01
Whiskeyspider Oh my god yes that was the problem. I am so stupid. If you type that as an answer i will mark it . Thanks ! — Nikolai Nikolov, Sep 23 '15 at 19:06

martinez314 · Accepted Answer · 2015-09-23T19:13:12.127

1

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.

edited Sep 23 '15 at 19:13

answered Sep 23 '15 at 19:07

martinez314

12,162
5
36
63

1

I would recommend editing this such that it says OP *isn't handling the case where the points are equal* (instead of wording it as a question). – But I'm Not A Wrapper Class Sep 23 '15 at 19:09

Sorting 2D points around center throws comparison exception

1 Answers1