Intersezione di due poligoni convessi

Question

Ho due poligoni convessi. I poligoni sono implementati come liste cicliche dei loro vertici. Come trovare un'intersezione di questi due poligoni?

Answer 1

For each edge V1-V2 in the first polygon, 
    Let H := Half-plane tangenting V1-V2, with the remaining 
     vertices on the "inside". 
    Let C := New empty polygon. 
    For each edge V3-V4 in the second polygon, 
     Let X := The intersection between V3-V4 and H. 
     If V3 inside H, and V4 is outside H then, 
      Add V3 to C. 
      Add X to C. 
     Else if both V3 and V4 lies outside H then, 
      Skip. 
     Else if V3 outside H, and V4 is inside H then, 
      Add X to C. 
     Else 
      Add V3 to C. 
    Replace the second polygon with C. 

Questo dovrebbe essere sufficiente per un utilizzo semplice; 10-20 vertici e non ricalcolare ogni fotogramma. — O (n)

---

Ecco alcuni link:

• Computer Graphics I – Polygon Clipping and Filling (pdf)
• rosettacode.org – Sutherland-Hodgman polygon clipping

Answer 2

è possibile beneficiare del fatto che entrambi i poligoni sono convessi. E con questa conoscenza è possibile ottenere il tempo O (n) utilizzando l'algoritmo della linea di scansione successiva:

Trova punti di punta in entrambi i poligoni. Per semplicità supponiamo di non avere bordi orizzontali. Crea elenchi di bordi che contribuiscono ai limiti sinistro e destro di un poligono.

Mentre si spiana il piano verso il basso, si memorizzano 4 spigoli. left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2. Non hai bisogno di alcun complesso per battere i bordi, perché ce ne sono solo quattro. Puoi trovare il prossimo punto dell'evento semplicemente ripetendo tutte le opzioni possibili.

In corrispondenza di ciascun punto di evento, alcuni bordi appaiono sul limite della loro intersezione. Fondamentalmente, in ogni punto dell'evento puoi avere uno dei casi gratuiti (vedi la foto).

Answer 3

Oltre @ bella descrizione aereo-sweep di Yola, c'è un algoritmo di tempo lineare descritto nel Computational Geometry in C, Capitolo 7. E C & codice Java è disponibile (presso lo stesso link). Esistono diversi casi degenerati difficili, ad esempio quando i due poligoni si intersecano in un punto o l'intersezione è un segmento.