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

有什么建议吗?


当前回答

对于那些使用中心点和一半大小的矩形数据的人,而不是典型的x,y,w,h或x0,y0,x1,x1,下面是你可以这样做:

#include <cmath> // for fabsf(float)

struct Rectangle
{
    float centerX, centerY, halfWidth, halfHeight;
};

bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b)
{
    return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) &&
           (fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight)); 
}

其他回答

设这两个矩形是矩形A和矩形b,设它们的中心为A1和B1 (A1和B1的坐标很容易求出来),设高为Ha和Hb,宽为Wa和Wb,设dx为A1和B1之间的宽度(x), dy为A1和B1之间的高度(y)。

现在我们可以说我们可以说A和B重叠,当

if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true

这是一个用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);

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

struct point { int x, y; };

struct rect { point tl, br; }; // top left and bottom right points

// return true if rectangles overlap
bool overlap(const rect &a, const rect &b)
{
    return a.tl.x <= b.br.x && a.br.x >= b.tl.x && 
           a.tl.y >= b.br.y && a.br.y <= b.tl.y;
}
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;
}
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;
}