Come calcolare la tesselazione di Voronoi in base alla distanza di manhattan in R

Question

Sto provando a calcolare una tessellazione Voronoi in 2D con la distanza Manhattan in R.

Idealmente questa sarebbe una funzione che riceve un insieme di punti bidimensionali ed emette una lista di poligoni che partizione lo spazio. Non sono sicuro che le rappresentazioni delle tessellazioni di Voronoi siano standard.

Ci sono naturalmente molti modi per farlo con la metrica euclidea (pacchetti come deldir e qhull rendono questo molto facile), ma non ho trovato un modo per farlo per la distanza di manhattan. Anche una ricerca utilizzando findFn('voronoi')sos non ha dato risultati.

Answer 1

Info: taxicabgeometry.net

Interactive: Manhattan-metric Voronoi diagram(Click version)

Sono stato a rotazione my own in python, e possono riassumere le basi qui: Tra centroids vicini è una linea perpendicolare, a Manhattan metrico - due raggi e un Molto più probabile una diagonale di 45 gradi, se i centroidi sono generati casualmente, ma può anche verificarsi una linea diagonale orizzontale, verticale o di 45 gradi. Dato un insieme di tali linee per ogni coppia di centroidi, i bordi che separano le regioni sono tra questi. Raccogli i punti intersecati di ogni coppia di linee che sono uguali-distanti (all'interno di un epsilon), in metrica manhattan, ai suoi 3 centroidi più vicini. Raccogliere anche i due punti medi della diagonale di 45 gradi che sono ugualmente distanti dal loro più vicino due centroidi. I poli esterni non saranno chiusi. Come gestirli dipende da ciò di cui hai bisogno. I poli bordi e i banchi di fronti avranno bisogno di essere ordinati, quindi i tuoi poli non sono un casino a zigzag. L'ordine di avvolgimento può essere determinato se devono essere in senso orario o altro. Più può essere fatto, dipende solo da ciò di cui hai bisogno.

Sfortunatamente, questo rallenta esponenzialmente più punti sono coinvolti. L'intersezione di ogni bisettrice con ogni altra bisettrice è il collo di bottiglia. Ho provato un metodo di inserimento, con un certo successo, ma. Ora sto pensando di provare prima a creare un collegamento più vicino-vicino tra i centroidi. Se i vicini sono noti, le bisettrici da intersecare saranno minime e molti centroidi possono essere calcolati rapidamente.

Comunque, l'approccio forza bruta funziona:

Il punto vicino al cursore è in realtà 2 punti di una piccola diagonale. È un metodo preciso, ma più complicato di quanto non sembri. Il codice java dal collegamento interattivo sopra può essere più veloce, ma era difficile ottenere una geometria solida e precisa.

Spiacente, non so R.

Answer 2

Forse la domanda è di trovare la massima area di un quadrato che corrispondono all'interno di un cerchio circoscritto (di un triangolo). L'equazione per un tale quadrato abs (x) + abs (y) = r (www.mathematische-basteleien.de/taxicabgeometry.htm). Quando hai una maglia di triangoli il diagramma di voronoi è il doppio.