Line clipping to arbitary 2D poligono

Question

Se ottengo un segmento di linea che è stato abbastanza lungo da attraversare un dato poligono, che potrebbe essere poligono concavo o convesso. Come ho trovato tutti i segmenti di luce intersecati che erano contenuti nel poligono?

Se la regione di destinazione non è poligonale, ma una curva funzione curva o spline implicita, come fare?

Grazie!

Answer 1

Non c'è davvero una soluzione semplice al problema, specialmente con le curve (beziers e spline). Oltre alla complessità del ritaglio poligonale, c'è una notevole sfida nel ricostruire le curve troncate (supponendo che si desideri che il risultato del ritaglio rimanga come beziers e spline e non solo approssimazioni della linea appiattita).

Ho recentemente rilasciato un aggiornamento beta * alla mia libreria di ritaglio di poligoni 'Clipper' che esegue il clipping linea-poligono e linea (dove anche le linee possono essere curve). Tuttavia, mentre la libreria principale è scritta in Delphi, C++ & C#, il nuovo codice beta è finora solo in Delphi che potrebbe non essere di aiuto. Tuttavia se osservate il codice vedrete perché dichiaro che non esiste una soluzione 'semplice'.

• Modifica 15 luglio 2011: Questo 'aggiornamento' mai andato oltre questa versione beta ed è ora semplicemente 'proof-of-concept'. Ora è basato su una vecchia versione della mia libreria Clipper e necessiterebbe di una maggiore riscrittura per essere mantenibile ed estensibile. (A un certo punto io possa rivisitare ma sono attualmente intento a migliorare ulteriormente la libreria di base.) Tuttavia, questo codice Delphi 'proof-of-concept' può essere scaricato here

Answer 2

• Fase uno: trovare tutti i punti di intersezione , in qualsiasi ordine. Per poligono, devi trovare l'intersezione della linea rossa e la linea di ogni segmento. Basta risolvere il sistema di due equazioni lineari. Se la soluzione è vincolata ai limiti del segmento di poligono, è necessario avere un'intersezione tra .
• Passo due: ordinare i punti trovati per la posizione sulla linea rossa. Sai che il primo e l'ultimo punto sono quelli esteriori. "Outerness" ribalta ogni punto: esterno-interno-esterno e così via. Tra due punti esterni adiacenti si ha un segmento di linea interno (verde). Modifica: non vero ... Inizia con il punto # 0, il segmento # 0 - # 1 è interno, il successivo è esterno, il successivo è interno di nuovo e così via.

Se la regione non è poligono, ma è data da una funzione implicita, è necessario trovare dove tale funzione è uguale alla linea rossa (l'approccio dipende dalla funzione, ovviamente).