
------------------------------------------------------------
Directory Structure
------------------------------------------------------------

Watchmen_Route_Problem/
│
├── LakeCoordinatesCreator/
│   ├── cache/
│   ├── .gitignore
│   ├── LakeGeorgeVolusiaCountyFloridaUnitedStates.txt
│   ├── LakeUrmiaEastAzerbaijanProvinceIran.txt
│   ├── LakeUrmiaEastAzerbaijanProvinceIran_2.txt
│   ├── PakwashaLakeEarFallsTownshipKenoraOntarioCanada.txt
│   └── main.py
│
│   Description:
│   This directory is responsible for generating polygon input files that
│   represent real-world lakes. The main.py script queries OpenStreetMap data
│   using OSMnx, retrieves the lake boundary geometry, and converts it into
│   a polygon-with-holes text format compatible with the Watchman Route system.
│
│   main.py functionality:
│   - Prompts the user for a lake name and location.
│   - Uses OSMnx to geocode the lake into a GeoDataFrame.
│   - Ensures the retrieved geometry is a single Polygon (not MultiPolygon).
│   - Projects the geometry to a planar coordinate system.
│   - Extracts the outer boundary and any interior holes (islands).
│   - Scales and rounds coordinates for numerical stability.
│   - Outputs a formatted text file describing the polygon and its holes.
│
│   Required libraries:
│   - osmnx
│   - geopandas
│   - shapely
│   - matplotlib
│
├── TrapezoidPathCreatorAndVisualizer/
│   ├── __pycache__/
│   ├── .gitignore
│   ├── decompositionP_WITH_HOLESnn_01.txt
│   ├── disjoint_set.py
│   ├── geometry_classes.py
│   ├── main.py
│   ├── output_test07_01.txt
│   ├── output_test08_01.txt
│   ├── output_test14_01.txt
│   ├── tree_classes.py
│   ├── tree_splitting.py
│   └── visualize.py
│
│   Description:
│   This directory contains the core implementation of the Watchman Route
│   solution. It processes trapezoidal decompositions, builds a weighted graph,
│   constructs a Minimum Spanning Tree (MST), optionally splits the MST into
│   k balanced patrol routes, and visualizes the results.
│
│   Key files:
│   - geometry_classes.py:
│     Defines geometric structures such as trapezoids, edges, and midpoints,
│     and supports hole-aware geometry processing.
│
│   - disjoint_set.py:
│     Implements Union-Find with path compression for Kruskal’s MST algorithm.
│
│   - tree_classes.py:
│     Defines tree and node data structures for representing the MST.
│
│   - tree_splitting.py:
│     Implements optimal MST partitioning into k subtrees using feasibility
│     checks and binary search to minimize the maximum route length.
│
│   - visualize.py:
│     Uses Matplotlib to render the lake boundary, obstacles, trapezoids,
│     graph edges, MST, and multi-boat patrol routes.
│
│   - main.py:
│     The primary execution script that ties together geometry parsing,
│     graph construction, MST creation, subtree splitting, and visualization.
│
├── CGAL_Trapezoid_Partitioning_2.exe
│
│   Description:
│   External executable used to generate trapezoidal decompositions from polygon
│   input files. Produces trapezoid data compatible with the Python pipeline.
│
├── get_file.py
│
│   Description:
│   Utility script used to assist with file selection and input handling
│   for decomposition and processing steps.
│
├── start.bat
│
│   Description:
│   Windows batch script that launches the project with predefined settings
│   for ease of execution.
│
├── placeholder
│
│   Description:
│   Placeholder file used to preserve directory structure in version control.
│
└── README.txt


------------------------------------------------------------
Deployable Code
------------------------------------------------------------

The deployable components of this project include:
- All Python scripts in:
  - LakeCoordinatesCreator/
  - TrapezoidPathCreatorAndVisualizer/
- CGAL_Trapezoid_Partitioning_2.exe
- start.bat for Windows execution

No web server or database is required.

------------------------------------------------------------
Installation Guide
------------------------------------------------------------

Requirements:
- Python 3.9 or newer
- Windows OS (for CGAL executable)
- Required Python libraries:
  - matplotlib
  - numpy
  - osmnx
  - geopandas
  - shapely

Installation Steps:
1. Install Python 3 and ensure it is added to PATH.
2. Install required libraries:
       pip install matplotlib numpy osmnx geopandas shapely
3. Place the Watchmen_Route_Problem directory on your local machine.
4. (Optional) Generate a lake polygon using:
       LakeCoordinatesCreator/main.py
5. Generate trapezoid decomposition using:
       CGAL_Trapezoid_Partitioning_2.exe
6. Run the system:
       python TrapezoidPathCreatorAndVisualizer/main.py
   or double-click:
       start.bat

------------------------------------------------------------
User Manual
------------------------------------------------------------

Usage Steps:
1. Enter a lake name in LakeCoordinatesCreator/main.py to generate a polygon file.
2. Generate trapezoidal decomposition using the CGAL executable.
3. Run the main processing script.
4. Enter the desired number of patrol boats (k).
5. Inspect the visualization:
   - Lake boundary and holes
   - Trapezoids
   - Minimum Spanning Tree
   - Split patrol routes
6. Review output_test*.txt files for numerical metrics.

------------------------------------------------------------
Security & Privacy
------------------------------------------------------------

- All computation is performed locally.
- No personal or sensitive data is stored.
- No network communication occurs during routing.

------------------------------------------------------------
License
------------------------------------------------------------

Provided for academic and research use.
MIT-style licensing assumptions apply unless otherwise specified.

------------------------------------------------------------
End of README.txt
------------------------------------------------------------
