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

Question

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

第 1 步：给定点列表 S，让 S 中的点标记为 s0、s1、 ...，斯克。 Select最右边最低点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 所示。)

第三步：若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 形成的线的右侧，则此方法 returns 为真。

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

YComparator class:

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 循环。

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

Finding convex hull using gift-wrapping algorithm

java

algorithm

convex-hull