Fast Rectangle to Rectangle Intersection

Fast rectangle to rectangle intersection

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

Fastest way to check intersection between a Rectangle List and a single Rectangle

You can try organize your rectangles in a structure called k-d-tree.

It gives you up to O(log N) complexity in a large rectangle array (> 100).

F.e. make binary tree with fixed length, say, 2. Divide your space into left and right halves, then each half divide into top and bottom quarters (and so on).

Inside leaf node create a list on rectangles. If a rectangles falls into left half and top quarter, locate it in the list of this quarter.

A rectangle may be locates in a few list at the same time (f.e. in case if it falls in left and right halves).

To check intersection you should test rectangle in responding halves and quarters.

Or, you removes too many rectangles, it's faster to copy remaining rectangles into the new list in your own code.

Small example.

public enum CheckBy
{
    Horizontal,

    Vertical
}

public class Node
{
    public Node First { get; set; }

    public Node Second { get; set; }

    public int Coordinate { get; set; }

    public CheckBy CheckBy { get; set; }

    public List<Rectangle> Rectangles { get; set; }
}

public bool IsRectangleInFist(Node node, Rectangle rectangle)
{
    if (node.CheckBy == CheckBy.Horizontal)
        return rectangle.Left <= node.Coordinate;

    return rectangle.Top <= node.Coordinate;
}

public bool IsRectangelInSecond(Node node, Rectangle rectangle)
{
    if (node.CheckBy == CheckBy.Horizontal)
        return rectangle.Right >= node.Coordinate;

    return rectangle.Bottom >= node.Coordinate;
}

public void AddRectangleInSuitableNode(Node node, Rectangle rectangle)
{
    if (InRectangleInFirst(node, rectangle))
        AddRectangleInSuitableNode(node.First, rectangle);

    if (InRectangleInSecond(node, rectangle))
        AddRectangleInSuitableNode(node.Second, rectangle);
}

public void SearchIntersectedRectangles(Node node, Rectangle rectangle, List<Rectangles> result)
{
    // If not-leaf node
    if (node.Rectangles == null && node.First != null && node.Second != null)
    {
        if (IsRectangleInFirst(node, rectangle))
            SearchIntersecatedRectangles(node.First, rectangle, result);

        if (IsRectangleInSecond(node, rectangle))
            SearchIntersecatedRectangles(node.Second, rectangle, result);

        return;
    }

    result.AddRangle(Rectangles.Where(r => r.IsIntersect(rectangle)));
}

These all lines makes simple 2D-tree. First, make the tree:

// Say, all rectangles would be inside this "space"
const int leftest = -1000;
const int rightest = 1000;
const int bottomest = -1000;
const int toppest = 1000;

// Tree with depth == 2
var tree = new Node
{
    CheckBy = CheckBy.Hozirontal,
    Coordinate = (leftest + rightest)/2,
    First = new Node
    {
        CheckBy = CheckBy.Vertical,
        Coordintate = (toppest + bottomest)/2,
        Rectangles = new List<Rectangle>(),
    },
    Second = new Node
    {
        CheckBy = CheckBy.Vertical,
        Coordintate = (toppest + bottomest)/2,
        Rectangles = new List<Rectangle>(),
    },
}

Then, sort all rectangles in this tree:

foreach (var rectangle in rectangles)
    AddRectangleInSuitableNode(tree, rectangle);

Now you can fast get intersecting rectangles:

var intersecting = new List<Rectangles>();
SearchIntersecatedRectangles(tree, targetRectangle, intersecting);
// Here you can remove intersecting rectangles...

Fast hiding of intersecting rectangles

Yes you should sort the rectangles by x.

Since your rectangles are on the same x axis and are the same height, after you sort them, you should be able to find the intersection in linear time. The algorithm you're looking for is called scan line.

You move a scan line over all your rectangles (jump from their x coords in the set you just sorted) and see which ones intersect at current x location. Load all the x coord overlapping rectangles into a datastructure and check if they intersect (based on y coord).

Rotated 2d rectangle intersection detection

One simple way is to check whether every vertex of one rectangle is on the same and exterior side of an edge of the one, and vice-versa. For faster and more general methods, see
http://gpwiki.org/index.php/Polygon_Collision and http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Plante/CompGeomProject-EPlante/algorithm.html

how to calculate many rectangles/boxes intersection

1) If box sizes are not equal:

Sort boxes on X-axis
Generate 1D adjacency list for each box, by comparing only within range (since it is 1D and sorted, you only compare the boxes within range) like [(1,2),(1,3),(1,5),....] for first box and [(2,1),(2,6),..] for second box, etc. (instead of starting from index=0, start from index=current and go both directions until it is out of box range)
Iterate over 1D adjacency list and remove duplicates or just don't do the last step on backwards (only compare to greater indexed boxes to evade duplication)
Group the adjacencies per box index like [(1,a),(1,b),..(2,c),(2,d)...]
Sort the adjacencies within each group, on Y-axis of the second box per pair
Within each group, create 2D adjacency list like [(1,f),(1,g),..]
Remove duplicates
Group by first box index again
Sort (Z) of second box per pair in each group
create 3D adjacency list
remove duplicates
group by first index in pairs
result=current adjacency list (its a sparse matrix so not a full O(N*N) memory consumption unless all the boxes touch all others)

So in total, there are:

1 full sort (O(N*logN))
2 partial sorts with length depending on number of collisions
3 lumping pairs together (O(N) each)
removing duplicates (or just not comparing against smaller index): O(N)

this should be faster than O(N^2).

2) If rectangles are equal sized, then you can do this:

scatter: put box index values in virtual cells of a grid (i.e. divide the computational volume into imaginary static cells & put your boxes into a cell that contains the center of selected box. O(N)
gather: Only once per box, using the grid cells around the selected box, check collisions using the index lists inside the cells. O(N) x average neighbor boxes within collision range

3) If rectangles are not equal sized, then you can still "build" them by multiple smaller square boxes and apply the second (2) method. This increases total computation time complexity by multiplication of k=number of square boxes per original box. This only requires an extra "parent" box pointer in each smaller square box to update original box condition.

This method and the (2) method are easily parallizable to get even more performance but I guess first(1) method should use less and less memory after each axis-scanning so you can go 4-dimension 5-dimension easily while the 2-3 methods need more data to scan due to increased number of cell-collisions. Both algorithms can become too slow if all boxes touch all boxes.

4) If there is "teapot in stadium" problem (all boxes in single cell of grid and still not touching or just few cells close to each other)

build octree from box centers (or any nested structure)
compute collisions on octree traversal, visiting only closest nodes by going up/down on the tree

1-revisited) If boxes are moving slowly (so you need to rebuild the adjacency list again in each new frame), then the method (1) gets a bit more tricky. With too small buffer zone, it needs re-computing on each frame, heavy computation. With too big buffer zone, it needs to maintain bigger collision lists with extra filtering to get real collisions.

2-revisited) If environment is infinitely periodic (like simulating Neo trapped in train station in the Matrix), then you can use grid of cells again, but this time using the wrapped-around borders as extra checking for collisions.

For all of methods (except first) above, you can accelerate the collision checking by first doing a spherical collision check (broad-collision-checking) to evade unnecessary box-collision-checks. (Spherical collision doesn't need square root since both sides have same computation, just squared sum of differences enough). This should give only linear speedup.

For method (2) with capped number of boxes per cell, you can use vectorization (SIMD) to further accelerate the checking. Again, this should give a linear speedup.

For all methods again, you can use multiple threads to accelerate some of their steps, for another a linear speedup.

Even without any methods above, the two for loops in the question could be modified to do tiled-computing, to stay in L1 cache for extra linear performance, then a second tiling but in registers (SSE/AVX) to have peak computing performance during the brute force time complexity. For low number of boxes, this can run faster than those acceleration structures and its simple:

select a group of boxes n=multiple of 8
    select another group of boxes n=multiple of 8
        iterate first group 8 by 8
            iterate second group 8 by 8
            Only rotate the vector to scan all 8 elements (64 collision checks for each 2 vectors)
        write results for 8 boxes in first group

Are coordinates only 16bit integers? Then you can cache each collision result using hash(distanceX,distanceY,distanceZ,sizeXYZ) as keys and true/false as values.

So, solution depends on your problem. What is N? Do the boxes overlap much? Do they lump together in a big environment or do they stay sparse? How many cores in system? How much memory? Are the boxes moving and how fast? What are your run-time expectations for how many boxes?

Edit: I tried to write an adaptive-grid (optimized the second method against "teapot in stadium" problem a bit) in less than 500 lines of codes: https://github.com/tugrul512bit/FastCollisionDetectionLib

It is not optimized to lower the buffer-allocation overhead, not multithreaded and not vectorized but it scales up linearly for uniformly distributed particles and close to linear when some of particles lumped together 100x far from center of mass. It is hundreds to thousands of times faster than the brute force method depending on number of particles between 20k and 100k. Also did not test it for unequal shaped boxes, only identical boxes.

Get the points of intersection from 2 rectangles

If the input rectangles are normalized, i.e. you already know that x1 < x2, y1 < y2 (and the same for the second rectangle), then all you need to do is calculate

int x5 = max(x1, x3);
int y5 = max(y1, y3);
int x6 = min(x2, x4);
int y6 = min(y2, y4);

and it will give you your intersection as rectangle (x5, y5)-(x6, y6). If the original rectangles do not intersect, the result will be a "degenerate" rectangle (with x5 >= x6 and/or y5 >= y6), which you can easily check for.

P.S. As usual, small details will depend on whether you have to consider touching rectangles as intersecting.

Determine if two rectangles overlap each other?

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )

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) ...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)

Say you have Rect A, and Rect B.
Proof is by contradiction. Any one of four conditions guarantees that no overlap can exist:

Cond1. If A's left edge is to the right of the B's right edge,
- then A is Totally to right Of B
Cond2. If A's right edge is to the left of the B's left edge,
- then A is Totally to left Of B
Cond3. If A's top edge is below B's bottom edge,
- then A is Totally below B
Cond4. If A's bottom edge is above B's top edge,
- then A is Totally above B

So condition for Non-Overlap is

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

Therefore, a sufficient condition for Overlap is the opposite.

Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

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

This is equivalent to:

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]

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/

Efficient way to find overlapping of N rectangles

First off: As with many a problem from computational geometry, specifying the parameters for order-of-growth analysis needs care: calling the lengths of the lists m and n, the worst case in just those parameters is Ω(m×n), as all areas might overlap (in this regard, the algorithm from the question is asymptotically optimal). It is usual to include the size of the output: t = f(m, n, o) (Output-sensitive algorithm).

Trivially, f ∈ Ω(m+n+o) for the problem presented.

Line Sweep is a paradigm to reduce geometrical problems by one dimension - in its original form, from 2D to 1D, plane to line.

Imagine all the rectangles in the plane, different colours for the lists.

Now sweep a line across this plane - left to right, conventionally, and infinitesimally further to the right "for low y-coordinates" (handle coordinates in increasing x-order, increasing y-order for equal x).

For all of this sweep (or scan), per colour keep one set representing the "y-intervals" of all rectangles at the current x-coordinate, starting empty. (In a data structure supporting insertion, deletion, and enumerating all intervals that overlap a query interval: see below.)

Meeting the left side of a rectangle, add the segment to the data structure for its colour. Report overlapping intervals/rectangles in any other colour.

At a right side, remove the segment.

Depending on the definition of "overlapping", handle left sides before right sides - or the other way round.

There are many data structures supporting insertion and deletion of intervals, and finding all intervals that overlap a query interval. Currently, I think Augmented Search-Trees may be easiest to understand, implement, test, analyse…

Using this, enumerating all o intersecting pairs of axis-aligned rectangles (a, b) from listA and listB should be possible in O((m+n)log(m+n)+o) time and O(m+n) space. For sizeable problem instances, avoid data structures needing more than linear space ((original) Segment Trees, for one example pertaining to interval overlap).

Another paradigm in algorithm design is Divide&Conquer: with a computational geometry problem, choose one dimension in which the problem can be divided into independent parts, and a coordinate such that the sub-problems for "coordinates below" and "coordinates above" are close in expected run-time. Quite possibly, another (and different) sub-problem "including the coordinate" needs to be solved. This tends to be beneficial when a) the run-time for solving sub-problems is "super-log-linear", and b) there is a cheap (linear) way to construct the overall solution from the solutions for the sub-problems.

This lends itself to concurrent problem solving, and can be used with any other approach for sub-problems, including line sweep.

There will be many ways to tweak each approach, starting with disregarding input items that can't possibly contribute to the output. To "fairly" compare implementations of algorithms of like order of growth, don't aim for a fair "level of tweakedness": try to invest fair amounts of time for tweaking.

How do I see if two rectangles intersect in JavaScript or pseudocode?

Check for the cases where the rectangles are definitely not intersecting. If none of these cases are true then the rectangles must intersect. i.e.:

public boolean rectanglesIntersect( 
    float minAx, float minAy, float maxAx, float maxAy,
    float minBx, float minBy, float maxBx, float maxBy ) {
    boolean aLeftOfB = maxAx < minBx;
    boolean aRightOfB = minAx > maxBx;
    boolean aAboveB = minAy > maxBy;
    boolean aBelowB = maxAy < minBy;

    return !( aLeftOfB || aRightOfB || aAboveB || aBelowB );
}

This illustrates the concept but could be made slightly faster by inlining the booleans so as to take advantage of the short-circuiting behavior of ||

Fast Rectangle to Rectangle Intersection