This script generates a Minimum Spanning Tree (MST) for a set of grid nodes within a defined polygon boundary. The process involves generating a random polygon, creating grid points, identifying valid nodes, computing the MST, and visualizing the results.
-
Generate Random Polygon
- A random polygon is generated based on a given centroid and parameters.
-
Create Grid Sets
- Set 1: Grids of size (2 \times \text{grid_size}).
- Set 2: Centers of Set 1 grids.
- Set 3: Centers of subdivided grids (half of grid_size).
-
Identify Valid Nodes (Set 4)
- Nodes from Set 2 are validated based on their surrounding grid points.
-
Generate MST
- Using Kruskal's algorithm, the MST is generated for nodes in Set 4.
-
Visualization
- The boundary, grid points, and MST connections are visualized using
matplotlib
.
- The boundary, grid points, and MST connections are visualized using
-
Install Dependencies
pip install numpy matplotlib shapely
-
Run the Script
python mst_grid_path_planning.py
This will display the polygon boundary, grid points, and MST connections as orange lines.