As the functionality and sophistication of computers has increased, the functionality and sophistication of the user interfaces employed by computers has increased as well. One common type of interface for computers is the graphical user interface. With this type of interface, information retrieved from and provided to the computer is pictographically represented by images. These images are typically rendered using a wide variety of differently-shaped polygons.
The process of rendering and manipulating polygons on a display may often require determining the amount of overlap between polygons. For example, in some situations, a first polygon may form the bounding area for content rendered on a display. A second polygon may then represent a selection area, for defining information that is to be selected in a selection process. The selection process may, for example, select content when more than 60% of the bounding area for that content is overlapped by the selection area. The polygon used to define this type of selection area is sometimes referred to as a selection “lasso”.
Conventionally, relatively complex algorithms have been employed to determine the amount of overlap of two polygons. For example, the Weiler-Atherton method is one commonly-used technique for determining an amount of overlap between two polygons. More particularly, the Weiler-Atherton method can be used to identify the area formed by the overlap of one polygon with another. This area can then be compared with the area of one of the polygons, to determine how much of that polygon is overlapped by the other polygon. These conventionally-employed methods, however, typically require a great deal of processing power to perform, and thus are relatively slow to implement. Moreover, some of these methods are error prone due to their complexity. Accordingly, there is a need for a relatively quick, efficient and accurate technique for determining the overlap between two polygons.