我有一条从 A 点到 B 点的线；我有 (x,y) 两点。我还有一个以 B 为中心的矩形以及矩形的宽度和高度。
我需要找到与矩形相交的线中的点。有没有一个公式可以给我那个点的（x，y）？
问问题
70184 次
13 回答
26
The point A is always outside of the rectangle and the point B is always at the center of the rectangle
Assuming the rectangle is axis-aligned, this makes things pretty simple:
The slope of the line is s = (Ay - By)/(Ax - Bx).
- If -h/2 <= s * w/2 <= h/2 then the line intersects:
- The right edge if Ax > Bx
- The left edge if Ax < Bx.
- If -w/2 <= (h/2)/s <= w/2 then the line intersects:
- The top edge if Ay > By
- The bottom edge if Ay < By.
Once you know the edge it intersects you know one coordinate: x = Bx ± w/2 or y = By ± h/2 depending on which edge you hit. The other coordinate is given by y = By + s * w/2 or x = Bx + (h/2)/s.
于 2009-10-18T18:18:43.123 回答
23
/**
* 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://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) {
//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>于 2015-07-06T19:37:16.397 回答
19
您可能想查看Graphics Gems - 这是一组经典的图形例程，包括许多所需的算法。尽管它是 C 语言并且稍微过时了，但算法仍然闪闪发光，并且转移到其他语言应该是微不足道的。
对于您当前的问题，只需为矩形创建四条线，然后查看哪条线与您的给定线相交。
于 2009-10-18T18:31:39.087 回答
10
这是 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;
于 2013-08-17T20:20:31.457 回答
6
这是一个适合我的解决方案。我假设矩形与轴对齐。
数据：
// 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
现在将点 A 平移到矩形的中心，使矩形以 O(0,0) 为中心，并考虑第一季度的问题（即 x > 0 和 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]
于 2018-04-25T14:37:55.000 回答
4
让我们做一些假设：
给定点
A和C，以便它们定义ABCD与传统轴对齐的矩形。假设它A是左下角，并且C是右上角（即xA < xC和yA < yC）。假设
X和Y是给定的两个点，它们X位于矩形内部（即xA < xX < xC && yA < yX < yC），而 Y 位于矩形外部（即not(xA < xY < xC && yA < yY < yC).
这使我们可以在线段和矩形之间定义一个唯一的交点。E[X,Y]∂ABCD
诀窍是在矩形上寻找某个0 < t < 1这样的。通过将条件重写为：t*Y+(1-t)*X∂ABCDΓ(t) ∈ ABCD
(xY - xX) * t ∈ [xA - xX, xC - xX]和(yY - yX) * t ∈ [yA - yX, yC - yX],
现在可以展开所有场景。这产生：
var t = 0;
if(xY == xX) {
t = max((yA - yX)/(yY - yX), (yC - yX)/(yY - yX));
} else {
if(yY == yX) {
t = max((xA - xX)/(xY - xX), (xC - xX)/(xY - xX));
} else {
if(xY > xX) {
if(yY > yX) {
t = min((xC - xX)/(xY - xX), (yC - yX)/(yY - yX));
} else {
t = min((xC - xX)/(xY - xX), (yA - yX)/(yY - yX));
}
} else {
if(yY > yX) {
t = min((xA - xX)/(xY - xX), (yC - yX)/(yY - yX));
} else {
t = min((xA - xX)/(xY - xX), (yA - yX)/(yY - yX));
}
}
}
}
xE = t * xY + (1 - t) * xX;
yE = t * yY + (1 - t) * yX;
于 2020-05-20T01:15:37.053 回答
3
I'll not give you a program to do that, but here is how you can do it:
- calculate the angle of the line
- calculate the angle of a line from the center of the rectangle to one of it's corners
- based on the angles determine on which side does the line intersect the rectangle
- calculate intersection between the side of the rectangle and the line
于 2009-10-18T17:52:28.073 回答
3
我不是数学爱好者，也不是特别喜欢翻译其他语言的东西（如果其他人已经这样做了），所以每当我完成一项无聊的翻译任务时，我都会将其添加到引导我找到代码的文章中。为了防止任何人做双重工作。
所以如果你想在 C# 中有这个交集代码，看看这里http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html
于 2013-10-04T16:12:42.467 回答
3
鉴于最初的问题，我认为@ivanross 的答案是迄今为止最简洁明了的，我发现自己使用了相同的方法。
如果我们有一个矩形
- 以 B 为中心
- 边平行于 x 和 y 轴
我们可以使用一些三角函数来获得：
- tan φ (phi) = h/w
- tan θ (theta) = (yB-yA)/(xB-xA)
以及一些简单的数学运算来获得点 A 在哪个象限（以 B 为中心的 xy 平面）。
最后，我们比较角度并使用切线来计算交点的坐标，再次应用基本的三角学原理。
/**
* Finds the intersection point between
* * a rectangle centered in point B
* with sides parallel to the x and y axes
* * a line passing through points A and B (the center of the rectangle)
*
* @param width: rectangle width
* @param height: rectangle height
* @param xB; rectangle center x coordinate
* @param yB; rectangle center y coordinate
* @param xA; point A x coordinate
* @param yA; point A y coordinate
* @author Federico Destefanis
* @see <a href="https://stackoverflow.com/a/31254199/2668213">based on</a>
*/
function lineIntersectionOnRect(width, height, xB, yB, xA, yA) {
var w = width / 2;
var h = height / 2;
var dx = xA - xB;
var dy = yA - yB;
//if A=B return B itself
if (dx == 0 && dy == 0) return {
x: xB,
y: yB
};
var tan_phi = h / w;
var tan_theta = Math.abs(dy / dx);
//tell me in which quadrant the A point is
var qx = Math.sign(dx);
var qy = Math.sign(dy);
if (tan_theta > tan_phi) {
xI = xB + (h / tan_theta) * qx;
yI = yB + h * qy;
} else {
xI = xB + w * qx;
yI = yB + w * tan_theta * qy;
}
return {
x: xI,
y: yI
};
}
var coords = lineIntersectionOnRect(6, 4, 0, 0, 1, 0);
console.log(coords);于 2022-01-04T15:15:19.927 回答
2
如果您计划测试具有相同矩形的多条线，则可以考虑的另一个选项是转换坐标系以使轴与矩形的对角线对齐。然后，由于您的线或射线从矩形的中心开始，您可以确定角度，然后您可以判断它将与哪个部分相交（即 <90deg seg 1、90deg< <180deg seg 2 等）。然后当然你必须转换回原来的坐标系
尽管这似乎需要更多的工作，但变换矩阵及其逆矩阵可以计算一次然后重用。这也更容易扩展到更高维度的矩形，您必须考虑象限和与 3D 中的面的交点等。
于 2016-01-20T07:21:55.747 回答
1
I don't know if this is the best way, but what you could do is to figure out the proportion of the line that is inside the rectangle. You can get that from the width of the rectangle and the difference between the x coordinates of A and B (or height and y coordinates; based on the width and height you can check which case applies, and the other case will be on the extension of a side of the rectangle). When you have this, just take that proportion of the vector from B to A and you have your intersection point's coordinates.
于 2009-10-18T17:56:21.117 回答
1
希望它100％有效
我也有同样的问题。所以经过两天的努力，我终于创建了这个方法，
主要方法，
enum Line
{
// Inside the Rectangle so No Intersection Point(Both Entry Point and Exit Point will be Null)
InsideTheRectangle,
// One Point Inside the Rectangle another Point Outside the Rectangle. So it has only Entry Point
Entry,
// Both Point Outside the Rectangle but Intersecting. So It has both Entry and Exit Point
EntryExit,
// Both Point Outside the Rectangle and not Intersecting. So doesn't has both Entry and Exit Point
NoIntersection
}
// Tuple<entryPoint, exitPoint, lineStatus>
private Tuple<Point, Point, Line> GetIntersectionPoint(Point a, Point b, Rectangle rect)
{
if (IsWithinRectangle(a, rect) && IsWithinRectangle(b, rect))
{
// Can't set null to Point that's why I am returning just empty object
return new Tuple<Point, Point, Line>(new Point(), new Point(), Line.InsideTheRectangle);
}
else if (!IsWithinRectangle(a, rect) && !IsWithinRectangle(b, rect))
{
if (!LineIntersectsRectangle(a, b, rect))
{
// Can't set null to Point that's why I am returning just empty object
return new Tuple<Point, Point, Line>(new Point(), new Point(), Line.NoIntersection);
}
Point entryPoint = new Point();
Point exitPoint = new Point();
bool entryPointFound = false;
// Top Line of Chart Area
if (LineIntersectsLine(a, b, new Point(0, 0), new Point(rect.Width, 0)))
{
entryPoint = GetPointFromYValue(a, b, 0);
entryPointFound = true;
}
// Right Line of Chart Area
if (LineIntersectsLine(a, b, new Point(rect.Width, 0), new Point(rect.Width, rect.Height)))
{
if (entryPointFound)
exitPoint = GetPointFromXValue(a, b, rect.Width);
else
{
entryPoint = GetPointFromXValue(a, b, rect.Width);
entryPointFound = true;
}
}
// Bottom Line of Chart
if (LineIntersectsLine(a, b, new Point(0, rect.Height), new Point(rect.Width, rect.Height)))
{
if (entryPointFound)
exitPoint = GetPointFromYValue(a, b, rect.Height);
else
{
entryPoint = GetPointFromYValue(a, b, rect.Height);
}
}
// Left Line of Chart
if (LineIntersectsLine(a, b, new Point(0, 0), new Point(0, rect.Height)))
{
exitPoint = GetPointFromXValue(a, b, 0);
}
return new Tuple<Point, Point, Line>(entryPoint, exitPoint, Line.EntryExit);
}
else
{
Point entryPoint = GetEntryIntersectionPoint(rect, a, b);
return new Tuple<Point, Point, Line>(entryPoint, new Point(), Line.Entry);
}
}
支持方法，
private Point GetEntryIntersectionPoint(Rectangle rect, Point a, Point b)
{
// For top line of the rectangle
if (LineIntersectsLine(new Point(0, 0), new Point(rect.Width, 0), a, b))
{
return GetPointFromYValue(a, b, 0);
}
// For right side line of the rectangle
else if (LineIntersectsLine(new Point(rect.Width, 0), new Point(rect.Width, rect.Height), a, b))
{
return GetPointFromXValue(a, b, rect.Width);
}
// For bottom line of the rectangle
else if (LineIntersectsLine(new Point(0, rect.Height), new Point(rect.Width, rect.Height), a, b))
{
return GetPointFromYValue(a, b, rect.Height);
}
// For left side line of the rectangle
else
{
return GetPointFromXValue(a, b, 0);
}
}
public bool LineIntersectsRectangle(Point p1, Point p2, Rectangle r)
{
return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
(r.Contains(p1) && r.Contains(p2));
}
private bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
{
float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X);
if (d == 0)
{
return false;
}
float r = q / d;
q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y);
float s = q / d;
if (r < 0 || r > 1 || s < 0 || s > 1)
{
return false;
}
return true;
}
// For Large values, processing with integer is not working properly
// So I here I am dealing only with double for high accuracy
private Point GetPointFromYValue(Point a, Point b, double y)
{
double x1 = a.X, x2 = b.X, y1 = a.Y, y2 = b.Y;
double x = (((y - y1) * (x2 - x1)) / (y2 - y1)) + x1;
return new Point((int)x, (int)y);
}
// For Large values, processing with integer is not working properly
// So here I am dealing only with double for high accuracy
private Point GetPointFromXValue(Point a, Point b, double x)
{
double x1 = a.X, x2 = b.X, y1 = a.Y, y2 = b.Y;
double y = (((x - x1) * (y2 - y1)) / (x2 - x1)) + y1;
return new Point((int)x, (int)y);
}
// rect.Contains(point) is not working properly in some cases.
// So here I created my own method
private bool IsWithinRectangle(Point a, Rectangle rect)
{
return a.X >= rect.X && a.X <= rect.X + rect.Width && a.Y >= rect.Y && a.Y <= rect.Y + rect.Height;
}
于 2021-05-09T17:45:33.510 回答
0
这是一个稍微冗长的方法，它仅使用基本数学返回（无限）线和矩形之间的相交间隔：
// 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;
}
这种方法提供了高度的数值稳定性（在所有情况下，区间都是单次减法和除法的结果），但涉及一些分支。
对于线段（带有起点和终点），您需要提供线段的起点作为原点和方向，end - start. 计算两个交点的坐标很简单 asentryPoint = origin + direction * contacts.Entry和exitPoint = origin + direction * contacts.Exit。
于 2014-03-04T10:45:24.980 回答