Punto nel poligono

Un test punto-nel-poligono risponde a una domanda di base di geometria computazionale: data una posizione di interrogazione e una forma chiusa definita da un anello ordinato di vertici, quella posizione cade nell’interno della forma? Rilievo, prodotti cartografici, maschere di collisione nei giochi, geofence logistiche e laboratori di geometria in aula hanno tutti bisogno della stessa risposta deterministica invece di uno schizzo a mano. Questo controllo implementa l’algoritmo classico di ray casting pari-dispari su coordinate planari: un semiraggio orizzontale è lanciato dal punto di prova verso l’infinito positivo, ogni spigolo del poligono è testato per un incrocio proprio, e la parità del conteggio degli incroci decide dentro versus fuori. I punti che cadono esattamente su uno spigolo o un vertice sono trattati come dentro e segnalati con un marcatore di contorno così i consumatori di insieme chiuso non necessitano di un secondo passaggio. Il poligono è chiuso implicitamente — non deve ripetere il primo vertice alla fine — e i vertici possono essere forniti come oggetti con campi x e y o come array di due elementi. Quando si forniscono meno di tre vertici la richiesta fallisce con un chiaro errore di validazione, perché un poligono richiede almeno un triangolo.

Come funziona il test di ray casting pari-dispari

Si parta da un punto di interrogazione finito con coordinate x e y e da un elenco ordinato di almeno tre vertici planari che formano un poligono semplice chiuso quando i vertici consecutivi sono collegati e l’ultimo si unisce al primo. L’algoritmo non richiede ordine orario o antiorario; entrambe le orientazioni sono valide sotto la regola pari-dispari. Dal punto di interrogazione, si immagini un raggio orizzontale che viaggia solo a destra, mai a sinistra.

Si percorra ogni spigolo del poligono e si decida se quello spigolo incrocia il raggio. Gli spigoli orizzontali sono ignorati per non creare doppi conteggi ambigui. Quando uno spigolo a cavallo dell’altezza del raggio — un estremo strettamente sopra la y di interrogazione e l’altro no — la x esatta dell’intersezione è calcolata con un parametro lineare lungo lo spigolo.

Se la x di interrogazione sta strettamente a sinistra di quell’intersezione, lo spigolo contribuisce un incrocio; se l’intersezione coincide con l’interrogazione entro una tolleranza numerica minuscola, il punto è classificato come sul contorno. Dopo aver processato tutti gli spigoli, un conteggio dispari di incroci significa dentro e un conteggio pari fuori, l’argomento classico di parità della curva di Jordan specializzato a un raggio orizzontale. Le coordinate devono essere finite; NaN e Infinity sono rifiutati.

Dove i controlli punto-nel-poligono compaiono nel lavoro reale

Prodotti di logistica e consegna chiedono se un fix GPS del corriere cade dentro un poligono di quartiere prima di offrire una tariffa per zona, e necessitano di una risposta deterministica che non derivi tra l’anteprima mappa del browser e il server. Giochi e media interattivi usano maschere di collisione allineate agli assi o a forma libera definite come anelli di vertici e testano posizioni di giocatore o proiettile ogni fotogramma senza tirare uno stack GIS pesante.

Moduli di geometria computazionale in aula insegnano ray casting, l’intuizione del teorema della curva di Jordan e casi limite di virgola mobile; un unico oracolo affidabile che restituisce sia il flag inside sia il conteggio grezzo degli incroci aiuta gli studenti a verificare i compiti passo per passo. Strumenti di pianificazione urbana e catastali classificano punti campione contro impronte di edifici o poligoni di zonizzazione in revisioni di progetto precoci quando le basi di topologia complete non sono ancora collegate.

Se in seguito Le serve perimetro di poligono, area di poligono, geodesia di grande cerchio, buchi multipoligono con la regola di winding non nullo o contenimento sferico sull’ellissoide WGS84, li tratti come intenti di ricerca e landing separati anziché sovraccaricare questa pagina del controllo planare punto-nel-poligono.