Qual è il modo più veloce per trovare il centro "visivo" di un poligono di forma irregolare?
https://stackoverflow.com/questions/1203135
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Devo trovare un punto che sia un centro visivo di un poligono di forma irregolare. Per centro visivo, intendo un punto che sembra essere al centro di una vasta area del poligono visivamente. L'applicazione deve inserire un'etichetta all'interno del poligono.
Ecco una soluzione che utilizza il buffering interno:
Se questo deve essere usato, qual è un modo efficace e veloce per trovare il buffer? Se deve essere usato un altro modo, qual è il modo?
Un buon esempio di poligoni davvero duri è una gigantesca U spessa (scritta in Arial Black o Impact o in qualche tipo di carattere).
Soluzione
Se è possibile convertire il poligono in un'immagine binaria, è possibile utilizzare la base esistente nel campo dell'elaborazione delle immagini, ad esempio: A Fast Skeleton Algorithm sulle immagini binarie rappresentate a blocchi .
Ma questo non è veramente ragionevole nel caso generale, a causa di errori di discretizzazione e lavoro extra.
Tuttavia, forse li trovi utili:
- Scheletro dritto di un semplice poligono
- Determinazione del Scheletro di un poligono semplice in (quasi) tempo lineare
MODIFICA: forse vuoi cercare il punto che è il centro del cerchio più grande contenuto nel poligono. Non è necessariamente sempre nel centro osservato, ma la maggior parte delle volte probabilmente darebbe il risultato atteso, e solo in casi leggermente patologici qualcosa che è totalmente spento.
Altri suggerimenti
Ho trovato un'ottima soluzione a questo da MapBox chiamato Polylabel . La fonte completa è disponibile anche sul Github .
Essenzialmente cerca di trovare il centro visivo del poligono come ha detto T Austin.
Alcuni dettagli suggeriscono che questa potrebbe essere una soluzione pratica:
Sfortunatamente, calcolare [la soluzione ideale] è sia complesso e lento. Le soluzioni pubblicate al problema richiedono neanche Triangolazione vincolata di Delaunay o calcolo di uno scheletro diritto come fasi di preelaborazione & # 8202; & # 8212; & # 8202; entrambe sono lente e soggette a errori.
Per il nostro caso d'uso, non abbiamo bisogno di una soluzione esatta & # 8202; & # 8212; & # 8202; siamo disposti a scambia un po 'di precisione per ottenere più velocità. Quando stiamo posizionando un'etichetta una mappa, è più importante per essere calcolata in millisecondi rispetto a per essere matematicamente perfetto.
Una breve nota sull'uso però. Il codice sorgente funziona benissimo per Javascript pronto all'uso, tuttavia se si intende utilizzarlo con un "normale" poligono quindi dovresti avvolgerlo in un array vuoto poiché le funzioni qui assumono GeoJSONPolygons piuttosto che normale poligoni cioè
var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
Hai studiato la formula del centroide?
Che ne dici di:
Se il centroide del poligono si trova all'interno del poligono, utilizzalo, altrimenti:
1) Estendi una linea dal centroide attraverso il poligono dividendo il poligono in due metà di uguale area
2) Il "centro visivo" è il punto a metà strada tra il punto più vicino in cui la linea tocca il perimetro e il punto successivo che taglia il perimetro nella direzione che si allontana dal centroide
Ecco un paio di foto per illustrarlo:
Calcola la posizione centrale (x, y) di ciascun bordo del poligono. Puoi farlo trovando la differenza tra le posizioni delle estremità di ciascun bordo. Prendi la media di ciascun centro in ogni dimensione. Questo sarà il centro del poligono.
Il metodo centroide è già stato suggerito più volte. Penso che questa sia una risorsa eccellente che descrive il processo (e molti altri trucchi utili con i poligoni) in modo molto intuitivo:
http://paulbourke.net/geometry/polygonmesh/centroid.pdf
Inoltre, per posizionare una semplice etichetta dell'interfaccia utente, potrebbe essere sufficiente calcolare il riquadro di delimitazione del poligono (un rettangolo definito dalle coordinate xey più basse e più alte di qualsiasi vertice nel poligono), e ottenere il suo centro in:
{
x = min_x + (max_x - min_x)/2,
y = min_y + (max_y - min_y)/2
}
Questo è un po 'più veloce del calcolo del centroide, che potrebbe essere significativo per un'applicazione incorporata in tempo reale.
Nota anche che se i tuoi poligoni sono statici (non cambiano forma), puoi ottimizzare salvando il risultato del calcolo del centro / centro di massa BB (relativo ad esempio al primo vertice del poligono) nel struttura dei dati del poligono.
Non sto dicendo che questo è il più veloce, ma ti darà un punto all'interno del poligono. Calcola il Scheletro dritto . Il punto che stai cercando è su questo scheletro. Ad esempio, potresti scegliere quello con la distanza normale più breve dal centro del rettangolo di selezione.
Che ne dici di trovare " incircle " del poligono (il cerchio più grande che si adatta al suo interno) e quindi centrare l'etichetta al centro di quello? Ecco un paio di link per iniziare:
http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/ 144373.html? 1.219.439,473 mila
Questo non funzionerà perfettamente su ogni poligono, molto probabilmente; un poligono che sembrava una C avrebbe l'etichetta in un punto un po 'imprevedibile. Ma il vantaggio sarebbe che l'etichetta si sovrappone sempre a una parte solida del poligono.
Se capisco il punto del documento a cui hai collegato (un problema piuttosto interessante, a proposito), questo "buffering interno" la tecnica è in qualche modo analoga alla modellazione della forma in questione a partire da un pezzo di zucchero che viene sciolto dall'acido dai bordi in. (ad es. quando la distanza del buffer aumenta, meno della forma originale rimane) L'ultimo bit rimanente è il punto ideale per posizionare un'etichetta.
Sfortunatamente non è molto chiaro come farlo in un algoritmo ....
Penso che se rompessi il poligono nei suoi vertici, e poi applicassi una funzione per trovare lo scafo convesso più grande, e poi trovi il centro fuori da quello scafo convesso, si abbinerebbe da vicino con "apparente"; Centro.
Trovare lo scafo convesso più grande dati i vertici: Guarda sotto il paragrafo Simple Polygon.
Media dei vertici dello scafo convesso per trovare il centro.
Potresti posizionare l'etichetta al centro ingenuo (del riquadro di delimitazione, forse), e quindi spostarla in base alle intersezioni dei bordi poligonali locali e al BB dell'etichetta? Spostati lungo le normali dei bordi che si intersecano e, se più bordi si intersecano, somma le loro normali per il movimento?
Sto solo indovinando qui; in questo tipo di problema probabilmente proverei a risolverlo iterativamente fintanto che le prestazioni non sono troppo preoccupanti.
Non ho molto tempo per elaborarlo o testarlo adesso, ma proverò a fare di più quando ne avrò la possibilità.
Usa i centroidi come metodo principale. Prova per vedere se il centroide è all'interno del poligono; in caso contrario, traccia una linea attraverso il punto più vicino e sull'altro lato del poligono. Nel punto medio della sezione di quella linea che si trova all'interno del poligono, posizionare l'etichetta.
Poiché è probabile che il punto più vicino al centroide rileghi un'area abbastanza ampia, penso che ciò potrebbe dare risultati simili agli incircoli di Kyralessa. Certo, questo potrebbe impazzire se avessi un poligono con buchi. In tal caso, gli incircles sarebbero probabilmente molto meglio. D'altra parte, il valore predefinito è il metodo centroide (veloce?) Per i casi tipici.
Questo problema sarebbe probabilmente analogo alla ricerca del "centro di massa" assumendo una densità uniforme.
EDIT: questo metodo non funziona se il poligono ha "fori"
puoi usare il metodo Center of Mass (o Center of Gravity) che viene utilizzato nell'ingegneria civile, ecco un link utile da Wikipedia:
