Java 实现：寻找两个点之间最短无遮挡路径

以下是用 Java 实现的代码：

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class ShortestPathFinder extends JPanel {
    private static final int WIDTH = 800; // 窗口宽度
    private static final int HEIGHT = 600; // 窗口高度
    private static final int POINT_SIZE = 10; // 端点大小
    private static final int LINE_WIDTH = 2; // 线段宽度
    private static final int MAX_INTERSECT_LINES = 10; // 最大干扰线段数量

    private List<Point> points; // 端点列表
    private List<Line> lines; // 线段列表
    private List<Line> intersectLines; // 干扰线段列表
    private Line shortestPath; // 最短路径

    public ShortestPathFinder() {
        points = new ArrayList<>();
        lines = new ArrayList<>();
        intersectLines = new ArrayList<>();
        shortestPath = null;

        generatePoints();
        generateLines();
        findShortestPath();
    }

    private void generatePoints() {
        Random random = new Random();
        int x1 = random.nextInt(WIDTH / 2 - POINT_SIZE);
        int y1 = random.nextInt(HEIGHT - POINT_SIZE);
        int x2 = random.nextInt(WIDTH / 2 - POINT_SIZE) + WIDTH / 2;
        int y2 = random.nextInt(HEIGHT - POINT_SIZE);
        points.add(new Point(x1, y1));
        points.add(new Point(x2, y2));
    }

    private void generateLines() {
        Random random = new Random();
        int numLines = random.nextInt(31) + 10;

        for (int i = 0; i < numLines; i++) {
            int x1 = random.nextInt(WIDTH);
            int y1 = random.nextInt(HEIGHT);
            int x2 = random.nextInt(WIDTH);
            int y2 = random.nextInt(HEIGHT);
            lines.add(new Line(new Point(x1, y1), new Point(x2, y2)));
        }

        for (int i = 0; i < MAX_INTERSECT_LINES; i++) {
            int x1 = random.nextInt(WIDTH);
            int y1 = random.nextInt(HEIGHT);
            int x2 = random.nextInt(WIDTH);
            int y2 = random.nextInt(HEIGHT);
            intersectLines.add(new Line(new Point(x1, y1), new Point(x2, y2)));
        }
    }

    private void findShortestPath() {
        double minDistance = Double.MAX_VALUE;

        for (Line line : lines) {
            if (!isLineIntersected(line, intersectLines)) {
                double distance = line.getStart().distance(line.getEnd());

                if (distance < minDistance) {
                    minDistance = distance;
                    shortestPath = line;
                }
            }
        }
    }

    private boolean isLineIntersected(Line line, List<Line> intersectLines) {
        for (Line intersectLine : intersectLines) {
            if (line.intersects(intersectLine)) {
                return true;
            }
        }
        return false;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        for (Line line : lines) {
            g.setColor(Color.BLACK);
            g.drawLine(line.getStart().x, line.getStart().y, line.getEnd().x, line.getEnd().y);
        }

        for (Line intersectLine : intersectLines) {
            g.setColor(Color.RED);
            g.drawLine(intersectLine.getStart().x, intersectLine.getStart().y,
                    intersectLine.getEnd().x, intersectLine.getEnd().y);
        }

        if (shortestPath != null) {
            Graphics2D g2d = (Graphics2D) g;
            g2d.setStroke(new BasicStroke(LINE_WIDTH));
            g2d.setColor(Color.GREEN);
            g2d.drawLine(shortestPath.getStart().x, shortestPath.getStart().y,
                    shortestPath.getEnd().x, shortestPath.getEnd().y);
        }

        for (Point point : points) {
            g.setColor(Color.BLUE);
            g.fillOval(point.x - POINT_SIZE / 2, point.y - POINT_SIZE / 2, POINT_SIZE, POINT_SIZE);
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame('Shortest Path Finder');
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(WIDTH, HEIGHT);
        frame.setLocationRelativeTo(null);

        ShortestPathFinder shortestPathFinder = new ShortestPathFinder();
        frame.add(shortestPathFinder);

        frame.setVisible(true);
    }
}

class Point {
    int x;
    int y;

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

    public double distance(Point other) {
        int dx = this.x - other.x;
        int dy = this.y - other.y;
        return Math.sqrt(dx * dx + dy * dy);
    }
}

class Line {
    private Point start;
    private Point end;

    public Line(Point start, Point end) {
        this.start = start;
        this.end = end;
    }

    public Point getStart() {
        return start;
    }

    public Point getEnd() {
        return end;
    }

    public boolean intersects(Line other) {
        int x1 = start.x;
        int y1 = start.y;
        int x2 = end.x;
        int y2 = end.y;
        int x3 = other.start.x;
        int y3 = other.start.y;
        int x4 = other.end.x;
        int y4 = other.end.y;

        int d = (y2 - y1) * (x4 - x3) - (x2 - x1) * (y4 - y3);
        if (d == 0) {
            return false;
        }

        double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / (double) d;
        double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / (double) d;

        return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1;
    }
}

将上述代码保存为ShortestPathFinder.java文件，并编译运行即可生成可执行文件。运行程序后会弹出一个窗口，窗口内会显示生成的线段，其中最短的一条线段会以绿色加粗标出。每次重新执行程序都会生成新的线段。