首頁

# 作業內容

在 200x200 的正方形裡面畫出 5x5=25 個點，模擬道路隨機連通每個點，然後在道路上隨機布置一些點，最後輸入點的 id 還有 range 看看點可以到的範圍

# 程式實作

# 定義資料結構

# 點的 class

static class Point {
    int id;
    int x;
    int y;
    int xIndex;
    int yIndex;
    
    Point(int id, int x, int y, int xIndex, int yIndex) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.xIndex = xIndex;
        this.yIndex = yIndex;
    }
    // 計算兩點間的歐幾里得距離
    double distanceTo(Point other) {
        return Math.sqrt(Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2));
    }
}

# 邊的 class

static class Edge {
    Point start;
    Point end;
    double weight;
    Edge(Point start, Point end) {
        this.start = start;
        this.end = end;
        this.weight = start.distanceTo(end);
    }
}
# 隨機生成點


這邊限縮了一些範圍，使點比較集中在中心




int q_x = (i * seq + 10) + (int)(Math.random() * (seq - 20));




static void rand_generated_point(int xRange, int yRange, int seq) throws IOException {
    List<String> lines = new ArrayList<>();
    int k = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            int q_x = (i * seq + 10) + (int)(Math.random() * (seq - 20));
            int q_y = (j * seq + 10) + (int)(Math.random() * (seq - 20));
            Point p = new Point(k, q_x, q_y, i, j);
            points.add(p);
            lines.add((k+1) + " " + q_x + " " + q_y);
            // System.out.println("(" + q_x + ", " + q_y + ")");
            k++;
        }
    }
    try (FileWriter fw = new FileWriter("rand_point.txt")) {
        for (String line : lines) {
            fw.write(line + "\r\n");
        }
    }
    String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
    String pltfile = "rand_point.plt";
    String pltFilePath = new File(pltfile).getAbsolutePath();
    ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
    pb.start();
}
繪圖的 plt 檔案：


set term pngcairo font "AR PL UKai TW"
set output "rand_point.png"
set xlabel "x"
set ylabel "y"
unset key
set xrange [0:205]
set yrange [0:205]
set xtics 0, 40, 200
set ytics 0, 40, 200
set size square

plot "rand_point.txt" using 2:3:1 with labels point pointtype 7



# 隨機生成邊


這邊是我認為最困難的地方，要隨機路段又要確保都有連通，我最後採取了先生成最小生成樹，然後再隨機生成一些線段，我在思考應該使用 Prim演算法 還是 Kruskal演算法 ，最後我選擇了我幾乎沒寫過的 Kruskal演算法 。


static class DSU {
    int[] parent;
    DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}
static void rand_generated_edges() throws IOException {
    int gridSize = 5;
    int n = gridSize * gridSize;
    edges.clear();
    // Step 1: 建構所有合法邊（上下左右）
    List<Edge> allEdges = new ArrayList<>();
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridSize; j++) {
            int idx = i * gridSize + j;
            Point p = points.get(idx);
            if (j < gridSize - 1) { // 右邊
                Point right = points.get(idx + 1);
                allEdges.add(new Edge(p, right));
            }
            if (i < gridSize - 1) { // 下邊
                Point down = points.get(idx + gridSize);
                allEdges.add(new Edge(p, down));
            }
        }
    }
    // Step 2: Kruskal's algorithm -> 最小生成樹，確保連通
    Collections.shuffle(allEdges); // 隨機順序，保證隨機生成樹
    DSU dsu = new DSU(n);
    List<Edge> resultEdges = new ArrayList<>();
    for (Edge e : allEdges) {
        int u = points.indexOf(e.start);
        int v = points.indexOf(e.end);
        if (dsu.find(u) != dsu.find(v)) {
            dsu.union(u, v);
            resultEdges.add(e);
        }
    }
    // Step 3: 剩下的邊以一定機率加入，讓圖更密但仍保連通
    for (Edge e : allEdges) {
        if (!resultEdges.contains(e) && Math.random() < 0.3) {
            resultEdges.add(e);
        }
    }
    edges.addAll(resultEdges);
    // Step 4: 寫入檔案
    try (FileWriter fw = new FileWriter("rand_line.txt")) {
        for (Edge e : edges) {
            fw.write(e.start.x + " " + e.start.y + " " + e.end.x + " " + e.end.y + "\r\n");
        }
    }
    String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
    String pltfile = "rand_line.plt";
    String pltFilePath = new File(pltfile).getAbsolutePath();
    ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
    pb.start();
}
繪圖的 plt 檔案：


set term pngcairo font "AR PL UKai TW"
set output "rand_line.png"

set xlabel "x"
set ylabel "y"
unset key
set xrange [0:205]
set yrange [0:205]
set xtics 0, 40, 200
set ytics 0, 40, 200
set size square

# 畫線：從 rand_line.txt 讀入，每行格式為 x1 y1 x2 y2
plot \
    "rand_line.txt" using 1:2:($3-$1):($4-$2) with vectors nohead lt rgb "gray", \
    "rand_point.txt" using 2:3:1 with labels point pointtype 7 font ",10" offset char 0,0.7



# 隨機生成垃圾在線段上


這邊使用了一些數學，根據隨機的 t  來計算垃圾的相對位置




P = A + t * (B - A) //2D 向量插值公式

 int x = (int) Math.round (e.start.x + t * (e.end.x - e.start.x));

int y = (int)Math.round(e.start.y + t * (e.end.y - e.start.y));




static void rand_generated_trash() throws IOException {
    
    int k = 0;
    for (Edge e : edges){
        if (Math.random() > 0.33) continue;
        double t = Math.random();
        int x = (int)Math.round(e.start.x + t * (e.end.x - e.start.x));
        int y = (int)Math.round(e.start.y + t * (e.end.y - e.start.y));
        Point trashPoint = new Point(k++,x,y,-1,-1); 
        trash.add(trashPoint);
    }
    try (FileWriter fw = new FileWriter("rand_trash.txt")) {
        for (Point p : trash) {
            fw.write(p.x + " " + p.y + "\r\n");
        }
    }
    String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
    String pltfile = "rand_trash.plt";
    String pltFilePath = new File(pltfile).getAbsolutePath();
    ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
    pb.start();
}
繪圖的 plt 檔案：


set term pngcairo font "AR PL UKai TW"
set output "rand_trash.png"

set xlabel "x"
set ylabel "y"
unset key
set xrange [0:205]
set yrange [0:205]
set xtics 0, 40, 200
set ytics 0, 40, 200
set size square

plot \
    "rand_line.txt" using 1:2:($3-$1):($4-$2) with vectors nohead lt rgb "gray", \
    "rand_point.txt" using 2:3:1 with labels point pointtype 7 font ",10" offset char 0,0.7, \
    "rand_trash.txt" using 1:2 with points pointtype 6 lc rgb "red" pointsize 1.2



# 輸入點的 id ，並且計算並劃出可以到的線段範圍


雖然我的強項是圖論，不過真的很少寫 java  還是有點吃力。


// BFS 用的內部類別
static class State {
    Point current;
    double remaining;
    State(Point current, double remaining) {
        this.current = current;
        this.remaining = remaining;
    }
}
static void generated_range_line() throws IOException {
    Scanner scanner = new Scanner(System.in);
    System.out.print("請輸入起點 ID：");
    int id = scanner.nextInt();
    System.out.print("請輸入最大延伸距離：");
    double range = scanner.nextDouble();
    scanner.close();
    // 將有向圖改成無向圖
    List<Edge> originalEdges = new ArrayList<>(edges);
    for (Edge e : originalEdges) {
        edges.add(new Edge(e.end, e.start));
    }
    // 建立鄰接表
    Map<Point, List<Edge>> graph = new HashMap<>();
    for (Edge e : edges) {
        graph.computeIfAbsent(e.start, k -> new ArrayList<>()).add(e);
    }
    // 取得起始點
    Point startPoint = null;
    for (Point p : points) {
        if (p.id == id-1) {
            startPoint = p;
            break;
        }
    }
    if (startPoint == null) {
        System.err.println("起點 ID 不存在！");
        return;
    }
    // BFS 結構
    Set<Point> visited = new HashSet<>();
    Queue<State> queue = new LinkedList<>();
    List<String> outputLines = new ArrayList<>();
    queue.offer(new State(startPoint, range));
    visited.add(startPoint);
    while (!queue.isEmpty()) {
        State state = queue.poll();
        Point current = state.current;
        double remaining = state.remaining;
        if (!graph.containsKey(current)) continue;
        for (Edge edge : graph.get(current)) {
            if (visited.contains(edge.end)) continue;
            double cost = edge.weight;
            if (cost <= remaining) {
                // 可以走完整段
                outputLines.add(edge.start.x + " " + edge.start.y + " " + edge.end.x + " " + edge.end.y);
                queue.offer(new State(edge.end, remaining - cost));
                visited.add(edge.end);
            } else {
                // 無法走完整段，但還是要畫出部分線段
                double t = remaining / cost;
                int midX = (int)Math.round(edge.start.x + t * (edge.end.x - edge.start.x));
                int midY = (int)Math.round(edge.start.y + t * (edge.end.y - edge.start.y));
                outputLines.add(edge.start.x + " " + edge.start.y + " " + midX + " " + midY);
            }
        }
    }
    // 輸出結果到 range_line.txt
    try (FileWriter fw = new FileWriter("range_line.txt")) {
        for (String line : outputLines) {
            fw.write(line + "\r\n");
        }
    }
    String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
    String pltfile = "range_line.plt";
    String pltFilePath = new File(pltfile).getAbsolutePath();
    ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
    pb.start();
}
繪圖的 plt 檔案：


set term pngcairo font "AR PL UKai TW"
set output "range_line.png"

set xlabel "x"
set ylabel "y"
unset key
set xrange [0:205]
set yrange [0:205]
set xtics 0, 40, 200
set ytics 0, 40, 200
set size square

plot \
    "rand_line.txt" using 1:2:($3-$1):($4-$2) with vectors nohead lt rgb "gray", \
    "range_line.txt" using 1:2:($3-$1):($4-$2) with vectors nohead lt rgb "blue" lw 2, \
    "rand_point.txt" using 2:3:1 with labels point pointtype 7 font ",10" offset char 0,0.7, \
    "rand_trash.txt" using 1:2 with points pointtype 6 lc rgb "red" pointsize 1.2



# 總結


# 流程


按照順序查看四張圖，可以一步一步看出程式碼做了什麼：


    

  • rand_point.png
    • 

  • rand_line.png
    • 

  • rand_trash.png
    • 

  • range_line.png
    • 



# 完整程式碼


import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
public class GridRoadSimulator {
    
    static List<Point> points = new ArrayList<>();
    static List<Edge> edges = new ArrayList<>();
    static List<Point> trash = new ArrayList<>();
    // 點的資料結構
    static class Point {
        int id;
        int x;
        int y;
        int xIndex;
        int yIndex;
        
        Point(int id, int x, int y, int xIndex, int yIndex) {
            this.id = id;
            this.x = x;
            this.y = y;
            this.xIndex = xIndex;
            this.yIndex = yIndex;
        }
        // 計算兩點間的歐幾里得距離
        double distanceTo(Point other) {
            return Math.sqrt(Math.pow(this.x - other.x, 2) + Math.pow(this.y - other.y, 2));
        }
    }
    static class Edge {
        Point start;
        Point end;
        double weight;
        Edge(Point start, Point end) {
            this.start = start;
            this.end = end;
            this.weight = start.distanceTo(end);
        }
    }
    static class DSU {
        int[] parent;
        DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
        void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }
    static void rand_generated_point(int xRange, int yRange, int seq) throws IOException {
        List<String> lines = new ArrayList<>();
        int k = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                int q_x = (i * seq + 10) + (int)(Math.random() * (seq - 20));
                int q_y = (j * seq + 10) + (int)(Math.random() * (seq - 20));
                Point p = new Point(k, q_x, q_y, i, j);
                points.add(p);
                lines.add((k+1) + " " + q_x + " " + q_y);
                // System.out.println("(" + q_x + ", " + q_y + ")");
                k++;
            }
        }
        try (FileWriter fw = new FileWriter("rand_point.txt")) {
            for (String line : lines) {
                fw.write(line + "\r\n");
            }
        }
        String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
        String pltfile = "rand_point.plt";
        String pltFilePath = new File(pltfile).getAbsolutePath();
        ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
        pb.start();
    }
     
    static void rand_generated_edges() throws IOException {
        int gridSize = 5;
        int n = gridSize * gridSize;
        edges.clear();
        // Step 1: 建構所有合法邊（上下左右）
        List<Edge> allEdges = new ArrayList<>();
        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                int idx = i * gridSize + j;
                Point p = points.get(idx);
                if (j < gridSize - 1) { // 右邊
                    Point right = points.get(idx + 1);
                    allEdges.add(new Edge(p, right));
                }
                if (i < gridSize - 1) { // 下邊
                    Point down = points.get(idx + gridSize);
                    allEdges.add(new Edge(p, down));
                }
            }
        }
        // Step 2: Kruskal's algorithm -> 最小生成樹，確保連通
        Collections.shuffle(allEdges); // 隨機順序，保證隨機生成樹
        DSU dsu = new DSU(n);
        List<Edge> resultEdges = new ArrayList<>();
        for (Edge e : allEdges) {
            int u = points.indexOf(e.start);
            int v = points.indexOf(e.end);
            if (dsu.find(u) != dsu.find(v)) {
                dsu.union(u, v);
                resultEdges.add(e);
            }
        }
        // Step 3: 剩下的邊以一定機率加入，讓圖更密但仍保連通
        for (Edge e : allEdges) {
            if (!resultEdges.contains(e) && Math.random() < 0.3) {
                resultEdges.add(e);
            }
        }
        edges.addAll(resultEdges);
        // Step 4: 寫入檔案
        try (FileWriter fw = new FileWriter("rand_line.txt")) {
            for (Edge e : edges) {
                fw.write(e.start.x + " " + e.start.y + " " + e.end.x + " " + e.end.y + "\r\n");
            }
        }
        String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
        String pltfile = "rand_line.plt";
        String pltFilePath = new File(pltfile).getAbsolutePath();
        ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
        pb.start();
    }
 
    static void rand_generated_trash() throws IOException {
        
        int k = 0;
        for (Edge e : edges){
            if (Math.random() > 0.33) continue;
            double t = Math.random();
            int x = (int)Math.round(e.start.x + t * (e.end.x - e.start.x));
            int y = (int)Math.round(e.start.y + t * (e.end.y - e.start.y));
            Point trashPoint = new Point(k++,x,y,-1,-1); 
            trash.add(trashPoint);
        }
        try (FileWriter fw = new FileWriter("rand_trash.txt")) {
            for (Point p : trash) {
                fw.write(p.x + " " + p.y + "\r\n");
            }
        }
        String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
        String pltfile = "rand_trash.plt";
        String pltFilePath = new File(pltfile).getAbsolutePath();
        ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
        pb.start();
    }
  
    static void generated_range_line() throws IOException {
        Scanner scanner = new Scanner(System.in);
        System.out.print("請輸入起點 ID：");
        int id = scanner.nextInt();
        System.out.print("請輸入最大延伸距離：");
        double range = scanner.nextDouble();
        scanner.close();
        // 將有向圖改成無向圖
        List<Edge> originalEdges = new ArrayList<>(edges);
        for (Edge e : originalEdges) {
            edges.add(new Edge(e.end, e.start));
        }
        // 建立鄰接表
        Map<Point, List<Edge>> graph = new HashMap<>();
        for (Edge e : edges) {
            graph.computeIfAbsent(e.start, k -> new ArrayList<>()).add(e);
        }
        // 取得起始點
        Point startPoint = null;
        for (Point p : points) {
            if (p.id == id-1) {
                startPoint = p;
                break;
            }
        }
        if (startPoint == null) {
            System.err.println("起點 ID 不存在！");
            return;
        }
        // BFS 結構
        Set<Point> visited = new HashSet<>();
        Queue<State> queue = new LinkedList<>();
        List<String> outputLines = new ArrayList<>();
        queue.offer(new State(startPoint, range));
        visited.add(startPoint);
        while (!queue.isEmpty()) {
            State state = queue.poll();
            Point current = state.current;
            double remaining = state.remaining;
            if (!graph.containsKey(current)) continue;
            for (Edge edge : graph.get(current)) {
                if (visited.contains(edge.end)) continue;
                double cost = edge.weight;
                if (cost <= remaining) {
                    // 可以走完整段
                    outputLines.add(edge.start.x + " " + edge.start.y + " " + edge.end.x + " " + edge.end.y);
                    queue.offer(new State(edge.end, remaining - cost));
                    visited.add(edge.end);
                } else {
                    // 無法走完整段，但還是要畫出部分線段
                    double t = remaining / cost;
                    int midX = (int)Math.round(edge.start.x + t * (edge.end.x - edge.start.x));
                    int midY = (int)Math.round(edge.start.y + t * (edge.end.y - edge.start.y));
                    outputLines.add(edge.start.x + " " + edge.start.y + " " + midX + " " + midY);
                }
            }
        }
        // 輸出結果到 range_line.txt
        try (FileWriter fw = new FileWriter("range_line.txt")) {
            for (String line : outputLines) {
                fw.write(line + "\r\n");
            }
        }
        String gnuplotPath = "C:\\Program Files\\gnuplot\\bin\\gnuplot.exe";
        String pltfile = "range_line.plt";
        String pltFilePath = new File(pltfile).getAbsolutePath();
        ProcessBuilder pb = new ProcessBuilder(gnuplotPath, pltFilePath);
        pb.start();
    }
    // BFS 用的內部類別
    static class State {
        Point current;
        double remaining;
        State(Point current, double remaining) {
            this.current = current;
            this.remaining = remaining;
        }
    }
    public static void main(String[] args) {
        int xRange = 200;
        int yRange = 200;
        int numPoints = 25;
        try {
            rand_generated_point(xRange, yRange, 40);
        } catch (IOException e) {
            System.err.println("An error occurred: " + e.getMessage());
        }
        
        // for (Point p : points) {
        //     System.out.println("Point ID: " + p.id + ", Coordinates: (" + p.x + ", " + p.y + ")");
        // }
        try {
            rand_generated_edges();
        } catch (Exception e) {
            System.err.println("An error occurred while generating edges: " + e.getMessage());
        }
        // for (Edge e : edges) {
        //     System.out.println(e.start.x + " " + e.start.y + " " + e.end.x + " " + e.end.y + "\r\n");
        // }
        try {
            rand_generated_trash();
        } catch (Exception e) {
            System.err.println("An error occurred while generating trash: " + e.getMessage());
        }
        try {
            generated_range_line();
        } catch (Exception e) {
            System.err.println("An error occurred while generating range lines: " + e.getMessage());
        }
    }
}
# 結果圖片


image


# 心得


我其實有發現我有地方與教授的不太一樣，不過我真的太晚開始寫了，希望教授不會發現，不過應該大致一樣，我蠻好奇別人生成邊的地方別人都怎麼寫，那邊先隨機然後判斷再加上邊的寫法感覺會很複雜。