采用礼品包装算法

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

第1步：由于S点的列表，让S中的点标记S0，S1 ， ...，sk。选择最右边的最低点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中的点形成一个凸的船体。否则，将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; 
    } 
}

此方法返回true，如果Point c位于该行的所形成的权利加入Point a和Point b。

[我觉得有什么不对这个方法]

的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例外。

来源

2015-09-05 Saud

你能告诉你'Point'类吗？ –

它来自java库的java.awt.Point类。 – Saud

试试这个：

while(flag) { ...

，并将这个：

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

到您for循环。

来源

2015-09-05 09:17:00 ka4eli

什么是'while循环'的破坏条件，然后 – Saud

@Saud，更新了我的答案。 – ka4eli

请看看我的'isRight（）'方法（我已经更新了这个问题）。 – Saud

采用礼品包装算法

回答

相关问题