Convergenza di breakpoint nell'algoritmo della fortuna

Question

Implemendo l'algoritmo di Sweepline di Fortune per il calcolo dei diagrammi di Voronoi. Il mio riferimento principale è "Geometria computazionale: algoritmi e applicazioni" di De Berg et al., E mentre la loro copertura dell'argomento è molto chiara, passano su diversi piccoli ma importanti dettagli che ho avuto difficoltà a risolvere me stesso. Ho cercato sul web per Guida, ma altri siti Web danno una panoramica ancora più elevata rispetto al libro di testo o dare lo stesso identico pseudocodice fornito dal libro.

Ho bisogno di un modo per determinare se una coppia di punti di interruzione determinati da un triplo di archi sulla linea di spiaggia converge o diverge, al fine di rilevare i prossimi eventi del cerchio. Sembra che prendere una decisione avrei bisogno della conoscenza della forma dei bordi delle cellule Voronoi che i punti di interruzione si tracciano come il progresso dell'algoritmo della fortuna. Ad esempio, se potessi trovare la pendenza del bordo tracciata da un punto di interruzione che potrei calcolare dove si intersecano le due linee formate dai punti di interruzione e le loro rispettive piste e decidere se convergono in base a tale risultato. Tuttavia, non ho idea di come ottenere informazioni sui pendii, solo la posizione corrente dei punti di interruzione.

Le uniche informazioni con cui devo lavorare è la posizione X, Y dei tre siti e l'attuale coordinata Y di Sweepline (sto usando una spazzatura orizzontale).

In realtà, ho un'idea per determinare la convergenza. Dato due siti, il punto di interruzione tra le due sezioni della spiaggia che definiscono è governato solo dalla posizione corrente della linea di sweep. Ho pensato di registrare la posizione dei due punti di interruzione, avanzando temporaneamente la linea di scansione una piccola quantità e registrando le loro nuove posizioni. Poiché i bordi in un normale diagramma Voronoi non si curva, se la distanza tra la nuova coppia di punti di interruzione è inferiore alla distanza tra la vecchia coppia, i punti di interruzione convergono; Altrimenti, si divergono. Ma questo sembra sia pericoloso (non ho idea se funziona sempre) e brutto. Sicuramente ci deve essere un modo migliore.

Qualsiasi idea sarebbe apprezzata e pseudocodice (in una sintassi del c #, se possibile, se possibile) soprattutto. Inoltre sono consapevole del fatto che ci sono librerie di geometria computazionale che potrei usare per ottenere diagrammi Voronoi, ma questo è un esercizio di apprendimento personale, quindi voglio implementare tutte le parti dell'algoritmo da solo.

Answer 1

Drake Benvenuto. L'ho implementato controllando se i punti di interruzione convergono fisicamente sul centro del cerchio in un incremento "fittizio" della posizione della spazzatura. Questo si complica effettivamente un po 'perché in alcuni casi il Centro Circle può essere quasi o con precisione nella posizione della sweepleline, quindi l'incremento della spazzatura deve essere proporzionale alla differenza tra la posizione attuale della spazzatura e il centro cerchio generato come si consiglia. .

Dì:

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (e ci stiamo muovendo verso il basso, cioè nella direzione della D decresante).

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (il divisore 10.0F è scelto arbitrariamente).

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

So che questo è probabilmente molto costoso, dal momento che devi calcolare le posizioni di breakpoint più volte, ma sono fiducioso che si prende cura di tutti i casi possibili.

Comunque, sto trovando problemi gravi con errore di precisione del punto flottante altrove nell'algoritmo. Sicuramente non così semplice come pensavo inizialmente.

Answer 2

Quindi questo è piuttosto imbarazzante, ma dopo aver dormito sul problema, la risposta sembra ovvia. Sto scrivendo questo per aiutare gli studenti in futuro con la stessa domanda di me.

Il bordo Voronoi tra due siti perpendicolarmente bisetta il segmento della linea (immaginario) che collega i siti. Potresti ricavare la pendenza del bordo prendendo il perpendicolare della pendenza del segmento della linea di collegamento, quindi eseguendo un test di intersezione di linea sui due bordi, ma c'è un modo ancora più semplice.

Finché tre siti sono non Collinear , quindi i bordi che perpendicolarmente bisettono i segmenti tra i siti sono tangenti al cerchio il cui bordo contiene tutti e tre i siti. Pertanto, i punti di interruzione definiti da un triplo di siti Voronoi convergono se il centro del cerchio definito dai tre siti è davanti al sito Middle , dove "in anteriore" e "dietro" dipendono dalla coordinata Sistema e allineamento di Sweepline che hai scelto.

Nel mio caso, ho una spatola orizzontale che sto spostando dal minimo Y al massimo y, quindi i punti di interruzione convergono se la coordinata Y del centro del cerchio è maggiore della coordinata Y del sito centrale, e diverge iltrimenti.

Modifica: Kristian D'Amato sottolinea giustamente che l'algoritmo sopra manca alcuni casi di convergenza. L'algoritmo finale che ho finito usando è sotto. Certo, non sono sicuro che il suo 100% corretto, ma sembra funzionare per tutti i casi in cui l'ho provato.

Given left, middle, right sites
    if they are collinear, return false
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right)
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center)

IsRightOfLine(start, end, point)
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0

.

Answer 3

Se i siti sono ordinati in senso orario attorno al centro del cerchio, l'arco è convergente.Se vengono ordinati in senso antiorario attorno al centro del cerchio, l'arco è divergente.(o viceversa, a seconda della tua implementazione).Test per CW o CCW cade dal codice che usi per trovare il centro del cerchio.

Ecco uno snippet di C # Codice per il calcolo del circumCenter D di Punti A, B, C:

        Vector2 ba = b - a;
        Vector2 ca = c - a;     
        float baLength = (ba.x * ba.x) + (ba.y * ba.y);
        float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
        float denominator = 2f * (ba.x * ca.y - ba.y * ca.x);   
        if (denominator <= 0f ) { // Equals 0 for colinear points.  Less than zero if points are ccw and arc is diverging.
            return false;  // Don't use this circle event!
        };
        d.x = a.x + (ca.y * baLength - ba.y * caLength) / denominator ;
        d.y = a.y + (ba.x * caLength - ca.x * baLength) / denominator ;

.