如何找到直线和矩形的交点?
我有一条从 A 点到 B 点的线;我有 (x,y) 两个点。我还有一个以 B 为中心的矩形以及矩形的宽度和高度。
我需要找到与矩形相交的直线上的点。有没有一个公式可以给出该点的 (x,y)?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
我有一条从 A 点到 B 点的线;我有 (x,y) 两个点。我还有一个以 B 为中心的矩形以及矩形的宽度和高度。
我需要找到与矩形相交的直线上的点。有没有一个公式可以给出该点的 (x,y)?
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
接受
或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论(14)
假设矩形是轴对齐的,这使得事情变得非常简单:
直线的斜率是 s = (Ay - By)/(斧头 - Bx)。
一旦知道了它相交的边,您就知道了一个坐标:x = Bx ± w/2 或 y = By ± h/2,具体取决于您击中的边。另一个坐标由 y = By + s * w/2 或 x = Bx + (h/2)/s 给出。
Assuming the rectangle is axis-aligned, this makes things pretty simple:
The slope of the line is s = (Ay - By)/(Ax - Bx).
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.
您可能想查看 Graphics Gems - 这是一套经典的套装图形例程并包括许多所需的算法。尽管它是用 C 语言编写的并且有点过时,但算法仍然很出色,并且转移到其他语言应该很简单。
对于您当前的问题,只需为矩形创建四条线,然后查看哪条线与给定线相交。
You might want to check out Graphics Gems - this is a classic set of routines for graphics and includes many of the algorithms required. Although it's in C and slightly dated the algorithms still sparkle and it should be trivial to transfer to other languages.
For your current problem the just create the four lines for the rectangle and see which intersect your given line.
这是 Java 中的一个解决方案,如果线段(前 4 个参数)与轴对齐矩形(最后 4 个参数)相交,则返回 true。返回交点而不是布尔值是很简单的。它的工作原理是首先检查是否完全在外部,否则使用直线方程
y=m*x+b
。我们知道构成矩形的线是轴对齐的,因此检查很容易。如果线段的起点或终点位于矩形内部,则可以采用快捷方式,但可能最好只进行数学计算,如果线段的一个或两个终点都在内部,则始终返回 true。如果您仍然需要快捷方式,请在“完全外部”检查后插入下面的代码。
Here is a solution in Java that returns true if a line segment (the first 4 parameters) intersects an axis aligned rectangle (the last 4 parameters). It would be trivial to return the intersection point instead of a boolean. It works by first checking if completely outside, else using the line equation
y=m*x+b
. We know the lines that make up the rectangle are axis aligned, so the checks are easy.It is possible to shortcut if the start or end of the segment is inside the rectangle, but probably it is better to just do the math, which will always return true if either or both segment ends are inside. If you want the shortcut anyway, insert the code below after the "completely outside" check.
鉴于最初的问题,我认为@ivanross 的答案是迄今为止最简洁和清晰的,而且我发现自己使用了相同的方法。
矩形,
我们可以使用一些三角函数来得到:
和一些简单的数学运算来获取点 A 位于哪个象限(以 B 为中心的 xy 平面)。
最后,我们再次应用基本的三角学原理,比较角度并使用切线计算交点的坐标。
Given the original question, I think that @ivanross answer is the most concise and clear so far, and I found myself using the same approach.
If we have a rectangle
we can use a bit of trigonometry to get:
and some trivial math to get in which quadrant (of the x-y plane centered in B) the point A is.
finally we compare the angles and use the tangents to calculate the coordinates of the intersection point, applying again basic trigonometry principles.
这是一个适合我的解决方案。我假设矩形与轴对齐。
数据:
现在将点 A 平移到矩形的中心,使矩形以 O(0,0) 为中心,并考虑第一季度的问题(即 x > 0 且 y > 0)。
Here is a solution that works for me. I assume that the rect is aligned to the axes.
Data:
Now translate point A by the center of the rectangle so the rect is centered in O(0,0) and consider the problem in the first quarter (i.e. x > 0 and y > 0).
我不是数学迷,也不是特别喜欢翻译其他语言的内容(如果其他人已经这样做了),所以每当我完成一项无聊的翻译任务时,我都会将其添加到引导我找到代码的文章中。防止有人做双重工作。
因此,如果您想在 C# 中使用此交集代码,请查看此处 http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html
I am not a math fan nor do I particularly enjoy translating stuff from other languages if others have already done so, so whenever I complete a boring translation task, I add it to the article that led me to the code. To prevent anyone doing double work.
So if you want to have this intersection code in C#, have a look here http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html
让我们做一些假设:
这允许我们在段
之间定义一个唯一交点
和矩形E
。 >[X,Y]∂ABCD
< img src="https://i.sstatic.net/ukWNO.png" alt="Illustration">
诀窍是寻找某个
0 < t < 1
使得t*Y+(1-t)*X
在矩形∂ABCD
上通过重写条件Γ(t) ∈ ABCD
。代码>为:现在可以展开所有场景。这产生:
Let's make some assumptions :
This allows us to define a unique intersection point
E
between the segment[X,Y]
and the rectangle∂ABCD
.The trick is to look for a certain
0 < t < 1
such thatt*Y+(1-t)*X
is on the rectangle∂ABCD
. By re-writing the conditionΓ(t) ∈ ABCD
as :it is now possible to unwind all the scenarios. This yields :
我不会给你一个程序来做到这一点,但你可以这样做:
I'll not give you a program to do that, but here is how you can do it:
希望它 100% 有效
我也遇到了同样的问题。经过两天的努力终于我创建了这个方法,
Main方法,
Supporting方法,
Hope It works 100%
I am also had this same problem. So after two days of hard effort finally I created this method,
Main method,
Supporting methods,
如果您计划使用同一矩形测试多条线,您可以考虑的另一个选择是转换坐标系以使轴与矩形的对角线对齐。然后,由于您的直线或射线从矩形的中心开始,您可以确定角度,然后您可以知道它将与哪个线段相交(即 <90deg seg 1、90deg<<180deg seg 2 等...) 。然后当然你必须变换回原始坐标系
虽然这看起来像是更多的工作,但变换矩阵及其逆可以计算一次然后重复使用。这也更容易扩展到更高维度的矩形,您必须考虑 3D 中的象限和与面的交集等。
Another option that you can consider especially if you are planning on testing many lines with the same rectangle is to transform your coordinate system to have the axes align with diagonals of the rectangle. Then since your line or ray starts at the center of the rectangle you can determine the angle then you can tell which segment it will intersect by the angle (i.e. <90deg seg 1, 90deg< <180deg seg 2 etc...). Then of course you have to transform back to the original coordinate system
Although this seems like more work the transformation matrix and its inverse can be calculated once and then reused. This also extends to higher dimensional rectangles more easily where you would have to consider quadrants and intersections with faces in 3D and so on.
我不知道这是否是最好的方法,但你可以做的是找出矩形内的线的比例。您可以从矩形的宽度以及 A 和 B 的 x 坐标(或高度和 y 坐标)之间的差值得到该值;根据宽度和高度,您可以检查哪种情况适用,其他情况将在扩展上矩形的一条边)。当你有了这个,只需取从 B 到 A 的向量的比例,你就得到了交点的坐标。
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.
这是一个稍微冗长的方法,它仅使用基本数学来返回(无限)线和矩形之间的相交间隔:
这种方法提供了高度的数值稳定性(在所有情况下,间隔都是单次减法和除法)但涉及一些分支。
对于线段(具有起点和终点),您需要提供线段的起点作为原点,并提供方向
end - start
。计算两个交叉点的坐标非常简单,如entryPoint = origin + Direction * contacts.Entry
和exitPoint = origin + Direction *contacts.Exit
。Here is a slightly verbose method that returns the intersection intervals between an (infinite) line and a rectangle using only basic math:
This approach offers a high degree of numerical stability (the intervals are, in all cases, the result of a single subtraction and division) but involves some branching.
For a line segment (with start and end points), you'd need to provide the segment's start point as the origin and for the direction,
end - start
. Calculating the coordinates of the two intersections is a simple asentryPoint = origin + direction * contacts.Entry
andexitPoint = origin + direction * contacts.Exit
.只需一点数学知识,您就可以比大多数答案所建议的更容易地解决这个问题。
策略:
在 C++ 中,这看起来像:
如果您可以通过运算符重载访问真正的向量和矩阵类,则代码变得均匀更简单:
警告:此代码不处理
px==r.centerx && 的情况py==r.centery
这将导致步骤 5 中出现被零除错误。处理该错误情况将留给读者作为练习。 :-)With a little math, you can solve this problem in a much easier fashion than most of these answers suggest.
Strategy:
In C++, this looks something like:
if you have access to a true vector and matrix class with operator overloading, the code becomes even easier:
Warning: This code doesn't handle the case where
p.x==r.centerx && p.y==r.centery
which will result in a divide-by-zero error in step 5. Handling that error condition will be left as an exercise to the reader. :-)