Java实现最短无遮挡线段查找算法

以下是用Java实现的程序：

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import javax.swing.JButton;
import javax.swing.JComponent;
import javax.swing.JFrame;
import javax.swing.JOptionPane;

public class ShortestLineFinder extends JComponent {

    private static final int WIDTH = 800;
    private static final int HEIGHT = 600;
    private static final int MIN_NUM_LINES = 10;
    private static final int MAX_NUM_LINES = 40;
    private static final int LINE_THICKNESS = 2;
    private static final Color LINE_COLOR = Color.BLACK;
    private static final Color SELECTED_LINE_COLOR = Color.RED;

    private List<Line2D> lines;
    private Line2D shortestLine;

    public ShortestLineFinder() {
        lines = new ArrayList<>();
        shortestLine = null;

        setLayout(null);

        JButton generateButton = new JButton('Generate');
        generateButton.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                generateRandomLines();
                findShortestLine();
                repaint();
            }
        });
        generateButton.setBounds(10, 10, 100, 30);
        add(generateButton);
    }

    private void generateRandomLines() {
        lines.clear();

        Random random = new Random();
        int numLines = random.nextInt(MAX_NUM_LINES - MIN_NUM_LINES + 1) + MIN_NUM_LINES;

        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);

            Line2D line = new Line2D.Double(x1, y1, x2, y2);
            lines.add(line);
        }
    }

    private void findShortestLine() {
        shortestLine = null;
        double minDistance = Double.MAX_VALUE;

        for (Line2D line : lines) {
            boolean isShortest = true;

            for (Line2D otherLine : lines) {
                if (line != otherLine && line.intersectsLine(otherLine)) {
                    isShortest = false;
                    break;
                }
            }

            if (isShortest) {
                double distance = line.getP1().distance(line.getP2());
                if (distance < minDistance) {
                    minDistance = distance;
                    shortestLine = line;
                }
            }
        }
    }

    protected void paintComponent(Graphics g) {
        Graphics2D g2d = (Graphics2D) g;

        // 设置抗锯齿
        g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

        // 绘制所有线段
        g2d.setColor(LINE_COLOR);
        g2d.setStroke(new BasicStroke(LINE_THICKNESS));
        for (Line2D line : lines) {
            g2d.draw(line);
        }

        // 绘制最短线段
        if (shortestLine != null) {
            g2d.setColor(SELECTED_LINE_COLOR);
            g2d.setStroke(new BasicStroke(LINE_THICKNESS + 2));
            g2d.draw(shortestLine);
        }
    }

    public static void main(String[] args) {
        JFrame frame = new JFrame('Shortest Line Finder');
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(WIDTH, HEIGHT);
        frame.add(new ShortestLineFinder());
        frame.setVisible(true);
    }
}

这个程序使用Java的Swing库创建了一个窗口，可以多次执行并重新生成线段。每次点击'Generate'按钮，程序会随机生成10到40条线段，然后找出其中最短的一条，该线段不能被其他线段遮挡。所有线段都会显示在窗口内，并且最短线段会加粗显示。