Skip to content

roboticsmick/ASV_STC_PATH_PLANNING

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 

Repository files navigation

ASV_MST_PATH_PLANNING

image

MST Grid Path Planning

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.

Overview

  1. Generate Random Polygon

    • A random polygon is generated based on a given centroid and parameters.
  2. 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).
  3. Identify Valid Nodes (Set 4)

    • Nodes from Set 2 are validated based on their surrounding grid points.
  4. Generate MST

    • Using Kruskal's algorithm, the MST is generated for nodes in Set 4.
  5. Visualization

    • The boundary, grid points, and MST connections are visualized using matplotlib.

Usage

  1. Install Dependencies

    pip install numpy matplotlib shapely
  2. Run the Script

    python mst_grid_path_planning.py

This will display the polygon boundary, grid points, and MST connections as orange lines.

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages