algorithm - tendencia - ¿Cómo encontrar el punto de intersección entre una línea y un rectángulo?
punto de interseccion de dos rectas (10)
El punto A está siempre fuera del rectángulo y el punto B siempre está en el centro del rectángulo
Suponiendo que el rectángulo está alineado con el eje, esto hace las cosas bastante simples:
La pendiente de la línea es s = (Ay - By) / (Ax - Bx).
- Si -h / 2 <= s * w / 2 <= h / 2, entonces 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, entonces la línea se cruza:
- El borde superior si Ay> Por
- El borde inferior si Ay <By.
Una vez que conoces el borde que interseca, conoces una coordenada: x = Bx ± w / 2 oy = By ± h / 2, dependiendo de qué borde toques. La otra coordenada está dada por y = By + s * w / 2 o x = Bx + (h / 2) / s.
Tengo una línea que va de 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?
Aquí hay un método ligeramente detallado que devuelve los intervalos de intersección entre una línea (infinita) y un rectángulo utilizando solo matemática 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 una única resta y división) pero implica cierta ramificación.
Para un segmento de línea (con puntos de inicio y final), debe proporcionar el punto de inicio del segmento como origen y dirección, end - start . Calcular las coordenadas de las dos intersecciones es un simple como entryPoint = origin + direction * contacts.Entry y exitPoint = origin + direction * contacts.Exit .
Aquí hay una solución en Java que devuelve verdadero si un segmento de línea (los primeros 4 parámetros) intersecta un rectángulo alineado del 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 atajar si el inicio o el final del segmento está dentro del rectángulo, pero probablemente sea mejor hacer los cálculos, que siempre serán verdaderos si uno o ambos extremos de los segmentos están dentro. 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;
Aquí hay una solución que funciona para mí. Supongo que el rect está alineado con los ejes.
Datos:
// Center of the Rectangle
let Cx: number
let Cy: number
// Width
let w: number
// Height
let h: number
// Other Point
let Ax: number
let Ay: number
Ahora traduzca el punto A por el centro del rectángulo para que el rect esté centrado en O (0,0) y considere el problema en el primer trimestre (es decir, x> 0 e y> 0).
// Coordinates Translated
let Px = Math.abs(Ax - Cx)
let Py = Math.abs(Ay - Cy)
// Slope of line from Point P to Center
let Pm = Py / Px
// Slope of rectangle Diagonal
let Rm = h / w
// If the point is inside the rectangle, return the center
let res: [number, number] = [0, 0]
// Check if the point is inside and if so do not calculate
if (!(Px < w / 2 && Py < h / 2)) {
// Calculate point in first quarter: Px >= 0 && Py >= 0
if (Pm <= Rm) {
res[0] = w / 2
res[1] = (w * Pm) / 2
} else {
res[0] = h / (Pm * 2)
res[1] = h / 2
}
// Set original sign
if (Ax - Cx < 0) res[0] *= -1
if (Ay - Cy < 0) res[1] *= -1
}
// Translate back
return [res[0] + Cx, res[1] + Cy]
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.
No soy fanático de las matemáticas ni disfruto especialmente de traducir cosas de otros idiomas si otros ya lo han hecho, así que cada vez que completo una tarea aburrida de traducción, la agrego al artículo que me llevó al código. Para evitar que alguien haga doble trabajo.
Entonces, si quiere tener este código de intersección en C #, eche un vistazo aquí http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html
No te daré un programa para hacer eso, pero aquí es cómo puedes hacerlo:
- calcular el ángulo de la línea
- calcular el ángulo de una línea desde el centro del rectángulo a una de sus esquinas
- en función de los ángulos, determina en qué lado se cruza la línea con el rectángulo
- calcular la intersección entre el lado del rectángulo y la línea
Otra opción que puede considerar especialmente si planea probar muchas líneas con el mismo rectángulo es transformar su sistema de coordenadas para que los ejes se alineen con las diagonales del rectángulo. Luego, dado que su línea o rayo comienza en el centro del rectángulo, puede determinar el ángulo y luego puede decir a qué segmento se intersectará por el ángulo (es decir, <90deg seg 1, 90deg <<180deg seg 2, etc. ...). Entonces, por supuesto, tienes que volver a transformar el 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.
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ál intersecta su línea dada.
/**
* 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
* @licence Dual CC0/WTFPL/Unlicence, whatever floats your boat
* @see <a href="http://.com/a/31254199/253468">source</a>
* @see <a href="http://.com/a/18292964/253468">based on</a>
*/
function pointOnRect(x, y, minX, minY, maxX, maxY, validate) {
//assert minX <= maxX;
//assert minY <= maxY;
if (validate && (minX < x && x < maxX) && (minY < y && y < maxY))
throw "Point " + [x,y] + "cannot be inside "
+ "the rectangle: " + [minX, minY] + " - " + [maxX, maxY] + ".";
var midX = (minX + maxX) / 2;
var midY = (minY + maxY) / 2;
// if (midX - x == 0) -> m == ±Inf -> minYx/maxYx == x (because value / ±Inf = ±0)
var m = (midY - y) / (midX - x);
if (x <= midX) { // check "left" side
var minXy = m * (minX - x) + y;
if (minY <= minXy && minXy <= maxY)
return {x: minX, y: minXy};
}
if (x >= midX) { // check "right" side
var maxXy = m * (maxX - x) + y;
if (minY <= maxXy && maxXy <= maxY)
return {x: maxX, y: maxXy};
}
if (y <= midY) { // check "top" side
var minYx = (minY - y) / m + x;
if (minX <= minYx && minYx <= maxX)
return {x: minYx, y: minY};
}
if (y >= midY) { // check "bottom" side
var maxYx = (maxY - y) / m + x;
if (minX <= maxYx && maxYx <= maxX)
return {x: maxYx, y: maxY};
}
// edge case when finding midpoint intersection: m = 0/0 = NaN
if (x === midX && y === midY) return {x: x, y: y};
// Should never happen :) If it does, please tell me!
throw "Cannot find intersection for " + [x,y]
+ " inside rectangle " + [minX, minY] + " - " + [maxX, maxY] + ".";
}
(function tests() {
var left = 100, right = 200, top = 50, bottom = 150; // a square, really
var hMiddle = (left + right) / 2, vMiddle = (top + bottom) / 2;
function intersectTestRect(x, y) { return pointOnRect(x,y, left,top, right,bottom, true); }
function intersectTestRectNoValidation(x, y) { return pointOnRect(x,y, left,top, right,bottom, false); }
function checkTestRect(x, y) { return function() { return pointOnRect(x,y, left,top, right,bottom, true); }; }
QUnit.test("intersects left side", function(assert) {
var leftOfRect = 0, closerLeftOfRect = 25;
assert.deepEqual(intersectTestRect(leftOfRect, 25), {x:left, y:75}, "point above top");
assert.deepEqual(intersectTestRect(closerLeftOfRect, top), {x:left, y:80}, "point in line with top");
assert.deepEqual(intersectTestRect(leftOfRect, 70), {x:left, y:90}, "point above middle");
assert.deepEqual(intersectTestRect(leftOfRect, vMiddle), {x:left, y:100}, "point exact middle");
assert.deepEqual(intersectTestRect(leftOfRect, 130), {x:left, y:110}, "point below middle");
assert.deepEqual(intersectTestRect(closerLeftOfRect, bottom), {x:left, y:120}, "point in line with bottom");
assert.deepEqual(intersectTestRect(leftOfRect, 175), {x:left, y:125}, "point below bottom");
});
QUnit.test("intersects right side", function(assert) {
var rightOfRect = 300, closerRightOfRect = 250;
assert.deepEqual(intersectTestRect(rightOfRect, 25), {x:right, y:75}, "point above top");
assert.deepEqual(intersectTestRect(closerRightOfRect, top), {x:right, y:75}, "point in line with top");
assert.deepEqual(intersectTestRect(rightOfRect, 70), {x:right, y:90}, "point above middle");
assert.deepEqual(intersectTestRect(rightOfRect, vMiddle), {x:right, y:100}, "point exact middle");
assert.deepEqual(intersectTestRect(rightOfRect, 130), {x:right, y:110}, "point below middle");
assert.deepEqual(intersectTestRect(closerRightOfRect, bottom), {x:right, y:125}, "point in line with bottom");
assert.deepEqual(intersectTestRect(rightOfRect, 175), {x:right, y:125}, "point below bottom");
});
QUnit.test("intersects top side", function(assert) {
var aboveRect = 0;
assert.deepEqual(intersectTestRect(80, aboveRect), {x:115, y:top}, "point left of left");
assert.deepEqual(intersectTestRect(left, aboveRect), {x:125, y:top}, "point in line with left");
assert.deepEqual(intersectTestRect(120, aboveRect), {x:135, y:top}, "point left of middle");
assert.deepEqual(intersectTestRect(hMiddle, aboveRect), {x:150, y:top}, "point exact middle");
assert.deepEqual(intersectTestRect(180, aboveRect), {x:165, y:top}, "point right of middle");
assert.deepEqual(intersectTestRect(right, aboveRect), {x:175, y:top}, "point in line with right");
assert.deepEqual(intersectTestRect(220, aboveRect), {x:185, y:top}, "point right of right");
});
QUnit.test("intersects bottom side", function(assert) {
var belowRect = 200;
assert.deepEqual(intersectTestRect(80, belowRect), {x:115, y:bottom}, "point left of left");
assert.deepEqual(intersectTestRect(left, belowRect), {x:125, y:bottom}, "point in line with left");
assert.deepEqual(intersectTestRect(120, belowRect), {x:135, y:bottom}, "point left of middle");
assert.deepEqual(intersectTestRect(hMiddle, belowRect), {x:150, y:bottom}, "point exact middle");
assert.deepEqual(intersectTestRect(180, belowRect), {x:165, y:bottom}, "point right of middle");
assert.deepEqual(intersectTestRect(right, belowRect), {x:175, y:bottom}, "point in line with right");
assert.deepEqual(intersectTestRect(220, belowRect), {x:185, y:bottom}, "point right of right");
});
QUnit.test("intersects a corner", function(assert) {
assert.deepEqual(intersectTestRect(left-50, top-50), {x:left, y:top}, "intersection line aligned with top-left corner");
assert.deepEqual(intersectTestRect(right+50, top-50), {x:right, y:top}, "intersection line aligned with top-right corner");
assert.deepEqual(intersectTestRect(left-50, bottom+50), {x:left, y:bottom}, "intersection line aligned with bottom-left corner");
assert.deepEqual(intersectTestRect(right+50, bottom+50), {x:right, y:bottom}, "intersection line aligned with bottom-right corner");
});
QUnit.test("on the corners", function(assert) {
assert.deepEqual(intersectTestRect(left, top), {x:left, y:top}, "top-left corner");
assert.deepEqual(intersectTestRect(right, top), {x:right, y:top}, "top-right corner");
assert.deepEqual(intersectTestRect(right, bottom), {x:right, y:bottom}, "bottom-right corner");
assert.deepEqual(intersectTestRect(left, bottom), {x:left, y:bottom}, "bottom-left corner");
});
QUnit.test("on the edges", function(assert) {
assert.deepEqual(intersectTestRect(hMiddle, top), {x:hMiddle, y:top}, "top edge");
assert.deepEqual(intersectTestRect(right, vMiddle), {x:right, y:vMiddle}, "right edge");
assert.deepEqual(intersectTestRect(hMiddle, bottom), {x:hMiddle, y:bottom}, "bottom edge");
assert.deepEqual(intersectTestRect(left, vMiddle), {x:left, y:vMiddle}, "left edge");
});
QUnit.test("validates inputs", function(assert) {
assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center");
assert.throws(checkTestRect(hMiddle-10, vMiddle-10), /cannot be inside/, "top left of center");
assert.throws(checkTestRect(hMiddle-10, vMiddle), /cannot be inside/, "left of center");
assert.throws(checkTestRect(hMiddle-10, vMiddle+10), /cannot be inside/, "bottom left of center");
assert.throws(checkTestRect(hMiddle, vMiddle-10), /cannot be inside/, "above center");
assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center");
assert.throws(checkTestRect(hMiddle, vMiddle+10), /cannot be inside/, "below center");
assert.throws(checkTestRect(hMiddle+10, vMiddle-10), /cannot be inside/, "top right of center");
assert.throws(checkTestRect(hMiddle+10, vMiddle), /cannot be inside/, "right of center");
assert.throws(checkTestRect(hMiddle+10, vMiddle+10), /cannot be inside/, "bottom right of center");
assert.throws(checkTestRect(left+10, vMiddle-10), /cannot be inside/, "right of left edge");
assert.throws(checkTestRect(left+10, vMiddle), /cannot be inside/, "right of left edge");
assert.throws(checkTestRect(left+10, vMiddle+10), /cannot be inside/, "right of left edge");
assert.throws(checkTestRect(right-10, vMiddle-10), /cannot be inside/, "left of right edge");
assert.throws(checkTestRect(right-10, vMiddle), /cannot be inside/, "left of right edge");
assert.throws(checkTestRect(right-10, vMiddle+10), /cannot be inside/, "left of right edge");
assert.throws(checkTestRect(hMiddle-10, top+10), /cannot be inside/, "below top edge");
assert.throws(checkTestRect(hMiddle, top+10), /cannot be inside/, "below top edge");
assert.throws(checkTestRect(hMiddle+10, top+10), /cannot be inside/, "below top edge");
assert.throws(checkTestRect(hMiddle-10, bottom-10), /cannot be inside/, "above bottom edge");
assert.throws(checkTestRect(hMiddle, bottom-10), /cannot be inside/, "above bottom edge");
assert.throws(checkTestRect(hMiddle+10, bottom-10), /cannot be inside/, "above bottom edge");
});
QUnit.test("doesn''t validate inputs", function(assert) {
assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle-10), {x:left, y:top}, "top left of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle), {x:left, y:vMiddle}, "left of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle+10), {x:left, y:bottom}, "bottom left of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle-10), {x:hMiddle, y:top}, "above center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle), {x:hMiddle, y:vMiddle}, "center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle+10), {x:hMiddle, y:bottom}, "below center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle-10), {x:right, y:top}, "top right of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle), {x:right, y:vMiddle}, "right of center");
assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle+10), {x:right, y:bottom}, "bottom right of center");
});
})();
<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>