Test di convessità del poligono

Un test di convessità del poligono risponde a una domanda fondamentale della geometria computazionale: dato un anello ordinato di vertici cartesiani, ogni angolo interno resta al più pari a centottanta gradi in modo che la forma non si infossi mai verso l'interno? I geometri che convalidano particelle catastali, gli sviluppatori di giochi che definiscono scafi di collisione, i team GIS che puliscono poligoni di geofence, gli esportatori CAD che impongono vincoli di convessità e gli strumenti didattici che valutano esercizi su poligoni semplici necessitano di una risposta deterministica sì o no senza erigere un'intera libreria geometrica. Questa capacità accetta un elenco ordinato di vertici, percorre l'anello chiuso una sola volta e confronta il prodotto vettoriale bidimensionale di ogni coppia di spigoli consecutivi. Quando ogni prodotto vettoriale non nullo condivide lo stesso segno, ogni svolta va nello stesso senso e il poligono è convesso; segni misti indicano almeno un angolo rientrante e il poligono è concavo. I prodotti vettoriali nulli segnano vertici collineari e sono ammessi senza rompere la convessità.

Come i prodotti vettoriali di spigoli consecutivi decidono la convessità

Etichetti i vertici ordinati da V zero a V n meno uno e chiuda l'anello trattando lo spigolo dall'ultimo vertice al primo come presente anche quando chi chiama non ripete il punto iniziale. In ogni vertice B con vertice precedente A e successivo C, formi i vettori uscenti da A a B e da B a C. Il loro prodotto vettoriale bidimensionale è lo scalare z uguale a (B.x meno A.x) per (C.y meno B.y) meno (B.y meno A.y) per (C.x meno B.x).

Il segno di z è la direzione di svolta in B: positivo per una svolta a sinistra quando il piano è orientato con y in alto e x a destra (percorso antiorario del contorno), negativo per una svolta a destra (percorso orario) e zero quando A, B e C sono collineari.

Un poligono semplice è convesso se e solo se ogni svolta non nulla condivide lo stesso segno, il che significa che ogni angolo interno è al più di centottanta gradi e il contorno non inverte mai il senso di rotazione. Svolte positive e negative miste dimostrano un angolo interno rientrante da qualche parte sull'anello, quindi il poligono è concavo. L'algoritmo è strettamente O(n) nel numero di vertici dopo un unico passaggio di normalizzazione che elimina un duplicato finale del primo punto quando chi chiama ha già chiuso l'anello.

Quando conviene verificare la convessità

Le pipeline di mappatura e GIS usano un test di convessità del poligono prima di algoritmi che assumono ingresso convesso — ritaglio contro una finestra convessa, scomposizione di regioni complesse o alimentatori di solver che rifiutano vertici rientranti. Motori di gioco e simulazione convalidano maglie di collisione definite dai designer affinché un solo avvallamento non rompa poi ipotesi di assi di separazione o GJK. Esportatori CAD e di produzione impongono vincoli di convessità su grezzi e poligoni di supporto prima di inviare la geometria a un utensile di taglio.

Piattaforme educative valutano voci «questo poligono è convesso?» con un oracolo deterministico che tratta in modo coerente i vertici collineari a metà spigolo invece di affidarsi all'occhio. La convalida fallita non consuma saldo.