Come verificare se il segmento di linea interseca un rettangolo?

Question

Se si dispone di 2 punti (x1, y1) e (x2, y2), che rappresentano due angoli opposti di un rettangolo e altri 2 punti (x3, y3) e (x4, y4), che rappresentano 2 punti finali di un segmento di linea, come puoi verificare se il segmento di linea interseca il rettangolo?

(Il segmento di linea è solo il segmento contenuta tra gli endpoint indicate. Non è una linea di lunghezza infinita definita da questi due punti.)

Answer 1

Un'opzione molto semplice sarebbe quella di utilizzare a standard algorithm for checking whether two line segments intersect per verificare se la linea i segmenti intersecano uno qualsiasi dei quattro segmenti di linea che compongono gli angoli della scatola. È molto efficiente dal punto di vista computazionale verificare se due segmenti di linea si intersecano, quindi mi aspetto che questo possa essere eseguito molto rapidamente.

Spero che questo aiuti!

Answer 2

Ottieni il prodotto punto di tutti e 4 i vertici (gli angoli del rettangolo) con il vettore di direzione del segmento di linea. Se tutti e 4 hanno valori dello stesso segno, allora tutti i vertici si trovano sullo stesso lato della linea (non il segmento di linea, ma la linea infinita) e quindi la linea non interseca il rettangolo. Questo approccio è possibile solo per il rilevamento di intersezioni 2D. Questo può essere usato per filtrare la maggior parte velocemente (usando solo moltiplicazioni e aggiunte). Dovrai eseguire ulteriori controlli per i segmenti di linea anziché per le linee.

Answer 3

Per capire come derivare la formula per verificare se un segmento di linea interseca un rettangolo, è importante ricordare le proprietà dello vector dot product.

Rappresenta il segmento di linea come un vettore unitario e una distanza tra il punto iniziale del segmento di linea e l'origine. Ecco qualche codice C# per calcolare che dalle PointF variabili a_ptStart e a_ptEnd, utilizzando un Vector:

Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y); 
double dLengthLine = vecLine.Length; 
vecLine /= dLengthLine; 
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y)); 

Avrete anche bisogno di calcolare il vettore perpendicolare, e la sua distanza dall'origine, per il segmento di linea. La rotazione di un vettore di unità di 90 ° è easy.

Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X); 
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y)); 

Supponendo che i quattro angoli del rettangolo sono in Vector variabili chiamate vecRect1, vecRect2, vecRect3 e vecRect4, calcolare la distance tra la linea-segmento e tutti e quattro gli angoli del rettangolo di selezione rettangolo del bersaglio:

double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine; 
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine; 
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine; 
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine; 
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2, 
    Math.Min(dPerpLineDist3, dPerpLineDist4))); 
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2, 
    Math.Max(dPerpLineDist3, dPerpLineDist4))); 

Se tutte le distanze sono positive o tutte le distanze sono negative, il rettangolo si trova su un lato della linea o sull'altro, quindi non c'è intersezione. (Rettangoli Zero-misura sono considerati non intersecarsi con qualsiasi linea-segmento.)

if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0 
     || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0) 
    /* no intersection */; 

Avanti, progetto di tutti e quattro gli angoli del bersaglio rettangolo sulla linea-segmento. Questo ci dà la distanza tra l'origine della linea e la proiezione dell'angolo rettangolo su quella linea.

double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine; 
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine; 
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine; 
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine; 
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2, 
    Math.Min(dDistLine3, dDistLine4))); 
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2, 
    Math.Max(dDistLine3, dDistLine4))); 

Se i punti del rettangolo non rientrano nell'estensione del segmento di linea, non vi sono intersezioni.

if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine) 
    /* no intersection */; 

Credo sia sufficiente.