如何find一个线和一个矩形的交点？
我有一条从A点到B点的路线; 我有两个点（x，y）。 我也有一个以B为中心的矩形和矩形的宽度和高度。
我需要find与矩形相交的线上的点。 有没有一个公式给我（x，y）那个点？
你可能想看看graphicsgem – 这是一个经典的graphics例程，包括许多所需的algorithm。 虽然它是C语言，并且稍微有点过时了，但algorithm仍然闪耀着，而且转移到其他语言应该是微不足道的。
对于你目前的问题，只需创build矩形的四条线，看看哪一条相交给你的线。
点A总是在矩形的外面，点B总是在矩形的中心
假设矩形是轴alignment的，这使得事情变得非常简单：
线的斜率是s =（Ay-By）/（Ax-Bx）。
- 如果-h / 2 <= s * w / 2 <= h / 2，则线相交：
- 如果Ax> Bx右边
- 如果Ax <Bx则左边。
- 如果-w / 2 <=（h / 2）/ s <= w / 2，那么该线相交：
- 顶部边缘如果Ay> By
- 底边如果Ay <By。
一旦知道了它相交的边缘，就可以知道一个坐标：x = Bx±w / 2或者y = By±h / 2，具体取决于你碰到的边缘。 另一个坐标由y = By + s * w / 2或x = Bx +（h / 2）/ s给出。
/** * 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) { //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="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>
这里是Java中的一个解决scheme，如果线段（前4个参数）与轴alignment的矩形（最后4个参数）相交，则返回true。 返回交点而不是布尔值将是微不足道的。 它首先检查是否完全在外面，否则使用直线方程y=m*x+b 。 我们知道组成矩形的线是轴alignment的，所以检查很容易。
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; }
如果段的开始或结束位于矩形内部，则可以进行快捷操作，但可能最好只做math运算，如果其中一个或两个段结束在里面，它总是返回true。 如果您想使用快捷方式，请在“完全外部”检查后插入以下代码。
// Start or end inside. if ((x1 > minX && x1 < maxX && y1 > minY && y1 < maxY) || (x2 > minX && x2 < maxX && y2 > minY && y2 < maxY)) return true;
我不会给你一个程序来做到这一点，但这是你如何做到这一点：
- 计算线的angular度
- 计算从矩形中心到其中一个angular的直线的angular度
- 基于angular度确定线与矩形相交的哪一侧
- 计算矩形的边和线之间的交点
我不是一个math迷，如果别人已经这样做了，我也不喜欢翻译其他语言的东西，所以无论什么时候我完成一个无聊的翻译任务，我把它添加到文章，导致我的代码。 为了防止任何人做双重工作。
所以如果你想在C＃中有这个交集，请看这里http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html
另一种select，你可以考虑，特别是如果你打算testing许多具有相同矩形的线条，就是转换坐标系使轴线与矩形的对angular线alignment。 那么由于你的直线或射线从矩形的中心开始，你可以确定angular度，那么你就可以知道它将与angular度相交（即90deg seg 1，90deg <<180deg seg 2等等）。 那么当然，你必须转换回原来的坐标系统
虽然这似乎更多的工作转换matrix及其逆可以计算一次，然后重新使用。 这也可以更容易地扩展到更高维的矩形，在那里你将不得不考虑与三维面的象限和交点，等等。
我不知道这是否是最好的方法，但你可以做的是找出矩形内部的线的比例。 你可以从矩形的宽度以及A和B的x坐标（或者高度和y坐标）之间的差异来得到它;根据宽度和高度，你可以检查哪种情况适用，另一种情况是在扩展矩形的一侧）。 当你有这个时，从B到A的vector的比例，你有你的交点的坐标。
下面是一个稍微冗长的方法，它只使用基本的math运算来返回（无限）线和矩形之间的交点间隔：
// 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 。 计算两个交点的坐标是一个简单的entryPoint = origin + direction * contacts.Entry和exitPoint = origin + direction * contacts.Exit 。
