Java 实现最小圆覆盖算法 - 代码示例

Java 实现最小圆覆盖算法 - 代码示例

本文提供一个使用 Java 代码实现最小圆覆盖算法的示例，并展示如何使用该算法找到覆盖所有点的最小圆的个数和位置。

import java.util.ArrayList;
import java.util.List;

class Point {
    double x;
    double y;
    
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

class Circle {
    Point center;
    double radius;
    
    public Circle(Point center, double radius) {
        this.center = center;
        this.radius = radius;
    }
}

public class MinimumCircleCover {
    
    public static List<Circle> findMinimumCircles(List<Point> points, double radius) {
        List<Circle> circles = new ArrayList<>();
        
        for (Point point : points) {
            boolean covered = false;
            
            for (Circle circle : circles) {
                if (distance(point, circle.center) <= 2 * radius) {
                    covered = true;
                    break;
                }
            }
            
            if (!covered) {
                Circle newCircle = new Circle(point, radius);
                circles.add(newCircle);
            }
        }
        
        return circles;
    }
    
    private static double distance(Point p1, Point p2) {
        double dx = p2.x - p1.x;
        double dy = p2.y - p1.y;
        return Math.sqrt(dx*dx + dy*dy);
    }

    public static void main(String[] args) {
        // 示例输入数据
        List<Point> points = new ArrayList<>();
        points.add(new Point(1, 2));
        points.add(new Point(3, 4));
        points.add(new Point(5, 6));
        points.add(new Point(7, 8));
        points.add(new Point(9, 10));
        points.add(new Point(11, 12));
        points.add(new Point(13, 14));
        points.add(new Point(15, 16));
        points.add(new Point(17, 18));
        points.add(new Point(19, 20));
        
        double radius = 5.0;
        
        // 寻找最小圆的个数和具体位置
        List<Circle> minimumCircles = findMinimumCircles(points, radius);
        
        // 输出结果
        System.out.println("需要的最小圆的个数：" + minimumCircles.size());
        for (Circle circle : minimumCircles) {
            System.out.println("圆心坐标：" + circle.center.x + ", " + circle.center.y);
        }
    }
}

代码说明：

• 代码定义了 Point 和 Circle 类分别表示点和圆。
• findMinimumCircles 方法接收一个点列表和圆的半径作为参数，返回一个包含所有最小圆的列表。
• 该方法使用贪心算法，依次遍历每个点，如果该点没有被已有的圆覆盖，就创建一个以该点为圆心，半径为输入半径的圆。
• distance 方法用于计算两个点之间的距离。
• main 方法提供了一个示例数据，并演示了如何使用 findMinimumCircles 方法找到最小圆的个数和具体位置。

注意：

• 这只是一个简单的示例，实际应用中可能需要更复杂的数据结构和算法来处理不同的情况。

希望这能满足您的需求！如果还有其他问题，请随时提问。