Point dans polygone

Un test point-dans-polygone répond à une question de base de géométrie computationnelle : étant donné une position de requête et une forme fermée définie par un anneau ordonné de sommets, cette position tombe-t-elle à l’intérieur de la forme ? Levé, produits cartographiques, masques de collision de jeux, géofences logistiques et laboratoires de géométrie en classe ont tous besoin de la même réponse déterministe plutôt que d’un croquis à main. Ce vérificateur implémente l’algorithme classique de ray casting pair-impair sur des coordonnées planes : un demi-rayon horizontal est lancé depuis le point de test vers l’infini positif, chaque arête du polygone est testée pour un croisement propre, et la parité du compte de croisements décide intérieur versus extérieur. Les points qui tombent exactement sur une arête ou un sommet sont traités comme intérieurs et marqués d’un indicateur de bord pour que les consommateurs d’ensemble fermé n’aient pas besoin d’un second passage. Le polygone est fermé implicitement — vous n’avez pas à répéter le premier sommet à la fin — et les sommets peuvent être fournis comme objets avec champs x et y ou comme tableaux de deux éléments. Lorsque moins de trois sommets sont fournis la requête échoue avec une erreur de validation claire, car un polygone a besoin d’au moins un triangle.

Comment fonctionne le test de ray casting pair-impair

Partir d’un point de requête fini de coordonnées x et y et d’une liste ordonnée d’au moins trois sommets plans formant un polygone simple fermé lorsque les sommets consécutifs sont reliés et que le dernier rejoint le premier. L’algorithme n’exige pas d’ordre horaire ou antihoraire ; les deux orientations sont valides sous la règle pair-impair. Depuis le point de requête, imaginez un rayon horizontal qui ne voyage qu’à droite, jamais à gauche.

Parcourez chaque arête du polygone et décidez si cette arête croise le rayon. Les arêtes horizontales sont ignorées pour ne pas créer de doubles comptes ambigus. Lorsqu’une arête chevauche la hauteur du rayon — une extrémité strictement au-dessus du y de requête et l’autre non — le x exact de l’intersection est calculé avec un paramètre linéaire le long de l’arête.

Si le x de requête se trouve strictement à gauche de cette intersection, l’arête contribue un croisement ; si l’intersection coïncide avec la requête dans une tolérance numérique minuscule, le point est classé comme sur le bord. Après traitement de toutes les arêtes, un compte impair de croisements signifie intérieur et un compte pair extérieur, l’argument classique de parité de la courbe de Jordan spécialisé à un rayon horizontal. Les coordonnées doivent être finies ; NaN et Infinity sont rejetés.

Où les tests point-dans-polygone apparaissent dans le travail réel

Les produits logistiques et de livraison demandent si un fix GPS de coursier tombe dans un polygone de quartier avant d’offrir un tarif par zone, et ont besoin d’une réponse déterministe qui ne dérive pas entre l’aperçu carte du navigateur et le serveur. Jeux et médias interactifs utilisent des masques de collision alignés ou libres définis comme anneaux de sommets et testent positions de joueur ou projectile à chaque image sans tirer une pile SIG lourde.

Les modules de géométrie computationnelle en classe enseignent le ray casting, l’intuition du théorème de la courbe de Jordan et les cas limites flottants ; un seul oracle de confiance qui renvoie à la fois le drapeau inside et le compte brut de croisements aide les étudiants à vérifier les devoirs étape par étape. Outils d’urbanisme et cadastraux classent des points d’échantillon contre empreintes de bâtiments ou polygones de zonage lors de revues de conception précoces quand les bases topologiques complètes ne sont pas encore connectées.

Si vous avez plus tard besoin de périmètre de polygone, d’aire de polygone, de géodésie grand cercle, de trous multipolygone avec la règle de winding non nulle ou de confinement sphérique sur l’ellipsoïde WGS84, traitez-les comme intentions de recherche et atterrissages séparés plutôt que de surcharger cette page du vérificateur plan point-dans-polygone.