¿Cómo encontrar el punto de intersección entre una línea y un rectángulo?

Question

Tengo una línea que va desde los puntos A a B; Tengo (x, y) de ambos puntos. También tengo un rectángulo centrado en B y el ancho y alto del rectángulo.

Necesito encontrar el punto en la línea que cruza el rectángulo. ¿Hay alguna fórmula que me dé el (x, y) de ese punto?

Answer 1

yo no te voy a dar un programa para hacer eso, pero aquí es cómo puede hacerlo:

• calcular el ángulo de la línea
• calcular el ángulo de una línea desde el centro de el rectángulo a una de las esquinas es
• basándose en los ángulos determinan en qué lado de la línea no intersecan el rectángulo
• calcular la intersección entre el lado del rectángulo y la línea

Answer 2

No sé si esta es la mejor manera, pero lo que podrías hacer es calcular la proporción de la línea que está dentro del rectángulo. Puede obtenerlo del ancho del rectángulo y la diferencia entre las coordenadas x de A y B (o las coordenadas de altura e y, en función del ancho y la altura, puede verificar qué caso se aplica y el otro caso estará en la extensión de un lado del rectángulo). Cuando tengas esto, simplemente toma esa proporción del vector de B a A y tienes las coordenadas de tu punto de intersección.

Answer 3

El punto A es siempre fuera del rectángulo y el punto B está siempre en el centro del rectángulo

Suponiendo que el rectángulo es eje alineados, esto hace cosas bastante simples:

La pendiente de la línea es s = (Ay - By)/(Ax - Bx).

• Si -h/2 < = s * w/2 < = h/2 a continuación, la línea se cruza:
  • El borde derecho si Ax> Bx
  • El borde izquierdo si Ax Bx < .
• Si -w/2 < = (h/2)/s < = w/2 a continuación, la línea se cruza:
  • El borde superior si Ay> Por
  • El borde inferior si Ay < Por.

Una vez conocido el borde que se cruza sabes una coordenada: x = Bx ± w/2 o y = Por ± h/2 dependiendo de borde por el que golpea. La otra coordenada está dada por y = By + s * w/2 o x = Bx + (h/2)/s.

Answer 4

Es posible que desee comprobar Graphics Gems - este es un conjunto clásico de rutinas para gráficos e incluye muchos de los algoritmos necesarios. Aunque está en C y ligeramente anticuado, los algoritmos aún brillan y debería ser trivial transferirlos a otros idiomas.

Para su problema actual, simplemente cree las cuatro líneas para el rectángulo y vea cuáles intersectan su línea dada.

Answer 5

Aquí hay una solución en Java que devuelve verdadero si un segmento de línea (los primeros 4 parámetros) interseca un rectángulo alineado en el eje (los últimos 4 parámetros). Sería trivial devolver el punto de intersección en lugar de un booleano. Funciona comprobando primero si está completamente afuera, sino usando la ecuación de línea y=m*x+b. Sabemos que las líneas que forman el rectángulo están alineadas con los ejes, por lo que los controles son fáciles.

public boolean aabbContainsSegment (float x1, float y1, float x2, float y2, float minX, float minY, float maxX, float maxY) { 
    // Completely outside. 
    if ((x1 <= minX && x2 <= minX) || (y1 <= minY && y2 <= minY) || (x1 >= maxX && x2 >= maxX) || (y1 >= maxY && y2 >= maxY)) 
     return false; 

    float m = (y2 - y1)/(x2 - x1); 

    float y = m * (minX - x1) + y1; 
    if (y > minY && y < maxY) return true; 

    y = m * (maxX - x1) + y1; 
    if (y > minY && y < maxY) return true; 

    float x = (minY - y1)/m + x1; 
    if (x > minX && x < maxX) return true; 

    x = (maxY - y1)/m + x1; 
    if (x > minX && x < maxX) return true; 

    return false; 
} 

Es posible acceso directo si el inicio o el final del segmento se encuentra dentro del rectángulo, pero probablemente es mejor simplemente hacen las cuentas, que siempre devuelve verdadero si termina uno o ambos segmentos están en el interior. Si quiere el atajo de todos modos, inserte el siguiente código después de la verificación "completamente afuera".

// Start or end inside. 
if ((x1 > minX && x1 < maxX && y1 > minY && y1 < maxY) || (x2 > minX && x2 < maxX && y2 > minY && y2 < maxY)) return true; 

Answer 6

no soy un fan de matemáticas ni me gusta especialmente la traducción de cosas de otros idiomas si otros ya lo han hecho, por lo que cada vez que complete una tarea de traducción aburrido, lo añado al artículo que me llevó a la código. Para evitar que alguien haga doble trabajo.

Así que si usted quiere tener este código intersección en C#, echar un vistazo aquí http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html

Answer 7

Aquí es un método poco detallado que devuelve los intervalos de intersección entre una línea (infinito) y un rectángulo con las matemáticas solamente básica:

// Line2  - 2D line with origin (= offset from 0,0) and direction 
// Rectangle2 - 2D rectangle by min and max points 
// Contacts - Stores entry and exit times of a line through a convex shape 

Contacts findContacts(const Line2 &line, const Rectangle2 &rect) { 
    Contacts contacts; 

    // If the line is not parallel to the Y axis, find out when it will cross 
    // the limits of the rectangle horizontally 
    if(line.Direction.X != 0.0f) { 
    float leftTouch = (rect.Min.X - line.Origin.X)/line.Direction.X; 
    float rightTouch = (rect.Max.X - line.Origin.X)/line.Direction.X; 
    contacts.Entry = std::fmin(leftTouch, rightTouch); 
    contacts.Exit = std::fmax(leftTouch, rightTouch); 
    } else if((line.Offset.X < rect.Min.X) || (line.Offset.X >= rect.Max.X)) { 
    return Contacts::None; // Rectangle missed by vertical line 
    } 

    // If the line is not parallel to the X axis, find out when it will cross 
    // the limits of the rectangle vertically 
    if(line.Direction.Y != 0.0f) { 
    float topTouch = (rectangle.Min.Y - line.Offset.Y)/line.Direction.Y; 
    float bottomTouch = (rectangle.Max.Y - line.Offset.Y)/line.Direction.Y; 

    // If the line is parallel to the Y axis (and it goes through 
    // the rectangle), only the Y axis needs to be taken into account. 
    if(line.Direction.X == 0.0f) { 
     contacts.Entry = std::fmin(topTouch, bottomTouch); 
     contacts.Exit = std::fmax(topTouch, bottomTouch); 
    } else { 
     float verticalEntry = std::fmin(topTouch, bottomTouch); 
     float verticalExit = std::fmax(topTouch, bottomTouch); 

     // If the line already left the rectangle on one axis before entering it 
     // on the other, it has missed the rectangle. 
     if((verticalExit < contacts.Entry) || (contacts.Exit < verticalEntry)) { 
     return Contacts::None; 
     } 

     // Restrict the intervals from the X axis of the rectangle to where 
     // the line is also within the limits of the rectangle on the Y axis 
     contacts.Entry = std::fmax(verticalEntry, contacts.Entry); 
     contacts.Exit = std::fmin(verticalExit, contacts.Exit); 
    } 
    } else if((line.Offset.Y < rect.Min.Y) || (line.Offset.Y > rect.Max.Y)) { 
    return Contacts::None; // Rectangle missed by horizontal line 
    } 

    return contacts; 
} 

Este enfoque ofrece un alto grado de estabilidad numérica (los intervalos son, en todos los casos, el resultado de un solo resta y división), sino que implica alguna ramificación.

Para un segmento de línea (con puntos de inicio y de finalización), debe proporcionar el punto de inicio del segmento como el origen y para la dirección, end - start. El cálculo de las coordenadas de las dos intersecciones es un simple como entryPoint = origin + direction * contacts.Entry y exitPoint = origin + direction * contacts.Exit.

Answer 8

/** 
 
* Finds the intersection point between 
 
*  * the rectangle 
 
*  with parallel sides to the x and y axes 
 
*  * the half-line pointing towards (x,y) 
 
*  originating from the middle of the rectangle 
 
* 
 
* Note: the function works given min[XY] <= max[XY], 
 
*  even though minY may not be the "top" of the rectangle 
 
*  because the coordinate system is flipped. 
 
* Note: if the input is inside the rectangle, 
 
*  the line segment wouldn't have an intersection with the rectangle, 
 
*  but the projected half-line does. 
 
* Warning: passing in the middle of the rectangle will return the midpoint itself 
 
*   there are infinitely many half-lines projected in all directions, 
 
*   so let's just shortcut to midpoint (GIGO). 
 
* 
 
* @param x:Number x coordinate of point to build the half-line from 
 
* @param y:Number y coordinate of point to build the half-line from 
 
* @param minX:Number the "left" side of the rectangle 
 
* @param minY:Number the "top" side of the rectangle 
 
* @param maxX:Number the "right" side of the rectangle 
 
* @param maxY:Number the "bottom" side of the rectangle 
 
* @param validate:boolean (optional) whether to treat point inside the rect as error 
 
* @return an object with x and y members for the intersection 
 
* @throws if validate == true and (x,y) is inside the rectangle 
 
* @author TWiStErRob 
 
* @see <a href="http://stackoverflow.com/a/31254199/253468">source</a> 
 
* @see <a href="http://stackoverflow.com/a/18292964/253468">based on</a> 
 
*/ 
 
function pointOnRect(x, y, minX, minY, maxX, maxY, validate) { 
 
\t //assert minX <= maxX; 
 
\t //assert minY <= maxY; 
 
\t if (validate && (minX < x && x < maxX) && (minY < y && y < maxY)) 
 
\t \t throw "Point " + [x,y] + "cannot be inside " 
 
\t \t  + "the rectangle: " + [minX, minY] + " - " + [maxX, maxY] + "."; 
 
\t var midX = (minX + maxX)/2; 
 
\t var midY = (minY + maxY)/2; 
 
\t // if (midX - x == 0) -> m == ±Inf -> minYx/maxYx == x (because value/±Inf = ±0) 
 
\t var m = (midY - y)/(midX - x); 
 

 
\t if (x <= midX) { // check "left" side 
 
\t \t var minXy = m * (minX - x) + y; 
 
\t \t if (minY <= minXy && minXy <= maxY) 
 
\t \t \t return {x: minX, y: minXy}; 
 
\t } 
 

 
\t if (x >= midX) { // check "right" side 
 
\t \t var maxXy = m * (maxX - x) + y; 
 
\t \t if (minY <= maxXy && maxXy <= maxY) 
 
\t \t \t return {x: maxX, y: maxXy}; 
 
\t } 
 

 
\t if (y <= midY) { // check "top" side 
 
\t \t var minYx = (minY - y)/m + x; 
 
\t \t if (minX <= minYx && minYx <= maxX) 
 
\t \t \t return {x: minYx, y: minY}; 
 
\t } 
 

 
\t if (y >= midY) { // check "bottom" side 
 
\t \t var maxYx = (maxY - y)/m + x; 
 
\t \t if (minX <= maxYx && maxYx <= maxX) 
 
\t \t \t return {x: maxYx, y: maxY}; 
 
\t } 
 

 
\t // edge case when finding midpoint intersection: m = 0/0 = NaN 
 
\t if (x === midX && y === midY) return {x: x, y: y}; 
 

 
\t // Should never happen :) If it does, please tell me! 
 
\t throw "Cannot find intersection for " + [x,y] 
 
\t  + " inside rectangle " + [minX, minY] + " - " + [maxX, maxY] + "."; 
 
} 
 

 
(function tests() { 
 
\t var left = 100, right = 200, top = 50, bottom = 150; // a square, really 
 
\t var hMiddle = (left + right)/2, vMiddle = (top + bottom)/2; 
 
\t function intersectTestRect(x, y) { return pointOnRect(x,y, left,top, right,bottom, true); } 
 
\t function intersectTestRectNoValidation(x, y) { return pointOnRect(x,y, left,top, right,bottom, false); } 
 
\t function checkTestRect(x, y) { return function() { return pointOnRect(x,y, left,top, right,bottom, true); }; } 
 
\t QUnit.test("intersects left side", function(assert) { 
 
\t \t var leftOfRect = 0, closerLeftOfRect = 25; 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 25), {x:left, y:75}, "point above top"); 
 
\t \t assert.deepEqual(intersectTestRect(closerLeftOfRect, top), {x:left, y:80}, "point in line with top"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 70), {x:left, y:90}, "point above middle"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, vMiddle), {x:left, y:100}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 130), {x:left, y:110}, "point below middle"); 
 
\t \t assert.deepEqual(intersectTestRect(closerLeftOfRect, bottom), {x:left, y:120}, "point in line with bottom"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 175), {x:left, y:125}, "point below bottom"); 
 
\t }); 
 
\t QUnit.test("intersects right side", function(assert) { 
 
\t \t var rightOfRect = 300, closerRightOfRect = 250; 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 25), {x:right, y:75}, "point above top"); 
 
\t \t assert.deepEqual(intersectTestRect(closerRightOfRect, top), {x:right, y:75}, "point in line with top"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 70), {x:right, y:90}, "point above middle"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, vMiddle), {x:right, y:100}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 130), {x:right, y:110}, "point below middle"); 
 
\t \t assert.deepEqual(intersectTestRect(closerRightOfRect, bottom), {x:right, y:125}, "point in line with bottom"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 175), {x:right, y:125}, "point below bottom"); 
 
\t }); 
 
\t QUnit.test("intersects top side", function(assert) { 
 
\t \t var aboveRect = 0; 
 
\t \t assert.deepEqual(intersectTestRect(80, aboveRect), {x:115, y:top}, "point left of left"); 
 
\t \t assert.deepEqual(intersectTestRect(left, aboveRect), {x:125, y:top}, "point in line with left"); 
 
\t \t assert.deepEqual(intersectTestRect(120, aboveRect), {x:135, y:top}, "point left of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, aboveRect), {x:150, y:top}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(180, aboveRect), {x:165, y:top}, "point right of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(right, aboveRect), {x:175, y:top}, "point in line with right"); 
 
\t \t assert.deepEqual(intersectTestRect(220, aboveRect), {x:185, y:top}, "point right of right"); 
 
\t }); 
 
\t QUnit.test("intersects bottom side", function(assert) { 
 
\t \t var belowRect = 200; 
 
\t \t assert.deepEqual(intersectTestRect(80, belowRect), {x:115, y:bottom}, "point left of left"); 
 
\t \t assert.deepEqual(intersectTestRect(left, belowRect), {x:125, y:bottom}, "point in line with left"); 
 
\t \t assert.deepEqual(intersectTestRect(120, belowRect), {x:135, y:bottom}, "point left of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, belowRect), {x:150, y:bottom}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(180, belowRect), {x:165, y:bottom}, "point right of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(right, belowRect), {x:175, y:bottom}, "point in line with right"); 
 
\t \t assert.deepEqual(intersectTestRect(220, belowRect), {x:185, y:bottom}, "point right of right"); 
 
\t }); 
 
\t QUnit.test("intersects a corner", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRect(left-50, top-50), {x:left, y:top}, "intersection line aligned with top-left corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right+50, top-50), {x:right, y:top}, "intersection line aligned with top-right corner"); 
 
\t \t assert.deepEqual(intersectTestRect(left-50, bottom+50), {x:left, y:bottom}, "intersection line aligned with bottom-left corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right+50, bottom+50), {x:right, y:bottom}, "intersection line aligned with bottom-right corner"); 
 
\t }); 
 
\t QUnit.test("on the corners", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRect(left, top), {x:left, y:top}, "top-left corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right, top), {x:right, y:top}, "top-right corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right, bottom), {x:right, y:bottom}, "bottom-right corner"); 
 
\t \t assert.deepEqual(intersectTestRect(left, bottom), {x:left, y:bottom}, "bottom-left corner"); 
 
\t }); 
 
\t QUnit.test("on the edges", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, top), {x:hMiddle, y:top}, "top edge"); 
 
\t \t assert.deepEqual(intersectTestRect(right, vMiddle), {x:right, y:vMiddle}, "right edge"); 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, bottom), {x:hMiddle, y:bottom}, "bottom edge"); 
 
\t \t assert.deepEqual(intersectTestRect(left, vMiddle), {x:left, y:vMiddle}, "left edge"); 
 
\t }); 
 
\t QUnit.test("validates inputs", function(assert) { 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, vMiddle-10), /cannot be inside/, "top left of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, vMiddle), /cannot be inside/, "left of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, vMiddle+10), /cannot be inside/, "bottom left of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle-10), /cannot be inside/, "above center"); 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle+10), /cannot be inside/, "below center"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, vMiddle-10), /cannot be inside/, "top right of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, vMiddle), /cannot be inside/, "right of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, vMiddle+10), /cannot be inside/, "bottom right of center"); 
 
\t \t assert.throws(checkTestRect(left+10, vMiddle-10), /cannot be inside/, "right of left edge"); 
 
\t \t assert.throws(checkTestRect(left+10, vMiddle), /cannot be inside/, "right of left edge"); 
 
\t \t assert.throws(checkTestRect(left+10, vMiddle+10), /cannot be inside/, "right of left edge"); 
 
\t \t assert.throws(checkTestRect(right-10, vMiddle-10), /cannot be inside/, "left of right edge"); 
 
\t \t assert.throws(checkTestRect(right-10, vMiddle), /cannot be inside/, "left of right edge"); 
 
\t \t assert.throws(checkTestRect(right-10, vMiddle+10), /cannot be inside/, "left of right edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, top+10), /cannot be inside/, "below top edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle, top+10), /cannot be inside/, "below top edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, top+10), /cannot be inside/, "below top edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, bottom-10), /cannot be inside/, "above bottom edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle, bottom-10), /cannot be inside/, "above bottom edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, bottom-10), /cannot be inside/, "above bottom edge"); 
 
\t }); 
 
\t QUnit.test("doesn't validate inputs", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle-10), {x:left, y:top}, "top left of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle), {x:left, y:vMiddle}, "left of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle+10), {x:left, y:bottom}, "bottom left of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle-10), {x:hMiddle, y:top}, "above center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle), {x:hMiddle, y:vMiddle}, "center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle+10), {x:hMiddle, y:bottom}, "below center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle-10), {x:right, y:top}, "top right of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle), {x:right, y:vMiddle}, "right of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle+10), {x:right, y:bottom}, "bottom right of center"); 
 
\t }); 
 
})();

<link href="https://code.jquery.com/qunit/qunit-2.3.2.css" rel="stylesheet"/> 
 
<script src="https://code.jquery.com/qunit/qunit-2.3.2.js"></script> 
 
<div id="qunit"></div>

Answer 9

Otra opción que se puede considerar especialmente si usted está pensando en probar muchas líneas con el mismo rectángulo es transformar el sistema de coordenadas de tener los ejes se alinean con diagonales del rectángulo. Luego, como su línea o rayo comienza en el centro del rectángulo, puede determinar el ángulo y luego puede indicar qué segmento intersectará por el ángulo (es decir, < 90deg seg 1, 90deg < < 180deg seg 2, etc.). Luego, por supuesto, tiene que volver a transformar al sistema de coordenadas original

Aunque esto parece más trabajo, la matriz de transformación y su inversa se pueden calcular una vez y luego reutilizar. Esto también se extiende a rectángulos dimensionales más altos con mayor facilidad, donde debería considerar cuadrantes e intersecciones con caras en 3D, y así sucesivamente.