Segmenti segmento di movimento

Question

Ho una domanda su questo problema algoritmico; Incollerò il problema quindi passerò ai miei pensieri e soluzioni attuali.

Ci sono N (up to 100,000) segmenti definiti [(x1, y1), (x2, y2)], dove x1 < x2 e y1 < y2 (ad esempio i segmenti hanno pendenza positiva). Nessun segmento di linea tocca o interseca, anche ai punti finali. Il primo segmento ha (x1, y1) = (0, 0). Immagina ogni segmento come una collina 2-D che una persona deve scalare.

Una persona inizia a (0, 0) e atterra sulla prima collina. Ogni volta che una persona atterra su una collina, si arrampica fino alla fine, che è (x2, y2) e salta verso il basso. Se atterra su un'altra collina (ovunque sul segmento), il processo continua: sale quella collina e salta. Se non ci sono più colline, cade a -INFINITY e il processo è finito. Ogni collina (x1, y1) -> (x2, y2) dovrebbe essere (x1, y1) come contenente il punto (x1, y1) ma non contenente il punto (x2, y2), in modo che la persona atterrerà sulla collina se cade sopra di esso a una posizione con x = x1, ma non atterrerà sulla collina se cade su da sopra a x = x2.

L'obiettivo è contare quante colline tocca.

mio attuale pensiero

sto pensando di spazzare una linea attraverso il piano lungo l'asse x. Ogni segmento è costituito da un evento BEGIN ed END; ogni volta che incontriamo l'inizio di un segmento di linea, lo aggiungiamo in un set. Ogni volta che incontriamo la fine di un segmento di linea, lo rimuoviamo dal set. E quando raggiungiamo il punto FINE della collina attuale, dovremmo controllare il set per la collina più alta su cui possiamo atterrare. Tuttavia, non so come determinare come controllare rapidamente, perché potrebbero esserci potenzialmente N voci all'interno del set. Inoltre, dopo aver saltato su un'altra collina, l'ordine di questi cambierà perché le pendenze di ciascun segmento sono probabilmente diverse, e non so come spiegare questa differenza.

Qualche idea?

Answer 1

Penso che un algoritmo di scansione della linea sia una buona idea qui. Lasciatemi riassumere il tuo algoritmo finora e aggiungi i miei miglioramenti:

• Si sta eseguendo una linea da sinistra a destra.
• Si dispone di un elenco attivo che elenca tutti i segmenti attualmente attivi. sono questi segmenti che si intersecano con la sweepline
• Ogni punto finale di ogni segmento di linea è considerato un 'evento'
• quando la linea spazia fino al 'start' di un segmento, il segmento viene aggiunto nella lista di segmenti attivi
• Quando la linea spazza la 'fine' di un segmento, il segmento viene rimosso dall'elenco di segmenti attivi
• Se non ci sono segmenti di linea nel set attivo alla rimozione di un segmento di linea, il processo termina
• Se ci sono segmenti di linea nel set attivo alla rimozione di un segmento di linea, dobbiamo determinare
  • A) Se sono presenti segmenti di linea nel set attivo con 'sotto' il vertice estremità precedentemente rimosso porzioni, e
  • B) Quale di questi segmenti la persona atterrerà su.

L'idea è quella di ordinare i segmenti di linea nel 'set attivo' in modo tale che questa query è efficiente. Quello che sto pensando è che se conosciamo pendenza e intercetta y di una linea siamo in grado di calcolare i punti di intersezione per la posizione x di un vertice inizio

GreaterThan(segment1,segment2){ // is segment 1 higher than segment 2? 
//y = mx + b; compute y value of point on segment 2 for a given x value from s1 
//that is, m and b are slope and y-intercept of s2 
yVal = m * (segment1.first.x) + b 
if (yVal < segment1.first.y) 
    return true //the point on s2 corresponding to s1.first is lower than s1.first 
return false 
} 

perché le linee non si intersecano, allora si può assumere alcuna altra linea sarà ' andare oltre e 'questa linea.

Se evitiamo di aggiungere segmenti di linea i cui vertici iniziali sono superiori al vertice finale della linea corrente della nostra "persona", allora dovremmo evitare di aggiungere qualsiasi segmento di linea estraneo al set attivo (cioè segmenti di linea "sopra" il nostro uno attuale)

Ora dobbiamo solo preoccuparci del caso speciale del vertice dell'ultimo segmento di linea che non è "landable". Poiché i vertici sono eventi, elaboreremo tutti gli eventi prima di eseguire il test del segmento. in questo modo, non accidentalmente atterri sul vertice finale di una linea nel set attivo, ma tu si terra su un segmento di linea che è stato appena aggiunto.

Ora che abbiamo un elenco ordinato di segmenti di linea nel set attivo, possiamo interrogarlo in tempo costante per ottenere quello superiore, e aggiungerne uno dovrebbe prendere solo il tempo logaritmico.

Come suona?

Answer 2

Ecco una direzione approssimativa in Haskell. "segmenti" sono i segmenti di linea. (In questo esempio, il terzo segmento è leggermente sopra il secondo segmento per testare il codice.) "Matches" trova le colline/segmenti che posizionano la parte superiore dell'ultimo segmento, pt (x0, y0), all'interno dei loro limiti x e sopra o uguale alla y corrispondente alla loro trasformazione affine di x0 ("affine" calcola la funzione affine per il segmento - ax + b, per intenderci). Infine, countHills verifica le possibili corrispondenze per la collina successiva e sceglie quella con la più vicina da y a y0 (calcolata dall'affine a * x0 + b) e emette il risultato, accumulando le colline montate in ordine. Chiaramente questa idea potrebbe richiedere l'ottimizzazione per elenchi di segmenti molto più lunghi.

L'output di risultato seguente mostra il primo e il terzo segmento. Il secondo segmento/segmento non è nel risultato perché è inferiore al terzo: ci occupiamo invece del terzo:

* Principale> segmenti countHills
[((0,0,0,0), (2,0,5,0)), ((1.0,1.5), (5.0,3.0))]

import Data.List 

segments = [((0,0),(2,5)),((1,1),(5,2)),((1,1.5),(5,3))] 

top segment = snd segment 

matches pt = 
    let x0 = fst pt 
     y0 = snd pt 
    in filter (\x -> x0 >= fst (fst x) 
        && x0 < fst (snd x) 
        && (affine x) x0 <= y0) segments 

affine segment = 
    let x1 = fst $ fst segment 
     y1 = snd $ fst segment 
     x2 = fst $ snd segment 
     y2 = snd $ snd segment 
    in (+ ((x1*y2-x2*y1)/(x1-x2))) . (* ((y2-y1)/(x2-x1))) 

countHills segments = countHills' (head segments) [] where 
    countHills' x result = 
    let hills = matches $ top x 
     x0 = fst (top x) 
     y0 = snd (top x) 
    in if null hills 
      then result ++ [x] 
      else let nextHill = 
        minimumBy (\a b -> compare 
             (y0 - (affine a) x0) 
             (y0 - (affine b) x0)) hills 
       in countHills' nextHill (result ++ [x]) 

Answer 3

In pre-elaborazione è possibile attraversare tutti i segmenti e aggiungere punti in uno STL multimap < coppia, segmento> o qualcosa di simile. Il costo di questa pre-elaborazione sarebbe O (NlogN). Quindi puoi continuare con il tuo metodo di scansione. Hai bisogno di punti iterati da multimap. Poiché tutti i punti sono ordinati e contengono un riferimento alla linea a cui corrisponde il punto, costerebbe O (N).

Answer 4

Barron, il tuo algoritmo è perfettamente corretto. L'ordine degli elementi nella lista ordinata non cambierà con lo spostamento della linea di scorrimento, perché se ciò accadesse avresti un'intersezione di segmenti di linea.

Hai solo bisogno di un modo per tenere traccia dei segmenti di linea ordinati. Un modo per farlo sarebbe quello di mantenere una mappa di segmenti di linea, in cui l'operatore di confronto confronta i segmenti di linea con il valore y del segmento come calcolato dal valore x attuale della posizione corrente di sweep. L'inserimento, l'eliminazione e l'interrogazione da questa mappa è O (log (n)).