0
private static void sort() {
    Arrays.sort(points, 1, 100, new Comparator<P>() {
        @Override
        public int compare(P p1, P p2) {
            double cp = cross_product(points[0], p1, p2);
            return cp > 0 ? -1 : 1;
        }
    });
}

public static double cross_product(P p1, P p2, P p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

I met this problem when I'm implementing the graham-scan algo for convex hull.

Turk Hussein
  • 15
  • 4
  • 3
    If `compare(a, b) > 0`, then `compare(b, a)` **must** be less than zero. That is the contract you're violating, because flipping `p1` and `p2` in call to `compare` means flipping `p2` and `p3` in call to `cross_product`, and that returns the exact *same* value, not the opposite value. --- Also, `compare(a, a)` **must** return zero, which is not the case either. – Andreas Sep 09 '17 at 17:53
  • In addition to @Andreas comment: your compare() method references `points[0]` while the `points` array is being modified by `Arrays.sort()`. Without detailed analysis, I guess that `compare(a,b)` might change its sign when points[0] is replaced by a different value during sorting. – Ralf Kleberhoff Sep 09 '17 at 19:20
  • @RalfKleberhoff I thought that at first too, but the sort is `fromIndex = 1, toIndex = 100`, so index 0 is unmodified. – Andreas Sep 10 '17 at 02:31

0 Answers0