Fast drawing of complex polygons/polygonal areas (24-Jan-2003)

Fast drawing of complex polygons/polygonal areas

1. Introduction

Any application drawing eg. cartographic data has to draw many, typically complex, polygons. Efficient and therefore quick drawing of polygons and polygonal areas is the key aspect of todays Geo Information Systems. Even simple map drawing applications depend for interactive usability on very short display update times. The user of such an application will zoom in and zoom out, change focus, and most importantly, wants any operation to be done immediately. This is still a problem even if the graphic hardware support is immense today.

    The basic operation for drawing polygons is that of "clipping" ([2],[3]), that is to determine the area of the polygon being visible. Clipping of a polygon is the operation of determining the polygon's intersection with the visible area. This operation is expensive because of the involved rational arithmetic. Even modern graphic cards quickly come to the point of slow drawing if many complex polygons are involved.

2. Problem statement

    The challenge for most applications is either to find a balance between polygon resolution and display speed or to make use of many different resolutions for the same set of polygons.

3. Solution

    The present invention solves the problems described by making use of a single high resolution base of polygons and a polgon reduction technique for the actual drawing comprising two operations:

    OP1) point collapsing: if two successive points of a polygon will be mapped to the same pixel of the display device, then it is allowed to remove one without any change on the display.

    OP2) point reduction: if three succesive points of the polygon will be mapped all either
above the top
right to the right border
below the bottom
left to the left border of the actual view, then the middle point may be removed from the polygon without changing the drawing of the polygon (and...