CyrilLeblanc/gresit

Fork 0

Dispersion physique des arrêts co-localisés (force-directed) #4

New issue

Closed

opened 2026-06-22 12:16:25 +02:00 by CyrilLeblanc · 0 comments

CyrilLeblanc commented

2026-06-22 12:16:25 +02:00

Owner

Dispersion physique des arrêts co-localisés (force-directed)

Contexte

Plusieurs poteaux d'arrêt peuvent partager exactement la même position GPS (même cluster physique). Actuellement, l'affichage place un point central et dispose les arrêts en cercle uniforme autour du premier. Cette approche montre ses limites quand le cluster contient beaucoup d'arrêts : les marqueurs se chevauchent, l'espacement est arbitraire et le rendu n'est pas naturel.

L'objectif est de remplacer cette logique par une simulation de forces physiques qui calcule dynamiquement une position d'affichage optimale pour chaque arrêt en fonction du niveau de zoom.

Feature

Implémenter un système de dispersion basé sur un algorithme force-directed pour les clusters d'arrêts co-localisés sur la carte MapLibre.

Comportement attendu

Zoom faible (< seuil) → les marqueurs sont masqués (inutiles à petite échelle)
Zoom intermédiaire → les marqueurs apparaissent groupés, légèrement espacés
Zoom fort → les marqueurs se dispersent naturellement autour de leur position GPS réelle, avec un espacement lisible quel que soit le nombre d'arrêts
Transition zoom/dézoom → la dispersion est animée (les marqueurs glissent vers leur nouvelle position)

Résultat visuel

Chaque arrêt est contraint dans un rayon maximum autour de son ancre GPS, radius proportionnel au zoom. La simulation converge vers un état d'équilibre où aucun marqueur ne se chevauche.

Contraintes techniques

Plateforme

Android natif, Kotlin
MapLibre Android SDK
Mise à jour des positions via GeoJSON source (geoJsonSource.setGeoJson(...))

Simulation

Travailler en coordonnées écran (pixels) pendant la simulation
Reconvertir en LatLng pour mettre à jour MapLibre à chaque frame
Recalculer la projection screen ↔ geo à chaque changement de caméra (zoom, pan)
Freezer la vue pendant la simulation ou absorber les changements de projection

Performance

La simulation doit converger en 20–30 ticks max (pas de boucle infinie)
Tourner sur un thread séparé (coroutine ou HandlerThread) pour ne pas bloquer l'UI
Complexité O(n²) acceptable pour des clusters de taille raisonnable (< ~50 arrêts)

Zoom

En dessous d'un seuil de zoom configurable → les marqueurs du cluster sont cachés (via filtre MapLibre ou visibilité de layer)

Le rayon de dispersion max (maxSpread) est une fonction continue du zoom, ex :

zoom 14–16 →  spread 0px → 20px
zoom 16–18 →  spread 20px → 80px
zoom > 18  →  spread 120px

Recalcul déclenché à chaque OnCameraChangeListener si Δzoom > 0.1

Design de l'algorithme

Forces appliquées

Force	Portée	Description
Répulsion intra-cluster	Entre arrêts du même cluster	Chaque paire de nœuds se repousse (inversement proportionnel à dist²)
Répulsion inter-clusters	Entre clusters distincts	Les groupes d'arrêts se repoussent mutuellement pour ne pas se superposer — appliquée sur le centroïde de chaque cluster
Ancrage	Par arrêt	Chaque nœud est rappelé vers sa position GPS réelle (ressort élastique)
Amortissement	Global	`velocity *= 0.85` à chaque tick pour converger
Contrainte rayon	Par arrêt	Le nœud est clampé dans un cercle de `maxSpread` px autour de son ancre

Répulsion inter-clusters — détail

Les clusters sont des entités indépendantes qui peuvent partager la même zone à l'écran. Sans répulsion inter-clusters, un groupe d'arrêts peut passer sous un autre groupe après dispersion.

La force est calculée entre les centroïdes écran de chaque paire de clusters
Elle est propagée à tous les nœuds du cluster (translation rigide du groupe)
L'ancrage de chaque nœud vers sa position GPS compense et empêche une dérive infinie
Recalculée à chaque tick et à chaque changement de zoom/pan

Pas de force de lien (ressort entre nœuds) — inutile ici, pas de topologie de graphe.

Architecture suggérée

ClusterSpreadSimulation.kt
  └── tick() — calcule un pas de simulation
  └── updateMaxSpread(px) — met à jour le rayon selon le zoom
  └── restart() — relance la convergence

StopClusterManager.kt
  └── détecte les clusters (arrêts co-localisés)
  └── écoute OnCameraChangeListener
  └── déclenche simulation + anime via ValueAnimator / coroutine

MapFragment / MapActivity
  └── geoJsonSource mis à jour à chaque frame d'animation
  └── layer avec filtre de visibilité selon zoom

État actuel (à remplacer)

Un point est placé au centroïde du cluster
Les arrêts sont disposés en cercle uniforme autour du premier
Pas d'animation
Rendu dégradé quand le nombre d'arrêts augmente (chevauchements, cercle trop grand ou trop petit)

Critères d'acceptance

Les arrêts d'un cluster ne se chevauchent plus à fort zoom
Deux clusters proches ne se superposent pas — la répulsion inter-clusters les écarte mutuellement
La répulsion inter-clusters se recalcule au zoom/pan comme la dispersion intra-cluster
La dispersion est proportionnelle au zoom (plus on zoome, plus ils s'écartent)
En dessous du seuil de zoom, les marqueurs sont masqués
La transition est animée lors d'un zoom/dézoom
La simulation converge sans freezer l'UI
Le comportement est correct après un pan (repositionnement de la projection)

Références

Algorithme force-directed : Wikipedia — Force-directed graph drawing
Optimisation Barnes-Hut (si clusters > 50 nœuds) : quadtree O(n log n)
MapLibre Android SDK — GeoJSON sources & layer filters

# Dispersion physique des arrêts co-localisés (force-directed) ## Contexte Plusieurs poteaux d'arrêt peuvent partager exactement la même position GPS (même cluster physique). Actuellement, l'affichage place un point central et dispose les arrêts en cercle uniforme autour du premier. Cette approche montre ses limites quand le cluster contient beaucoup d'arrêts : les marqueurs se chevauchent, l'espacement est arbitraire et le rendu n'est pas naturel. L'objectif est de remplacer cette logique par une **simulation de forces physiques** qui calcule dynamiquement une position d'affichage optimale pour chaque arrêt en fonction du niveau de zoom. --- ## Feature Implémenter un système de dispersion basé sur un algorithme force-directed pour les clusters d'arrêts co-localisés sur la carte MapLibre. ### Comportement attendu - **Zoom faible** (`< seuil`) → les marqueurs sont masqués (inutiles à petite échelle) - **Zoom intermédiaire** → les marqueurs apparaissent groupés, légèrement espacés - **Zoom fort** → les marqueurs se dispersent naturellement autour de leur position GPS réelle, avec un espacement lisible quel que soit le nombre d'arrêts - **Transition zoom/dézoom** → la dispersion est animée (les marqueurs glissent vers leur nouvelle position) ### Résultat visuel Chaque arrêt est contraint dans un rayon maximum autour de son ancre GPS, radius proportionnel au zoom. La simulation converge vers un état d'équilibre où aucun marqueur ne se chevauche. --- ## Contraintes techniques ### Plateforme - Android natif, Kotlin - MapLibre Android SDK - Mise à jour des positions via **GeoJSON source** (`geoJsonSource.setGeoJson(...)`) ### Simulation - Travailler en **coordonnées écran (pixels)** pendant la simulation - Reconvertir en `LatLng` pour mettre à jour MapLibre à chaque frame - Recalculer la projection screen ↔ geo à chaque changement de caméra (zoom, pan) - **Freezer la vue** pendant la simulation ou absorber les changements de projection ### Performance - La simulation doit converger en **20–30 ticks max** (pas de boucle infinie) - Tourner sur un **thread séparé** (coroutine ou `HandlerThread`) pour ne pas bloquer l'UI - Complexité O(n²) acceptable pour des clusters de taille raisonnable (< ~50 arrêts) ### Zoom - En dessous d'un seuil de zoom configurable → les marqueurs du cluster sont **cachés** (via filtre MapLibre ou visibilité de layer) - Le rayon de dispersion max (`maxSpread`) est une fonction continue du zoom, ex : ``` zoom 14–16 → spread 0px → 20px zoom 16–18 → spread 20px → 80px zoom > 18 → spread 120px ``` - Recalcul déclenché à chaque `OnCameraChangeListener` si `Δzoom > 0.1` --- ## Design de l'algorithme ### Forces appliquées | Force | Portée | Description | |---|---|---| | **Répulsion intra-cluster** | Entre arrêts du même cluster | Chaque paire de nœuds se repousse (inversement proportionnel à dist²) | | **Répulsion inter-clusters** | Entre clusters distincts | Les groupes d'arrêts se repoussent mutuellement pour ne pas se superposer — appliquée sur le centroïde de chaque cluster | | **Ancrage** | Par arrêt | Chaque nœud est rappelé vers sa position GPS réelle (ressort élastique) | | **Amortissement** | Global | `velocity *= 0.85` à chaque tick pour converger | | **Contrainte rayon** | Par arrêt | Le nœud est clampé dans un cercle de `maxSpread` px autour de son ancre | ### Répulsion inter-clusters — détail Les clusters sont des entités indépendantes qui peuvent partager la même zone à l'écran. Sans répulsion inter-clusters, un groupe d'arrêts peut passer sous un autre groupe après dispersion. - La force est calculée entre les **centroïdes écran** de chaque paire de clusters - Elle est propagée à tous les nœuds du cluster (translation rigide du groupe) - L'ancrage de chaque nœud vers sa position GPS compense et empêche une dérive infinie - Recalculée à chaque tick et à chaque changement de zoom/pan ### Pas de force de lien (ressort entre nœuds) — inutile ici, pas de topologie de graphe. --- ## Architecture suggérée ``` ClusterSpreadSimulation.kt └── tick() — calcule un pas de simulation └── updateMaxSpread(px) — met à jour le rayon selon le zoom └── restart() — relance la convergence StopClusterManager.kt └── détecte les clusters (arrêts co-localisés) └── écoute OnCameraChangeListener └── déclenche simulation + anime via ValueAnimator / coroutine MapFragment / MapActivity └── geoJsonSource mis à jour à chaque frame d'animation └── layer avec filtre de visibilité selon zoom ``` --- ## État actuel (à remplacer) - Un point est placé au centroïde du cluster - Les arrêts sont disposés en **cercle uniforme** autour du premier - Pas d'animation - Rendu dégradé quand le nombre d'arrêts augmente (chevauchements, cercle trop grand ou trop petit) --- ## Critères d'acceptance - [ ] Les arrêts d'un cluster ne se chevauchent plus à fort zoom - [ ] Deux clusters proches ne se superposent pas — la répulsion inter-clusters les écarte mutuellement - [ ] La répulsion inter-clusters se recalcule au zoom/pan comme la dispersion intra-cluster - [ ] La dispersion est proportionnelle au zoom (plus on zoome, plus ils s'écartent) - [ ] En dessous du seuil de zoom, les marqueurs sont masqués - [ ] La transition est animée lors d'un zoom/dézoom - [ ] La simulation converge sans freezer l'UI - [ ] Le comportement est correct après un pan (repositionnement de la projection) --- ## Références - Algorithme force-directed : [Wikipedia — Force-directed graph drawing](https://en.wikipedia.org/wiki/Force-directed_graph_drawing) - Optimisation Barnes-Hut (si clusters > 50 nœuds) : quadtree O(n log n) - MapLibre Android SDK — GeoJSON sources & layer filters

CyrilLeblanc added the

enhancement

label

2026-06-22 12:16:25 +02:00

CyrilLeblanc self-assigned this

2026-06-22 12:16:25 +02:00

CyrilLeblanc referenced this issue from a commit

2026-06-22 23:56:17 +02:00

feat(map): force-directed dispersion of co-located stop poles (#4)

CyrilLeblanc referenced this issue from a commit

2026-06-22 23:59:26 +02:00

docs: refresh README and rename app to Gresit