How solalbaudoincs/tipe works
• Core Geometry Module:
– Represented by the file "polygone.py", which defines the essential data structures (Point, Vecteur, Segment, and Polygone) for computational geometry.
• Algorithm Modules:
– "decompositionConvexe.py": Implements the convex decomposition algorithm based on Keil’s method using dynamic programming.
– "decompositionEtoile.py": Contains the analogous algorithm for decomposing into “polygones étoilés.”
– Additionally, "decomposition_convexe_naive.py" might be noted as an alternate (or baseline) implementation.
• Utility Functions:
– "helpers.py": Contains generic utility functions (example: a dichotomic search function) to support various computational processes.
• Visualization and Debug Components:
– "demo.py": A graphical application interface that allows interactive experimentation with the decomposition algorithms.
• Data Analysis and Notebooks:
– "src/notebooks": Contains Jupyter notebooks (e.g., "Analyse plan de voirie paris.ipynb" and debug notebooks) that demonstrate how the algorithms are applied to real-world data (such as the Paris road plan in "plan-de-voirie-chaussees-paris.geojson").
• External Documentation and Presentation Materials:
– Documents such as "paper.pdf", "MCOT.pdf", and "PPT_TIPE.pdf" provide background, theoretical basis, and presentation context for the project.
Out the Relationships and Data Flows
• Data Flow and Module Interaction:
– User Interaction: The user starts by interacting with the demo interface (demo.py), which serves as the front end.
– Input → Data Structures: The demo collects or simulates polygon data; these are translated into geometric objects via the classes from "polygone.py."
– Algorithm Invocation: The geometric objects are then processed by calls to the decomposition algorithms (either convex in "decompositionConvexe.py" or étoilé in "decompositionEtoile.py"). Note the dynamic programming approaches and their potential computational complexity (e.g., O(n^7)).
– Visualization: Once the computation is complete, the results are passed back to the visualization module ("affichage.py") to display the resulting decomposition.
– Analysis: Separately, Jupyter notebooks connect to the same underlying modules to process external geospatial data (from the geojson file) and to analyze algorithm performance.
Architectural Patterns and Design Principles
• Modularity and Separation of Concerns: The project is clearly segmented into geometric modeling, algorithmic processing, and visualization with distinct modules for each.
• Reusability: Core components (e.g., the geometry classes) are reused across both algorithm implementations and visualization routines.
• Extensibility: The structured layout (with notebooks for analysis and a demo application) allows new algorithms or additional visualization features to be integrated later.
– User/Analyst at one end interfacing with the Demo Application and Jupyter Notebooks.
– Core System Modules (split into “Geometry”, “Algorithms”, and “Visualization”) in the center.
– External Data Sources and Documentation (geojson file, PDFs) connected appropriately.
– Detailing the internal structure within the “Algorithms” block, listing out convex and étoilé decomposition as separate but related modules.
– Including the supporting utility functions available in "helpers.py."
– Demonstrating the directory layout where relevant if it helps show organization.
– Data flow (input → processing → output)
– Module dependencies (e.g., The demo application depends on both the algorithm and visualization components.)
Final Advice
• Be as detailed as possible: Do not shy away from showing even minor modules such as “affichage.py” and “helpers.py” to give a complete picture.
• Relevant performance annotations (e.g., run-time expectations for decomposition algorithms) where appropriate.