确定两个矩形是否相互重叠? [英] Determine if two rectangles overlap each other?
问题描述
我正在尝试编写一个 C++ 程序，它从用户那里获取以下输入来构造矩形(2 到 5 之间):高度、宽度、x-pos、y-pos.所有这些矩形都将平行于 x 轴和 y 轴存在，也就是说，它们的所有边都将具有 0 或无穷大的斜率.
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.
我当前的实现如下:
// 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) 我是否正确实现了链接到的算法，或者我是否准确地解释了这一点?
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?
有什么建议吗?
推荐答案
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
或者，使用笛卡尔坐标
(X1为左坐标，X2为右坐标，从左到右递增，Y1为上坐标，Y2为下坐标，从下到上递增> -- 如果这不是您的坐标系 [例如大多数计算机的 Y 方向相反]，交换下面的比较) ...
(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) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
假设你有矩形 A 和矩形 B.证明是自相矛盾的.四个条件中的任何一个都保证不会存在重叠:
Say you have Rect A, and Rect B. Proof is by contradiction. Any one of four conditions guarantees that no overlap can exist:
- 条件 1.如果 A 的左边缘在 B 的右边缘的右侧，- 那么 A 完全在 B 的右边
- 条件 2.如果 A 的右边缘在 B 的左边缘的左侧，- 那么 A 完全在 B 的左边
- 条件 3.如果 A 的顶部边缘低于 B 的底部边缘，- 那么A完全低于B
- 条件 4.如果 A 的底边高于 B 的顶边，- 那么 A 完全高于 B
非重叠的条件是
NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4因此，Overlap 的充分条件是相反的.
Therefore, a sufficient condition for Overlap is the opposite.
Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)德摩根定律说Not (A or B or C or D) 等同于 Not A And Not B And Not C And Not D
所以使用德摩根，我们有
De Morgan's law says
Not (A or B or C or D) is the same as Not A And Not B And Not C And Not D
so using De Morgan, we have
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4这相当于:
- A 的左边缘到 B 的右边缘的左边，[
RectA.Left <;RectB.Right] 和 - A 的右边缘到 B 的左边缘的右边，[
RectA.Right >RectB.Left] 和 - A 的顶部高于 B 的底部，[
RectA.Top >RectB.Bottom] 和 - A 的底部低于 B 的顶部 [
RectA.Bottom <RectB.Top]
- A's Left Edge to left of B's right edge, [
RectA.Left < RectB.Right], and - A's right edge to right of B's left edge, [
RectA.Right > RectB.Left], and - A's top above B's bottom, [
RectA.Top > RectB.Bottom], and - A's bottom below B's Top [
RectA.Bottom < RectB.Top]
注意 1:很明显，同样的原则可以扩展到任意数量的维度.
注意 2:计算一个像素的重叠也应该是相当明显的，更改 < 和/或 ><= 或 >= 的边界.
注意 3:这个答案，当使用笛卡尔坐标 (X, Y) 时基于标准代数笛卡尔坐标(x 从左到右增加，Y 从下到上增加).显然，如果计算机系统可能会以不同的方式机械化屏幕坐标(例如，从上到下增加 Y，或从右到左增加 X)，则需要相应地调整语法/
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/
这篇关于确定两个矩形是否相互重叠?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
