Come verificare se un segmento di linea interseca una rectange allineata all’asse in 2D?

Come verificare se un segmento di linea interseca una rectange allineata all’asse in 2D? Il segmento è definito con le sue due estremità: p1, p2. Il rettangolo è definito con i punti in alto a sinistra e in basso a destra.

Il poster originale voleva RILEVARE un’intersezione tra un segmento di linea e un poligono. Non è stato necessario LOCARE l’intersezione, se ce n’è una. Se è così che intendi, puoi fare meno lavoro di Liang-Barsky o Cohen-Sutherland:

Lascia che i punti finali del segmento siano p1 = (x1 y1) e p2 = (x2 y2).
Lascia che gli angoli del rettangolo siano (xBL yBL) e (xTR yTR).

Quindi tutto ciò che devi fare è

A. Controlla se tutti e quattro gli angoli del rettangolo si trovano sullo stesso lato della linea. L’equazione implicita per una linea che attraversa p1 e p2 è:

F (xy) = (y2-y1) * x + (x1-x2) * y + (x2 * y1-x1 * y2)

Se F (xy) = 0, (xy) è ON sulla linea.
Se F (xy)> 0, (xy) è “sopra” la linea.
Se F (xy) <0, (xy) è "sotto" la linea.

Sostituisci tutti e quattro gli angoli in F (xy). Se sono tutti negativi o tutti positivi, non c’è intersezione. Se alcuni sono positivi e alcuni negativi, andare al passaggio B.

B. Proiettare l’endpoint sull’asse x e verificare se l’ombra del segmento interseca l’ombra del poligono. Ripeti sull’asse y:

Se (x1> xTR e x2> xTR), nessuna intersezione (la linea è a destra del rettangolo).
Se (x1 Se (y1> yTR e y2> yTR), nessuna intersezione (la linea è sopra il rettangolo).
Se (y1 altrimenti, c’è un incrocio. Do Cohen-Sutherland o qualsiasi altro codice è stato menzionato nelle altre risposte alla tua domanda.

Puoi, ovviamente, prima B, poi A.

Alejo

Ha scritto una soluzione abbastanza semplice e funzionante:

bool SegmentIntersectRectangle(double a_rectangleMinX, double a_rectangleMinY, double a_rectangleMaxX, double a_rectangleMaxY, double a_p1x, double a_p1y, double a_p2x, double a_p2y) { // Find min and max X for the segment double minX = a_p1x; double maxX = a_p2x; if(a_p1x > a_p2x) { minX = a_p2x; maxX = a_p1x; } // Find the intersection of the segment's and rectangle's x-projections if(maxX > a_rectangleMaxX) { maxX = a_rectangleMaxX; } if(minX < a_rectangleMinX) { minX = a_rectangleMinX; } if(minX > maxX) // If their projections do not intersect return false { return false; } // Find corresponding min and max Y for min and max X we found before double minY = a_p1y; double maxY = a_p2y; double dx = a_p2x - a_p1x; if(Math::Abs(dx) > 0.0000001) { double a = (a_p2y - a_p1y) / dx; double b = a_p1y - a * a_p1x; minY = a * minX + b; maxY = a * maxX + b; } if(minY > maxY) { double tmp = maxY; maxY = minY; minY = tmp; } // Find the intersection of the segment's and rectangle's y-projections if(maxY > a_rectangleMaxY) { maxY = a_rectangleMaxY; } if(minY < a_rectangleMinY) { minY = a_rectangleMinY; } if(minY > maxY) // If Y-projections do not intersect return false { return false; } return true; } 

Poiché il tuo rettangolo è allineato, Liang-Barsky potrebbe essere una buona soluzione. È più veloce di Cohen-Sutherland, se qui la velocità è significativa.

Spiegazione Siggraph
Un’altra buona descrizione
E, naturalmente, Wikipedia

Puoi anche creare un rettangolo fuori dal segmento e verificare se l’altro rettangolo si scontra con esso, poiché si tratta solo di una serie di confronti. Dalla fonte di pygame:

 def _rect_collide(a, b): return ax + aw > bx and bx + bw > ax and \ ay + ah > by and by + bh > ay 

Utilizzare l’ algoritmo Cohen-Sutherland .

È usato per il clipping ma può essere leggermente modificato per questa attività. Divide lo spazio 2D in una tavola da tris con il rettangolo come “quadrato centrale”.
poi controlla per vedere quale delle nove regioni si trovano in ciascuna delle due linee della tua linea.

  • Se entrambi i punti sono a sinistra, a destra, in alto o in basso, respingi banalmente.
  • Se uno dei due punti è dentro, accettate banalmente.
  • Nei rari casi rimanenti puoi fare in modo che la matematica si intersechi con qualsiasi lato del rettangolo sia ansible intersecare, in base alle regioni in cui si trovano.

O semplicemente usa / copia il codice già nel metodo Java

 java.awt.geom.Rectangle2D.intersectsLine(double x1, double y1, double x2, double y2) 

Ecco il metodo dopo essere stato convertito in statico per comodità:

 /** * Code copied from {@link java.awt.geom.Rectangle2D#intersectsLine(double, double, double, double)} */ public class RectangleLineIntersectTest { private static final int OUT_LEFT = 1; private static final int OUT_TOP = 2; private static final int OUT_RIGHT = 4; private static final int OUT_BOTTOM = 8; private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) { int out = 0; if (rectWidth <= 0) { out |= OUT_LEFT | OUT_RIGHT; } else if (pX < rectX) { out |= OUT_LEFT; } else if (pX > rectX + rectWidth) { out |= OUT_RIGHT; } if (rectHeight <= 0) { out |= OUT_TOP | OUT_BOTTOM; } else if (pY < rectY) { out |= OUT_TOP; } else if (pY > rectY + rectHeight) { out |= OUT_BOTTOM; } return out; } public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) { int out1, out2; if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) { return true; } while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) { if ((out1 & out2) != 0) { return false; } if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) { double x = rectX; if ((out1 & OUT_RIGHT) != 0) { x += rectWidth; } lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1) / (lineX2 - lineX1); lineX1 = x; } else { double y = rectY; if ((out1 & OUT_BOTTOM) != 0) { y += rectHeight; } lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1) / (lineY2 - lineY1); lineY1 = y; } } return true; } } 

Una rapida ricerca su Google ha fatto apparire una pagina con codice C ++ per testare l’intersezione.

Fondamentalmente verifica l’intersezione tra la linea e ogni bordo o rettangolo.

Codice di intersezione rettangolo e linea

Ho fatto una piccola soluzione di tovagliolo

Quindi trova m e c e quindi l’equazione y = mx + c

 y = (Point2.Y - Point1.Y) / (Point2.X - Point1.X) 

Sostituire le coordinate P1 per trovare ora c

Ora per un vertice del rettangolo, inserisci il valore X nell’equazione della linea, ottieni il valore Y e verifica se il valore Y si trova nei limiti del rettangolo mostrati di seguito

(puoi trovare i valori costanti X1, X2, Y1, Y2 per il rettangolo tale che)

 X1 <= x <= X2 & Y1 <= y <= Y2 

Se il valore Y soddisfa la condizione sopra e si trova tra (Punto1.Y, Punto2.Y) - abbiamo un'intersezione. Prova ogni vertice se questo non riesce a fare il taglio.

Stavo guardando un problema simile ed ecco cosa mi è venuto in mente. Prima stavo confrontando i bordi e ho realizzato qualcosa. Se il punto medio di un bordo che si trova all’interno dell’asse opposto del primo riquadro si trova a metà della lunghezza di quel bordo dei punti esterni sul primo nello stesso asse, allora c’è un’intersezione di quel lato da qualche parte. Ma quello stava pensando 1 dimensionalmente e bisognava guardare da ogni lato della seconda scatola per capire.

Improvvisamente mi è venuto in mente che se trovi il “punto medio” del secondo riquadro e confronti le coordinate del punto medio per vedere se cadono entro 1/2 lunghezza di un lato (del secondo riquadro) delle dimensioni esterne del primo , poi c’è un incrocio da qualche parte.

 ie box 1 is bounded by x1,y1 to x2,y2 box 2 is bounded by a1,b1 to a2,b2 the width and height of box 2 is: w2 = a2 - a1 (half of that is w2/2) h2 = b2 - b1 (half of that is h2/2) the midpoints of box 2 are: am = a1 + w2/2 bm = b1 + h2/2 So now you just check if (x1 - w2/2) < am < (x2 + w2/2) and (y1 - h2/2) < bm < (y2 + h2/2) then the two overlap somewhere. If you want to check also for edges intersecting to count as 'overlap' then change the < to <= 

Ovviamente si potrebbe facilmente confrontare il contrario (controllando i punti medi del riquadro1 in una lunghezza di 1/2 delle dimensioni esterne del riquadro 2)

E ancora più semplificazione: sposta il punto medio di metà lunghezza ed è identico al punto di origine di quella casella. Il che significa che ora puoi controllare solo quel punto per rientrare nell'intervallo di delimitazione e spostando il piano verso l'alto e verso sinistra, l'angolo inferiore è ora l'angolo inferiore della prima casella. Molto meno matematica:

 (x1 - w2) < a1 < x2 && (y1 - h2) < b1 < y2 [overlap exists] 

o non sostituito:

 ( (x1-(a2-a1)) < a1 < x2 ) && ( (y1-(b2-b1)) < b1 < y2 ) [overlap exists] ( (x1-(a2-a1)) <= a1 <= x2 ) && ( (y1-(b2-b1)) <= b1 <= y2 ) [overlap or intersect exists] 

esempio di codifica in PHP (sto usando un modello di oggetti che ha metodi per cose come getLeft (), getRight (), getTop (), getBottom () per ottenere le coordinate esterne di un poligono e ha anche un getWidth () e getHeight () – a seconda di quali parametri sono stati alimentati, calcolerà e memorizzerà nella cache le incognite – cioè posso creare un poligono con x1, y1 e … w, h o x2, y2 e può calcolare gli altri)

Io uso ‘n’ per designare il ‘nuovo’ object da verificare per la sovrapposizione ($ nItem è un’istanza del mio object poligono) – gli elementi da testare di nuovo [questo è un programma di bin / sort nello zaino] si trovano in un array che consiste più istanze dello (stesso) object poligono.

 public function checkForOverlaps(BinPack_Polygon $nItem) { // grab some local variables for the stuff re-used over and over in loop $nX = $nItem->getLeft(); $nY = $nItem->getTop(); $nW = $nItem->getWidth(); $nH = $nItem->getHeight(); // loop through the stored polygons checking for overlaps foreach($this->packed as $_i => $pI) { if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) { return false; } } return true; } 

Alcuni esempi di codice per la mia soluzione (in PHP):

 // returns 'true' on overlap checking against an array of similar objects in $this->packed public function checkForOverlaps(BinPack_Polygon $nItem) { $nX = $nItem->getLeft(); $nY = $nItem->getTop(); $nW = $nItem->getWidth(); $nH = $nItem->getHeight(); // loop through the stored polygons checking for overlaps foreach($this->packed as $_i => $pI) { if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) { return true; } } return false; } 

Ecco una versione javascript della risposta di @ metamal

 var isRectangleIntersectedByLine = function ( a_rectangleMinX, a_rectangleMinY, a_rectangleMaxX, a_rectangleMaxY, a_p1x, a_p1y, a_p2x, a_p2y) { // Find min and max X for the segment var minX = a_p1x var maxX = a_p2x if (a_p1x > a_p2x) { minX = a_p2x maxX = a_p1x } // Find the intersection of the segment's and rectangle's x-projections if (maxX > a_rectangleMaxX) maxX = a_rectangleMaxX if (minX < a_rectangleMinX) minX = a_rectangleMinX // If their projections do not intersect return false if (minX > maxX) return false // Find corresponding min and max Y for min and max X we found before var minY = a_p1y var maxY = a_p2y var dx = a_p2x - a_p1x if (Math.abs(dx) > 0.0000001) { var a = (a_p2y - a_p1y) / dx var b = a_p1y - a * a_p1x minY = a * minX + b maxY = a * maxX + b } if (minY > maxY) { var tmp = maxY maxY = minY minY = tmp } // Find the intersection of the segment's and rectangle's y-projections if(maxY > a_rectangleMaxY) maxY = a_rectangleMaxY if (minY < a_rectangleMinY) minY = a_rectangleMinY // If Y-projections do not intersect return false if(minY > maxY) return false return true }