我有一条从A点到B点的线; 我有(x,y)这两点.我还有一个以B为中心的矩形以及矩形的宽度和高度.
我需要找到与矩形相交的线中的点.有没有一个公式给我这一点的(x,y)？
点A始终位于矩形之外,点B始终位于矩形的中心
假设矩形是轴对齐的,这使事情变得非常简单:
线的斜率是s =(Ay-By)/(Ax-Bx).
如果-h/2 <= s*w/2 <= h/2则该线相交:
Ax> Bx时的右边缘
Ax 如果-w/2 <=(h/2)/ s <= w/2则该线相交:
最高的边缘,如果Ay> By Ay
一旦你知道它相交的边缘就知道一个坐标:x = Bx±w/2或y = By±h/2,具体取决于你击中的边缘.另一个坐标由y = By + s*w/2或x = Bx +(h/2)/ s给出. 您可能想查看Graphics Gems - 这是一组经典的图形例程,包括许多所需的算法.虽然它在C语言中略显陈旧,但算法仍然闪烁,转换到其他语言应该是微不足道的. 对于您当前的问题,只需为矩形创建四条线,并查看与给定线相交的线.
谢谢Joren,我做了这个算法的小提琴:http://jsfiddle.net/524ctnfh/它似乎左右和上下边缘交换,所以它应该是:*right*:Ax
对不起,我在脚本中犯了一些错误,这里是固定版本:http://jsfiddle.net/524ctnfh/1/
2> peter.murray..：
/**
* 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 source
* @see based on
*/
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");
});
})();
这是Java中的解决方案,如果线段(前4个参数)与轴对齐的矩形(最后4个参数)相交,则返回true.返回交叉点而不是布尔值将是微不足道的.它首先检查是否完全在外,否则使用线方程y=m*x+b.我们知道构成矩形的线是轴对齐的,因此检查很容易.
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;
}
如果段的开头或结尾在矩形内部,则可以快捷方式,但可能最好只进行数学运算,如果其中一个或两个段结束在内,则总是返回true.如果您还想要快捷方式,请在"完全外部"检查后插入下面的代码.
// Start or end inside.
if ((x1 > minX && x1 < maxX && y1 > minY && y1 < maxY) || (x2 > minX && x2 < maxX && y2 > minY && y2 < maxY)) return true;
京公网安备 11010802040832号 | 京ICP备19059560号-6 