Trovare un raggio che interseca un poligono come numero di volte possibile

Question

Ecco un esercizio interessante:

Sia P un semplice, ma non necessariamente convesso, poligono e q un punto arbitrario non necessariamente in P.

design un algoritmo efficace per trovare un segmento di linea proveniente da q che interseca il massimo numero di bordi di P.

in altre parole, se in piedi al punto q, in quale direzione si dovrebbe puntare una pistola in modo che il proiettile passerà attraverso il maggior numero di muri?

Una pallottola attraverso un vertice di P ottiene credito per un solo muro.

Un algoritmo O (n log n) è possibile. n è il numero di vertici o spigoli, poiché è un poligono, il numero di spigoli equivale approssimativamente al numero di vertici.

Ecco il mio pensiero:

Collegare q con tutti i vertici (diciamo ci sono N vertici) in P prima. Ci saranno N linee, o N-1 coppie di linee.

La linea di tiro finale deve essere tra queste coppie. Quindi dobbiamo trovare la coppia che contiene il maggior numero di bordi.

Non penso che questa soluzione sia O (n log n).

Qualche idea?

Answer 1

Ebbene, prima trasformare i punti di coordinate in un sistema polare centrato P.

• Senza perdita di generalità, scegliamo senso orario speciale con rispetto all'angolo di coordinate.
• Ora facciamo una passeggiata circolare in sequenza lungo tutti i bordi del poligono, e notiamo il punto iniziale e finale di quei bordi, dove la camminata ci porta in senso orario rispetto a P.
• chiama il punto finale di tale spigolo un 'culo', e il punto di partenza a 'testa'. Tutto ciò dovrebbe essere fatto in O (n). Ora dovremo ordinare quelle teste e le estremità, quindi con quicksort potrebbe essere O(nlog(n)). Li stiamo ordinando in base alla loro coordinata angolare (φ) dal più piccolo φ verso l'alto, assicurando che in caso di coordinate uguali φ le teste siano considerate più piccole dei butts (questo è importante per rispettare l'ultima regola del problema).
• Una volta terminato, inizieremo a percorrerle dal φ più piccolo, incrementando la somma di corsa ogni volta che incontriamo un calcio, e decrementando ogni volta che incontriamo una testa, notando un massimo globale, che sarà un intervallo sulla coordinata φ . Questo dovrebbe essere fatto anche in O (n), quindi la complessità complessiva è O(nlog(n)).

Ora mi diresti perché stai facendo questo tipo di domande?

Answer 2

Ho usato l'algoritmo di Boris Stitnicky e ho scritto la mia soluzione in Java. Ma ho scelto la direzione in senso antiorario e per verificare quale punto di un intervallo è il punto di partenza e quale punto è la fine di un intervallo in cui ho usato il prodotto incrociato. Puoi trovarlo qui: https://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java