Sweep line algorithm
category: code [glöplog]
Here's my first thought:
- For each axis, sweep all the rectangles and note intersecting pairs in a set.
- Compute intersection of the two sets.
O(n log n), right?
- For each axis, sweep all the rectangles and note intersecting pairs in a set.
- Compute intersection of the two sets.
O(n log n), right?
Alternatively, plot rectangles on a texture, compute total area from brightness of 1x1 mipmap. That's what a elite demo coder would do.
you can have on the order of N^2 intersections for both 1D projections even when the rectangles are actually intersection-free. so that's still a non-output-sensitive O(N^2), although it will run faster for "sparser" sets.
