软件构造Lab1-ConvexHulls
程序员文章站
2024-02-09 16:07:22
...
要求如下:
/**
* Given a set of points, compute the convex hull, the smallest convex set that contains all the points
* in a set of input points. The gift-wrapping algorithm is one simple approach to this problem, and
* there are other algorithms too.
*
* @param points a set of points with xCoords and yCoords. It might be empty, contain only 1 point, two points or more.
* @return minimal subset of the input points that form the vertices of the perimeter of the convex hull
*/
意思就是说,给你一堆点,要你在这些点里找到最外面的那一圈,这个其实比较简单,流程如下:
- 如果点的个数小于4,直接返回点集,否则:
- 找到当前最左下的点为起始点和终结点,并加入点集
- 执行如下循环
计算当前点到其余每个点的转角度数并遍历 这些点中距离当前点最远的那个点即为下一个要找的点 以该点为当前点,并将其加入集合 - 直到终结点等于起始点,返回点集
代码如下,还是比较简单的
public static Set<Point> convexHull(Set<Point> points) {
Point pointNow;
Point pointNext = null;
Point pointMin = null;
Point[] pointsArr = points.toArray(new Point[0]);
int len = pointsArr.length;
double bearingNow;
double bearingNext;
double bearingPre;
double lengthNext;
Set<Point> pointsNew = new HashSet<Point>();
if(len != 0) {
if(len < 4)
return points;
for(int i = 0; i < len; i ++) {
if(pointMin == null)
pointMin = pointsArr[i];
else if(pointMin.x() > pointsArr[i].x()) pointMin = pointsArr[i];
else if(pointMin.x() == pointsArr[i].x())
if(pointsArr[i].y() < pointMin.y()) pointMin = pointsArr[i];
}
pointsNew.add(pointMin);
pointNow = pointMin;
bearingPre = 0;
while(true) {
bearingNext = 360;
lengthNext = Double.MAX_VALUE;
for(int i = 0; i < len; i ++) {
if(pointsArr[i].equals(pointNow)) continue;
bearingNow = calculateBearingToPoint(bearingPre,(int)pointNow.x(),(int)pointNow.y(),(int)pointsArr[i].x(),(int)pointsArr[i].y());
if(bearingNext == bearingNow) {
if(lengthNext < (Math.pow(pointsArr[i].x()-pointNow.x(), 2)+Math.pow(pointsArr[i].y()-pointNow.y(), 2))) {
lengthNext = Math.pow(pointsArr[i].x()-pointNow.x(), 2)+Math.pow(pointsArr[i].y()-pointNow.y(), 2);
pointNext = pointsArr[i];
}
} else if (bearingNext > bearingNow) {
lengthNext = Math.pow(pointsArr[i].x()-pointNow.x(), 2)+Math.pow(pointsArr[i].y()-pointNow.y(), 2);
bearingNext = bearingNow;
pointNext = pointsArr[i];
}
}
if(pointMin.equals(pointNext)) break;
pointNow = pointNext;
bearingPre += bearingNext;
pointsNew.add(pointNext);
}
}
return pointsNew;
}
上一篇: filter过滤器的基本使用
下一篇: http --- > 基本认证与摘要认证