判断两个矩形是否重叠?
我正在尝试编写一个 C++ 程序,它接受用户的以下输入来构造矩形(2 到 5 之间):高度、宽度、x 位置、y 位置。 所有这些矩形都将平行于 x 轴和 y 轴存在,即它们的所有边都将具有 0 或无穷大的斜率。
我尝试实现 this 问题中提到的内容,但我运气不佳。
我当前的实现执行以下操作:
// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
但是,我不太确定是否(a)我已经正确实现了链接到的算法,或者我是否准确地解释了这一点?
有什么建议么?
I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that is all of their edges will have slopes of 0 or infinity.
I've tried to implement what is mentioned in this question but I am not having very much luck.
My current implementation does the following:
// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
However I'm not quite sure if (a) I've implemented the algorithm I linked to correctly, or if I did exactly how to interpret this?
Any suggestions?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(21)
检查一个矩形是否完全在另一个矩形之外更容易,因此如果它位于
左侧...
或右侧...
或顶部...
或底部...
第二个矩形的 ,它不可能与它相撞。 因此,要拥有一个返回布尔值表示矩形是否发生碰撞的函数,我们只需通过逻辑或组合条件并对结果取反:
要仅在触摸时就已经收到正结果,我们可以更改“<” 和“>” 通过“<=”和“>=”。
It is easier to check if a rectangle is completly outside the other, so if it is either
on the left...
or on the right...
or on top...
or on the bottom...
of the second rectangle, it cannot possibly collide with it. So to have a function that returns a Boolean saying weather the rectangles collide, we simply combine the conditions by logical ORs and negate the result:
To already receive a positive result when touching only, we can change the "<" and ">" by "<=" and ">=".
这是用 C++ 检查两个矩形是否重叠的非常快速的方法:
它的工作原理是计算相交矩形的左边框和右边框,然后比较它们:如果右边框等于或小于左边框,则意味着交集是空的,因此矩形不重叠; 否则,它会再次尝试使用顶部和底部边框。
与传统的 4 次比较相比,该方法有什么优势? 这是关于现代处理器的设计方式。 他们有一种叫做分支预测的东西,当比较结果始终相同时,它的效果很好,但否则会带来巨大的性能损失。 然而,在没有分支指令的情况下,CPU 的性能相当不错。 通过计算交叉点的边界,而不是对每个轴进行两次单独的检查,我们可以保存两个分支,每对一个。
如果第一次比较很可能是错误的,那么四次比较方法的性能可能会优于此方法。 不过,这种情况非常罕见,因为这意味着第二个矩形通常位于第一个矩形的左侧,而不是右侧或与之重叠; 大多数情况下,您需要检查第一个矩形两侧的矩形,这通常会抵消分支预测的优势。
这种方法还可以进一步改进,具体取决于矩形的预期分布:
请注意将
&&
更改为单个&
)This is a very fast way to check with C++ if two rectangles overlap:
It works by calculating the left and right borders of the intersecting rectangle, and then comparing them: if the right border is equal to or less than the left border, it means that the intersection is empty and therefore the rectangles do not overlap; otherwise, it tries again with the top and bottom borders.
What is the advantage of this method over the conventional alternative of 4 comparisons? It's about how modern processors are designed. They have something called branch prediction, which works well when the result of a comparison is always the same, but have a huge performance penalty otherwise. However, in the absence of branch instructions, the CPU performs quite well. By calculating the borders of the intersection instead of having two separate checks for each axis, we're saving two branches, one per pair.
It is possible that the four comparisons method outperforms this one, if the first comparison has a high chance of being false. That is very rare, though, because it means that the second rectangle is most often on the left side of the first rectangle, and not on the right side or overlapping it; and most often, you need to check rectangles on both sides of the first one, which normally voids the advantages of branch prediction.
This method can be improved even more, depending on the expected distribution of rectangles:
(Note the change of
&&
to a single&
)假设您已经定义了矩形的位置和大小,如下所示:
我的 C++ 实现如下:
根据上图给出的函数调用示例:
if
块内的比较如下所示:Suppose that you have defined the positions and sizes of the rectangles like this:
My C++ implementation is like this:
An example function call according to the given figure above:
The comparisons inside the
if
block will look like below:问自己相反的问题:如何确定两个矩形是否根本不相交? 显然,完全位于矩形 B 左侧的矩形 A 不相交。 另外,如果 A 完全位于右侧。 同样,如果 A 完全高于 B 或完全低于 B。在任何其他情况下,A 和 B 相交。
下面的内容可能有错误,但我对算法很有信心:
Ask yourself the opposite question: How can I determine if two rectangles do not intersect at all? Obviously, a rectangle A completely to the left of rectangle B does not intersect. Also if A is completely to the right. And similarly if A is completely above B or completely below B. In any other case A and B intersect.
What follows may have bugs, but I am pretty confident about the algorithm:
在这个问题中,您链接到矩形何时处于任意旋转角度的数学。 然而,如果我理解问题中有关角度的一点,我会解释所有矩形都是相互垂直的。
一般了解重叠面积的公式是:
使用示例:
1)将所有 x 坐标(左侧和右侧)收集到一个列表中,然后对其进行排序并删除重复项
2)收集所有 y 坐标(顶部和底部)放入列表中,然后对其进行排序并删除重复项
3) 通过唯一 x 坐标之间的间隙数 * 唯一 y 坐标之间的间隙数创建一个 2D 数组。
4) 将所有矩形绘制到该网格中,增加其出现的每个单元格的计数:
5) 当您绘制矩形时,很容易拦截重叠部分。
In the question, you link to the maths for when rectangles are at arbitrary angles of rotation. If I understand the bit about angles in the question however, I interpret that all rectangles are perpendicular to one another.
A general knowing the area of overlap formula is:
Using the example:
1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates
2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates
3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.
4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:
5) As you paint the rectangles, its easy to intercept the overlaps.
下面是它在 Java API 中的实现方式:
Here's how it's done in the Java API:
不要将坐标视为指示像素所在的位置。 将它们视为像素之间。 这样,2x2 矩形的面积应该是 4,而不是 9。
Don't think of coordinates as indicating where pixels are. Think of them as being between the pixels. That way, the area of a 2x2 rectangle should be 4, not 9.
最简单的方法是
首先让您记住,在计算机中,坐标系是颠倒的。 x 轴与数学中的相同,但 y 轴向下增加,向上减少。
如果矩形是从中心绘制的。
如果 x1 坐标大于 x2 加上其宽度的一半。 那么这意味着走一半他们就会互相碰触。 以同样的方式向下+其高度的一半。 会碰撞..
Easiest way is
first of all put it in to your mind that in computers the coordinates system is upside down. x-axis is same as in mathematics but y-axis increases downwards and decrease on going upward..
if rectangle are drawn from center.
if x1 coordinates is greater than x2 plus its its half of widht. then it means going half they will touch each other. and in the same manner going downward + half of its height. it will collide..
对于那些使用中心点和一半大小作为矩形数据的人,而不是典型的 x,y,w,h 或 x0,y0,x1,x1,以下是您可以执行的操作方法:
For those of you who are using center points and half sizes for their rectangle data, instead of the typical x,y,w,h, or x0,y0,x1,x1, here's how you can do it:
假设这两个矩形是矩形A和矩形B。设它们的中心为A1和B1(A1和B1的坐标很容易找到),设高度为Ha和Hb,宽度为Wa和Wb,设dx为width(x) A1 和 B1 之间的距离,dy 是 A1 和 B1 之间的 height(y) 距离。
现在我们可以说 A 和 B 重叠:
Lets say the two rectangles are rectangle A and rectangle B. Let their centers be A1 and B1 (coordinates of A1 and B1 can be easily found out), let the heights be Ha and Hb, width be Wa and Wb, let dx be the width(x) distance between A1 and B1 and dy be the height(y) distance between A1 and B1.
Now we can say we can say A and B overlap: when
如果矩形重叠,则重叠面积将大于零。 现在让我们找到重叠区域:
如果它们重叠,那么重叠矩形的左边缘将是 max(r1.x1, r2.x1) ,右边缘将是 min(r1 .x2,r2.x2)。 因此,重叠的长度将为 min(r1.x2, r2.x2) - max(r1.x1, r2.x1) ,
因此面积将为:
如果
area = 0< /code> 那么它们就不会重叠。
很简单不是吗?
If the rectangles overlap then the overlap area will be greater than zero. Now let us find the overlap area:
If they overlap then the left edge of overlap-rect will be the
max(r1.x1, r2.x1)
and right edge will bemin(r1.x2, r2.x2)
. So the length of the overlap will bemin(r1.x2, r2.x2) - max(r1.x1, r2.x1)
So the area will be:
If
area = 0
then they don't overlap.Simple isn't it?
我已经实现了一个C#版本,它很容易转换为C++。
I have implemented a C# version, it is easily converted to C++.
我有一个非常简单的解决方案
让 x1,y1 x2,y2 ,l1,b1,l2,be 坐标和它们的长度和宽度分别
考虑条件 ((x2
现在,这些矩形重叠的唯一方法是,x1,y1 的对角线点将位于另一个矩形内,或者类似地,x2,y2 的点对角线将位于另一个矩形内。 这正是上述条件所暗示的。
I have a very easy solution
let x1,y1 x2,y2 ,l1,b1,l2,be cordinates and lengths and breadths of them respectively
consider the condition ((x2
now the only way these rectangle will overlap is if the point diagonal to x1,y1 will lie inside the other rectangle or similarly the point diagonal to x2,y2 will lie inside the other rectangle. which is exactly the above condition implies.
A和B是两个矩形。 C 是它们的覆盖矩形。
它会照顾所有可能的情况。
A and B be two rectangle. C be their covering rectangle.
It takes care all possible cases.
这是来自《Java 编程入门 - 综合版》一书的练习 3.28。 该代码测试两个矩形是否有齿,一个是否在另一个内部以及一个是否在另一个外部。 如果这些条件都不满足,则两者重叠。
**3.28(几何:两个矩形)编写一个程序,提示用户输入
两个矩形的中心 x、y 坐标、宽度和高度,并确定
第二个矩形是否在第一个矩形内部或与第一个矩形重叠,如图所示
如图 3.9 所示。 测试您的程序以涵盖所有情况。
以下是运行示例:
输入 r1 的中心 x、y 坐标、宽度和高度:2.5 4 2.5 43
输入 r2 的中心 x、y 坐标、宽度和高度:1.5 5 0.5 3
r2 在 r1 内部
输入 r1 中心的 x、y 坐标、宽度和高度:1 2 3 5.5
输入 r2 的中心 x、y 坐标、宽度和高度:3 4 4.5 5
r2 与 r1 重叠
输入 r1 中心的 x、y 坐标、宽度和高度:1 2 3 3
输入 r2 的中心 x、y 坐标、宽度和高度:40 45 3 2
r2 不与 r1 重叠
This is from exercise 3.28 from the book Introduction to Java Programming- Comprehensive Edition. The code tests whether the two rectangles are indenticle, whether one is inside the other and whether one is outside the other. If none of these condition are met then the two overlap.
**3.28 (Geometry: two rectangles) Write a program that prompts the user to enter the
center x-, y-coordinates, width, and height of two rectangles and determines
whether the second rectangle is inside the first or overlaps with the first, as shown
in Figure 3.9. Test your program to cover all cases.
Here are the sample runs:
Enter r1's center x-, y-coordinates, width, and height: 2.5 4 2.5 43
Enter r2's center x-, y-coordinates, width, and height: 1.5 5 0.5 3
r2 is inside r1
Enter r1's center x-, y-coordinates, width, and height: 1 2 3 5.5
Enter r2's center x-, y-coordinates, width, and height: 3 4 4.5 5
r2 overlaps r1
Enter r1's center x-, y-coordinates, width, and height: 1 2 3 3
Enter r2's center x-, y-coordinates, width, and height: 40 45 3 2
r2 does not overlap r1
或者,使用笛卡尔坐标
(X1为左坐标,X2为右坐标,从左到右递增,Y1为上坐标,Y2为下坐标,从下到上递增< /strong> -- 如果这不是您的坐标系 [例如,大多数计算机的 Y 方向相反],交换下面的比较)...
假设您有矩形 A 和矩形 B。
证明是通过反证法。 四个条件中的任何一个都保证不存在重叠:
- 那么 A 完全位于 B
- 那么 A 完全位于 B
- 那么 A 完全低于 B
- 那么 A 完全高于 B
因此,非重叠的条件是
因此,重叠的充分条件是相反的。
德摩根定律说
Not (A or B or C or D)
与Not A And Not B And Not C And Not D
相同
所以使用 De Morgan,我们有
这相当于:
RectA.Left < RectB.Right
],并且RectA.Right > RectB.Left
],并且RectA.Top > RectB.Bottom
],并且RectA.Bottom < RectB.Top
]注释 1:很明显,同样的原理可以扩展到任意数量的维度。
注 2:仅对一个像素的重叠进行计数也应该相当明显,请更改该像素上的
<
和/或>
<=
或>=
的边界。注3:当使用笛卡尔坐标(X,Y)时,这个答案是基于标准代数笛卡尔坐标(x从左到右增加,Y从下到上增加)。 显然,如果计算机系统可能以不同的方式机械化屏幕坐标(例如,从上到下增加 Y,或从右到左增加 X),则需要相应地调整语法/
or, using Cartesian coordinates
(With X1 being left coord, X2 being right coord, increasing from left to right and Y1 being Top coord, and Y2 being Bottom coord, increasing from bottom to top -- if this is not how your coordinate system [e.g. most computers have the Y direction reversed], swap the comparisons below) ...
Say you have Rect A, and Rect B.
Proof is by contradiction. Any one of four conditions guarantees that no overlap can exist:
- then A is Totally to right Of B
- then A is Totally to left Of B
- then A is Totally below B
- then A is Totally above B
So condition for Non-Overlap is
Therefore, a sufficient condition for Overlap is the opposite.
De Morgan's law says
Not (A or B or C or D)
is the same asNot A And Not B And Not C And Not D
so using De Morgan, we have
This is equivalent to:
RectA.Left < RectB.Right
], andRectA.Right > RectB.Left
], andRectA.Top > RectB.Bottom
], andRectA.Bottom < RectB.Top
]Note 1: It is fairly obvious this same principle can be extended to any number of dimensions.
Note 2: It should also be fairly obvious to count overlaps of just one pixel, change the
<
and/or the>
on that boundary to a<=
or a>=
.Note 3: This answer, when utilizing Cartesian coordinates (X, Y) is based on standard algebraic Cartesian coordinates (x increases left to right, and Y increases bottom to top). Obviously, where a computer system might mechanize screen coordinates differently, (e.g., increasing Y from top to bottom, or X From right to left), the syntax will need to be adjusted accordingly/