Tree Planted. In the Zone? - Farouk Ghodhbane

Context

Imagine the University of California, Riverside's (UCR's) Landscape Services (LS) hosting a tree planting event within designated protected zones. Each participant records the geographic coordinates for each tree they plant. At the end of the event, using those coordinates, LS wants to verify whether each tree was planted within its intended zone to ensure compliance with conservation regulations.

This is where "Tree Planted. In the Zone?" comes in. It is a C++ application that models protected zones as polygons and tree locations as points. The user provides an input file containing polygon boundaries and tree coordinates. The app then classifies each tree as Inside, Outside, or On edge and outputs a summary report including total count of trees analyzed.

Implementation

Protected zones are represented as ordered lists of vertices forming simple polygons, while trees are modeled as 2D points with double-precision coordinates. For each tree, the application evaluates its position relative to a polygon by iterating over the polygon's edges and applying a pip classification based on the Even-Odd Rule also known as the ray-casting algorithm.

The algorithm uses a rightward ray-casting approach. For each point, a horizontal ray is projected to the right and the number of times it intersects with a polygon's edges is analyzed. Each intersection toggles an inside/outside flag according to the Even-Odd Rule. (More on that under the "visual" section below). Points that lie exactly on an edge or more specifically on a vertex are detected separately and classified as On edge

The implementation is optimized using a bounding-box pre-check. For a given polygon, an axis-aligned bounding box is computed using the minimum and maximum x and y coordinates of its vertices. This allows the early classification of points obviously outside the zone before applying the full ray-casting algorithm, hence avoiding unnecessary computations.

A small tolerance value (1e-12) is used to mitigate floating-point precision errors when comparing values. Edge cases such as points in concave polygon regions and ray crossing a polygon vertex are handled to ensure correctness of the classification.

Example input:

# Number of polygon vertices
4
0 0
10 0
10 10
0 10
# Number of points (trees)
3
5 5
12 5
10 10

Results

For each tree coordinate, the app outputs a classification indicating whether the tree lies inside, outside, or on the edge of the polygon. This provides a an interpretation of each tree’s spatial relationship to the defined protected zone.

After processing all trees, a summary report aggregates the total number of trees in each category along with the total count of trees analyzed, completing the spatial query and verifying the extent of conservation compliance.

Example output:

Tree 1 at (5, 5): inside polygon
Tree 2 at (12, 5): outside polygon
Tree 3 at (10, 10): on edge
-------------------------------------------------
Summary report:
-------------------------------------------------
Inside: 1 | On edge: 1 | Outside: 1
Total trees analyzed: 3

Testing

Unit tests validate core geometric operations, including bounding-box computation, and bounding-box pre-check. Additional tests focus on edge cases, specifically with concave polygons such as points within concave regions (see code snippets below).
Golden tests compare program output against expected results for predefined input datasets. This verifies the app's workflow including the command-line output, file parsing, and classification logic working together correctly and helps detect regressions during future changes.

Sample concave polygon tests

Polygon concave;
concave.vertices = {{0,0},{10,0},{10,4},{4,4},{4,10},{0,10}};

// Test: Point in concave dent
Point in_dent{7,7};
assert(PointInPolygon(in_dent,concave) == -1);

// Test: Point on concave edge
Point on_concave_edge{7,4};
assert(PointInPolygon(on_concave_edge,concave) == 0);

Visual

Open in a new tab

Ray-Casting algorithm visual explanation.

Discussion & Resources

The classification function runs in O(n). More precisely, it runs in O(T*V), where T is the number of trees and V the number of polygon vertices. That is because for each tree, we need to loop through all polygon edges in order to classify its position. In practice, the preliminary bounding-box check optimizes the app by reducing unnecessary calculations for obviously outside points.

One limitation of the current implementation is that it assumes polygons are simple (i.e, no self intersections or interior holes). In practice, geographical regions may contain overlapping boundaries and/or inner exclusions (inner rings defined by their own boundaries). This may call for more complex polygon representation such as multi-ring structures (e.g., a vector of vectors or a list of lists) and more contextually accurate pip algorithms such as the winding number algorithm.

This experiment is framed as a "exp1-vector-model” because it represents spatial data using discrete geometric features: points (trees) and polygons. This contrasts with the raster model, which represents continuous spatial phenomena as a grid of uniformly distributed cells. The vector model is suitable for precise geometric reasoning, such as exact boundary detection.