The Central Idea

A geographic information system connects descriptive information with spatial location.

A simplified GIS model is

\[ \boxed{ \text{GIS} = \text{geometry} + \text{coordinates} + \text{attributes} + \text{spatial relationships} }. \]

The same geometry studied throughout computational geometry becomes tied to real places, measurements, and geographic decisions.

Spatial Features

GIS commonly represents geographic features as:

Each representation supports a different family of spatial questions.

Point Features

A point feature stores a location such as

\[ P=(x,y). \]

Examples include:

Line Features

Linear features are often represented as polylines:

\[ P_0\to P_1\to\cdots\to P_n. \]

Examples include:

Polygon Features

Polygons represent regions with area.

Examples include:

Raster Layers

Raster GIS stores values on a regular grid.

A raster can represent:

Layers

GIS organizes different kinds of information into layers.

A map might contain:

Layers can be analyzed separately or combined.

Geometry and Attributes

A GIS feature usually has both:

A road segment might store geometry plus:

Coordinate Reference Systems

Coordinates have meaning only within a reference system.

A coordinate reference system, or CRS, specifies how coordinate values correspond to positions on or near Earth.

Without a CRS, a pair such as

\[ (500000,5200000) \]

is not geographically interpretable by itself.

Geographic Coordinates

Geographic coordinate systems commonly describe location using longitude and latitude.

Longitude measures angular position east or west.

Latitude measures angular position north or south.

These are angular coordinates on a reference surface rather than ordinary planar Cartesian coordinates.

Projected Coordinates

A projected coordinate system maps geographic positions onto a plane.

The resulting coordinates can often be treated as approximately Cartesian over the intended region.

This makes operations such as distance, area, and buffering more convenient.

Map Projection

A map projection is a transformation from a curved reference surface to a plane:

\[ \boxed{ (\lambda,\phi) \longrightarrow (x,y) }. \]

Here \(\lambda\) may denote longitude and \(\phi\) latitude.

No Flat Map Preserves Everything

Mapping a curved surface onto a plane necessarily introduces distortion.

A projection may preserve or emphasize some properties at the expense of others, including:

Projection choice must match the intended analysis.

Conformal Projections

A conformal projection preserves local angles.

Small shapes are represented with locally correct angular relationships, although area may be distorted.

Equal-Area Projections

An equal-area projection preserves area ratios.

If two regions have equal area on the reference surface, they remain equal in mapped area under an ideal equal-area projection.

Shape and angle may distort.

Distance Measurements Depend on the CRS

Ordinary Euclidean distance

\[ d= \sqrt{ (x_2-x_1)^2+ (y_2-y_1)^2 } \]

is appropriate only when the coordinates and projection support that interpretation over the region of interest.

Using longitude and latitude as though they were ordinary planar lengths can produce misleading results.

Reprojection

GIS layers may arrive in different coordinate reference systems.

To combine them, coordinates can be transformed into a common system.

\[ \boxed{ \text{CRS}_1 \longrightarrow \text{CRS}_2 }. \]

Reprojection is essential before many spatial overlays and measurements.

Datum and Reference Surface

Geographic coordinates depend not only on angular measurements but also on a reference model of Earth.

Different datums can assign different coordinates to the same physical location.

Therefore, CRS compatibility requires more than matching units.

Vector Topology

GIS often needs to know relationships such as:

These are topological as well as geometric questions.

Shared Boundaries

Two adjacent polygons may share the same physical boundary.

A topology-aware representation can store that boundary once and reference it from both regions.

This can reduce gaps and overlaps caused by independently digitized edges.

Containment Queries

A common GIS query asks:

\[ \boxed{ \text{Which polygon contains this point?} } \]

This is exactly a point-in-region problem.

Ray casting, winding tests, spatial indexes, and bounding boxes can all participate in the solution.

Intersection Queries

GIS may ask:

These are geometric intersection problems.

Distance Queries

Distance questions include:

Nearest-Neighbor Queries

Given query location \(Q\) and site set \(P_i\), nearest-neighbor search asks for

\[ \boxed{ \operatorname*{argmin}_i d(Q,P_i) }. \]

Voronoi diagrams, Delaunay structures, spatial trees, and search indexes can accelerate these queries.

Buffers

A buffer around a geometric object is the set of points within a chosen distance \(r\).

For a point \(P\), the Euclidean buffer is a disk:

\[ \boxed{ B_r(P)= \{X:\|X-P\|\le r\} }. \]

Buffers around Lines

A buffer around a line or polyline creates a corridor of fixed distance.

The boundary typically combines:

Buffers around Polygons

Positive buffering expands a polygon outward.

Negative buffering contracts it inward when the geometry permits.

Offsetting concave and convex corners requires careful geometric treatment.

Buffer Applications

Buffers are useful for questions such as:

Overlay

Overlay combines two or more spatial layers.

Vector overlay can involve:

\[ A\cap B, \qquad A\cup B, \qquad A\setminus B. \]

New geometry and new attributes are created from the spatial relationships between the inputs.

Polygon Intersection Overlay

Suppose layer \(A\) contains zoning polygons and layer \(B\) contains flood zones.

Their intersection identifies areas having both classifications.

Geometrically, this requires polygon clipping and topological reconstruction.

Raster Overlay

Rasters on a common aligned grid can be combined cell by cell.

For example,

\[ S_{ij} = w_1A_{ij} + w_2B_{ij} + w_3C_{ij} \]

can define a weighted suitability score.

Map Algebra

Cellwise raster operations are often described as map algebra.

A new raster can be computed from existing layers using arithmetic, logical, and conditional expressions.

For example,

\[ R_{ij} = \begin{cases} 1,&A_{ij}>10\text{ and }B_{ij}<5,\\ 0,&\text{otherwise}. \end{cases} \]

Spatial Join

A spatial join transfers or combines attributes according to spatial relationships rather than ordinary database keys.

Examples include:

Spatial Indexing

Large geographic datasets require efficient search structures.

A spatial index uses geometry or bounding regions to avoid checking every feature.

Broad candidate selection is followed by exact geometric testing.

Bounding Boxes in GIS

A feature's axis-aligned bounding box is

\[ [x_{\min},x_{\max}] \times [y_{\min},y_{\max}]. \]

If two bounding boxes do not overlap, the corresponding features cannot intersect.

This gives a fast first-stage filter.

R-Trees

One important family of spatial indexes groups nearby bounding rectangles hierarchically.

Querying a region can then discard large portions of the dataset whose bounding rectangles do not overlap the search area.

Grid Indexes

Space can also be divided into regular cells.

Features are associated with the cells they occupy.

Queries inspect only relevant cells rather than the full dataset.

Quadtrees

Quadtrees recursively divide two-dimensional space into four subregions.

Dense regions can be subdivided more deeply than sparse ones.

This adaptive hierarchy can support raster and vector spatial indexing.

Network GIS

Roads, pipes, transmission lines, and similar systems are naturally modeled as networks.

A network contains:

Shortest Paths

A road route is not usually the straight-line segment between origin and destination.

Network distance is the sum of edge costs along a permitted path:

\[ \boxed{ C(\text{path}) = \sum_{e\in\text{path}}w_e }. \]

The shortest path minimizes this total.

Network Cost Is Not Necessarily Distance

Edge weight may represent:

The best route depends on the chosen objective.

Service Areas

A network service area contains locations reachable within a cost threshold.

For threshold \(T\),

\[ \boxed{ \{X: \text{minimum network cost from source to }X \le T \} }. \]

This differs from an ordinary Euclidean-radius buffer.

Terrain Representation

Terrain can be represented as:

Digital Elevation Models

A digital elevation model, or DEM, stores elevation values on a raster grid.

If the cell spacing is

\[ \Delta x,\qquad\Delta y, \]

local elevation differences can approximate slope and gradient.

Slope from Elevation

If elevation is modeled by

\[ z=f(x,y), \]

then the gradient is

\[ \boxed{ \nabla f= \left( \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y} \right) }. \]

Raster methods estimate these derivatives from nearby samples.

Aspect

Terrain aspect describes the direction of steepest descent or a related orientation derived from the elevation gradient.

It connects geographic terrain analysis with vector direction and field concepts.

Contours

A contour is a level set

\[ \boxed{ f(x,y)=c }. \]

Contour extraction converts a continuous or sampled elevation field into vector curves representing equal elevation.

Triangulated Irregular Networks

A TIN represents terrain using connected triangles built from irregularly spaced elevation samples.

More vertices can be concentrated where terrain changes rapidly.

This connects GIS terrain modeling directly to triangulation and mesh generation.

Interpolation

GIS often knows values at sampled locations but needs estimates elsewhere.

Interpolation constructs an estimated field from the known samples.

Nearest-Neighbor Interpolation

The simplest interpolation assigns each location the value of its nearest sample.

This produces regions closely related to Voronoi cells.

Inverse-Distance Weighting

A common interpolation model gives nearby samples greater influence.

One form is

\[ \boxed{ \hat f(X) = \frac{ \sum_i w_i f_i }{ \sum_i w_i }, \qquad w_i= \frac{1}{d(X,P_i)^p} }. \]

Here \(p>0\) controls how quickly influence decreases with distance.

Triangular Interpolation

If samples are connected by a triangulation, values can be interpolated across each triangle with barycentric coordinates:

\[ \boxed{ f(P) = \alpha f(A) + \beta f(B) + \gamma f(C) }. \]

Voronoi and Delaunay in GIS

Voronoi diagrams provide nearest-site territories.

Delaunay triangulations provide neighborhood connectivity and useful terrain or interpolation structure.

The two are geometric duals and appear frequently in spatial analysis.

Geocoding

Geocoding associates descriptive location information with coordinates.

Conceptually:

\[ \boxed{ \text{address or place description} \longrightarrow \text{geographic coordinate} }. \]

The returned location may itself have uncertainty.

Reverse Geocoding

Reverse geocoding performs the opposite lookup:

\[ \boxed{ \text{coordinate} \longrightarrow \text{descriptive location} }. \]

This requires spatial search among geographic features.

Geometric Accuracy

GIS data can be mathematically precise in storage while still being geographically inaccurate.

Coordinate precision and real-world accuracy are different ideas.

A coordinate with many decimal places does not prove that the surveyed or inferred location is known equally well.

Positional Uncertainty

A measured position may have uncertainty radius

\[ r. \]

Instead of treating the recorded point as exact, one may conceptualize the true location as lying within a neighborhood around the measurement.

Attribute Uncertainty

Spatial location is not the only source of uncertainty.

Attributes may also be estimated, classified, generalized, or outdated.

GIS analysis should distinguish geometric uncertainty from attribute uncertainty.

Scale and Generalization

A map intended for a continental overview does not require the same geometric detail as a parcel survey.

Generalization simplifies geometry and information for an intended scale or purpose.

Line Simplification

A coastline or road represented by many vertices may be simplified while keeping geometric deviation within a tolerance.

This reduces storage and visual clutter.

Excessive simplification can change topology or erase important features.

Polygon Generalization

Simplifying polygon boundaries must preserve more than visual shape.

A poor simplification can create:

Raster Resolution and Scale

Raster resolution places a direct lower bound on distinguishable spatial detail.

Features smaller than one cell may be lost or strongly distorted.

Upsampling does not recover missing original information.

Spatial Aggregation

Fine-scale information can be summarized into larger regions or cells.

For example, population counts from small areas may be accumulated into larger administrative units.

Aggregation changes spatial resolution and can change observed patterns.

Raster Zonal Statistics

A polygon layer can define zones over a raster.

For each zone, one may compute:

Spatial Selection

GIS supports selection by geometric relationships.

Examples include:

Spatial Predicates

Common spatial predicates include:

\[ \boxed{ \text{intersects}, \text{ contains}, \text{ within}, \text{ touches}, \text{ overlaps}, \text{ disjoint} }. \]

These convert qualitative spatial relationships into computational tests.

Bounding-Box Filter plus Exact Predicate

A reliable spatial query often uses two stages:

\[ \boxed{ \text{bounding-box filter} \rightarrow \text{exact geometry test} }. \]

This is the same broad-phase/narrow-phase strategy used in collision detection.

Spatial Databases

GIS often stores geometry inside a database system.

This allows spatial queries to be combined with ordinary attribute queries.

For example:

find all parcels larger than a threshold that intersect a particular zone.

Raster and Vector Integration

Many GIS workflows combine both representation types.

A vector watershed boundary may be used to extract values from a raster precipitation grid.

A raster classification may later be vectorized into polygons.

Vector-to-Raster Conversion

Rasterizing vector GIS data requires:

Different choices can produce different raster results.

Raster-to-Vector Conversion

Vectorization identifies geometric boundaries or paths from raster cells.

The output may require:

Spatial Modeling

GIS can combine geometry and attributes into models of:

The mathematics determines how spatial relationships are computed, but the model assumptions determine what those relationships mean.

Suitability Modeling

Suppose several normalized raster criteria are

\[ C_1,C_2,\ldots,C_k \]

with weights

\[ w_1,w_2,\ldots,w_k. \]

A weighted suitability score can be

\[ \boxed{ S= \sum_{i=1}^{k}w_iC_i }. \]

Weights Are Model Assumptions

The arithmetic of weighted overlay may be straightforward, but the choice of weights is not purely geometric.

It reflects assumptions about importance, policy, or decision criteria.

GIS separates computational geometry from the interpretation placed on the resulting analysis.

Viewshed Analysis

A viewshed identifies locations visible from an observation point over a terrain model.

The computation involves:

This closely resembles visibility problems in computer graphics.

Line of Sight

Let observer \(A\) and target \(B\) define the segment

\[ P(t)=A+t(B-A), \qquad 0\le t\le1. \]

If terrain rises above this segment at an intermediate location, the target may be occluded.

Watershed and Flow Modeling

Terrain grids can be used to infer downhill flow directions.

Accumulating those directions can identify:

These analyses combine fields, gradients, discrete grids, and topology.

Three-Dimensional GIS

GIS increasingly represents:

This extends the same spatial principles into three dimensions.

Time as an Additional Dimension

Some geographic data changes with time.

A spatial feature may therefore be modeled as

\[ X(t) \]

or as a sequence of time-stamped geometries or raster layers.

This connects GIS with motion, fields, and multidimensional data.

Numerical Robustness

GIS operations depend on computational predicates such as:

Floating-point and measurement error can affect all of them.

Near-Coincident Boundaries

Two independently collected datasets may contain boundaries intended to coincide but differing by a small amount.

Overlay can then produce:

Sliver Polygons

A sliver polygon is a very small region created by slight mismatch between boundaries during overlay.

Slivers may represent real narrow features, data error, or numerical artifacts.

They should not be removed automatically without understanding their cause.

Snapping

Snapping moves nearby vertices or edges into exact coincidence according to a tolerance.

It can repair intended connectivity but can also alter legitimate geometry if the tolerance is too large.

Topology Validation

Depending on the dataset, validation rules may require:

Common Error: Mixing Coordinate Systems without Reprojection

Two layers may appear to use similar numeric coordinates while referring to different reference systems.

Overlaying them directly can place features in the wrong locations.

Common Error: Measuring Longitude and Latitude with Planar Distance

Degrees are angular units, not fixed linear distances across Earth.

Euclidean distance in raw longitude-latitude coordinates can therefore be inappropriate for serious distance analysis.

Common Error: Assuming Raster Resolution Equals Accuracy

A raster with small cells may still contain inaccurate source data.

Resolution describes sampling density, not guaranteed real-world accuracy.

Common Error: Treating a Buffer as a Universal Travel-Time Zone

A Euclidean buffer measures geometric proximity.

Travel time depends on networks, speeds, barriers, and access.

A network service area may be more appropriate.

Common Error: Assuming Overlay Results Are Automatically Clean

Boundary mismatch can create tiny gaps and slivers.

Overlay results should be checked for geometric and topological artifacts.

Common Error: Confusing Precision with Accuracy

A coordinate such as

\[ 47.123456789 \]

contains many digits, but that does not imply the underlying location is known to corresponding physical accuracy.

Common Error: Ignoring Representation Choice

A problem involving continuous elevation may be natural in raster form.

A parcel-ownership problem may be natural in vector form.

Representation should follow the structure of the question.

A Reliable Procedure for Combining GIS Layers

  1. Identify each layer's coordinate reference system.
  2. Reproject layers into a suitable common CRS.
  3. Check units and spatial extent.
  4. Validate geometry and topology.
  5. Build or use spatial indexes for large datasets.
  6. Apply the desired overlay, join, or query.
  7. Inspect the output for slivers, gaps, and unexpected topology.
  8. Document assumptions and tolerances.

A Reliable Procedure for Distance-Based GIS Analysis

  1. Determine whether Euclidean, geodesic, or network distance is appropriate.
  2. Choose a coordinate system suitable for the measurement.
  3. Validate source geometry.
  4. Compute distance, buffers, or service areas using the chosen model.
  5. Apply spatial queries against the resulting regions.
  6. Check sensitivity to resolution and positional uncertainty.

A Reliable Procedure for Raster Analysis

  1. Confirm grid resolution, origin, and CRS.
  2. Align rasters when necessary.
  3. Choose appropriate resampling methods.
  4. Apply cellwise or neighborhood calculations.
  5. Track no-data values and classification rules.
  6. Validate important results against source resolution and uncertainty.

A Reliable Procedure for Spatial Querying

  1. Express the desired spatial predicate clearly.
  2. Use a spatial index or bounding-box filter to identify candidates.
  3. Apply the exact geometric predicate.
  4. Resolve boundary cases according to the application.
  5. Combine spatial results with attribute conditions if required.
  6. Verify representative edge cases.

Practice 1: Feature Type

Which vector geometry type is most natural for representing a property parcel?

Practice 2: Feature Type

Which vector geometry type is most natural for representing a road centerline?

Practice 3: CRS

Why is a coordinate pair incomplete without a coordinate reference system?

Practice 4: Overlay

Which set operation identifies the region common to polygon layers \(A\) and \(B\)?

Practice 5: Buffer

What is the Euclidean buffer of radius \(r\) around a point \(P\)?

Practice 6: Nearest Neighbor

What geometric structure partitions the plane into nearest-site regions?

Practice 7: Terrain

What raster data model commonly stores elevation on a regular grid?

Practice 8: Network Analysis

Why can straight-line distance be a poor model of driving travel time?

Practice 9: Spatial Index

Why are bounding boxes useful in large GIS intersection queries?

Practice 10: Precision and Accuracy

Does storing more decimal places automatically make a geographic position more accurate?

Practice Answers

Practice 1

\[ \boxed{\text{polygon}} \]

A parcel is an area with a closed boundary.

Practice 2

\[ \boxed{\text{polyline or line}} \]

Practice 3

The CRS defines how the numeric coordinate values correspond to real geographic locations.

Practice 4

\[ \boxed{ A\cap B }. \]

Practice 5

\[ \boxed{ B_r(P)= \{X:\|X-P\|\le r\} }. \]

Practice 6

\[ \boxed{\text{a Voronoi diagram}} \]

Practice 7

\[ \boxed{\text{a digital elevation model, or DEM}} \]

Practice 8

Travel follows a constrained road network with different speeds, directions, barriers, and access rules rather than an unrestricted straight segment.

Practice 9

Disjoint bounding boxes prove that the underlying features cannot intersect, allowing most candidate pairs to be rejected cheaply.

Practice 10

No. Additional stored digits increase numerical precision but do not improve the underlying measurement automatically.

\[ \boxed{\text{No}.} \]

What to Remember

Geographic information systems apply computational geometry to real-world spatial data.

The broader computational principle is that geographic space becomes analyzable when locations, boundaries, fields, and relationships are encoded mathematically. GIS brings together nearly every major idea from computational and constructive geometry.

Section Perspective

Computational and Constructive Geometry began by treating coordinates and vectors as geometric data. From there, we developed algorithms for intersection, containment, convex hulls, triangulation, Voronoi partitions, mesh generation, collision detection, raster and vector representation, CAD, computer graphics, and GIS.

The unifying idea is that geometry can be transformed into data structures and predicates without losing its mathematical meaning.

Once spatial relationships are encoded computationally, they can support design, simulation, visualization, navigation, measurement, mapping, and analysis across a wide range of fields.