Computational Aspects of Geographic Information Systems

Spatial data combines geometry and meaning

A GIS associates location with attributes such as road type, land use or elevation. Vector data represents discrete objects as points, lines and polygons; raster data samples a field on a grid. Neither representation is universally preferable: a parcel boundary and a temperature surface have different structure. Preserve provenance, coordinate reference systems and collection resolution alongside coordinates, because a numerical position without its interpretation can be misleading.

References: Carleton 4202 official calendar record · Open Geospatial Consortium: Simple Feature Access standard

Coordinate systems determine valid calculations

Latitude and longitude describe angular coordinates on an Earth model, not ordinary Cartesian distances in metres. A map projection transforms them into planar coordinates with specified distortions. Choose a projection appropriate to the region and operation rather than applying Euclidean distance blindly to degrees. Axis order and units must be explicit when exchanging data. Two datasets can display plausibly together while still disagreeing by a systematic offset caused by incompatible reference systems.

References: Carleton 4202 official calendar record · Open Geospatial Consortium: Simple Feature Access standard

Spatial predicates and robust geometry

Operations such as contains, touches and intersects depend on both geometry and boundary conventions. A point on a polygon boundary is not the same case as a point strictly inside it. Ray-crossing tests can determine containment, but vertices and horizontal edges need consistent handling to avoid counting the same crossing twice. Floating-point errors can also change a near-collinear orientation result. Test degenerate cases and invalid geometries before trusting large spatial overlays.

References: Carleton 4202 official calendar record · Open Geospatial Consortium: Simple Feature Access standard

Spatial indexes filter candidate objects

A spatial index groups objects by regions or bounding boxes so a query avoids scanning every object. An R-tree stores nested bounding rectangles; a query first rejects disjoint rectangles and then checks surviving geometries exactly. Bounding-box overlap is necessary but not sufficient for actual intersection. A point structure such as a kd-tree partitions space differently and suits different workloads. Compare update costs, query selectivity and data distribution instead of choosing solely by asymptotic labels.

References: Carleton 4202 official calendar record · Open Geospatial Consortium: Simple Feature Access standard

Overlay, subdivision and map complexity

Combining polygon layers requires finding intersections, splitting boundaries and assigning attributes to resulting regions. Output complexity can dominate runtime: two modest input collections may generate many intersection pieces. A sweep-line method can organize segment events, while a planar subdivision records adjacency and faces. Keep topological relations consistent after every split. Simplifying geometry for display can improve speed, but an aggressive simplification may erase a narrow connection that matters for a later analytical query.

References: Carleton 4202 official calendar record · Open Geospatial Consortium: Simple Feature Access standard

Routing is a graph problem with spatial constraints

A road network can be represented as a weighted directed graph, with weights for distance or estimated travel time. Direction matters for one-way roads, and turning restrictions may require a richer state than a vertex alone. Dijkstra's algorithm assumes nonnegative edge weights. A* can prioritize a goal-directed search when its heuristic is suitably admissible; a straight-line distance bound is useful only when its units and relationship to actual route cost are justified.

References: Carleton 4202 official calendar record · Open Geospatial Consortium: Simple Feature Access standard

Worked candidate filtering and quality checks

Suppose a spatial query seeks parks within a circular one-kilometre region. First search an index using the circle's bounding square, then compute exact intersections or distances for returned candidates. A park in a square's corner can be outside the circle and must be filtered out. State whether distance is measured from the park boundary, centroid or entrance. Those definitions answer different questions even when the indexing algorithm is perfectly correct.

References: Carleton 4202 official calendar record · Open Geospatial Consortium: Simple Feature Access standard

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Carleton 4202 official calendar record ↗Course scope · 2026–27
• Open Geospatial Consortium: Simple Feature Access standard ↗Supplementary primary reference