The storage and reconstruction of polygon boundaries using circles

This paper investigates the accuracy of using circles to store polygon boundaries. Can a series of xy points be accurately replaced by a smaller array of variably-sized circles used in a non space filling sense to approximate to the edge of the polygon? Two measures were used to ascertain this, areal error and visual error. A vector dataset representing the island of Rarotonga was converted from boundary coordinates to circle storage using a Voronoi-based medial axis approach. Three parameters were altered to derive as many as 150 circle-based realisations – minimum allowed circle radius, degree of overlap allowed between circles and Douglas-Peucker algorithm threshold (the latter algorithm of line reduction was used to extract “important” points from the polygon and add them to the circle list as “zero-radius circles”). This presentation presents and analyses the areal error and visual error results for all realisations.PublishedNon Peer ReviewedAlani, H, Jones, C B and Tudhope, D. (2001). Voronoi-based region approximation for geographical information system retrieval with gazetteers. International Journal of Geographical Information Science, 15, 4, 287-306. Douglas, D and Peucker, T. (1973). Algorithm for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 10, 112-122. Fortune, S. (1987). A Sweepline Algorithm for Voronoi Diagrams. Algorithmica, 2, 153-174. Hubbard, P. (1996). Approximating polyhedra with spheres for time-critical collision detection. ACM Transactions on Graphics, 15, 3, 179-210. Jones, C B. (1997). Geographical information systems and computer cartography. London: Longman Jones, C B and Abraham, I M. (1987). Line Generalization in a global cartographic database. Cartographica, 24, 3, 32-45. Moore, A B. (2002). The circle tree – a hierarchical structure for efficient storage, access and multiscale representation of spatial data. In: P A Whigham (ed), Proceedings of the 14th Annual Colloquium of the Spatial Information Research Centre, Victoria University, Wellington, New Zealand. Dunedin, NZ: SIRC, University of Otago, pp.149-156. Moore, A, Mason, C, Whigham, P and Thompson-Fawcett, M. (2003). The Use of the Circle Tree for the Efficient Storage of Polygons. Proceedings of GeoComputation 2003, University of Southampton, UK, CD-ROM. Odgaard, A and Nielsen, B K. (2003). A visual implementation of Fortune’s Voronoi algorithm. http://www.diku.dk/hjemmesider/studerende/duff/Fortune. Accessed: 14th July, 2003. Perkal, J. (1956). On epsilon length. Bulletin de l’Academie Polonaise des Sciences, 4, 399-403. Pham, T-L, Schneider, G and Goose, S. (2000) Exploiting Location-Based Composite Devices to Support and Facilitate Situated Ubiquitous Computing. In: P Thomas and H W Gellersen (eds.) Handheld and Ubiquitous Computing, Berlin: Springer. pp. 143-156. Rigaux P, Scholl M and Voisard A. (2002). Spatial Databases with Application to GIS. Morgan Kauffmann. van Oosterom, P. (1993). Reactive Data Structures for Geographic Information Systems. Oxford: Oxford University Press. Wu, J and Amaratunga, K. (2003). Wavelet triangulated irregular networks. International Journal of Geographical Information Science, 17, 3, 173-289