NivaarExam PrepOfficial exam papers ↗

18-Geom-A7 Geospatial Information Systems · May 2014

Question 16 of 23: The Point-in-Polygon Problem

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Exams — May 2014 — 04-Geom-A7 Geospatial Information Systems. Closed-book; no calculator permitted. Format: twenty-three short-answer questions of equal value (5 marks each); a candidate answers any twenty, but all twenty-three are solved in full below. Datum and coordinate conventions follow the Canadian spatial reference framework — NAD83(CSRS) horizontally and CGVD2013 vertically.

Reference texts: P. A. Longley, M. F. Goodchild, D. J. Maguire & D. W. Rhind, Geographic Information Systems and Science (4th ed., Wiley, 2015); P. Bolstad, GIS Fundamentals: A First Text on Geographic Information Systems (6th ed., XanEdu, 2019); P. A. Burrough, R. A. McDonnell & C. D. Lloyd, Principles of Geographical Information Systems (3rd ed., Oxford, 2015); M. Worboys & M. Duckham, GIS: A Computing Perspective (2nd ed., CRC, 2004); ISO 19115 Geographic information — Metadata.

Question 16: The Point-in-Polygon Problem (5 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

The point-in-polygon problem is the fundamental test of whether a given point lies inside, outside or on the boundary of a polygon — the operation behind spatial joins ("which parcel contains this GNSS point?"), overlay and containment queries. The standard method in a GIS is the ray-casting (even–odd / Jordan-crossing) algorithm: from the test point, cast a semi-infinite ray in an arbitrary fixed direction (conventionally horizontal) and count how many times it crosses the polygon's edges. If the number of crossings is odd, the point is inside; if even (including zero), it is outside.

P (inside)2 crossings? re-checkQ (outside)
Figure — A ray from an interior point crosses the boundary an odd number of times; a ray from an exterior point crosses an even number of times.

A GIS accelerates this over large datasets by first using a bounding-box or spatial-index (R-tree) filter to reject polygons the point cannot possibly be in, then applying the exact ray-cast only to candidates. Care must be taken with degenerate cases — the ray passing exactly through a vertex or running along an edge — which are handled by consistent tie-breaking rules (e.g., counting only edges whose one endpoint is strictly above the ray). An alternative exact method is the winding-number algorithm, which sums the signed angles subtended by the polygon edges about the point: a total of ±360° (one full turn) means inside, 0° means outside. Ray casting is the more common implementation because it is simple and fast.