How richeyhuang/coverageplanner works
This project – CoveragePlanner – is a coverage path planning tool that takes in a map in PGM format and uses computational geometry, image processing, and optimization techniques for generating a coverage path (for example, for a cleaning robot or similar application). The project leverages dependencies like CGAL for computational geometry, OpenCV for image processing, and Eigen for matrix operations.
Main Components
• Input/Preprocessing:
• Data Input: The “data” folder holds the PGM map files.
• Image Processing: OpenCV is likely used to process the input map (e.g., to detect polygons, obstacles, and boundaries).
• Core Algorithm Modules:
• Polygon and Obstacle Extraction: Components that extract the polygon boundary and obstacles from the map.
• Decomposition Modules: Files like “decomposition.h/cc” and “bcd.h/cc” indicate boustrophedon cellular decomposition, where the workspace is segmented into navigable cells.
• Visibility Graph and Sweep Algorithms: The headers “visibility_graph.h/cc” and “sweep.h/cc” point to generating connectivity graphs and planning sweep paths inside cells.
• TSP Path Planning: “tcd.h/cc” suggests that after decomposing the space, the system uses a traveling salesman (TSP) approach to compute an optimal path through the cells.
• Additional geometric computations: Provided by modules interfacing with CGAL (cgal_comm.h/cc, cgal_definitions.h) to handle robust geometric operations.
• Output:
• Result Generation: The “result” folder holds output images (e.g., planning visualization and decomposition results) that demonstrate the coverage path planned.
• Main Execution:
• The “src/main.cpp” file is the entry point that integrates all these components into a final pipeline.
• Input Layer: “Data Input & Preprocessing” (map loading, image processing via OpenCV).
• Processing Layer:
• Geometric Computation Block – using CGAL and Eigen (core functions in cgal_comm, cgal_definitions).
• Decomposition & Planning Algorithms Block – split into submodules:
▪ Boustrophedon Cellular Decomposition (bcd)
▪ Sweep Algorithm (sweep)
▪ Visibility Graph Construction (visibility_graph, visibility_polygon)
▪ TSP based path planning (tcd)
• Output Layer: “Result Generation & Visualization” (storing images in the result folder).
• Geometric computations feed into the decomposition/polygon extraction phase.
• The resulting cells or navigable areas then are input into the path planning (TSP solver).
• Finally, the computed path is rendered and displayed as output.
c. Technology Dependencies:
▪ CGAL: In geometric computation and algorithm modules.
▪ OpenCV: In the preprocessing and result visualization steps.
▪ Eigen: For any numerical or matrix computation supporting CGAL operations.
Architectural Patterns & Design Principles
• Modularity: Each algorithm (decomposition, sweep, visibility graph, and TSP) operates as independent modules/components that integrate in the main execution.
• Data Flow Orientation: Emphasize a linear pipeline – data flows from input through processing to output.
• External Dependencies: Clearly indicate where external libraries (CGAL, OpenCV, Eigen) are used, as they are critical for computational geometry and image processing.