L'altroieri per questioni professionali mi sono imbattuto nel problema di stabilire computazionalmente un qualsiasi punto interno di un poligono. Supponiamo che vi si dia un poligono P costituito da N vertici: voi dovete rispondere con P_int, cioè dovete dotarmi di una procedura computazionale (cioè un algoritmo) che consenta di stabilire le coordinate di un punto (P_int) che si è certi essere contenuto nel poligono e non sul bordo. Tengo a precisare che la procedura deve funzionare con un qualsiasi poligono, cioè anche con uno concavo, altrimenti è troppo facile.

Nel caso di un poligono convesso, la soluzione sarebbe semplicemente di rispondere con la formuletta del calcolo del centroide (punto medio tra tutti i vertici) o del baricentro.

Tra le varie ipotesi fantasiose, verosimili ed inverosimili, la più stupida che ho trovato nella rete è stata questa: "basta guardarlo il poligono e indicare un punto interno". A dir poco geniale!

Le soluzioni algoritmiche più comuni a questa problematica si basano di solito sul ragionamento dell'attraversamento: provo ad attraversare il poligono. Alla prima intersezione entro nel poligono, alla successiva esco. Se il poligono è convesso, sono sicuro che entro una sola volta ed esco una sola volta. Se il poligono è concavo, a seconda della retta di attraversamento, potrei entrare ed uscire più volte, pertanto basta contare il numero di volte che ho incontrato un segmento del perimetro per dire se sono dentro o fuori. Se ne ho già incontrato un numero dispari di segmenti, mi trovo dentro il poligono; se invece ho incontrato i segmenti del poligono per un numero pari di volte, sono certamente fuori.

In una versione algoritmica la cosa difficile è proprio stabilire bene una buona retta di attraversamento:

• costruisco il bounding box (rettangolo contenitore) che contiene completamente il poligono (AABB)
• stabilisco un punto di prova che si trova dentro uno degli quattro quadranti al di fuori del bounding box: tale punto è sicuramente fuori dal poligono
• stabilisco la retta di attraversamento congiungendo tale punto ed il centro del bounding box
• determino tutte le intersezioni tra i segmenti del poligono e la retta di attraversamento
• se ho scelto opportunamente la retta di attraversamento, avrò sicuramente almeno un paio di intersezioni
• il risultato della computazione, cioè la risposta al problema, è il punto medio tra la prima e la seconda intersezione

Questo approccio algoritmico è però da evitare, perché potrebbe essere necessario dover cambiare la retta di attraversamento alcune volte. In più la retta di attraversamento potrebbe incrociare "malamente" qualche segmento, perché le è esattamente parallela, con tutti i problemi del caso. In tal caso non riusciamo a stabilire se l'intersezione che non è puntuale, ma è a tutti gli effetti un segmento vero e proprio, ci faccia entrare o uscire dal poligono. La gestione di questa casistica porterebbe a scrivere del codice specifico e comunque saremmo in presenza di approssimazioni nella valutazione dell'intersezione tra due segmenti pressoché paralleli.

Ce l'avete voi un'idea migliore per trovare una semplice soluzione al problema? Vi dico subito che c'è - è elegante e molto affascinante - e che l'ho già implementata, però ve la espongo più avanti.