Fast Window Overlap Checking Algorithm
Many algorithms to check if two windows overlap (a very common activity in window system and interface design) rely on doing multiple comparisons of the positions of the sides of the two rectangular areas in question. This is usually fine for most instances, especially in these days of multi-gigahertz desktop PC’s. But sometimes you need to do so many such comparisons that speed becomes the paramount concern. And sometimes you do not have a super fast processor to rely on - such as on small hand-held devices or cell-phones.
The algorithm described here is one I wrote back in 1988 for a graphics workstation product. It relies on some interesting relationships between the sign of the result of subtracting opposite sides of two rectangles. By taking advantage of this, it is possible to write few lines of C code which will compile down to 20 or fewer assembly instructions.
