如何查找直线和矩形之间的交点？

Question

我有一条从A点到B点的线;我有两个点的（x，y）。我也有一个以B为中心的矩形和矩形的宽度和高度。

我需要找到与矩形相交的那一行中的点。有没有一个公式给我（x，y）那个点？

Answer 1

我不会给你一个计划要做到这一点，但这里是你如何做到这一点：

• 计算线路
• 的角度从中心计算线的角度矩形以它的一个角部
• 基于所述角度确定在哪一侧并行相交的矩形的侧和线路之间
• 计算相交的矩形

Answer 2

我不知道这是否是最好的方法，但你可以做的是找出矩形内部的线的比例。您可以从矩形的宽度以及A和B的x坐标（或者高度和y坐标;根据宽度和高度您可以检查哪种情况适用，而另一种情况将在扩展上矩形的一侧）。当你有这个时，从B到A的矢量的比例，你有你的交点的坐标。

Answer 3

点A总是矩形外和点B总是在矩形

假设矩形的中心是轴对齐，这使事情很简单：

线的斜率是s =（Ay-By）/（Ax-Bx）。

• 如果-h/2 < = S * W/2 < = H/2，则线相交：
  • 右边缘如果斧> Bx的
  • 左边缘如果斧< Bx的。
• 如果-w/2 < =（H/2）/ S < = W/2，则线相交：
  • 如果Ay的顶部边缘>按照
  • 底边如果Ay的< By。

一旦知道它相交的边缘你知道一个坐标点：x =±Bx的W/2或y =±通过H/2取决于你打哪个边缘。另一个坐标由y = By + s * w/2或x = Bx +（h/2）/ s给出。

Answer 4

您可能想看看Graphics Gems - 这是一套经典的图形例程，包含许多所需的算法。虽然它是用C语言编写的，但它们的算法仍然很闪亮，而且转换为其他语言应该是微不足道的。

对于您当前的问题，只需为矩形创建四条线并查看与给定线相交的线。

Answer 5

这里是在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; 

Answer 6

我不是一个数学迷况且我特别喜欢翻译其他语言的东西，如果别人已经这样做了，所以每当我完成一个无聊的翻译任务，我将它添加到，导致我的文章码。防止任何人做双重工作。

所以，如果你想在C＃此交汇代码，看看这里http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html

Answer 7

这里只使用基本的数学返回一个（无穷大）线和矩形之间的交叉间隔稍微详细的方法：

// 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。

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

，你可以考虑，特别是如果你是在用相同的矩形测试多行计划的另一种选择是把你的坐标系有轴与矩形的对角线排列。然后，因为你的线或射线起始于矩形的中心可以确定角度，那么你能告诉它将由角度（即90度< SEG 1，90度< < 180deg SEG 2等...）相交哪个段。然后，当然，你必须转变回原来的坐标系

虽然这似乎是更多的工作变换矩阵，可以计算出它的逆一次，然后再利用。这也可以更容易地扩展到更高维的矩形，在这种情况下，您将不得不考虑与3D中的面相交的象限和交点等等。