Punto in poligono
Il classico test geometrico per stabilire se un dato punto si trova all'interno o all'esterno di un poligono.
La soluzione abituale è il ray casting: si lancia un raggio dal punto in una direzione qualsiasi e si contano i lati del poligono che attraversa — un numero dispari significa dentro, un numero pari fuori. L'alternativa è il winding number, che somma quante volte il poligono avvolge il punto e gestisce anche le figure autointersecanti. Entrambi hanno costo lineare nel numero di lati.
Il test è alla base dell'hit detection nei giochi 2D, dei clic del mouse su pulsanti di forma irregolare, del geofencing e dei GIS. Per i poligoni convessi basta un più semplice test del segno rispetto a ciascun lato; nei casi pesanti il poligono viene preelaborato o indicizzato spazialmente.