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

Question

Un O (n) algoritmo per rilevare se una linea interseca un poligono convesso consiste nel verificare se qualsiasi bordo delle interseca poligono linea, e cerca se il numero di incroci è pari o dispari.

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

Answer 1

La risposta di LHF è vicino a corretto. Ecco una versione che dovrebbe risolvere il problema con la sua.

Lasciate che il poligono Hanno vertici v0, v1, ..., vn in ordine antiorario. Lasciate che i punti x0 e x1 essere sulla linea.

Nota due cose: primo, trovare l'intersezione di due linee (e ne determinano la sua esistenza) può essere fatto in tempo costante. In secondo luogo, determinare se un punto è a sinistra oa destra di una linea può essere fatto in tempo costante.

Si seguirà la stessa idea di base di LHF per ottenere un algoritmo O (log n). I casi sono di base quando il poligono ha 2 o 3 vertici. Questi possono essere entrambi gestiti in tempo costante.

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

Caso 1:. Loro non si intersecano

In questo caso la linea che interessa è sia a sinistra oa destra della linea scissione del poligono, e in modo da poter ricorsivamente che la metà del poligono. In particolare, se x0 è a sinistra di (v0, v (n / 2)) allora tutti i vertici nel giusto "metà", {v0, v1, ... v (n / 2)} sono sullo stesso lato di (x0, x1) e così sappiamo che non c'è intersezione in quella "metà" del poligono.

Caso 2: Essi si intersecano

.

Questo caso è un po 'più complicato, ma possiamo ancora restringere l'incrocio ad una "metà" del poligono in tempo costante. Ci sono 3 sottocasi:

Caso 2.1: L'intersezione è tra i punti V0 e v (n / 2)

è fatto. La linea interseca il poligono.

Caso 2.2: L'intersezione è più vicino a v0 (che è, al di fuori del poligono dalla parte di V0)

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

Se non, allora abbiamo finito, la linea non fa intersecano il poligono.

Se è così, trovare l'intersezione, p. Se p è a destra della linea (v0, v (n / 2)) poi ricorsivamente destra "metà" del poligono, {v0, v1, ..., v (n / 2)}, altrimenti recurse al "mezzo" sinistra {V0, v (n / 2), ... vn}.

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

Caso 2.3: L'intersezione è più vicino a v (n / 2)

Questo caso viene gestito in modo simile a Caso 2.2, ma utilizzando il vicino appropriata di v (n / 2).

è fatto. Per ogni livello, ciò richiede due intersezioni delle linee, un controllo sinistra-destra, e determinare dove un punto è su una linea. Ogni ricorsione divide il numero di vertici da 2 (tecnicamente li divide per almeno 4/3). E così otteniamo un tempo di esecuzione di O (log n).

Answer 2

questo articolo dà una chiara O (log n) soluzione. Trova gli estremi nella direzione perpendicolare alla linea data.

Answer 3

rettangoli di selezione possono essere utili.

Si ricordi che una parte convessa di uno spazio affine è l'intersezione di tutti i suoi iperpiani busta: si potrebbe ottenere un'approssimazione del poligono (leggere un "delimitazione convessa poligono") considerando soltanto l'intersezione di un sottoinsieme dei iperpiani busta , test per l'intersezione della linea con questa approssimazione, e perfezionare se necessario.

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

Answer 4

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

Answer 5

richiedere casuale due punti A e B dal poligono convesso.

• se sono sul lato diverso della linea, si intersecano
• se sono sullo stesso lato, su entrambi le parti poligon (diciamo in senso orario e AB BA) do:
  
  • creare una linea parallela alla linea L che passa attraverso un
    
  • punto ritrovamento alla distanza massima dal l sul poligono, che è lo stesso come trovare massima in funzione che viene prima monotono non decrescente, e quindi monotona non crescente. questo può essere fatto in O (log n) da ternario di ricerca

se quei due punti più lontani sono lato diverso della vostra linea, interseca linea Poligon, altrimenti non fa

Tra l'altro si possono anche trovare punti di intersezione effettivi in ??O (log n) anche.