Involucro convesso di punti

L'involucro convesso è il più piccolo poligono convesso che contiene tutti i punti di un insieme finito — il contorno di un elastico teso attorno a chiodi su una tavola. Topografi, analisti GIS, sviluppatori di giochi e studenti di geometria computazionale hanno bisogno di quel contorno a partire da campioni non ordinati: tracce GPS, impronte di edifici, vertici di sprite o nubi di classe di coppie (x, y). Questo strumento di involucro convesso di punti esegue la scansione a catena monotona di Andrew: ordina i punti per coordinata orizzontale e poi verticale, costruisce le catene inferiore e superiore in passate lineari e restituisce i vertici estremi in senso antiorario. I punti interni e i campioni collineari a metà spigolo vengono eliminati automaticamente. Lei può inviare coppie planari x/y oppure punti geografici lat/lon; la modalità geo esegue comunque un involucro planare nel piano longitudine–latitudine, l'approssimazione locale usuale per inviluppi a scala cittadina o di sito.

Che cos'è un involucro convesso e come funziona la catena monotona

Dato un insieme finito di punti nel piano, l'involucro convesso è l'unico insieme convesso minimo che li contiene tutti. Il suo bordo è un poligono convesso i cui vertici sono un sottoinsieme dell'ingresso: ogni punto estremo che «sporge» compare sull'involucro, e ogni punto scrivibile come combinazione convessa di altri giace strettamente all'interno o su uno spigolo. La catena monotona di Andrew (detta anche scansione a catena monotona) calcola quel bordo in tempo O(n log n) dominato dall'ordinamento.

Dopo l'ordinamento per x crescente (e per y in caso di parità su x), l'algoritmo cammina da sinistra a destra per l'involucro inferiore, mantenendo sempre una svolta stretta a sinistra sugli ultimi tre vertici dello stack; poi cammina da destra a sinistra per l'involucro superiore con lo stesso test di svolta. Concatenare le due catene senza duplicare gli estremi condivisi più a sinistra e più a destra produce l'involucro completo in senso antiorario, a partire dall'estremo più a sinistra (poi il più basso).

Un test di svolta non stretto (prodotto vettoriale minore o uguale a zero) rimuove i punti collineari intermedi così ogni spigolo è massimale. Gli insiemi degeneri sono gestiti con chiarezza: un solo punto unico restituisce un involucro a un vertice; due punti distinti, un segmento a due vertici; tre o più collineari, solo i due estremi. Questo comportamento corrisponde alle definizioni di aula dell'involucro dei punti estremi e evita «incavi» di area nulla negli strumenti poligonali a valle causati da campioni a metà spigolo.

Dove un contorno convesso torna utile

I team di mappatura e logistica calcolano l'inviluppo convesso di fermate di consegna, ping di asset o segnali di rilievo per tracciare un contorno esterno semplice senza digitalizzazione manuale. Le pipeline di giochi e CAD riducono i proxy di collisione o le caselle di selezione UI all'involucro dei vertici di mesh o sprite così i test di sovrapposizione restano economici.

I notebook di data science usano l'involucro come contorno esterno robusto per grafici a dispersione e revisione delle anomalie quando un bounding box è troppo largo e una forma alfa concava è troppo pesante. Le piattaforme scolastiche e di gara necessitano di un oracolo deterministico per esercizi «elencare i punti estremi in ordine»; una capacità parse pura restituisce coordinate stabili a precisione fissa così i correttori non falliscono per rumore floating. La convalida fallita non consuma saldo.

Mantenga le nubi sotto il tetto di diecimila punti, fissi i vertici dell'involucro nei test e ottiene inviluppi riproducibili per ETL GIS, worker di edge e compiti senza erigere una libreria di geometria completa propria.