Initial data: rectangles specified as an array of elements from x, y, w, h. It is required to determine if there are intersections of at least two rectangles.

The current implementation is in the forehead, we cycle through all the rectangles except the last one, and for each nested loop we check the intersection with the subsequent ones. At the first intersection both cycles are interrupted.

Is there a better way?

Regarding my case, the number of rectangles:> 10000, runtime: javascript in the browser.

  • Is it necessary to determine which rectangles intersected, or is it enough to check the presence / absence of intersection? - Sergiks
  • @Sergiks just the fact that there is at least two intersections - Vladimir Gamalyan
  • still determine the boundary condition: if two rectangles have only one common corner point - do they intersect? - Sergiks
  • @Sergiks intersect, or maybe I missed something, in what situations can they be taken as non-intersecting? - Vladimir Gamalyan
  • one
    related: Collision detection (part 2): Box intersection - jfs

1 answer 1

The task is built on top of two one-dimensional search for overlapping ranges.

The initial array is not very useful, it is necessary to lead to arrays of coordinates only, two X each and two Y per rectangle. Let them always be ascending, X beginnings are always less than X of the end of the rectangle.

Using the example of X. Two rectangles gave the following X's: [3,7], [5,9] . These values ​​must somehow be merged into one array and sorted by ascending coordinates, while retaining their purpose — who is the beginning, and who is the end of a rectangle. You can bring them to objects like:

 [ { x:3, io: 1, rect_id: 0 }, { x:7, io:-1, rect_id: 0 }, { x:5, io: 1, rect_id: 1 }, { x:9, io:-1, rect_id: 1 }, ]

and sort by property x .

Then it remains to move from the smallest to the largest and count the current amount io . While there are no intersections, there will be 0 or 1 . As the intersection begins, the value >1 will appear. This means that the projection of the rectangle to which the current point belongs on the X axis is superimposed with the projection of the rectangle to which the previous point belongs.

So there will be pairs (or more companies) of candidates for intersections along the X and Y axes. And it remains to find common ones among them.

  • one
    I clarify. In fact, this is a method of vertical decomposition, but only its initial steps. Then you need to use some kind of tree or sorting again to quickly check the intersections in groups. But this method usually solves a much more complicated task - the search for the total area. For the original task, you can use the algorithm of the sweeping straight e-maxx.ru/algo/intersecting_segments , since All lines are parallel to the axes, the algorithm can be greatly simplified. And you can not simplify, but simply copy the implementation. The complexity of n log n should suffice, although it is possible to finish pressing n. - pavel