[OSM-talk-fr] doublon way fermé

[Philippe Verdy]

Note: je n'ai pas décrit comment on peut automatiquement, et
efficacement, déterminer le sens horaire ou antihoraire d'un segment
sur un contour fermé. La solution est simple:

- Nos coordonnées étant stockées avec une précision maximale de 32
bits (sur un float), il est toujours possible de convertir ces
coordonnées en double (64 bits) pour y ajouter une quantité espsilon
suffisante permettant de déterminer les coordonnées d'un point de
référence en dehors de tout chemin de la base. Il suffit de multiplier
ces coordonnées (converties en double) par la constante (double 64
bits) = (1 + 2 ^ -47). Donc il suffit de le faire pour le premier nœud
d'un chemin dont on cherche à savoir s'il est en sens horaire ou
antihoraire.

- Ensuite on utilise ce point de référence pour savoir s'il est à
l'intérieur ou à l'extérieur du chemin fermé, en comptant là encore
les points (à l'est comme à l'ouest, peu importe !) où une ligne
horizontale de référence (passant par le point de référence), coupe
les segments du chemin testé (il n'y a aucun point particulier car il
n'y aura aucun chemin horizontal à la même latitude que ce point de
référence !)

- Il n'est même pas nécessaire de déterminer les coordonnées
d'intersection de cette horizontale avec chaque segment, juste de
déterminer d'abord si ce segment a ses deux sommets du même côté de
l'horizontale de références (latitudes toutes deux supérieures ou
toutes deux inférieures, auquel cas il n'y a pas d'intersection
possible) ; sinon le segment est vertical ou oblique et sa droite
coupe nécessairement l'horizontale quelquepart.

- Nul besoin de déterminer où sur l'horizontale, la plupart du temps :
pas de calcul compliqué à faire, ni même de déterminer si
l'intersection avec l'horizontale de la droite porteuse du segment est
située sur ce segment ou pas !), tout ce qu'on voulait savoir c'est si
chaque segment coupe ou pas l'horizontale (ou pourrait le couper si un
sommet de segment était déplacé, sans changer l'orientation horaire,
pour traverser l'horizontale deux fois, une fois chaque segment
partageant ce sommet) .

- Le seul cas est pour les segments verticaux et obliques de savoir si
cette intersection de l'horizontale de référence avec la droite
porteuse de segment est sur le segment ou pas : un calcul linaire
simple avec deux soustraction et une division (dont le diviseur ne
peut pas être nul car on sait que l'intersection de l'horizontale de
référence avec de la droite porteuse du segment existe bien) fournira
le résultat.

- si le nombre d'intersections des droites portant les segments avec
l'horizontale de référence est multiple de 4 (ou nul) on sait alors
que le chemin est dans le sens antihoraire. Sinon ce nombre est pair
mais non multiple de 4 le chemin est en sens horaire... Si le nombre
est impair, le contour n'est pas fermé et il n'a pas de sens
définissable autre que celui qu'il utilise !

Pas besoin de faire de trigo ! Cet algo est extrêmement rapide ! Noter
que tous les calculs effectués avec des double 64-bits sont plus
rapides qu'avec des float (32-bits) à cause des règles d'arrondis IEEE
et les conversions multiples de type pour les résultats
intermédiaires.