7 Computational Geometry and Its Application to GIS Computational geometry is defined broadly as the design and analysis of al- gorithms for solving problems involving geometric objects. Use of the term ‘computational geometry’ and its meaning differs in different application con- texts. Most researchers in computer science interpret the subject as design and optimization of algorithms involving geometric problems. The term ‘al- gorithm design’ carries the connotation of discrete algorithms as opposed to the algorithms used in numerical analysis.
The numerical analysis problems are used for solving computational problems in continuous domains. Com- putational geometry is useful in solving problems of discrete combinatorial geometry rather than continuous geometry. This chapter describes the com- putational geometric algorithms in the context of their applications in GIS and how these algorithms are used to process spatial data which are the primary inputs of GIS. Computational geometry emerged as a field of research three decades ago.
Since this area has been identified, a number of core geometric problems have emerged. A number of computational geometric algorithms have been designed to solve these problems. These algorithms are optimized for their computa- tion time and memory. Research in computational geometry is progressing to compute large volumes of geometric data and degenerate data.
Therefore the robust versions of these algorithms have been devised for processing the degen- erate spatial data often encountered by GIS. These algorithms are important for many applications, of great generality and applicability.1 Introduction Many of the problems that arise in application areas such as computer graph- ics, computer-aided design and manufacturing, robotics, GIS, computer vision, human-computer interface, astronomy, computational fluid dynamics, molec- ular biology etc. can be described using discrete geometrical structures. These problems can be solved using a set of algorithms known as computational geometric algorithms.
However it should be remembered that not all the geo- 119 120 Computing in Geographic Information Systems metric applications can be modelled using the discrete geometric structures or solved using computational geometric algorithms. For example, problems in computer vision and computer graphics to some extent are not modelled on the Euclidean plane, but using a matrix of digitized locations of pixels. Problems in computer-aided manufacturing often involve curved surfaces rather than polyhedral surfaces. Problems in fluid dynamics are generally of a continuous nature defined by differential equations.
Thus, computational geometry as it is commonly defined is not quite broad enough to address all problems in all these areas. However, the field is broad enough such that virtually all of these application areas can use some of the algorithms in computational geometry. A good introduction to computational geometry along with the algorithms and data structures has been compiled by Preparata and Shamos in [49]. The algorithms in computational geometry discussed in this chapter along with their applications to GIS in the context of processing spatial data per- taining to land, sea and air are listed below.
Algorithms to determine line-line intersection. Algorithms to find whether a point lies inside a triangle, polygon, circle, or sphere. Algorithms for computing convex hull. Computing triangulation of a simple polygon in 2D.
Computing Delaunay triangulation of a set of points in a plane. Computing the Voronoi tessellation of a set of points in a plane. These sets of algorithms are often called Computational Geometric Algo- rithmic Library (CGAL). The input to CGAL algorithms are typically a finite collection of geometric elements such as points(locations associated with place names in the map), lines or line segments (communication lines such as roads, rails, power transmission lines etc.), polygons (coverage of states within the geographic boundary of a country, water bodies), polyhedrons, circles, spheres in the Euclidean space.1 Triangulation and Partitioning Triangulation is a generic method for subdividing a complex domain into a dis- joint collection of ‘simple’ objects.
A triangle is the simplest region into which one can decompose a plane and this process is known as triangulation. The Computational Geometry and Its Application to GIS 121 higher dimensional generalization of a triangle in 3D is a tetrahedron. There- fore a 3D bounded volume can be decomposed to tetrahedrals. Triangulation or domain decomposition or tessellation is typically a first step performed in number of algorithms.
These triangles are then subjected to computational operations through an iterative process to compute the objective and analyze the overall domain. Triangulation ‘T ’ is tessellation of a polygonal region of the plane into non- overlapping, continuous triangles Ti such that, their intersection is empty, or it is coincident with a vertex, or an edge of both triangles.1) i=1 where, |ti | is the number of triangles in the domain. Hence the domain of T is the plane curved by its triangles. In addition to the above definition, if the triangulation of the domain is such that, the circumcircle of each triangles does not contains any other points of the domain then it is called Delaunay Triangulation (DT).
This is known as the empty circumcircle property of DT.2 Convex Hull Perhaps the first problem in the field of computational geometry is the problem of computing convex hulls, that is, the smallest convex shape that surrounds a given set of objects. In other words, it suffices to say that the convex hull can be imagined as a stretched elastic membrane surrounding the objects which snap tightly around the objects. It is an interesting problem both because of its applications as an initial step towards solving other algorithms, and the number of interesting algorithmic approaches that have been devised to solve this problem. Mathematically Convex Hull (CH) can be defined through the set theoretic operations as follows.
Let S be a set of discrete objects in 2D plane. The set S is convex if ¯ S XS ∧ Y S ⇔ XY (7.2) Generally segment xy ¯ is the set of points x, y of the form αx + βy = 1 and α ≥ 0 and β ≥ 0.3 Voronoi Diagram and Delaunay Triangulation Given a collection of points in space, perhaps the most important geometric data structures for describing the relationships among these points and the 122 Computing in Geographic Information Systems relationship of any points in space to these points are very well addressed by structures of the Voronoi diagram and DT. A number of important prob- lems such as the notion of ‘proximity’ and ‘line of sight’ can be solved using these two structures. These structures possess a number of beautiful mathe- matical properties that distinguish them as important geometric structures.
Informally, the Voronoi diagram of a finite set of points in the plane is a sub- division of the plane into disjoint regions, one for each point. The Voronoi region of a point consists of the points in the plane for which this point is the closest point of the set. The dual graph of the Voronoi diagram is the Delaunay triangulation. Given a set P of M unique random points in an n-dimensional space, Let us define a region Di such that Di = {x : |x − pi | ≤ |x − Pj |, ∀(i, j)} Then the collection of the subdivisions Di is defined as the Voronoi tes- sellation or Dirichilet tessellation of the set of points P that satisfies the constraint m X D= Dm (7.3 Geometric Computational Techniques The most important aspect of solving computational geometric problems is learning the design techniques needed in the creation of algorithms.
Some of the standard algorithm design techniques pursued in solving any problems in computer science are divide-and-conquer, dynamic programming, greedy technique etc. These techniques work perfectly with alpha numeric data or data where indexing and sorting can be carried out easily. Spatial geometric data often is associated with dimension and randomness. Therefore prepro- cessing techniques have been developed to bring the spatial geometric data to a representation where ordering and indexing can be applied.
Some of these techniques which are often treated as the pre-processing techniques in com- putational geometry are: 1. Plane Sweep 2-dimensional problems can be converted into a dynamic 1- dimensional problem by sweeping an imaginary line across the place and solving the problem incrementally as the line sweeps across. In general, if you can solve a dynamic version of a (d-1)-dimensional problem efficiently, you can use that to solve a static d-dimensional problem using this technique. A radial sweep line algorithm for con- struction of Triangular Irregular Network (TIN) has been developed by Mirante et al.
An Implementation of Watsons algorithm for computing 2D Delaunay triangulation is discussed in [46],[47]. Computational Geometry and Its Application to GIS 123 2. Randomized incremental algorithms One of the simplest techniques for the construction of geometric structures is the technique of adding objects to the structure one by one in some order [16]. It turns out that for any data set there may be particularly bad orders in which to insert things (leading to inefficient running times), as well as particularly good orders (leading to efficient running times).
It is difficult to know in advance what the proper insertion order of items should be, but it is true for many problems that a random insertion order is efficient with high probability. Fractional cascading One important technique needed in the design of efficient geometric search problems is that of cascading a sequence of complex decisions up a search tree to generate a longer sequence of simple decisions. This technique has applications in a large number of search prob- lems.4 Triangulation of Simple Polygons The problem of triangulating polygons can be introduced by way of an ex- ample in the field of combinatorial geometry. Combinatorial geometry is the field of mathematics that deals with counting problems in geometry.
Combi- natorial geometry and computational geometry are closely related, because the analysis and design of efficient geometric algorithms often depends on a knowledge of how many times or how many things can arise in an arbitrary geometric configuration of a given size. A polygonal curve is a finite sequence of line segments, called edges joined end to end. The endpoints of the edges are vertices. For example, let v0 , v1 , ., vn denote the set of n+1 vertices, and let e0 , e1 , ., en−1 denote a sequence of n edges, where ei = vi vi+1.
A polygonal curve is closed if the last endpoint equals the first vn = v0. A polygonal curve is simple if it is not self-intersecting. More precisely this means that each edge ei does not inter- sect any other edge, except for the endpoints it shares with its adjacent edges (Figure 7. The famous Jordan curve theorem states that every simple closed plane curve divides the place into two regions i.
the interior and the exterior re- gions. Although the theorem seems intuitively obvious, it is quite difficult to prove, and many erroneous proofs were announced before Jordan finally pro- duced a correct proof. A polygon can be defined as the region of the plane bounded by a simple, closed polygonal curve. The term simple polygon is also often used to emphasize the simplicity of the polygonal curve.
124 Computing in Geographic Information Systems FIGURE 7.1 Polygonal curves Let us denote the interior of the polygon, as int(P), as an open set which does not contain the boundary. When discussing a polygon P, sometimes it is the interior region of the polygon, that is of interest. Therefore unless ex- plicitely mentioned a polygon means unambiguously the int(P). O’Rourke makes the rather standard convention that when dealing with polygons, the edges are directed in counter clockwise order about the bound- ary.
Thus the interior of the polygon int(P) is locally to the left of the directed boundary. Such a listing of the edges is called a boundary traversal.1 Theory of Polygon Triangulation Before getting to discussion of algorithms for polygon triangulation, it is per- tinent to establish some basic facts about polygons and triangulations. These facts may seem obvious but one must look at them carefully when making ge- ometric arguments.