所以我正在学习凸包算法，并编写了从朴素的蛮力到格雷厄姆扫描的所有算法。
这是我的 Bruteforce O(n^4) 算法。一开始，假设所有点都是船体的一部分。对于每个可能的三角形，消除位于三角形内的所有点。最后，那些没有消除的点将成为船体的一部分。
这是 Java 代码(已修复:使用 Thomash 的解决方案)
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;
}
}
我试过目测这些点，它们似乎是正确的，但是我不知道如何建立点的顺序来绘制凸包多边形？感谢您的帮助。
最佳答案
如果您要通过暴力法查找哪些点是船体的一部分，您还不如继续做丑陋的事情来查找这些点的顺序。
- 从最左上角的点开始。
- 计算从该点到所有其他点的角度。
- 选择角度最接近 0 度的点。这是船体顺时针方向的下一个点。
- 冲洗、起泡、重复。
当您绕着船体转时，您必须调整目标角度，但这行得通(而且这是您在纸上做的一种方法。)
关于java - Convex Hull - 确定点的顺序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10513920/