Asintoticamente ottimale algoritmo per calcolare se una linea che interseca un poligono convesso

Un O(n) algoritmo per rilevare se una linea che interseca un poligono convesso consiste nel verificare se il bordo del poligono interseca la linea, e guardare se il numero di intersezioni è pari o dispari.

C’è un asintoticamente algoritmo più veloce, ad esempio, un O(log n) uno?

InformationsquelleAutor infinity_x | 2010-12-21

 

5 Replies
  1. 17

    lhf la risposta è vicino a correggere. Qui è una versione che dovrebbe risolvere il problema con la sua.

    Lasciare che il poligono avere dei vertici v0, v1, …, vn in ordine antiorario. Lasciate che siano i punti x0 e x1 essere sulla linea.

    Notare due cose: in Primo luogo, trovare il punto di intersezione di due linee (e nella determinazione della sua esistenza) può essere fatto in un tempo costante. Secondo, determinare se un punto è a sinistra o a destra di una riga può essere fatto in un tempo costante.

    Seguiremo la stessa idea di base di lhf per ottenere un O(log n) algoritmo. Base casi sono quando il poligono ha 2 o 3 vertici. Questi possono essere gestiti in tempo costante.

    Determinare se la linea (v0,v(n/2)) interseca la linea di (x0,x1).

    Caso 1: non si intersecano.

    In questo caso la linea che ci interessa è a sinistra o a destra della linea di dividere il poligono, e così siamo in grado di recurse in cui la metà del poligono. In particolare, se x0 è a sinistra (v0,v(n/2)) quindi tutti i vertici del diritto “a metà”, {v0, v1, … v(n/2)} sono sullo stesso lato di (x0,x1) e quindi sappiamo che non c’è intersezione, che “metà” del poligono.

    Caso 2: a Loro si intersecano.

    Questo caso è un po ‘ più complicato, ma siamo ancora in grado di restringere l’intersezione di una “metà” del poligono in un tempo costante. Ci sono 3 subcases:

    Caso 2.1: L’incrocio è tra i punti v0 e v(n/2)

    Abbiamo finito. La linea interseca il poligono.

    Caso 2.2: L’incrocio è più vicino a v0 (che è, al di fuori del poligono su v0 lato)

    Determinare se la linea (x0,x1) si interseca con la linea (v0,v1).

    Se poi non abbiamo finito, la linea non interseca il poligono.

    Se non, trovare l’intersezione, p. Se p è a destra della linea (v0, v(n/2)) quindi recurse in diritto “metà” del poligono, {v0, v1, …, v(n/2)}, in caso contrario recurse a sinistra “metà” {v0, v(n/2), … vn}.

    L’idea di base in questo caso è che tutti i punti del poligono sono a lato della linea (v0, v1). Se (x0, x1) è divergenti lontano da (v0, v1) su un lato della sua intersezione con (v0, v(n/2)). Sappiamo che su quel lato non ci può essere alcuna intersezione con il poligono.

    Caso 2.3: L’incrocio è più vicina a v(n/2)

    Questo caso è trattata in modo simile al Caso 2.2, ma utilizzando l’apposito vicino di casa di v(n/2).

    Abbiamo finito. Per ogni livello, e questo richiede due intersezioni di linee, una sinistra e destra per controllare e determinare la posizione di un punto è tutto su una riga. Ogni ricorsione divide il numero di vertici da 2 (tecnicamente li divide da almeno 4/3). E si ottiene un tempo di esecuzione di O(log n).

    • Si prega di chiarire che cosa è sinistra/destra metà del poligono. Forse sarebbe meglio usare termini v0->vk o vk->v0 supponendo che l’ordine è in senso ANTIORARIO.
    • Ogni volta che ho detto a sinistra/destra metà ho fatto chiarire, ho elencato i vertici in quel mezzo. In particolare, la metà di sinistra è i vertici che non sono di destra della riga (v0,v(n/2)), {v0, v1, …, v(n/2)}. Io uso il termine non è a destra, perché è l’insieme di vertici a sinistra della linea, in aggiunta a quelli sulla linea.
    • +1 Fino a quando ho trovato un contro-esempio. Nota: credo che il chiarimento è sbagliato. In senso ANTIORARIO ordine la metà destra è v0->v(n/2).
    • grazie per tirar fuori il mio breve descrizione.
    • Sì, hai ragione. Risolto.
    • Come si fa a scegliere x0 e x1? Voglio dire, se abbiamo scelto x0 e x1 per essere al di fuori del poligono, quindi intersezione non potrebbe mai accadere?

  2. 2

    Riquadri possono rivelarsi utili.

    Ricordiamo che una parte convessa di un affine spazio è l’intersezione di tutti i suoi busta iperpiani: si potrebbe ottenere un’approssimazione del poligono (leggere una “delimitazione poligono convesso”), considerando solo l’intersezione di un sottoinsieme della busta iperpiani, test di intersezione della linea con questa approssimazione, e perfezionare, se necessario.

    Tutto questo funziona meglio se si prevede un basso numero di intersezioni.

  3. 1

    Hai solo bisogno di trovare un punto che si trova sul lato sinistro della linea e un altro punto che si trova sul lato destro. Il restante domanda è come trovare punti rapidamente.

  4. 0

    prendere un casuale due punti A e B, da convesso dei poligoni.

    • se sono su diversi lati della linea, si intersecano
    • se sono sullo stesso lato, sia dei poligoni parti (diciamo in senso orario AB e BA) fare:
      • creare una linea parallela alla linea l che passa attraverso Un
      • trovare il punto di massima distanza dalla l su dei poligoni, che è come trovare il massimo in funzione prima monotona nondecreasing, e quindi monotona nonincreasing. questo può essere fatto in O(log n) da ternario di ricerca


    se questi due estremi i punti sono sul lato diverso della tua linea, linea interseca dei poligoni, altrimenti non

    Dal modo in cui è possibile trovare anche i reali punti di intersezione in O(log n) troppo.

    • L’algoritmo non è valido. 1) sequenze di vertici AB e BA non può essere valido per ternario di ricerca. 2) Avendo punti con distanza massima dal l su queste polilinee non garantisce che i punti sono su lati opposti della indagati linea. Anche quando la linea attraversa il poligono.
    • A distanza non deve essere assoluto (in modo che da un lato è negativo, sull’altro positivo), o per un lato l passa per A e B su un altro.
    • Non assoluta distanza sarebbe di aiuto, ma non in tutti i casi. Vedere jurajblaho.wz.cz/path2816.png . A->B in CW ordine non è valido per ternario di ricerca in quanto è in aumento, in diminuzione e, infine, aumentare.
    • una linea parallela alla linea l che passa attraverso: Se B è su questa linea, questo algoritmo non riesce…
    • No, non è un problema.
    • Non vedo perché questo si ottiene downvoted. Certo, l’estrema distanza-per-L algoritmo di ricerca ha per ottenere fisso, ma trovo l’idea ottima.
    • C. : Sì, l’idea è bella, ma l’algoritmo è semplicemente sbagliato. L’algoritmo è barare. Per me è come la descrizione macchine per il moto perpetuo. Sono anche ben progettato e sembra funzionare quando solo un piccolo dettaglio sarebbe risolto.

Lascia un commento