快速矩形到矩形相交

测试两个矩形是否相交的快速方法是什么？

在互联网上搜索出了这个笑话(WOOT!)，但我不知道如何用 Javascript 编写它，它似乎是用一种古老的 C + + 形式编写的。

struct
{
LONG    left;
LONG    top;
LONG    right;
LONG    bottom;
} RECT;


bool IntersectRect(const RECT * r1, const RECT * r2)
{
return ! ( r2->left > r1->right
|| r2->right < r1->left
|| r2->top > r1->bottom
|| r2->bottom < r1->top
);
}
97259 次浏览
小开 
function intersect(a, b) {
return (a.left <= b.right &&
b.left <= a.right &&
a.top <= b.bottom &&
b.top <= a.bottom)
}

This assumes that the top is normally less than bottom (i.e. that y coordinates increase downwards).

小开
最佳答案

This is how that code can be translated to JavaScript. Note that there is a typo in your code, and in that of the article, as the comments have suggested. Specifically r2->right left should be r2->right < r1->left and r2->bottom top should be r2->bottom < r1->top for the function to work.

function intersectRect(r1, r2) {
return !(r2.left > r1.right ||
r2.right < r1.left ||
r2.top > r1.bottom ||
r2.bottom < r1.top);
}

Test case:

var rectA = {
left:   10,
top:    10,
right:  30,
bottom: 30
};


var rectB = {
left:   20,
top:    20,
right:  50,
bottom: 50
};


var rectC = {
left:   70,
top:    70,
right:  90,
bottom: 90
};


intersectRect(rectA, rectB);  // returns true
intersectRect(rectA, rectC);  // returns false
小开

This is how the .NET Framework implements Rectangle.Intersect

public bool IntersectsWith(Rectangle rect)
{
if (rect.X < this.X + this.Width && this.X < rect.X + rect.Width && rect.Y < this.Y + this.Height)
return this.Y < rect.Y + rect.Height;
else
return false;
}

Or the static version:

public static Rectangle Intersect(Rectangle a, Rectangle b)
{
int x = Math.Max(a.X, b.X);
int num1 = Math.Min(a.X + a.Width, b.X + b.Width);
int y = Math.Max(a.Y, b.Y);
int num2 = Math.Min(a.Y + a.Height, b.Y + b.Height);
if (num1 >= x && num2 >= y)
return new Rectangle(x, y, num1 - x, num2 - y);
else
return Rectangle.Empty;
}
小开

Another more simple way. (This assumes the y-axis increases downwards).

function intersect(a, b) {
return Math.max(a.left, b.left) < Math.min(a.right, b.right) &&
Math.max(a.top, b.top) < Math.min(a.bottom, b.bottom);
}

The 4 numbers (max's and min's) in the condition above also give the intersection points.

小开

This has a Rect type you can use. It is already JavaScript.

https://dxr.mozilla.org/mozilla-beta/source/toolkit/modules/Geometry.jsm

小开

I used a blend of methods, to detect a smaller rectangle inside a large rectangle. This is a nodejs method and uses width/height but can easily be adapted.

            isIntersectingRect: function (r1, r2) {
var quickCheck = (r1.x <= r2.x + r2.w &&
r2.x <= r1.x + r1.w &&
r1.y <= r2.y + r2.h &&
r2.y <= r1.y + r1.h)
if (quickCheck) return true;
var x_overlap = Math.max(0, Math.min(r1.x + r1.w, r2.x + r2.w) - Math.max(r1.x, r2.x));
var y_overlap = Math.max(0, Math.min(r1.y + r1.h, r2.y + r2.h) - Math.max(r1.y, r2.y));
var overlapArea = x_overlap * y_overlap;
return overlapArea == 0;
}
小开

The current .NET way is simply

    public bool IsEmpty => _width < 0.0;


public bool IntersectsWith(Rect rect)
{
if (IsEmpty || rect.IsEmpty)
{
return false;
}


if (rect.Left <= Right && rect.Right >= Left && rect.Top <= Bottom)
{
return rect.Bottom >= Top;
}


return false;
}

提交答案