Windowing Systems and User Interface Programming
The rectangular geometry of most windowing user interfaces lends itself naturally to the orthogonal range searching techniques studied in computational geometry. A typical problem arising in this context might be to find a data structure for quickly determining which window or window system object is topmost at a given screen pixel (for instance this information is needed to process mouse clicks and to set the mouse's appearance). Range searching techniques can be useful even within a single window, to speed up scrolling and redisplay by determining which objects are visible in a region. In my own programming experience, I have used (a simplified implementation of) interval trees to greatly speed up scrolling in code for displaying large family trees.
- US
Patent 5459831 covers the use of quadtrees to perform the range
queries needed for object selection in graphical user interfaces.
- US
Patent 5461712 uses quadtrees to allocate memory to different
objects in a windowing system.
- US
Patent 5564004 uses Voronoi diagrams as part of a user interface
that highlights the icon nearest the cursor in a windowing system.