M2 — Constructeur glouton

Catalogue

Cotes d'un emplacement

Chaque système a un rectangle d'emprise (entraxe × profondeur) et une largeur d'allée de desserte.

Râtelier perp. Resserré Longitudinal Double étage Arceau

Système	Entraxe	Profondeur	Allée	Vélos/empr.	Emprise
Râtelier perpendiculaire	`0,75 m`	`2,00 m`	`1,80 m`	1	`0,75 × 2,00 m`
Resserré	`0,60 m`	`2,00 m`	`1,80 m`	1	`0,60 × 2,00 m`
Longitudinal sol	`0,75 m`	`2,00 m`	`0,90 m`	1	`0,75 × 2,00 m`
Double étage	`0,60 m`	`2,00 m`	`2,65 m`	2	`0,60 × 2,00 m`
Arceau	`1,00 m`	`2,00 m`	`1,80 m`	2	`1,00 × 2,00 m`

📏

Bande simple = profondeur + allée. Bande double = 2 × profondeur + allée. Ex. : bande double râtelier = 2 × 2,00 + 1,80 = 5,80 m.

Pavage

Zone locale et pavage par bandes

Transformer un polygone quelconque en un problème de pavage 1D, bande par bande.

Rotation vers le repère local

On tourne tous les sommets du polygone par l'angle principal θ. Dans ce repère, les rangées sont horizontales (axe s) et les bandes s'empilent verticalement (axe t).

Bounding box (AABB) du polygone tourné

On calcule le rectangle englobant du polygone dans le repère local : [s_min, s_max] × [t_min, t_max]. C'est l'espace maximal disponible.

Empilement des bandes

À partir de t_min, on empile les bandes de bas en haut. Chaque bande a une épaisseur = profondeur (× 2 si double) + allée. Les bandes ne se chevauchent jamais.

Remplissage de chaque rangée

Pour chaque bande, on remplit la rangée par le glissement leftmost-fit (voir ci-dessous). On ne place une emprise que si ses 4 coins sont à l'intérieur du polygone.

📐

Pourquoi tourner ? — Travailler dans le repère local simplifie énormément le pavage : les bandes sont des tranches horizontales, le test d'inclusion se réduit à vérifier les coins, et les coordonnées sont alignées sur la grille.

Algorithme

Le glissement leftmost-fit

Un algorithme glouton simple mais optimal pour une rangée à système fixé.

Scanner de gauche à droite

On part de s_min et on avance par pas d'entraxe le long de la rangée.

Vérifier l'emprise

Pour chaque position candidate, on vérifie que les 4 coins de l'emprise sont à l'intérieur du polygone et hors des zones interdites (dégagements de porte, poteaux).

Placer ou avancer

Si l'emprise est valide, on la place et on avance de entraxe. Sinon, on avance d'un petit pas (0,01 m) et on réessaie.

Optimal pour une rangée

Ce glissement est optimal pour une rangée à système fixé : il est démontrable qu'aucune autre disposition de gauche à droite ne place plus d'emprises (argument d'échange).

🧮

Complexité — O(L / entraxe × n) par rangée, où L = longueur de la rangée et n = nombre d'arêtes du polygone (coût du ray-casting par coin).

Exploration

Les 8 combinaisons

2 orientations × 2 sens de balayage × 2 côtés de départ = 8 candidats. Le meilleur est retenu.

🔀 Les trois axes de variation

Paramètre	Option A	Option B	Impact
Orientation	`θ`	`θ + π/2`	Rangées parallèles ou perpendiculaires au mur dominant
Sens de balayage	t croissant ↑	t décroissant ↓	Où commence l'empilement des bandes
Côté de départ	s croissant →	s décroissant ←	Où commence le remplissage de chaque rangée

🏆 Sélection du meilleur candidat

Les 8 combinaisons sont évaluées et celle qui produit le maximum de vélos est retenue. En cas d'égalité, on préfère celle qui laisse le plus de surface libre (pour la circulation M4).

best = max(candidates, key=lambda c: (c.total_bikes, c.free_area))

💡

Pourquoi 8 et pas plus ? — 8 combinaisons suffisent pour explorer les symétries naturelles d'un rectangle. Pour des polygones très irréguliers, le NSGA-II (M5) explore des angles libres supplémentaires via son génome.

Stratégie

Mélange de systèmes par bande

Chaque bande peut utiliser un système différent. On garde le meilleur.

📊 Algorithme de sélection par bande +

Pour chaque bande, on teste tous les systèmes autorisés et on garde celui qui place le plus de vélos :

for band in bands: best_system = None best_count = 0 for system in allowed_systems: count = try_fill(band, system) if count > best_count: best_count = count best_system = system band.system = best_system

Hystérésis 5% — Pour éviter les oscillations quand deux systèmes donnent des résultats proches, un nouveau système ne remplace le précédent que s'il apporte au moins 5% de vélos en plus. Cela stabilise les résultats sur les pièces limites.

⚖️

L'hystérésis empêche par exemple le resserré (0,60 m) de « voler » une seule place au râtelier (0,75 m) au prix d'un confort moindre.

🔄 Exemple : pièce 46 en mix perp+longi +

Sur la pièce 46 en mode « mix perpendiculaire + longitudinal » :

Bandes 1-2 : râtelier perpendiculaire (0,75 m) — la zone large permet des rangées longues
Bande 3 : longitudinal (allée 0,90 m) — la zone étroite exploite mieux l'espace réduit
Résultat final : 22 vélos — identique au legacy

Option

Réserve grande dimension (cargo)

🚲

Emplacement cargo — Un emplacement de 2,50 × 1,00 m peut être réservé pour les vélos cargo, longtails ou triporteurs. Il est placé avant le pavage par bandes et exclu de la zone de remplissage. Le constructeur s'adapte automatiquement à l'espace restant.

📐 Dimensions réglementaires

Paramètre	Valeur	Source
Longueur	`2,50 m`	Arrêté du 30 juin 2022, art. 5
Largeur	`1,00 m`	Arrêté du 30 juin 2022, art. 5
Position	Près d'une porte	Facilité de manœuvre

⚠️

Invariant 5 — Si l'utilisateur demande une réserve cargo, l'optimiseur NSGA-II ne peut jamais la supprimer pour gagner de la capacité. C'est un choix utilisateur respecté.

Complexité

Décomposition L/T

Pour les pièces non rectangulaires, on décompose en zones traitables séparément.

📐 Plus grand rectangle inscrit +

On cherche le plus grand rectangle inscrit dans le polygone via un algorithme d'histogramme :

Discrétiser le polygone en une grille binaire (0,05 m de résolution)
Pour chaque ligne, calculer la hauteur maximale de rectangle au-dessus
Algorithme de pile (largest rectangle in histogram) en O(n × m)
Le rectangle trouvé est la « zone principale » du pavage

📊

Complexité O(n × m) où n = lignes et m = colonnes de la grille. Pour une pièce de 10 × 8 m à 0,05 m de résolution : 200 × 160 = 32 000 cellules — instantané.

🧩 Traitement des zones résiduelles +

Après extraction du plus grand rectangle, les zones résiduelles (les « branches » du L ou du T) sont traitées séparément :

Chaque zone résiduelle reçoit son propre pavage par bandes
L'orientation peut différer de la zone principale
Les bandes des zones résiduelles ne chevauchent jamais celles de la zone principale
Le total est la somme des vélos de toutes les zones

Vérification

Validation SAT

🛡️

Théorème des axes séparateurs (SAT) — Pour vérifier qu'aucune paire d'emprises ne se chevauche, on utilise le SAT en repère local. Deux rectangles ne se chevauchent pas s'il existe un axe sur lequel leurs projections sont disjointes. En repère local aligné, cela se réduit à un test AABB (axis-aligned bounding box) — simple comparaison de coordonnées.

✅ Invariant 3 vérifié

Après chaque implantation, le validateur parcourt toutes les paires d'emprises et vérifie :

def check_no_overlap(placements): for i, a in enumerate(placements): for b in placements[i+1:]: assert not aabb_overlap(a, b), \ f"Overlap: {a.id} ∩ {b.id}"

Ce test est exécuté à chaque run du pipeline et fait partie des 53 tests unitaires.

Parité

Golden numbers — parité legacy

Le M2 CPython doit produire exactement les mêmes résultats que le moteur pyRevit legacy.

Legacy (pyRevit)

Pièce 46 râtelier : 22

Pièce 46 mix : 22

Pièce 46 resserré : 29

Pièce 47 râtelier : 10

Pièce 47 mix : 12

Pièce 48 râtelier : 10

Pièce 48 mix : 11

M2 CPython ✓

Pièce 46 râtelier : 22 ✓

Pièce 46 mix : 22 ✓

Pièce 46 resserré : 29 ✓

Pièce 47 râtelier : 10 ✓

Pièce 47 mix : 12 ✓

Pièce 48 râtelier : 10 ✓

Pièce 48 mix : 11 ✓

Pièce	Système	Legacy	M2	Statut
46	Râtelier	22	22	✓ Parité
46	Mix perp+longi	22	22	✓ Parité
46	Resserré	29	29	✓ Parité
47	Râtelier	10	10	✓ Parité
47	Mix perp+longi	12	12	✓ Parité
47	Resserré	14	14	✓ Parité
48	Râtelier	10	10	✓ Parité
48	Mix perp+longi	11	11	✓ Parité
48	Resserré	14	14	✓ Parité

🏆

Invariant 1 vérifié — Δ = 0 sur toutes les pièces et tous les systèmes. Le portage CPython reproduit exactement le comportement du legacy pyRevit. Cette parité est la condition préalable à toute optimisation ultérieure (M3→M5).

Résumé M2

Ce que M2 nous donne

🔧 Constructeur

Pavage par bandes + leftmost-fit. Produit une implantation valide par construction.

🔀 Exploration

8 combinaisons exhaustives. Mélange de systèmes par bande.

🧩 Décomposition

L/T via plus grand rectangle inscrit. Gère les pièces non rectangulaires.

✅ Parité

Golden numbers reproduits à l'identique. Base de confiance pour M3→M5.

➡️

Limites du glouton — Le constructeur M2 est optimal par rangée mais pas globalement : le choix de l'empilement des bandes est heuristique. Le packing exact (M3) résout ce problème par programmation dynamique. Direction → M3 — Packing exact.

← PrécédentM1 — Géométrie Suivant →M3 — Packing exact