java实现从蛮力法实现凸包问题
时间: 2024-05-01 14:23:36 浏览: 21
凸包问题可以使用蛮力法(暴力枚举)解决,具体实现如下:
1. 首先定义一个 Point 类表示平面上的点,包含 x 和 y 坐标两个属性。
```
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
```
2. 接着,定义一个函数来计算三个点组成的向量叉积,用于判断是否是左转或右转。
```
private int crossProduct(Point A, Point B, Point C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
```
3. 定义一个函数来判断三个点是否是左转,即是否形成左拐。
```
private boolean isLeftTurn(Point A, Point B, Point C) {
return crossProduct(A, B, C) > 0;
}
```
4. 接下来,定义一个函数来查找凸包。
```
public List<Point> convexHull(List<Point> points) {
List<Point> hull = new ArrayList<>();
int n = points.size();
if (n < 3) return hull;
int leftMost = 0;
for (int i = 1; i < n; i++) {
if (points.get(i).x < points.get(leftMost).x) {
leftMost = i;
}
}
int p = leftMost;
do {
hull.add(points.get(p));
int q = (p + 1) % n;
for (int i = 0; i < n; i++) {
if (isLeftTurn(points.get(p), points.get(i), points.get(q))) {
q = i;
}
}
p = q;
} while (p != leftMost);
return hull;
}
```
在函数中,先找到 x 坐标最小的点作为起点,然后从起点开始顺时针遍历所有的点,每次找到当前点与下一个点形成左拐的点,直到回到起点。最后得到的点序列就是凸包。
使用示例:
```
public static void main(String[] args) {
List<Point> points = new ArrayList<>();
points.add(new Point(0, 0));
points.add(new Point(0, 1));
points.add(new Point(1, 0));
points.add(new Point(1, 1));
points.add(new Point(0.5, 0.5));
List<Point> hull = convexHull(points);
for (Point p : hull) {
System.out.println("(" + p.x + ", " + p.y + ")");
}
}
```
输出结果:
```
(0, 0)
(0, 1)
(1, 1)
(1, 0)
```