1.1 用到的技術棧

• geotools?
• JTS
• Jgrapht

1.2 實現思路

          // 定義柵格網格參數private static final double CELL_SIZE_DEGREES = 0.005;private static int gridWidth = 0;//格子高度 index + 1private static int gridHeight = 0;//格子寬度// 1. 讀取GeoJSON文件File geoJsonFile = new File("C:/aaa/src/main/resources/" + "map.geojson");SimpleFeatureCollection features = readGeoJson(geoJsonFile);// 2. 獲取邊界范圍Envelope envelope = getEnvelope(features);// 3. 創建柵格網格GridCell[][] grid = createGrid(envelope);// 4. 將GeoJSON要素柵格化rasterizeFeatures(features, grid, envelope);// 5. 構建圖結構SimpleWeightedGraph<GridCell, DefaultWeightedEdge> graph = buildGraph(grid);// 6. 定義起點和終點  new GridCell[gridHeight][gridWidth];GridCell start = grid[2][2]; // 左下角GridCell end = grid[gridHeight -1][gridWidth - 1]; // 右上角// 7. 運行A*算法AStarShortestPath<GridCell, DefaultWeightedEdge> aStar = new AStarShortestPath<>(graph, new ManhattanDistance());GraphPath<GridCell, DefaultWeightedEdge> path = aStar.getPath(start, end);// 8. 輸出結果if (path != null) {System.out.println("找到路徑，長度: " + path.getLength());for (GridCell cell : path.getVertexList()) {System.out.println("[" + cell.centerX + ", " + cell.centerY + "],");}} else {System.out.println("未找到路徑");}}

• 讀取GeoJSON文件

    // 讀取GeoJSON文件private static SimpleFeatureCollection readGeoJson(File file) throws IOException {FeatureJSON fjson = new FeatureJSON();try (FileInputStream in = new FileInputStream(file)) {return (SimpleFeatureCollection) fjson.readFeatureCollection(in);}}

• ?利用圖形邊界創建柵格網格

// 創建柵格網格private static GridCell[][] createGrid(Envelope envelope) {double minLon = envelope.getMinX() - CELL_SIZE_DEGREES * 1.5;double minLat = envelope.getMinY() - CELL_SIZE_DEGREES * 1.5;double maxLon = envelope.getMaxX() + CELL_SIZE_DEGREES * 1.5;double maxLat = envelope.getMaxY() + CELL_SIZE_DEGREES * 1.5;gridWidth = (int) Math.ceil((maxLon - minLon) / CELL_SIZE_DEGREES);gridHeight = (int) Math.ceil((maxLat - minLat) / CELL_SIZE_DEGREES);GridCell[][] grid = new GridCell[gridHeight][gridWidth];for (int y = 0; y < gridHeight; y++) {for (int x = 0; x < gridWidth; x++) {// 3. 計算當前單元格的左下角坐標 (minX, minY)// 3. 計算當前單元格的左下角坐標 (minX, minY)double currentCellMinX = minLon + x * CELL_SIZE_DEGREES;double currentCellMinY = minLat + y * CELL_SIZE_DEGREES;// 4. 計算當前單元格的右上角坐標 (maxX, maxY)double currentCellMaxX = currentCellMinX + CELL_SIZE_DEGREES;double currentCellMaxY = currentCellMinY + CELL_SIZE_DEGREES;// 5. 計算當前單元格的中心點坐標double centerX = currentCellMinX + CELL_SIZE_DEGREES / 2.0;double centerY = currentCellMinY + CELL_SIZE_DEGREES / 2.0;grid[y][x] = new GridCell(x, y,centerX,centerY);}}return grid;}// 網格單元類static class GridCell {final int x, y; // 網格坐標final double centerX, centerY; // 地理坐標boolean isObstacle = false;GridCell(int x, int y, double centerX, double centerY) {this.x = x;this.y = y;this.centerX = centerX;this.centerY = centerY;}@Overridepublic String toString() {return "Cell(" + x + "," + y + ")" + "lonlat(" + centerX + "," + centerY + ")" ;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;GridCell gridCell = (GridCell) o;return x == gridCell.x && y == gridCell.y;}@Overridepublic int hashCode() {return 31 * x + y;}}

• ?柵格化要素

    // 柵格化要素private static void rasterizeFeatures(SimpleFeatureCollection features, GridCell[][] grid, Envelope envelope)throws FactoryException, TransformException {try (SimpleFeatureIterator it = features.features()) {while (it.hasNext()) {SimpleFeature feature = it.next();Geometry geom = (Geometry) feature.getDefaultGeometry();// 檢查每個網格單元是否與幾何圖形相交for (int y = 0; y < gridHeight; y++) {for (int x = 0; x < gridWidth; x++) {GridCell cell = grid[y][x];GeometryFactory geometryFactory = new GeometryFactory();// 定義矩形的邊界 (minX, minY) 到 (maxX, maxY)double minX = cell.centerX - CELL_SIZE_DEGREES / 2;double minY = cell.centerY - CELL_SIZE_DEGREES / 2;double maxX = cell.centerX + CELL_SIZE_DEGREES / 2;double maxY = cell.centerY + CELL_SIZE_DEGREES / 2;// 2. 定義矩形的頂點坐標 (按順時針或逆時針順序，最后一個點與第一個點相同)Coordinate[] coords = new Coordinate[] {new Coordinate(minX, minY), // 左下new Coordinate(maxX, minY), // 右下new Coordinate(maxX, maxY), // 右上new Coordinate(minX, maxY), // 左上new Coordinate(minX, minY)  // 回到左下，閉合環};// 3. (可選，如果你需要更復雜的序列，這里直接用Coordinate數組)// CoordinateSequence coordinateSequence = geometryFactory.getCoordinateSequenceFactory().create(coords);// 4. 創建 LinearRing (外部邊界)LinearRing shell = geometryFactory.createLinearRing(coords);// 5. 創建 Polygon (矩形)// 第二個參數是內孔的 LinearRing 數組，對于簡單矩形，通常是空的Polygon rectangle = geometryFactory.createPolygon(shell, null);//                        Point point = new GeometryFactory().createPoint(new Coordinate(cell.centerX, cell.centerY));if (geom.intersects(rectangle)) {cell.isObstacle = true;}}}}}}

• 構建圖結構

    // 構建圖結構private static SimpleWeightedGraph<GridCell, DefaultWeightedEdge> buildGraph(GridCell[][] grid) {SimpleWeightedGraph<GridCell, DefaultWeightedEdge> graph =new SimpleWeightedGraph<>(DefaultWeightedEdge.class);// 添加所有頂點for (int y = 0; y < gridHeight; y++) {for (int x = 0; x < gridWidth; x++) {if (!grid[y][x].isObstacle) {graph.addVertex(grid[y][x]);}}}// 添加邊（8連通）for (int y = 0; y < gridHeight; y++) {for (int x = 0; x < gridWidth; x++) {if (grid[y][x].isObstacle) continue;// 檢查8個相鄰方向for (int dy = -1; dy <= 1; dy++) {for (int dx = -1; dx <= 1; dx++) {if (dx == 0 && dy == 0) continue; // 跳過自身int nx = x + dx;int ny = y + dy;if (nx >= 0 && nx < gridWidth && ny >= 0 && ny < gridHeight) {if (!grid[ny][nx].isObstacle && graph.containsVertex(grid[ny][nx])) {DefaultWeightedEdge edge = graph.addEdge(grid[y][x], grid[ny][nx]);if (edge != null) {// 對角線距離為√2，直線距離為1double weight = (dx != 0 && dy != 0) ? Math.sqrt(2) : 1.0;graph.setEdgeWeight(edge, weight);}}}}}}}return graph;}

• 實現啟發函數

    public static class ManhattanDistance implements AStarAdmissibleHeuristic<GridCell> {@Overridepublic double getCostEstimate(GridCell source, GridCell target) {double dx = Math.abs(source.x - target.x);double dy = Math.abs(source.y - target.y);return dx + dy;//            double dx = source.centerX - target.centerX;
//            double dy = source.centerY - target.centerY;
//            return Math.sqrt(dx * dx + dy * dy);}}

• 完美實現