Ho un set S di punti (2D: definito da x e y) e voglio trovare P, il più piccolo (nel senso: con il più piccolo numero di punti) poligono che racchiude tutti i punti di il set, P essendo un sottoinsieme ordinato di S.Poligono che racchiude una serie di punti
Esistono algoritmi noti per il calcolo di questo? (La mia mancanza di cultura in questo settore è sorprendente ...)
Grazie per il vostro aiuto
Ci sono molti algoritmi per questo problema. Si chiama "minimum bounding box". Troverete anche le soluzioni alla ricerca di "convex hull", in particolare here.
Un modo è trovare il punto più a sinistra e poi ripetere per cercare un punto in cui tutti gli altri punti si trovano a destra della linea p (n-1) p (n).
Grazie, questo era esattamente quello che stavo cercando. Digitando "jarvis march java" o "quick hull java" su google, ho persino trovato i java implants. –
"riquadro di limitazione minimo" è ... una casella. Non un poligono generico. Gli altri collegamenti potrebbero essere buoni. –
Non si sa quale "bounding box minimo" abbia a che fare con esso, considerando che P deve essere un sottoinsieme di S. – AnT
Probabilmente vuoi dire che vuoi l'area più piccola, che è lo scafo convesso.
Se vuoi davvero il minor numero di punti , puoi semplicemente creare un triangolo con posizioni vertici super-grandi in modo che tutti i tuoi punti siano racchiusi.
I punti P nel tuo enorme triangolo non sarebbero un sottoinsieme di S, che è uno dei requisiti. –
@DanielDaranas Come si possono ottenere i vertici di questo triangolo super grande? – Dinesh
Ecco una soluzione semplice ...
cominciare con tre punti qualsiasi in modo da formare un triangolo. Aggiungi ogni punto aggiuntivo al poligono con la seguente operazione:
Dividi i bordi in due percorsi continui, dove in un percorso la linea di ciascun bordo separa il punto da aggiungere dal resto del poligono (chiamiamolo il "percorso di separazione") e nell'altro percorso, la linea di ciascun bordo ha il punto sullo stesso lato del poligono.
(Nota: finchè la forma rimane convessa, quale deve, questi due percorsi sarà continuo e formare l'intera forma)
Se il percorso di separazione ha bordi, il punto è all'interno del poligono e dovrebbe essere ignorato, altrimenti rimuovere il percorso di separazione dal poligono. Sostituirlo con due segmenti, collegando ciascun punto finale del percorso di separazione al nuovo punto.
Ta-da! :)
Ecco una buona risorsa su algoritmi convesso: The Convex Hull of a 2D Point Set or Polygon (by Dan Sunday)
ciao, ho bisogno di implementare stessa funzionalità nella mia applicazione. per favore condividi l'algoritmo con me? –
Ho usato QuickHull. Riferimento qui: https://en.wikipedia.org/wiki/Quickhull –