0-66122 · HIT · Elective Course · Semester B · Year of Study 2025
Computational Geometry and Geographic Information Systems
גיאומטריה חישובית ומערכות מידע גיאוגרפי
GIS concepts taught through computational geometry primitives, spatial data structures, and map algorithms
HIT Catalogue Documents
Downloadable DOCX catalogue documents for course approval and publication.
About This Course
This elective combines Geographic Information Systems knowledge with the computational geometry primitives that make GIS systems work. Students learn GIS as an integrated system for capturing, storing, managing, querying, analyzing, visualizing, and communicating spatial information. Core GIS concepts such as maps, coordinate systems, projections, vector and raster layers, terrain, imagery, geodatabases, cartography, and web maps are taught alongside the geometric representations and algorithms behind them.
The course treats every GIS topic as both an application and a computation. A parcel layer becomes a set of polygons; a road network becomes a graph embedded in the plane; a terrain model becomes a triangulation or raster surface; an orthophoto becomes georeferenced imagery; a spatial query becomes a geometric predicate, index lookup, or range search.
The goal is for students to understand GIS practice and the computer-science foundations underneath it: robust geometric primitives, spatial predicates, planar subdivisions, triangulations, nearest-neighbor search, range queries, map overlay, spatial indexing, shortest paths, approximation, and scalable map processing.
Course Objectives And Learning Outcomes
By the end of the course, students will be able to explain GIS as a complete spatial-information system, connect GIS knowledge with computational geometry primitives, and use that connection to design, explain, and evaluate spatial analysis workflows.
Semester Project
The running project is the center of the course. Each team chooses a GIS problem, represents the data geometrically, and applies computational geometry primitives or spatial data structures to solve it. The project should include a real or realistic spatial dataset, a clear GIS question, explicit geometric representation choices, at least one core algorithmic method, and a final map, query workflow, prototype, or analysis artifact.
Teams may use QGIS, PostGIS, GeoPandas, Shapely, CGAL, Python, JavaScript mapping libraries, or another approved toolchain. The point is not tool volume; it is the ability to explain the GIS meaning, the geometric model, the algorithmic method, and the limitations of the result.
P1Student Project Presentation 1 · Proposal
- GIS problem, motivation, target users, and intended map or analysis output.
- Dataset or map layers, coordinate reference system, and data quality risks.
- Initial geometric representation: points, lines, polygons, rasters, surfaces, or network graph.
- Planned computational geometry primitive, algorithm, or spatial data structure.
P2Student Project Presentation 2 · Interim
- Working prototype, notebook, map workflow, database query, or algorithm demo.
- Current GIS layers, geometric data model, spatial predicates, and indexing choices.
- Early results, map screenshots, query outputs, or validation examples.
- Open issues, next steps, and algorithmic or data-quality tradeoffs.
P3Student Project Presentation 3 · Final
- Completed GIS product or analysis with final maps, queries, prototype, or report.
- Clear explanation of the computational geometry primitive, algorithm, or index used.
- Evaluation of correctness, edge cases, performance, and spatial interpretation.
- Short oral defense: any team member can explain any part of the project.
Example Project Ideas
Each idea below combines GIS knowledge with computational geometry. Teams may take one as-is or propose a variant of comparable scope.
Weekly Materials
Each week combines the in-class plan with a study trail: lecture focus, practice brief, videos, official documentation, tutorials, and readings. In weeks 5, 8, and 13, the practice slot is a Student Project Presentation.
| Weekly plan, lecture focus, and practice focus |
|---|
| Part I · GIS Concepts As Geometric Objects |
|
Week 1GIS layers, maps, and geometric representation LectureMapping technologies, map scale, vector layers, raster layers, thematic layers, image layers, and GIS as geometric data.
PracticeInspect GIS layers and classify each dataset as points, polylines, polygons, rasters, grids, or surfaces. Define possible semester project domains.
Reading QGIS Training Manual, course introduction and creating a basic map.Tutorial Introduction to QGIS.
|
|
Week 2Coordinate systems, projections, and robust predicates LectureGeodesy, datums, projections, coordinate systems, spatial reference systems, orientation tests, sidedness tests, and degeneracies.
PracticeTransform sample coordinates, compare projected and geographic coordinates, and implement basic orientation and distance predicates.
Reading QGIS coordinate reference systems.Tutorial QGIS reprojection and transformation lesson.
|
|
Week 3Containment, crossing, and topology in vector GIS LecturePoint-in-polygon tests, ray casting, winding number intuition, segment intersection, parcel containment, network crossings, and topology cleaning.
PracticeImplement point-in-polygon and segment-intersection checks on small parcel, road, or zoning examples.
Reading Performing Spatial Queries in QGIS.Tutorial Shapely predicates and relationships.
|
|
Week 4Spatial extent, convex hulls, and bounding geometries LectureSpatial extent analysis, bounding boxes, convex hulls, monotone chain or Graham scan, geographic envelopes, and point-cloud summaries.
PracticeCompute bounding boxes and convex hulls for sample GPS or facility datasets. Prepare project proposal materials.
Reading Convex Hull construction.Tutorial Shapely convex hull.
|
| Part II · Geometric Algorithms For GIS Analysis |
|
Week 5Project proposal presentations, terrain, and triangulation LectureDigital terrain models, TIN surfaces, polygon decomposition, triangulation, elevation data, and surface representation.
Practice · Project PresentationProposal presentations. GIS problem, dataset, representation, geometric primitive, and planned implementation.
Reading CGAL 2D triangulations.Tutorial QGIS raster module, for terrain and elevation context.
|
|
Week 6Proximity GIS, Voronoi diagrams, and Delaunay triangulation LectureNearest facilities, service areas, proximity regions, Voronoi diagrams, Delaunay triangulation, interpolation intuition, and facility-location examples.
PracticeBuild a proximity analysis for service points or sensors, and relate Voronoi cells to GIS service areas.
Reading CGAL 2D Voronoi diagrams; CGAL Delaunay triangulations.Tutorial QGIS Voronoi polygons algorithm.
|
|
Week 7Map overlay, polygon clipping, and planar subdivisions LectureLayer intersection, polygon clipping, overlay analysis, planar subdivisions, arrangement intuition, and combining thematic GIS layers.
PracticePerform an overlay workflow such as land-use by municipal boundary, buffer by parcel, or environmental zone by road corridor.
Reading PostGIS spatial joins.Tutorial QGIS spatial queries tutorial.
|
| Part III · Scalable GIS Queries And Map Systems |
|
Week 8Interim project presentations, geodatabases, and spatial indexing LectureGeodatabases, spatial database queries, quadtrees, k-d trees, R-trees, bounding boxes, indexing tradeoffs, and map-query acceleration.
Practice · Project PresentationInterim presentations. Prototype, data representation, spatial query strategy, early results, and next steps.
Reading PostGIS spatial indexing; Shapely STRtree.Tutorial QGIS spatial database queries.
|
|
Week 9Spatial queries, nearest neighbors, and remote-sensing layers LecturePoint location, window queries, proximity search, spatial joins, GPS observations, LiDAR point clouds, imagery-derived features, and query complexity.
PracticeImplement or configure a nearest-neighbor, range-query, or spatial-join workflow using project-style data.
Reading PostGIS nearest-neighbor search; PostGIS KNN distance operator.Tutorial PostGIS spatial joins.
|
|
Week 10Spatial networks and shortest paths LectureRoad networks, graph models embedded in space, shortest paths, routing, network costs, and spatial constraints.
PracticeModel a small road, pedestrian, or utility network and run a routing or reachability analysis.
Reading QGIS network analysis lesson.Tutorial Basic Network Visualization and Routing in QGIS.
|
|
Week 11Cartography, symbology, and geometric simplification LectureCartographic communication, symbology, labeling, scale-dependent detail, line simplification, polygon simplification, and geometric approximation.
PracticeSimplify a map layer, compare geometry quality across scales, and design a readable project map.
Reading QGIS symbology lesson; GeoPandas simplify.Tutorial Shapely simplify.
|
|
Week 12Web maps, imagery integration, and scalable spatial products LectureImage integration, mosaics, orthophotos, image pyramids, tiled web maps, spatial APIs, and scalable geometric processing.
PracticePrepare final project maps, figures, query outputs, or prototype demonstrations for presentation.
|
|
Week 13Final student project presentations LectureCourse synthesis: GIS knowledge, geometric primitives, spatial data structures, and map algorithms as one design vocabulary.
Practice · Project PresentationFinal presentations. Completed project, GIS interpretation, computational-geometry explanation, evaluation, limitations, and demonstration.
Reading Review selected project-relevant sections from the QGIS Training Manual, PostGIS workshop, and computational geometry references.Tutorial Final project documentation, map export, and oral defense rehearsal.
|
Video References
These video resources support the weekly plan. English materials are the primary watch list; Hebrew materials support review, terminology, and local context where a relevant source exists.
English Videos
Useful for GIS components, vector data, topology, raster data, and introductory spatial analysis.
Practical GIS workflow support for data loading, layer inspection, styling, and map production.
Algorithmic support for line sweep, visibility, triangulation, Voronoi diagrams, and geometric searching.
Concise lecture sequence beginning with convex hulls and other core geometric algorithms.
Direct support for week 2 on CRS and projection choices.
Direct support for week 3 point-in-polygon analysis.
Direct support for week 10 routing and spatial networks.
Hebrew Videos
Hebrew GIS course page covering spatial data types, coordinate systems, cartography, and analysis topics.
Hebrew introduction to computational geometry concepts from an Open University style course sequence.
Hebrew course page describing geometric modelling with points, segments, polygons, and efficient algorithms.
AI Usage
Using an AI assistant is encouraged in this course for exploration, code review, data-cleaning ideas, map interpretation, and explanation practice. Two conditions keep the learning genuine: students keep full ownership of, and responsibility for, everything they submit, and must be able to explain and defend every GIS decision, geometric method, prompt-assisted result, and line of code.
Every weekly project increment follows a three-part model:
Part A · AI assistant welcomeExplore
Use an assistant to compare GIS workflows, generate small examples, clarify geometric predicates, or identify edge cases in spatial data.
Part B · verification requiredRun And Inspect
Run the workflow, inspect maps and attributes, check coordinate systems, test edge cases, and verify that generated outputs match the spatial question.
Part C · in plain languageReview And Defend
Explain the GIS meaning, the geometric representation, the algorithmic method, and where the result would fail or need better data.
Assessment And Grading
Grading is project-based, with weight on GIS understanding, correct spatial representation, algorithmic reasoning, map quality, validation, and the ability to defend decisions. The running project is the single deliverable, built up through weekly increments and graded at the three Student Project Presentations. There are no written exams.
| Component | What it covers | Weight |
|---|---|---|
| Project · Proposal | Student Project Presentation 1: GIS problem, dataset, coordinate choices, geometric representation, planned algorithm, risks, and work plan (week 5). | 20% |
| Project · Interim | Student Project Presentation 2: working prototype or workflow, spatial data model, GIS outputs, algorithmic method, validation examples, and next steps (week 8). | 30% |
| Project · Final | Student Project Presentation 3: complete GIS product or analysis, computational-geometry explanation, final maps or outputs, evaluation, limitations, and oral defense (week 13). | 50% |
Bibliography
The reading list combines GIS foundations with computational-geometry and algorithmic-spatial-analysis references.
Fourth edition, 2015.
Ninth edition, 2018 or 2019.
Seventh edition, 2022.
Core reference for geometric primitives, triangulations, arrangements, Voronoi diagrams, and geometric searching.
Algorithmic reference for polygon operations, convex hulls, triangulation, and implementation-oriented geometry.
Third edition, 2015.
Edition published in 2024.