Convex Hull - Determine order of the points

Question

So I'm learning about Convex Hull Algorithms, and writing up all the algorithms from a naive Bruteforce to the Graham Scan.

This is my Bruteforce O(n^4) Algorithm. In the beginning, assume all the points are part of the hull. For each triangle possible, eliminate all points that lie inside the triangle. In the End, those points that were not eliminated will be part of the hull.

Here's the Java code (FIXED: With Thomash's Solution)

public List<Point> naive(List<Point> points) {
    if (points == null)
        return Collections.emptyList();
    if (points.size() <= 3)
        return points;
    boolean[] extremePoints = new boolean[points.size()];
    Arrays.fill(extremePoints, true);
    for (int i = 0, sz = points.size(); i < sz; i++) {
        if (extremePoints[i])
            for (int j = 0; j < sz; j++) {
                if (i != j && extremePoints[j]) {
                    for (int k = 0; k < sz; k++) {
                        if (k != i && k != j) {
                            for (int l = 0; l < sz; l++) {
                                if (extremePoints[l] && l != i && l != j
                                        && l != k) {
                                    // Check if P[l] lies in triangle formed
                                    // by
                                    // P[i],P[j],P[k]

                                    Polygon p = new Polygon();
                                    p.addPoint(points.get(i).x,
                                            points.get(i).y);
                                    p.addPoint(points.get(j).x,
                                            points.get(j).y);
                                    p.addPoint(points.get(k).x,
                                            points.get(k).y);
                                    if (p.contains(points.get(l)))
                                        extremePoints[l] = false;
                                }
                            }
                        }
                    }
                }
            }
    }

    Point centerOfHull = null; // Arbitrary point inside the hull
    // Order?
    for (int i = 0; i < extremePoints.length; i++) {
        if (!extremePoints[i]) {
            centerOfHull = points.get(i);
            break;
        }
    }
    List<Point> convexHull = new ArrayList<Point>();
    for (int i = 0; i < extremePoints.length; i++) {
        if (extremePoints[i]) {
            convexHull.add(points.get(i));
        }
    }
    Collections.sort(convexHull, new PointComp(centerOfHull));
    // or use a heap. still O(nlogn)
    return convexHull;
}

private class PointComp implements Comparator<Point> {

    private Point center;

    public PointComp(Point center) {
        this.center = center;
    }

    @Override
    public int compare(Point o1, Point o2) {
        double angle1 = Math.atan2(o1.y - center.y, o1.x - center.x);
        double angle2 = Math.atan2(o2.y - center.y, o2.x - center.x);
        if (angle1 < angle2)
            return 1;
        else if (angle2 > angle1)
            return -1;
        return 0;
    }
}

I tried visually seeing these points, and they seem to be correct, however I don't know how to establish the order of the points to draw the convex hull polygon? Any help is appreciated.

Answer 1

Pick a point O inside the convex hull and another point A. For each B in the convex hull, compute the angle AÔB and sort points using these angles (if AÔB < AÔB' then we consider B < B').

Answer 2

If you're brute-forcing to find which points are part of the hull, you might as well continue doing ugly things to find the order of the points.

1. Start with the upper-leftmost point.
2. Calculate the angles from that point to all other points.
3. Pick the point with the angle closest to 0 degrees. This is the next point clockwise around the hull.
4. Rinse, lather, repeat.

You have to adjust the target angle as you go around the hull, but this works (and it's one way you'd do it on paper.)