Polyhedron Coverage

Tessellated drone coverage examples for 2D graphs and 3D cuboid spaces.

The core idea is simple: tessellation cells are coverage units. Drones patrol inside one cell, then move to another cell, until the tessellated space has been covered. The visualizations show inside-cell coverage motion rather than long cross-zone routes.

Highlights

• 2D pointy-top hexagonal tessellation for positioned NetworkX graphs.
• Bundled Santiago bus graph example with 11,720 stops and 15,087 edges.
• 3D cuboid tessellation example with a floor-center charging base.
• Round-robin drone allocation across tessellation cells.
• 2D and 3D logistics simulations with carrier vehicles and deployable drone swarms.
• 2D and 3D Stackelberg security games with Greedy, Random, MaxMin, and RL defenders.
• Static PNG and animated GIF outputs for public reports and READMEs.
• Reproducible examples, tests, CI, and data provenance notes.

Gallery

2D Santiago Graph

3D Cube Space

3D Security Patrol

3D Logistics

Install

Python 3.10 or newer is recommended.

python3 -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip
python -m pip install -e ".[dev]"

For a minimal script-only setup, this also works:

python3 -m pip install -r requirements.txt

Quick Start

Generate the Santiago 2D hex tessellation examples:

polyhedron-santiago-2d --targets 50 100 250 --drones 3 --make-gif

Generate the 3D cube example:

polyhedron-cube-3d --divisions 4 4 3 --drones 3 --make-gif

Run the 3D security game:

polyhedron-security-3d --divisions 3 2 1 --days 60 --rl-episodes 500 --make-gif

Run the 3D logistics simulation:

polyhedron-logistics-3d --targets 4 --divisions 3 3 2 --strategy all --make-gif

By default, generated JSON and figures are written to output/, which is ignored by Git. The Santiago and cube examples remain runnable under examples/; package CLIs are the official entrypoints for coverage, security, and logistics workflows.

Python API

2D graph tessellation:

from polyhedron_coverage.coverage2d.santiago import load_santiago_graph
from polyhedron_coverage.coverage2d.hex_tessellation import tessellate_graph
from polyhedron_coverage.coverage2d.patrol_allocation import allocate_hexagons, build_patrol_routes

graph = load_santiago_graph()
tessellation = tessellate_graph(graph, target_hexagons=100, pos_attrs=("lon", "lat"))
allocations = allocate_hexagons(tessellation["hexagons"], num_drones=3)
routes = build_patrol_routes(tessellation["hexagons"], allocations)

3D cuboid tessellation:

from polyhedron_coverage.coverage3d.cube_tessellation import (
    allocate_cells,
    build_cube_patrol_routes,
    create_cube_tessellation,
)

tessellation = create_cube_tessellation(
    bounds=((0, 0, 0), (12, 12, 8)),
    divisions=(4, 4, 3),
)
allocations = allocate_cells(tessellation["cells"], num_drones=3)
routes = build_cube_patrol_routes(tessellation, allocations)

3D security game:

from polyhedron_coverage.coverage3d.cube_tessellation import create_cube_tessellation
from polyhedron_coverage.security.game_env_3d import SecurityGame3D
from polyhedron_coverage.security.strategies.maximin_defender import MaximinDefender

tessellation = create_cube_tessellation(divisions=(3, 2, 1))
game = SecurityGame3D(tessellation=tessellation, time_budget=42.0)
defender = MaximinDefender()
defender.fit(game)
schedule = defender.select_schedule(game)
coverage = game.execute_schedule(schedule)

Data

The bundled file src/polyhedron_coverage/data/santiago_bus_graph.json is a compact Santiago bus-stop graph used for the 2D example. It contains graph topology and stop coordinates, not passenger-level data.

See DATA.md for provenance and the reproduction command. To rebuild the JSON from the source workbook when available:

python tools/extract_santiago_graph.py /path/to/Data\ Grafo.xlsx src/polyhedron_coverage/data/santiago_bus_graph.json

Project Structure

src/polyhedron_coverage/  Main Python package namespace
  coverage2d/             2D planar coverage algorithms and tessellations
  coverage3d/             3D volumetric coverage algorithms and cuboid tessellations
  security/               2D/3D Stackelberg security models and defender strategies
  logistics/              2D/3D carrier routing and drone-swarm logistics simulations
  cli/                    Console script implementations
  data/                   Bundled Santiago graph data
examples/                 Public runnable example wrappers
tests/                    Unit and public smoke tests
docs/                     Domain notes and README-ready generated figures
tools/                    Data extraction and maintenance helpers

Tests

Run the local release check:

python3 -m unittest discover
python3 examples/santiago_2d.py --targets 20 --drones 2 --no-gif --output-dir /tmp/santiago_smoke
python3 examples/cube_3d.py --divisions 3 3 2 --drones 3 --no-gif --output-dir /tmp/cube_smoke
python3 -m polyhedron_coverage.cli.security_3d --divisions 2 2 1 --days 4 --rl-episodes 2 --no-gif --output-dir /tmp/security3d_smoke
python3 -m polyhedron_coverage.cli.logistics_3d --targets 2 --divisions 2 2 1 --strategy greedy --max-ticks 120 --no-gif --output-dir /tmp/logistics3d_smoke
python3 -m polyhedron_coverage.cli.santiago_2d --targets 20 --drones 2 --no-gif --output-dir /tmp/santiago_module_smoke

The test suite checks cell assignment, adjacency symmetry, allocation coverage, inside-cell patrol waypoints, bundled Santiago loading, 2D and 3D CLI smoke examples, logistics/security behavior, and README asset validity.

Regenerating README Assets

polyhedron-santiago-2d \
  --targets 50 100 250 \
  --drones 3 \
  --make-gif \
  --asset-dir docs/assets/santiago

polyhedron-cube-3d \
  --divisions 4 4 3 \
  --drones 3 \
  --make-gif \
  --asset-dir docs/assets/cube3d

polyhedron-security-3d \
  --divisions 2 2 1 \
  --days 10 \
  --rl-episodes 10 \
  --make-gif \
  --asset-dir docs/assets/security3d \
  --output-dir /tmp/polyhedron_security3d_assets

polyhedron-logistics-3d \
  --targets 2 \
  --divisions 2 2 1 \
  --strategy greedy \
  --max-ticks 120 \
  --make-gif \
  --asset-dir docs/assets/logistics3d \
  --output-dir /tmp/polyhedron_logistics3d_assets

License

MIT. See LICENSE.