So, I study Convex Hull algorithms and record all the algorithms from naive Bruteforce to Graham Scan.
This is my Bruteforce O (n ^ 4) algorithm. Assume first that all points are part of the hull. For each triangle, you can exclude all points that lie inside the triangle. In the end, those points that have not been eliminated will be part of the body.
Here's the Java code (FIXED: with Thomash 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) {
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;
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));
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 to visually see these points, and they seem correct, however I do not know how to set the order of the points for drawing the polygon of a convex hull. Any help is appreciated.
st0le source
share