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.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
