那些遇到过的问题

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

Joh*_*son 50 algorithm geometry intersection line

我有一条从A点到B点的线; 我有(x,y)这两点.我还有一个以B为中心的矩形以及矩形的宽度和高度.

我需要找到与矩形相交的线中的点.有没有一个公式给我这一点的(x,y)？

Jor*_*ren 20

点A始终位于矩形之外,点B始终位于矩形的中心

假设矩形是轴对齐的,这使事情变得非常简单:

线的斜率是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给出.

  • 谢谢Joren,我做了这个算法的小提琴:http://jsfiddle.net/524ctnfh/它似乎左右和上下边缘交换,所以它应该是:*right*:Ax <Bx ;*left*:Ax> Bx;*顶部*:Ay <By;*底*:Ay> By; (3认同)
  • 对不起,我在脚本中犯了一些错误,这里是固定版本:http://jsfiddle.net/524ctnfh/1/ (2认同)

pet*_*ust 19

您可能想查看Graphics Gems - 这是一组经典的图形例程,包括许多所需的算法.虽然它在C语言中略显陈旧,但算法仍然闪烁,转换到其他语言应该是微不足道的.

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

  • 这与OP提出的要求相差太远. (2认同)

TWi*_*Rob 15 

/**
 * 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");
	});
})();
Run Code Online (Sandbox Code Playgroud) 
<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>
Run Code Online (Sandbox Code Playgroud)

  • @Mark 归因从来都不是无耻的，而且比仅链接的答案要好得多；） (3认同)

Nat*_*teS 9

这是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;
}
Run Code Online (Sandbox Code Playgroud)

如果段的开头或结尾在矩形内部,则可以快捷方式,但可能最好只进行数学运算,如果其中一个或两个段结束在内,则总是返回true.如果您还想要快捷方式,请在"完全外部"检查后插入下面的代码.

// Start or end inside.
if ((x1 > minX && x1 < maxX && y1 > minY && y1 < maxY) || (x2 > minX && x2 < maxX && y2 > minY && y2 < maxY)) return true;
Run Code Online (Sandbox Code Playgroud)

  • 非常感谢！，这就是我正在寻找的。我将它移到 javascript，这是我用来测试它的小提琴 http://jsfiddle.net/pjnovas/fPMG5/ 欢呼！ (2认同)

Fed*_*nis 7

鉴于最初的问题，我认为@ivanross 的答案是迄今为止最简洁和清晰的，而且我发现自己使用了相同的方法。

\n

在此输入图像描述

\n

如果我们有一个矩形

\n
    \n
  • 以B为中心
    • \n
  • 边平行于 x 轴和 y 轴
    • \n
\n

我们可以使用一些三角学来得到：

\n
    \n
  • tan \xcf\x86 (phi) = h/w
    • \n
  • tan \xce\xb8 (θ) = (yB-yA)/(xB-xA)
    • \n
\n

以及一些简单的数学计算来确定 A 点位于（以 B 为中心的 xy 平面）的哪个象限。

\n

最后，我们再次应用基本的三角学原理，比较角度并使用切线计算交点的坐标。

\n

\r\n
\r\n
/**\n * Finds the intersection point between\n *     * a rectangle centered in point B\n *       with sides parallel to the x and y axes\n *     * a line passing through points A and B (the center of the rectangle)\n *\n * @param width: rectangle width\n * @param height: rectangle height\n * @param xB; rectangle center x coordinate\n * @param yB; rectangle center y coordinate\n * @param xA; point A x coordinate\n * @param yA; point A y coordinate\n * @author Federico Destefanis\n * @see <a href="https://stackoverflow.com/a/31254199/2668213">based on</a>\n */\n\nfunction lineIntersectionOnRect(width, height, xB, yB, xA, yA) {\n\n  var w = width / 2;\n  var h = height / 2;\n\n  var dx = xA - xB;\n  var dy = yA - yB;\n\n  //if A=B return B itself\n  if (dx == 0 && dy == 0) return {\n    x: xB,\n    y: yB\n  };\n\n  var tan_phi = h / w;\n  var tan_theta = Math.abs(dy / dx);\n\n  //tell me in which quadrant the A point is\n  var qx = Math.sign(dx);\n  var qy = Math.sign(dy);\n\n\n  if (tan_theta > tan_phi) {\n    xI = xB + (h / tan_theta) * qx;\n    yI = yB + h * qy;\n  } else {\n    xI = xB + w * qx;\n    yI = yB + w * tan_theta * qy;\n  }\n\n  return {\n    x: xI,\n    y: yI\n  };\n\n}\n\n\nvar coords = lineIntersectionOnRect(6, 4, 0, 0, 1, 0);\nconsole.log(coords);
Run Code Online (Sandbox Code Playgroud)\r\n
\r\n
\r\n

\n

  • 效果很好。交点正确 (2认同)

小智 5

这是一个对我有用的解决方案。我假设矩形与轴对齐。

数据：

// 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
Run Code Online (Sandbox Code Playgroud)

现在将点 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]
Run Code Online (Sandbox Code Playgroud)

Luk*_*ský 3

我不会给你一个程序来做到这一点，但你可以这样做：

  • 计算线的角度
  • 计算从矩形中心到其一个角的直线的角度
  • 根据角度确定线与矩形的哪一侧相交
  • 计算矩形边与直线之间的交点

归档时间：

查看次数：

55925 次

最近记录：

7 年，10 月 前
箭头未触及d3.js中的节点 0
更多相关链接
相关归档
当样本量很大时,计算字符串相似度得分的有效方法？ 15
Xiaolin Wu在C语言中的行算法的源代码？ 11
良好的情绪分析算法 7
如何在Java中使用前导零对数字进行排序？ 7
给定来自K个连续整数的每个数字的数字恢复序列 6
Java中形状的快速联合 5
Corona SDK矢量圆圈抗锯齿 - 它有效吗？ 5
在ggplot2中向x轴添加文本 3
使用ruby中的另一个值数组搜索数组 2
四边形的对角线 1
难疑归档
从Git存储库中删除文件而不从本地文件系统中删除它 2892
在Python中查找包含它的列表的项目的索引 2887
检查JavaScript对象中是否存在密钥？ 2750
在YAML中,如何在多行中断字符串？ 1388
如何正确强制推送Git？ 1206
如何重置MySQL中的AUTO_INCREMENT？ 1174
如何撤消git reset --hard HEAD~1？ 1083
为什么使用'=='或'is'比较字符串有时会产生不同的结果？ 1076
jQuery的jquery-1.10.2.min.map触发了404(未找到) 1051
字段和属性之间有什么区别？ 1032