Solutions: Algorithmic Challenges

Challenge 1: Bounding Box

A bounding box is four numbers

• The axis-aligned bounding box of a set of points is the smallest rectangle (with sides parallel to the axes) that contains all of them
• Numerically: just four values

\[\text{BB} = (x_{\min},\ y_{\min},\ x_{\max},\ y_{\max})\]

• Key insight: you never need to store the full point list — only the current extremes

The algorithm

Initialize with the first point:

\[x_{\min} = x_{\max} = x_0 \quad y_{\min} = y_{\max} = y_0\]

For every subsequent point \((x, y)\):

• if \(x < x_{\min}\) → update \(x_{\min}\)
• if \(x > x_{\max}\) → update \(x_{\max}\)
• if \(y < y_{\min}\) → update \(y_{\min}\)
• if \(y > y_{\max}\) → update \(y_{\max}\)

Four comparisons per point. Memory: constant (four numbers, regardless of stream length).

R implementation

stream <- matrix(c(
  2489750, 1117500,
  2506250, 1172500,
  2552750, 1223500,
  2498000, 1198000,
  2470000, 1145000
), ncol = 2, byrow = TRUE)

bb <- c(xmin = stream[1,1], xmax = stream[1,1],
        ymin = stream[1,2], ymax = stream[1,2])

for (i in seq_len(nrow(stream))) {
  bb["xmin"] <- min(bb["xmin"], stream[i, 1])
  bb["xmax"] <- max(bb["xmax"], stream[i, 1])
  bb["ymin"] <- min(bb["ymin"], stream[i, 2])
  bb["ymax"] <- max(bb["ymax"], stream[i, 2])
}
bb

   xmin    xmax    ymin    ymax 
2470000 2552750 1117500 1223500 

Challenge 2: Point in Polygon

The intuition

Draw a ray from the point horizontally to the right (→ infinity):

• Count how many polygon edges the ray crosses
• Odd number of crossings → point is inside
• Even number of crossings → point is outside

Ray casting: the algorithm

For each edge of the polygon (vertex \(i\) → vertex \(i+1\)):

1. Does the edge straddle the horizontal line \(y = p_y\)? \[( y_i > p_y ) \ne ( y_{i+1} > p_y )\]

2. If yes: is the ray–edge intersection to the right of \(p_x\)? \[x_{\text{hit}} = x_i + \frac{(p_y - y_i)(x_{i+1} - x_i)}{y_{i+1} - y_i} > p_x\]

3. If both conditions hold → flip an inside boolean (starts FALSE)

Result: inside after all edges = TRUE if the point is inside.

R implementation

point_in_poly <- function(px, py, vx, vy) {
  n <- length(vx)
  inside <- FALSE
  j <- n
  for (i in seq_len(n)) {
    if (((vy[i] > py) != (vy[j] > py)) &&
        (px < (vx[j] - vx[i]) * (py - vy[i]) / (vy[j] - vy[i]) + vx[i])) {
      inside <- !inside
    }
    j <- i
  }
  inside
}

# polygon: a rough triangle
vx <- c(1, 4, 2.5); vy <- c(1, 1, 4)

point_in_poly(2.5, 2,   vx, vy)  # inside  → TRUE

[1] TRUE

point_in_poly(0,   0,   vx, vy)  # outside → FALSE

[1] FALSE

point_in_poly(3.5, 3.5, vx, vy)  # outside → FALSE

[1] FALSE

Edge cases

Situation	How to handle
Ray passes exactly through a vertex	Use strict > on one side, >= on the other — ensures each vertex is counted at most once
Point lies exactly on an edge	Technically undefined; most implementations return TRUE
Polygon is not closed	Close it: ensure last vertex = first vertex
Concave / complex polygons	Algorithm works unchanged — this is its strength over simpler methods

References