# richeyhuang/coverageplanner architecture

> Architecture diagram of the GitHub repository richeyhuang/coverageplanner, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-04-08). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/richeyhuang/coverageplanner
- Repository: https://github.com/richeyhuang/coverageplanner

## Overview

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.

## Diagram (Mermaid)

```mermaid
flowchart TD
    DI["PGM Map Input"]:::input
    IP["Image Preprocessing (OpenCV)"]:::process
    CT["Main Execution Controller"]:::controller
    CG1["CGAL Comm (Header)"]:::comp
    CG2["CGAL Definitions (Header)"]:::comp
    CG3["CGAL Comm (Source)"]:::comp
    PO1["Polygon & Obstacle Extraction (Header)"]:::algo
    PO2["Polygon & Obstacle Extraction (Source)"]:::algo
    BCD1["BCD (Header)"]:::algo
    BCD2["BCD (Source)"]:::algo
    SW1["Sweep Algorithm (Header)"]:::algo
    SW2["Sweep Algorithm (Source)"]:::algo
    VG1["Visibility Graph (Header)"]:::algo
    VG2["Visibility Graph (Source)"]:::algo
    VP1["Visibility Polygon (Header)"]:::algo
    VP2["Visibility Polygon (Source)"]:::algo
    TCD1["TSP Path Planning (Header)"]:::algo
    TCD2["TSP Path Planning (Source)"]:::algo
    RG["Result Generation & Visualization"]:::output

    DI --> IP
    IP --> CT
    CT --> CG1
    CG1 --> CG2
    CG2 --> CG3
    CG3 --> PO1
    PO1 --> PO2
    PO2 --> BCD1
    BCD1 --> BCD2
    BCD2 --> SW1
    SW1 --> SW2
    SW2 --> VG1
    VG1 --> VG2
    VG2 --> VP1
    VP1 --> VP2
    VP2 --> TCD1
    TCD1 --> TCD2
    TCD2 --> RG

    click DI "https://github.com/richeyhuang/coverageplanner/blob/master/data/map.pgm"
    click CT "https://github.com/richeyhuang/coverageplanner/blob/master/src/main.cpp"
    click CG1 "https://github.com/richeyhuang/coverageplanner/blob/master/include/cgal_comm.h"
    click CG2 "https://github.com/richeyhuang/coverageplanner/blob/master/include/cgal_definitions.h"
    click CG3 "https://github.com/richeyhuang/coverageplanner/blob/master/src/cgal_comm.cc"
    click PO1 "https://github.com/richeyhuang/coverageplanner/blob/master/include/decomposition.h"
    click PO2 "https://github.com/richeyhuang/coverageplanner/blob/master/src/decomposition.cc"
    click BCD1 "https://github.com/richeyhuang/coverageplanner/blob/master/include/bcd.h"
    click BCD2 "https://github.com/richeyhuang/coverageplanner/blob/master/src/bcd.cc"
    click SW1 "https://github.com/richeyhuang/coverageplanner/blob/master/include/sweep.h"
    click SW2 "https://github.com/richeyhuang/coverageplanner/blob/master/src/sweep.cc"
    click VG1 "https://github.com/richeyhuang/coverageplanner/blob/master/include/visibility_graph.h"
    click VG2 "https://github.com/richeyhuang/coverageplanner/blob/master/src/visibility_graph.cc"
    click VP1 "https://github.com/richeyhuang/coverageplanner/blob/master/include/visibility_polygon.h"
    click VP2 "https://github.com/richeyhuang/coverageplanner/blob/master/src/visibility_polygon.cc"
    click TCD1 "https://github.com/richeyhuang/coverageplanner/blob/master/include/tcd.h"
    click TCD2 "https://github.com/richeyhuang/coverageplanner/blob/master/src/tcd.cc"
    click RG "https://github.com/richeyhuang/coverageplanner/tree/master/result/"

    classDef input fill:#ADD8E6,stroke:#000,stroke-width:2px
    classDef process fill:#90EE90,stroke:#000,stroke-width:2px
    classDef controller fill:#FFD700,stroke:#000,stroke-width:2px
    classDef comp fill:#DDA0DD,stroke:#000,stroke-width:2px
    classDef algo fill:#FFA07A,stroke:#000,stroke-width:2px
    classDef output fill:#FFB6C1,stroke:#000,stroke-width:2px
```
