Computational Geometry › Lesson

Capstone: Meridian's Coverage Map

50 minCombine this section's convex hull with the shoelace formula to report a depot's actual service area, not just a list of stops

You're building a piece ofMeridian — service areas & coverage

This piece — coverage_report(): Reports a depot's service boundary and the area it covers, over a real stop set.

Scenario A depot manager wants one report: here is the boundary your stops actually draw on the map, and here is how much ground it covers.

Your task

Build coverage_report(stops). Return [hull, area]: the convex hull of stops (counter-clockwise, as in the convex hull lesson), and the area it encloses, computed with the shoelace formula: sum of (x_i * y_{i+1} - x_{i+1} * y_i) over every edge of the hull (wrapping the last edge back to the first vertex), take the absolute value, and divide by 2. Points arrive as plain [x, y] lists, so deduplicate with sorted({tuple(p) for p in points}) inside convex_hull, not sorted(set(points)) — a list can't go inside a set(). Example: coverage_report([(0,0), (8,0), (8,6), (0,6), (4,3), (2,5), (6,1), (3,7)]) -> [[(0,0), (8,0), (8,6), (3,7), (0,6)], 52.0].

Additional resources

ArticleShoelace formula↗

Capstone: Meridian's Coverage Map

In short: this capstone puts two things from this section together into one report a depot manager would actually read. The convex hull (lesson 3) turns a scattered list of stops into the boundary Meridian's service area actually draws on the map. The shoelace formula turns that boundary into one number: the area it encloses, found from the vertices alone — sum x_i * y_{i+1} - x_{i+1} * y_i around every edge, take the absolute value, halve it. No new geometry idea here, just the orientation test and the hull it builds, read all the way through to a number a dashboard can show.

A depot's eight stops plotted on a coordinate plane, five of them connected by a solid boundary line labelled "coverage boundary" and shaded lightly inside, with the three interior stops marked as dots with no line touching them and a small area readout in the corner

A depot's service boundary, with a number attached

Eight of Meridian's stops, four of them sitting inside wherever the others end up:

step through it

1def orientation(a, b, c):

2 cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

3 if cross > 0:

4 return 1

5 if cross < 0:

6 return -1

7 return 0

9def half_hull(points):

10 hull = []

11 for p in points:

12 while len(hull) >= 2 and orientation(hull[-2], hull[-1], p) <= 0:

13 hull.pop()

14 hull.append(p)

15 return hull

17def convex_hull(points):

18 pts = sorted(set(points))

19 if len(pts) < 3:

20 return pts

21 lower = half_hull(pts)

22 upper = half_hull(list(reversed(pts)))

23 return lower[:-1] + upper[:-1]

25def shoelace_area(polygon):

26 n = len(polygon)

27 total = 0

28 for i in range(n):

29 x1, y1 = polygon[i]

30 x2, y2 = polygon[(i + 1) % n]

31 total += x1 * y2 - x2 * y1

32 return abs(total) / 2

34def coverage_report(stops):

35 hull = convex_hull(stops)

36 area = shoelace_area(hull)

37 return hull, area

39stops = [(0, 0), (8, 0), (8, 6), (0, 6), (4, 3), (2, 5), (6, 1), (3, 7)]

40print(coverage_report(stops))

Five stops make the boundary; three — (4,3), (2,5), (6,1) — sit inside it and never show up in hull at all. The area comes out to exactly 52.0, found without ever drawing anything: just the hull's five vertices, fed through one formula.

A new stop can grow the boundary, or change nothing

Add one new stop far outside the current boundary, and both the hull and the area change. Add one well inside it, and nothing does:

python

(4, 3) sits in the middle of the rectangle, so convex_hull pops it right back off — the report comes back identical, area 48.0 both times. (12, 2) sits well past the eastern edge, so it becomes a new vertex on the boundary, and the shaded area grows from 48.0 to 64.0.

Quick practice

What does this print?

def shoelace_area(polygon):
    n = len(polygon)
    total = 0
    for i in range(n):
        x1, y1 = polygon[i]
        x2, y2 = polygon[(i + 1) % n]
        total += x1 * y2 - x2 * y1
    return abs(total) / 2

print(shoelace_area([(0, 0), (5, 0), (5, 4), (0, 4)]))

What does this print?

hull = [(0, 0), (4, 0), (4, 4), (0, 4)]
hull_set = set(hull)
stops = [(0, 0), (4, 0), (4, 4), (0, 4), (2, 2)]
print([p for p in stops if p not in hull_set])

🎯 Your turn

Build coverage_report(stops): return [hull, area], combining convex_hull from lesson 3 with the shoelace formula.

coverage_report([(0,0), (8,0), (8,6), (0,6), (4,3), (2,5), (6,1), (3,7)]) → [[(0,0), (8,0), (8,6), (3,7), (0,6)], 52.0]
coverage_report([(0,0), (4,0), (4,4), (0,4)]) → [[(0,0), (4,0), (4,4), (0,4)], 16.0]

Hint: build the hull exactly as in lesson 3 — dedupe with sorted({tuple(p) for p in points}), not sorted(set(points)), since stops arrives as plain [x, y] lists. Then shoelace: sum x_i * y_{i+1} - x_{i+1} * y_i for every edge (wrapping with % n), take abs(), divide by 2.

Press ▶ Run, try the Live App chips, then ✓ Check.

Practice — level up

0/5 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upThe area of a polygon, from its vertices alone

Write shoelace_area(polygon), where polygon's vertices are already in order (clockwise or counter-clockwise, either works). Return its area using the shoelace formula. shoelace_area([(0,0), (4,0), (4,4), (0,4)]) -> 16.0.

shoelaceconvex-hull

DrillIs this point inside the coverage boundary?

Write depot_covered(hull, point), returning True if point lies inside or on the boundary of the convex hull (given counter-clockwise). depot_covered([(0,0),(8,0),(8,6),(3,7),(0,6)], (4,3)) -> True.

convex-hullpoint-in-polygon

BuildWhat fraction of the city does the depot cover?

Write coverage_ratio(stops, city_area), returning the depot's coverage area divided by city_area, rounded to 4 decimal places. coverage_ratio([(0,0),(8,0),(8,6),(0,6),(4,3),(2,5),(6,1),(3,7)], 100) -> 0.52.

shoelaceconvex-hull

BossWhich stops sit inside the boundary, not on it?

Write underserved_stops(stops, hull), returning every stop in stops that is NOT one of the hull's vertices — the stops the boundary passes around, not through. underserved_stops([(0,0),(8,0),(8,6),(0,6),(4,3),(2,5),(6,1),(3,7)], [(0,0),(8,0),(8,6),(3,7),(0,6)]) -> [(4,3), (2,5), (6,1)].

convex-hull

CapstoneWhat changes when a new stop joins?

Write add_stop_and_report(stops, new_stop), adding new_stop to stops and returning the FULL coverage_report (hull and area) of the updated set, as [hull, area]. add_stop_and_report([(0,0),(8,0),(8,6),(0,6),(4,3),(2,5),(6,1),(3,7)], (12,2)) -> [[(0,0),(8,0),(12,2),(8,6),(3,7),(0,6)], 64.0].

convex-hullshoelace