Come faccio a determinare se due poligoni convessi intersecano?

Question

Supponiamo che ci sono un certo numero di poligoni convessi su un piano, forse una mappa. Questi poligoni possono urtare contro l'altro e condividere un vantaggio, ma non possono sovrapporsi.

Per testare se due poligoni P e D sovrapposizione, prima posso testare ciascun bordo in P per vedere se interseca qualsiasi i bordi in D . Se viene trovato un incrocio, dichiaro che P e Q si intersecano. Se nessuno intersecano, poi devo verificare il caso che P è completamente contenuta dalla D , e viceversa. Poi, c'è il caso che P == Q . Infine, c'è il caso che condividono un paio di bordi, ma non tutti. (Questi ultimi due casi possono probabilmente essere considerati come lo stesso caso generale, ma che potrebbero non essere importante.)

Ho un algoritmo che rileva in cui due segmenti di linea si intersecano. Se i due segmenti sono co-lineari, non sono considerati intersecare per i miei scopi.

Ti ho enumerato correttamente i casi? Eventuali suggerimenti per il test per questi casi?

Si noti che non sto cercando di trovare il nuovo poligono convesso che è l'incrocio, voglio solo sapere se esiste un incrocio. Ci sono molti algoritmi ben documentati per trovare l'incrocio, ma non hanno bisogno di passare attraverso tutto lo sforzo.

Answer 1

Si potrebbe utilizzare questo algoritmo di collisione :

  

Per essere in grado di decidere se due poligoni convessi si intersecano (si toccano) siamo in grado di utilizzare la separazione Axis Teorema. In sostanza:

     

  
• Se due poligoni convessi non si intersecano, esiste una linea che passa tra loro.
  
• Tale linea esiste solo se uno dei lati di uno dei poligoni forma una tale linea.
  

     

La prima affermazione è facile. Dal momento che i poligoni sono entrambi convessi, sarete in grado di tracciare una linea con un poligono da una parte e l'altra del poligono sul lato opposto a meno che non si intersecano. Il secondo è leggermente meno intuitivo. Cerca figura 1. Salvo il più vicino lati dei poligoni sono parallele tra loro, il punto dove ottengono vicini l'uno all'altro è il punto in cui un angolo di un poligono ottiene più vicino ad un lato dell'altro poligono. Questo lato sarà quindi formare un asse di separazione tra i poligoni. Se i lati sono paralleli, entrambi sono separazione assi.

     

     

Così come questo concretamente aiutarci a decidere se poligono A e B si intersecano? Ebbene, andiamo appena su ogni lato di ogni poligono e verificare se esso forma un asse di separazione. Per fare questo useremo po 'di matematica vettore di base per schiacciare tutti i punti di entrambi i poligoni su una linea che è perpendicolare alla linea di separazione potenziale (vedi figura 2). Ora l'intero problema è convenientemente 1-dimensionale. Possiamo determinare una regione in cui i punti per ogni poligono menzogna, e questa linea è un asse di separazione se queste regioni non si sovrappongono.

     

     

Se, dopo aver controllato ogni riga da entrambi i poligoni, è stato trovato nessun asse di separazione, è stato dimostrato che i poligoni si intersecano e qualcosa deve essere fatto su di esso.

Answer 2

• se i poligoni sono sempre convessa, prima calcolare l'angolo di una linea tracciata dal centro a centro dei poligoni. è quindi possibile eliminare la necessità di testare segmenti marginali nella metà del poligono (s) 180 gradi allontanamento dall'altra poligono (s).

• per eliminare i bordi, iniziare con il poligono a sinistra. prendere il segmento di linea dal centro del poligono perpendicolare al segmento linea dal punto precedente, e tocca entrambi i lati del poligono. chiamare questo segmento p, con vertici p1 e p2. Quindi, per tutti i vertici se la coordinata x è minore di P1.x e p2.x Tale vertice può andare in "secchio sicuro".

• se così non fosse, è necessario controllare per assicurarsi che sia sul lato "sicuro" della linea (basta controllare coordina anche la y)

-Se un segmento nel poligono ha tutti i vertici del "secchio sicuro" si può ignorarlo.

-reverse la polarità e pertanto si è "giusto oriented" per il secondo poligono.

Answer 3

I tuoi casi di test dovrebbero funzionare, dal momento che si sta controllando il caso in cui i poligoni non si intersecano a tutti (completamente al di fuori o completamente all'interno), così come dove non v'è alcuna forma di intersezione parziale (bordi si intersecano sempre se ci è sovrapposizione).

Per i test, vorrei solo fare in modo di testare ogni combinazione potenziale. Quella mancante sopra da quello che vedo è un singolo bordo condiviso, ma un poli contenuta nell'altra. Vorrei anche aggiungere test per alcune forme poli più complesse, da tri -.> Molti lati, solo per precauzione

Inoltre, se si ha un poli a forma di U che completamente circondato il poli, ma non si sovrappongono, credo che il tuo caso sarebbe gestire questo, ma vorrei aggiungere che come controllo, pure.

Answer 4

Dal altCognito già ti ha dato una soluzione, io segnalo un ottimo libro sulla geometria computazionale che potrebbe interessarti.

Answer 5

GJK collisione href="https://mollyrocket.com/forums/viewtopic.php?t=245" rel="nofollow noreferrer"> dovrebbe lavoro .

Answer 6

Ecco un'idea:

• Trova il punto centrale di ogni poligono

• Trova i due punti di ogni poligono più vicino al punto centrale dell'altro. Saranno punti adiacenti in poligono convesso. Questi definiscono il bordo più vicino di ogni poligono, chiamiamoli i punti {A, B} e {Y, Z}

• Trova l'intersezione delle linee AB e YZ. Se i segmenti di linea attraversano (l'intersezione su AB compreso tra A e B), poligoni si intersecano. Se AB e XY sono paralleli ignorare questa condizione, il passo successivo intercetterà il problema.

• C'è un altro caso è necessario verificare la presenza, che è quando i poligoni si intersecano abbastanza pesante che AB e XY sono completamente passati a vicenda e in realtà non si intersecano. Per intercettare questo caso, calcolare le distanze perpendicolari AB e XY per ogni punto poligoni centrali. Se uno dei due punto centrale è più vicino al segmento di linea del poligono opposta poligono si sovrappongono pesantemente.

Answer 7

Esistono diversi modi per rilevare intersezione e / o contenimento tra poligono convesso. Tutto dipende da come efficiente si desidera l'algoritmo di essere. Considerare due poligoni convessi R e B con R e B vertici, rispettivamente:

1. linea spazzata algoritmo basato. Come lei ha ricordato è possibile eseguire una procedura di linea di sweep e mantenere gli intervalli risultanti dall'intersezione dei poligoni con la linea di spazzare. Se in qualsiasi momento gli intervalli si sovrappongono, quindi i poligoni si intersecano. La complessità è O ((r + b) log (r + b)) tempo.
2. algoritmo basato Rotating Compassi . Vedere qui e qui per maggiori dettagli. La complessità è O (r + b) tempo.
3. I metodi più efficienti possono essere trovati qui e qui . Questi algoritmi prendono O (log r + log b) tempo.