Representation of Many-Sided Polygons
and Polygonal Lines for Rapid Processing

A representation for polygons and polygonal
lines is described which allows sets of consecutive 
sides to be collectively examined.  The set of sides are
arranged in a binary tree hierarchy by inclusion. 
 A fast algorithm for testing the inclusion of a poin t
in a many-sided polygon is given.  The speed of 
the algorithm is discussed for both ideal and practical
examples.  It is shown that the poin ts of intersection 
of two polygonal lines can be located by what is essentially
a binary tree search.  The algorithm and 
a practical example are discussed.  The representation
overcomes many of the disadvantages associated 
with the various fixed-grid methods for representing curves and regions

CACM March, 1977

Burton W.

boundary line representation, cartography, computer
graphics computer-searchable structures, contour 
representation, geographic information processing, graphic
data retrieval, in tersection of curves, line-drawing 
processing, poin ts in polygons, regional boundary
representation, spatial information

3.14 3.23 3.30 3.79 8.2

CA770305 JB December 30, 1977  12:44 AM

1630	4	2987
1804	4	2987
1804	4	2987
2547	4	2987
2987	4	2987
2987	4	2987
2987	4	2987
2987	4	2987
2987	4	2987
2987	4	2987
2987	4	2987
3165	4	2987
1326	5	2987
1630	5	2987
2125	5	2987
2547	5	2987
2633	5	2987
2987	5	2987
2987	5	2987
2987	5	2987
421	5	2987
524	5	2987
3165	5	2987
1326	6	2987
2987	6	2987