M1 — Géométrie — BikeOptim

Aire

Aire d'un polygone — formule du lacet (shoelace)

Calculer l'aire d'un polygone quelconque à partir de ses sommets, sans trigonométrie.

A = ½ · |Σ_i=0…n−1 (x_i · y_i+1 − x_i+1 · y_i)|

🔢 Comment ça marche

On parcourt les sommets dans l'ordre. Pour chaque arête (xᵢ, yᵢ) → (xᵢ₊₁, yᵢ₊₁), on calcule le produit croisé des coordonnées consécutives. La somme de ces produits donne le double de l'aire signée.

Signe positif → sommets dans le sens trigonométrique (anti-horaire)
Signe négatif → sommets dans le sens horaire
La valeur absolue donne l'aire indépendamment de l'orientation

🐍 Implémentation Python (stdlib) +

def polygon_area(vertices: list[tuple[float, float]]) -> float: """Shoelace formula — O(n), stdlib pur.""" n = len(vertices) area = 0.0 for i in range(n): j = (i + 1) % n area += vertices[i][0] * vertices[j][1] area -= vertices[j][0] * vertices[i][1] return abs(area) / 2.0

Complexité O(n) où n = nombre de sommets. Aucune allocation mémoire.

✅

Vérifié — Le test test_polygon_area compare le résultat à Shapely sur les 4 pièces de référence. Écart maximal : 10⁻¹⁰ m².

Inclusion

Point dans un polygone — ray casting

Le test fondamental du moteur : est-ce qu'une emprise est « dedans » ?

🎯 Principe

Lancer un rayon horizontal depuis le point vers l'infini (+∞). Compter le nombre d'intersections avec les arêtes du polygone.

Parité impaire → intérieur
Parité paire → extérieur

⚡ Performance

Coût O(n) par requête, où n = nombre d'arêtes. Le constructeur appelle cette fonction des centaines de fois par implantation.

Mémoïsé — les résultats sont cachés pour les positions déjà testées dans une même exécution du constructeur.

🐍 Implémentation avec traitement des cas limites +

def point_in_polygon(px, py, vertices): """Ray-casting — rayon horizontal vers +∞.""" n = len(vertices) inside = False j = n - 1 for i in range(n): xi, yi = vertices[i] xj, yj = vertices[j] if ((yi > py) != (yj > py)) and \ (px < (xj - xi) * (py - yi) / (yj - yi) + xi): inside = not inside j = i return inside

Les cas limites (point exactement sur une arête, sommet partagé) sont gérés par la condition stricte > plutôt que >=.

📖

Référence — Algorithme classique de Jordan. Voir Computational Geometry: Algorithms and Applications, de Berg et al., chapitre 1.

Orientation

Angle principal

L'angle qui aligne les rangées sur le « mur dominant » de la pièce.

θ = atan2(Δy, Δx) de l'arête la plus longue, modulo π

🧭 Pourquoi l'arête la plus longue ?

L'arête la plus longue correspond en général au mur principal de la pièce. Aligner les rangées dessus maximise le nombre d'emprises sur la longueur disponible. Le modulo π assure que les deux directions d'un même mur sont équivalentes.

🔄 Deux orientations testées

Le constructeur teste systématiquement θ et θ + π/2 (les rangées perpendiculaires au mur dominant). C'est un des « 8 combinaisons » du M2.

angles = [theta, theta + math.pi / 2] for angle in angles: # tester les 4 combinaisons (sens × côté) pour chaque angle ...

💡

Cas pathologique — Pour un polygone régulier (ex. hexagone), toutes les arêtes ont la même longueur. L'angle choisi est alors celui de la première arête trouvée. Cela n'a pas d'impact car le NSGA-II explore de toute façon les deux orientations.

Portes

Géométrie des portes

Comment calculer le dégagement de porte et le nœud d'accès — en 4 étapes.

Direction de la paroi

La porte est située sur une arête du polygone. On projette le centre de la porte sur l'arête la plus proche pour obtenir le vecteur tangent à la paroi.

Direction intérieure

Perpendiculaire au vecteur tangent, orientée vers le centroïde du polygone. C'est la direction « vers l'intérieur de la pièce ».

Rectangle de dégagement

Rectangle de 1,20 m de profondeur devant la porte, centré sur l'ouverture. Aucune emprise ne peut être placée dans cette zone.

Nœud d'accès

Point d'ancrage pour le graphe de circulation (M4). Position = centre de la porte + 0,15 m vers l'intérieur (un pas de grille).

🐍 Calcul du nœud d'accès +

# centre de la porte cx, cy = door.position # direction intérieure (normalisée) dx, dy = inward_normal(door, polygon) # nœud d'accès : 0.15 m vers l'intérieur access_x = cx + 0.15 * dx access_y = cy + 0.15 * dy

Le décalage de 0,15 m correspond à un pas de la grille fine du module de circulation (M4). Il garantit que le nœud est bien à l'intérieur du polygone et sur un nœud de la grille.

🚪

Multi-portes — Une pièce peut avoir plusieurs portes. Le module M4 (circulation) calcule des couloirs depuis chaque porte indépendamment, puis mutualise les passages pour minimiser l'espace dédié à la circulation.

Architecture

shapely vs stdlib

Une frontière de dépendance claire et volontaire.

📦

Règle d'architecture — Le socle (io, core.geometry) est stdlib pur — aucun import de shapely ni de numpy. Ces dépendances ne sont autorisées que dans room_model.py et viz/.

Module	Dépendances	Justification
core.geometry	`math` (stdlib)	Portabilité maximale, exécutable dans pyRevit (IronPython)
io.loader	`json` (stdlib)	Chargement JSON sans dépendance tierce
room_model	`shapely`	Opérations booléennes complexes (intersection, buffer) pour la décomposition L/T
viz/	`matplotlib`, `numpy`	Rendu PNG des implantations — optionnel en production
nsga2	`random` (stdlib)	Déterminisme via `Random(seed)` — pas de numpy.random

⚠️

Pourquoi pas Shapely partout ? — Le moteur legacy tournait dans pyRevit (IronPython 2.7) qui n'a pas accès à Shapely. Le stdlib pur permet de valider la parité M2 dans le même environnement que le legacy.

Résumé M1

Ce que M1 nous donne

📐 Aire

Shoelace formula. Sert à estimer la capacité théorique et à valider les polygones.

📍 Inclusion

Ray-casting. Vérifie que chaque emprise est bien à l'intérieur de la pièce.

🧭 Orientation

Angle principal. Aligne les rangées sur le mur dominant.

🚪 Portes

Dégagement + nœud d'accès. Points d'ancrage pour M4.

➡️

Et ensuite ? — Ces fondations sont consommées par le constructeur glouton (M2) qui les utilise pour pavez la pièce de rangées de vélos. Direction → M2 — Le constructeur.

← PrécédentLe problème Suivant →M2 — Constructeur