CODEWITHSUNDEEP
javascriptc#algorithmmath
Ferry
Ferry

Reputation: 583

What is the best way to check if there are any rectangles (total: N) overlapping with each other in a container?

There is an image container with height 5000px and width 5000px.

And there are also N images (in form of rectangle) randomly placed in this container. Each of these images has 4 properties, positionX, positionY (they are the coordinates of where the upper left corner of the image is in the container), height and width.

The question is, what is the most efficient way to check if there are any of these images overlapping with each other in the container? I am going to write the function with either C# or JavaScript.

I was thinking to use an 5000 x 5000 array (int) with starting value 0, then put these images one by one in the array (add 1 to all the elements in the array where image is). If there are any elements in the array turns to 2, return false.

It doesn't seem that efficient by this way.

Upvotes: 0

Views: 220

Answers (3)

Dstarred
Dstarred

Reputation: 351

"It doesn't seem that efficient by this way." - haha! (Sorry, no offense though) You are going to run almost 5000 * 5000 checks (loops), which is definitely not worth the work.

Edit:

Sorry, the previous algorithm does not work.

I know this question is closed, but anyways:

This was a method I used in my 3D game to check for collision detection. I tried to change it to fit this situation. Hopefully, it works this time...

    public boolean intersects(Image other) { // This should be your image class where you store data like its width, height, startPos, endPos
    
    float thisSizeX = Math.abs(WIDTH) / 2.0f; //Math.abs returns absolute value.
    float thisSizeY = Math.abs(HEIGHT) / 2.0f;
    
    
    float otherSizeX = Math.abs(other.WIDTH) / 2.0f;
    float otherSizeY = Math.abs(other.HEIGHT) / 2.0f;
    
    float thisCenterX = endPositionX - thisSizeX;
    float thisCenterY = endPositionY - thisSizeY;
    
    float otherCenterX = other.endPositionX - otherSizeX;
    float otherCenterY = other.endPositionY - otherSizeY;
    
    //check the X axis
    if(Math.abs(thisCenterX - otherCenterX) < thisSizeX + otherSizeX)
       {
          //check the Y axis
          if(Math.abs(thisCenterY - otherCenterY) < thisSizeY + otherSizeY)
          {
              
              return true;
          }
       }

       return false;
       
       }

**This is written in Java but should be fairly easy to port to other languages.

Upvotes: 0

citykid
citykid

Reputation: 11070

Use a line-sweep based algorithm.

https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/

You have to think about which state to associate with the sweep line.

One consideration for instance would to be that a rectangle that has the left side on the sweep line (which I assume is vertical and goes left to right) cannot intersect rectangles whose right side is left of the sweep line.

You would also track all rects that intersect the sweep line.

Upvotes: 2

JonasH
JonasH

Reputation: 36391

Checking if two rectangles overlap is fairly cheep. So if N is small (say 10k) you should just be able to check each combination. This would be O(N^2), but if you have a bound on 'N' that should not be a problem.

If you have more rectangles an R-Tree might be appropriate. This creates a tree of minimum bounding rectangles that should allow for O(n log n) complexity.

Marking an array as you propose is also possible, and should allow for O(n) complexity if the size and position of the rectangles is bounded. But the constant factor might be larger than the other methods.

Upvotes: 2

Related Questions