java - 使用礼品包装算法寻找凸包

Question

这是使用礼品包装算法寻找凸包的伪代码:

第 1 步:给定点列表 S，让 S 中的点标记为 s0、s1、...，斯克。选择最右边的最低点S。如图24.9a，h0就是这么一点。将 h0 添加到列表 H。(H 最初是空的。H 将包含所有点在算法完成后的凸包中。)设 t0 为 h0。

第 2 步:设 t1 为 s0。对于 S 中的每个点 p，如果 p 在 t0 到 t1 的直线的右侧，则设 t1 为 p。(在第 2 步之后，没有点位于从 t0 开始的直线的右侧到 t1，如图 24.9b 所示。)

第 3 步:如果 t1 是 h0(见图 24.9d)，H 中的点形成一个凸S 的船体。否则，将 t1 添加到 H，令 t0 为 t1，然后返回步骤 2(见图 24.9c)。

到目前为止，这是我设法做到的:

public void getConvexHull(ArrayList<Point> points) {
    ArrayList<Point> h = new ArrayList<Point>();
    points.sort(new YComparator());
    h.add(points.get(points.size()-1)); // Add the rightmost lowest point to h
    Point t0 = h.get(0);
    Point t1 = points.get(0);
    while(true) {
        for(int i = 0; i<points.size(); i++) {
            if(isRight(t0,t1,points.get(i)) == 1) {
                t1 = points.get(i);
            }
        }
        if(t1.equals(h.get(0))) {
            break;
        }
        h.add(t1); // The exception occurs at this line
        t0 = t1;
        t1 = points.get(0);
    }
    for(Point x: h)
        System.out.println(x);
}

isRight() 方法:

public int isRight(Point a, Point b, Point c){
    int pos = ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x));
    if(pos < 0) {
        return 1;
    }
    else if(pos > 0) {
        return -1;
    }
    else {
        return 0;
    }
}

如果 Point c 位于 Point a 和 Point b 连接线的右侧，则此方法返回 true。

[我觉得这个方法有问题]

YComparator 类:

public class YComparator implements Comparator<Point>{
@Override
public int compare(Point a, Point b) {
    if(a.y > b.y) {
        return 2;
    }
    else if(a.y < b.y) {
        return -2;
    }
    else if(a.y == b.y) {
        if(a.x > b.x) {
            return 1;
        }
        else if(a.x < b.x) {
            return -1;
        }
    }
    return 0;
}
}

当我运行程序时，它抛出 java.lang.OutOfMemoryError: Java heap space 异常。

Answer 1

试试这个:

while(flag) { ...

然后移动这个:

if(t1.equals(h.get(0))) {
    flag = false;
}

进入你的 for 循环。