pouët.net

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?
added on the 2010-12-28 10:40:53 by doomdoom doomdoom
Alternatively, plot rectangles on a texture, compute total area from brightness of 1x1 mipmap. That's what a elite demo coder would do.
added on the 2010-12-28 10:55:37 by doomdoom doomdoom
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.
added on the 2010-12-28 14:44:28 by ryg ryg

login