Un algoritmo O (n) per rilevare se una linea interseca un poligono convesso consiste nel verificare se un qualsiasi bordo del poligono interseca la linea e controllare se il numero di intersezioni è strano o pari.Algoritmo asintoticamente ottimale per calcolare se una linea interseca un poligono convesso
C'è un algoritmo asintoticamente più veloce, ad es. uno O (log n)?
La risposta di lhf è corretta. Ecco una versione che dovrebbe risolvere il problema con il suo.
Lascia che il poligono abbia i vertici v0, v1, ..., vn in senso antiorario. Lascia che i punti x0 e x1 siano sulla linea.
Nota due cose: in primo luogo, trovare l'intersezione di due linee (e determinarne l'esistenza) può essere eseguita in tempo costante. Secondo, determinare se un punto è a sinistra o a destra di una linea può essere fatto in tempo costante.
Seguiremo la stessa idea di base di lhf per ottenere un algoritmo O (log n). I casi base sono quando il poligono ha 2 o 3 vertici. Questi possono essere entrambi gestiti in tempo costante.
Determina se la linea (v0, v (n/2)) interseca la linea (x0, x1).
Caso 1: non si intersecano.
In questo caso la linea che ci interessa è a sinistra oa destra della linea che divide il poligono, e quindi possiamo recurse in quella metà del poligono. Specificamente, se x0 è alla sinistra di (v0, v (n/2)) allora tutti i vertici nella "metà" destra, {v0, v1, ... v (n/2)} si trovano sullo stesso lato di (x0, x1) e quindi sappiamo che non c'è intersezione in quella "metà" del poligono.
Caso 2: si intersecano.
Questo caso è un po 'più complicato, ma possiamo ancora restringere l'intersezione a una "metà" del poligono in tempo costante. Ci sono 3 sottocasi:
Caso 2.1: L'intersezione è tra i punti V0 e v (n/2)
Abbiamo finito. La linea interseca il poligono.
Caso 2.2: L'intersezione è più vicino a V0 (cioè al di fuori del poligono dalla parte di V0)
Determinare se la linea (x0, x1) si interseca con la linea (v0, v1).
Se non è così, abbiamo finito, la linea non interseca il poligono.
In caso affermativo, trovare l'intersezione, p. Se p è a destra della linea (v0, v (n/2)), quindi recita nella "metà" destra del poligono, {v0, v1, ..., v (n/2)}, altrimenti recurse a sinistra "metà" {v0, v (n/2), ... vn}.
L'idea di base in questo caso è che tutti i punti nel poligono sono su un lato della linea (v0, v1). Se (x0, x1) è divergente da (v0, v1) su un lato della sua intersezione con (v0, v (n/2)). Sappiamo che da quella parte non può esserci intersezione con il poligono.
Caso 2.3: L'intersezione è più vicino a v (n/2)
Questo caso è gestita in modo simile al caso 2.2 ma utilizzando il vicino appropriata di v (n/2).
Abbiamo finito. Per ogni livello, ciò richiede due intersezioni di linea, un controllo left-right e la determinazione di dove un punto si trova su una linea. Ogni ricorsione divide il numero di vertici per 2 (tecnicamente li divide di almeno 4/3). E così otteniamo un runtime di O (log n).
I riquadri di contenimento possono rivelarsi utili.
Ricorda che una parte convessa di uno spazio affine è l'intersezione di tutti gli iperpiani dell'inviluppo: potresti ottenere un'approssimazione del tuo poligono (leggi un "poligono convesso di delimitazione") considerando solo l'intersezione di un sottoinsieme della busta iperpiani, prova per l'intersezione della tua linea con questa approssimazione e raffina se necessario.
Tutto questo funziona meglio se si prevede un basso numero di incroci.
Hai solo bisogno di trovare un punto A che si trova sul lato sinistro della linea e un altro punto che è sul lato destro. La domanda rimanente è come trovare rapidamente quei punti.
prendere a caso due punti A e B dal poligono convesso.
se quei due punti più lontani sono lato diverso della vostra linea, linea interseca poligon, altrimenti non fa
Tra l'altro puoi anche trovare i punti di intersezione reali in O (log n).
L'algoritmo non è valido. 1) le sequenze di vertici AB e BA potrebbero non essere valide per la ricerca ternaria. 2) Avere punti con distanza massima da l su queste polilinee non garantisce che i punti si trovino su lati opposti della linea investigata. Anche quando la linea attraversa il poligono. –
O una distanza non deve essere assoluta (in modo che su un lato è negativo, su altro positivo), o per un lato I passa attraverso A e attraverso B su un altro. – Sarmun
La distanza non assoluta sarebbe di aiuto, ma non in tutti i casi. Vedi http://jurajblaho.wz.cz/path2816.png. L'ordine A-> B in CW non è valido per la ricerca ternaria in quanto aumenta, diminuisce e infine aumenta. –
Penso che this article fornisce una soluzione O (log n) chiara. Trova gli estremi nella direzione perpendicolare alla linea indicata.
Si prega di chiarire cosa è metà sinistra/destra del poligono. Forse sarebbe meglio usare i termini v0-> vk o vk-> v0 assumendo che l'ordine sia CCW. –
Ogni volta che ho detto metà sinistra/destra ho chiarito, ho elencato i vertici in quella metà. Nello specifico, la metà sinistra è i vertici che non si trovano a destra della linea (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 più quelli sulla linea. –
+1 Fino a quando non trovo un contro-esempio. Nota: penso che il chiarimento sia sbagliato. Nell'ordine CCW, la metà destra è v0-> v (n/2). –