Search Page

Showing 1 - 2 of 2
FC-22 - Geometric Primitives and Algorithms

Geometric primitives are the representations used and computations performed in a GIS that concern the spatial aspects of the data, data objects described by coordinates. In vector geometry, we distinguish in zero-, one-, two-, and three-dimensional objects, better known as points, linear features, areal or planar features, and volumetric features. A GIS stores and performs computations on all of these. Often, planar features form a collective known as a (spatial) subdivision. Computations on geometric objects show up in data simplification, neighborhood analysis, spatial clustering, spatial interpolation, automated text placement, segmentation of trajectories, map matching, and many other tasks. They should be contrasted with computations on attributes or networks.

There are various kinds of vector data models for subdivisions. The classical ones are known as spaghetti and pizza models, but nowadays it is recognized that topological data models are the representation of choice. We overview these models briefly.

Computations range from simple to highly complex: deciding whether a point lies in a rectangle needs four comparisons, whereas performing map overlay on two subdivisions requires advanced knowledge of algorithm design. We introduce map overlay, Voronoi diagrams, and Delaunay triangulations and mention algorithmic approaches to compute them.

FC-15 - Shape

Shape is important in GI Science because the shape of a geographical entity can have far-reaching effects on significant characteristics of that entity. In geography we are mainly concerned with two-dimensional shapes such as the outlines of islands, lakes, and administrative areas, but three-dimensional shapes may become important, for example in the treatment of landforms. Since the attribute of shape has infinitely many degrees of freedom, there can be no single numerical measure such that closely similar shapes are assigned close numerical values. Therefore different shape descriptors have been proposed for different purposes. Although it is generally desirable for a shape descriptor to be scale invariant and rotation invariant, not all proposed descriptors satisfy both these requirements. Some methods by which a shape is described using a single number are described, followed by a discussion of moment-based approaches. It is often useful to represent a complex shape by means of a surrogate shape of simpler form which facilitates storage, manipulation, and comparison between shapes; some examples of commonly used shape surrogates are presented. Another important task is to compare different shapes to determine how similar they are. The article concludes with a discussion of a number of such measures of similarity.