我试图写一个c++程序,从用户获取以下输入来构造矩形(2和5之间):高度,宽度,x-pos, y-pos。所有这些矩形都平行于x轴和y轴,也就是说它们所有边的斜率都是0或无穷大。

我试图实现这个问题中提到的东西,但我没有太多的运气。

我目前的实现如下:

// 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)我是否已经正确地实现了我链接的算法,或者如果我确实如何解释这一点?

有什么建议吗?


当前回答

最简单的方法是

/**
 * Check if two rectangles collide
 * x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
 * x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
 */
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
  return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}

首先要记住在计算机中坐标系统是颠倒的。x轴与数学中的相同,但y轴向下增大,向上减小。 如果矩形是从中心画的。 如果x1坐标大于x2加上它的一半宽。然后这意味着他们会互相接触。用同样的方法向下+一半高。它会碰撞的。

其他回答

struct Rect
{
   Rect(int x1, int x2, int y1, int y2)
   : x1(x1), x2(x2), y1(y1), y2(y2)
   {
       assert(x1 < x2);
       assert(y1 < y2);
   }

   int x1, x2, y1, y2;
};

//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
    return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
           r1.y1 < r2.y2 && r2.x1 < r1.y2;
}

//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
    return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
           r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}

问你自己一个相反的问题:我如何确定两个矩形是否完全不相交?显然,矩形a完全在矩形B的左边不相交。如果A完全在右边。同样,如果A完全高于B或完全低于B,在任何其他情况下,A和B相交。

以下内容可能有bug,但我对算法相当有信心:

struct Rectangle { int x; int y; int width; int height; };

bool is_left_of(Rectangle const & a, Rectangle const & b) {
   if (a.x + a.width <= b.x) return true;
   return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
   return is_left_of(b, a);
}

bool not_intersect( Rectangle const & a, Rectangle const & b) {
   if (is_left_of(a, b)) return true;
   if (is_right_of(a, b)) return true;
   // Do the same for top/bottom...
 }

bool intersect(Rectangle const & a, Rectangle const & b) {
  return !not_intersect(a, b);
}
bool Square::IsOverlappig(Square &other)
{
    bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
    bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
    bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
    bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
    return result1 | result2 | result3 | result4;
}

这是一个用c++快速检查两个矩形是否重叠的方法:

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
    && std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

它的工作原理是计算相交矩形的左右边界,然后比较它们:如果右边界等于或小于左边界,这意味着交点是空的,因此矩形不重叠;否则,它将再次尝试顶部和底部边框。

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.

如果第一个比较有很高的错误几率,那么四个比较方法可能比这个方法更好。但这是非常罕见的,因为这意味着第二个矩形通常在第一个矩形的左边,而不是在右边或重叠;大多数情况下,您需要检查第一个矩形的两侧,这通常会使分支预测的优势失效。

根据矩形的预期分布,这种方法还可以进一步改进:

If you expect the checked rectangles to be predominantly to the left or right of each other, then the method above works best. This is probably the case, for example, when you're using the rectangle intersection to check collisions for a game, where the game objects are predominantly distributed horizontally (e.g. a SuperMarioBros-like game). If you expect the checked rectangles to be predominantly to the top or bottom of each other, e.g. in an Icy Tower type of game, then checking top/bottom first and left/right last will probably be faster:

return std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom)
    && std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right);

然而,如果相交的概率接近于不相交的概率,那么最好有一个完全无分支的替代方案:

return std::max(rectA.left, rectB.left) < std::min(rectA.right, rectB.right)
     & std::max(rectA.top, rectB.top) < std::min(rectA.bottom, rectB.bottom);

(注意&&变成了一个&)

A和B是两个矩形。C是它们的覆盖矩形。

four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom)
four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom)

A.width = abs(xAleft-xAright);
A.height = abs(yAleft-yAright);
B.width = abs(xBleft-xBright);
B.height = abs(yBleft-yBright);

C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright);
C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom);

A and B does not overlap if
(C.width >= A.width + B.width )
OR
(C.height >= A.height + B.height) 

它考虑到所有可能的情况。