how general example graphics geometry 2d

graphics - general - ¿Cómo probar si un segmento de línea intersecta una rectángulos alineada con el eje en 2D?



java 2d graphics (12)

¿Cómo probar si un segmento de línea intersecta una rectángulos alineada con el eje en 2D? El segmento se define con sus dos extremos: p1, p2. El rectángulo se define con puntos arriba a la izquierda e inferior a la derecha.

Escribió una solución bastante simple y funcional:

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; }

Hice una pequeña solución de servilleta ..

Luego encuentra m y c y de ahí la ecuación y = mx + c

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

Sustituya las coordenadas P1 para encontrar ahora c

Ahora, para un vértice rectángulo, coloque el valor X en la ecuación de línea, obtenga el valor Y y vea si el valor Y se encuentra en los límites del rectángulo que se muestran a continuación

(Puede encontrar los valores constantes X1, X2, Y1, Y2 para el rectángulo tal que)

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

Si el valor Y satisface la condición anterior y se encuentra entre (Punto1Y, Punto2.Y) - tenemos una intersección. Pruebe cada vértice si este no logra hacer el corte.

Use el algoritmo de Cohen-Sutherland .

Se usa para clipping pero se puede modificar ligeramente para esta tarea. Divide el espacio 2D en un tablero de tres en raya con su rectángulo como el "cuadrado central".
luego verifica en cuál de las nueve regiones se encuentran cada uno de los dos puntos de tu línea.

  • Si ambos puntos están a la izquierda, derecha, arriba o abajo, rechaza trivialmente.
  • Si alguno de los puntos está dentro, aceptas trivialmente.
  • En los pocos casos restantes, puede hacer los cálculos para intersectarse con los lados del rectángulo con los que se puede intersecar, en función de las regiones en las que se encuentren.

El póster original quería DETECTAR una intersección entre un segmento de línea y un polígono. No hubo necesidad de LOCALIZAR la intersección, si es que hay una. Si así es como lo dijiste, puedes hacer menos trabajo que Liang-Barsky o Cohen-Sutherland:

Deje que los puntos finales del segmento sean p1 = (x1 y1) y p2 = (x2 y2).
Deje que las esquinas del rectángulo sean (xBL yBL) y (xTR yTR).

Entonces todo lo que tienes que hacer es

A. Verifique si las cuatro esquinas del rectángulo están en el mismo lado de la línea. La ecuación implícita para una línea a través de p1 y p2 es:

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

Si F (xy) = 0, (xy) está en la línea.
Si F (xy)> 0, (xy) está "arriba" de la línea.
Si F (xy) <0, (xy) está "debajo" de la línea.

Sustituye las cuatro esquinas en F (xy). Si son todos negativos o todos positivos, no hay intersección. Si algunos son positivos y otros negativos, vaya al paso B.

B. Proyecte el punto final en el eje x y verifique si la sombra del segmento intersecta la sombra del polígono. Repita en el eje y:

Si (x1> xTR y x2> xTR), no hay intersección (la línea está a la derecha del rectángulo).
If (x1 <xBL y x2 <xBL), no hay intersección (la línea está a la izquierda del rectángulo).
Si (y1> yTR e y2> yTR), no hay intersección (la línea está encima del rectángulo).
Si (y1 <yBL e y2 <yBL), no hay intersección (la línea está debajo del rectángulo).
De lo contrario, hay una intersección. Haga Cohen-Sutherland o el código que se mencionó en las otras respuestas a su pregunta.

Puedes, por supuesto, hacer B primero, luego A.

Alejo

O simplemente use / copie el código que ya está en el método Java

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

Aquí está el método después de convertirlo a estático por conveniencia:

/** * 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; } }

Estaba viendo un problema similar y esto es lo que se me ocurrió. Estaba primero comparando los bordes y me di cuenta de algo. Si el punto medio de un borde que cayó dentro del eje opuesto de la primera caja está dentro de la mitad de la longitud de ese borde de los puntos exteriores en la primera en el mismo eje, entonces hay una intersección de ese lado en alguna parte. Pero eso fue pensar 1 dimensión y requirió mirar cada lado de la segunda caja para descubrir.

De repente, se me ocurrió que si se encuentra el "punto medio" de la segunda casilla y se comparan las coordenadas del punto medio para ver si caen dentro de la 1/2 longitud de un lado (de la segunda casilla) de las dimensiones externas de la primera , entonces hay una intersección en alguna parte.

i.e. 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 <=

Por supuesto, podría fácilmente compararlo al revés (verificando que los puntos medios de la casilla 1 estén dentro de 1/2 de la longitud de las dimensiones externas de la casilla 2)

Y aún más simplificación: cambie el punto medio por la mitad de su longitud y sea idéntico al punto de origen de esa caja. Lo que significa que ahora puedes verificar exactamente ese punto para que quede dentro de tu margen delimitador y al desplazar el plano hacia arriba y hacia la izquierda, la esquina inferior es ahora la esquina inferior del primer cuadro. Mucho menos matemáticas

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

o no sustituido:

( (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]

ejemplo de codificación en PHP (estoy usando un modelo de objetos que tiene métodos para cosas como getLeft (), getRight (), getTop (), getBottom () para obtener las coordenadas externas de un polígono y también tiene un getWidth () y getHeight () - dependiendo de qué parámetros fueron alimentados, calculará y almacenará en caché las incógnitas, es decir, puedo crear un polígono con x1, y1 y ... w, h o x2, y2 y puede calcular los demás)

Uso ''n'' para designar el elemento ''nuevo'' que se comprueba para la superposición ($ nItem es una instancia de mi objeto polígono) - los elementos para probar de nuevo [este es un programa de mochila bin / sort] están en una matriz que consiste en más instancias del (mismo) objeto polígono.

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; }

Algunos ejemplos de código para mi solución (en 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; }

También podría crear un rectángulo fuera del segmento y probar si el otro rectángulo colisiona con él, ya que es solo una serie de comparaciones. De la fuente de pygame:

def _rect_collide(a, b): return a.x + a.w > b.x and b.x + b.w > a.x and / a.y + a.h > b.y and b.y + b.h > a.y

Aquí hay una versión de JavaScript de la respuesta de @ 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 }