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. _______________________________________________ Talk-fr mailing list Talk-fr@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-fr
