Computational Geometry Basics

The simplest spatial fact about any set of points is its bounding box: the smallest upright rectangle that contains them all. You get it by taking the minimum and maximum of every coordinate - no clever maths, just min and max over the x values and the y values.

def bounding_box(pts):
    xs = [p[0] for p in pts]
    ys = [p[1] for p in pts]
    return (min(xs), min(ys), max(xs), max(ys))   # (minx, miny, maxx, maxy)

plan = [(2, 1), (6, 3), (4, 8), (1, 5)]
print(bounding_box(plan))   # (1, 1, 6, 8)

Humble as it looks, the bounding box does a lot of real work. Its width and height tell you the overall extent of a plan or site; its centre gives a quick location; and it is the standard fast pre-check before an expensive test. If two objects' bounding boxes do not overlap, the objects cannot possibly overlap, so you skip the costly detailed check - a trick that keeps clash tests and packing loops fast.

def box_size(pts):
    minx, miny, maxx, maxy = bounding_box(pts)
    return (maxx - minx, maxy - miny)   # (width, height)

print(box_size(plan))   # (5, 7)

Start here whenever you face a spatial problem: the bounding box is almost free to compute and often answers the question, or cheaply rules out most of the work before you reach for anything heavier.

The same idea extends to 3D by taking min and max of the z values too, giving a box that reports a model's overall footprint and height at a glance - handy for a quick sanity check that imported geometry is the size you expected, and not, say, a thousand times too big because of a unit mix-up.

Given a room or plot as a closed polygon of points, two facts come up constantly: its area and its centroid (the balance point, useful for placing a label or finding a centre of mass). Area comes from the elegant shoelace formula, which sums a criss-cross of coordinate products around the polygon - so named because the pattern of multiplications looks like lacing a shoe.

def polygon_area(poly):
    area = 0.0
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]   # next point, wrapping to the first
        area += x1 * y2 - x2 * y1
    return abs(area) / 2.0

room = [(0, 0), (4, 0), (4, 3), (0, 3)]
print(polygon_area(room))   # 12.0

The (i + 1) % n is the closing trick from Lesson 5.3: it pairs each point with the next and wraps the last point back to the first, so the polygon closes cleanly. The formula works for any simple polygon, not just rectangles - an L-shaped room, a splayed plot - which is exactly where doing it by hand gets error-prone and code shines.

A quick, good-enough centroid for many purposes is simply the average of the vertices. (The true area-weighted centroid needs a little more, but the vertex average is fine for placing a tag or getting a rough centre.)

def centroid(poly):
    n = len(poly)
    cx = sum(p[0] for p in poly) / n
    cy = sum(p[1] for p in poly) / n
    return (cx, cy)

print(centroid(room))   # (2.0, 1.5)

With these two you can total the areas of every room in a plan, flag rooms below a minimum, or drop a label at each room's centre - a schedule-and-annotate task that pairs naturally with the pandas work of Module 4.

Perhaps the most useful spatial test of all: is a given point inside a polygon? Is this tree within the plot, this fixture inside the room, this sample point on the site? The classic answer is the ray-casting algorithm, and its logic is delightfully visual: shoot an imaginary ray sideways from the point and count how many polygon edges it crosses. An odd number of crossings means the point is inside; an even number means outside.

def point_in_polygon(pt, poly):
    x, y = pt
    inside = False
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]
        crosses = (y1 > y) != (y2 > y)         # edge straddles the ray height
        if crosses:
            x_at = x1 + (y - y1) * (x2 - x1) / (y2 - y1)
            if x < x_at:                        # crossing is to the right
                inside = not inside
    return inside

square = [(0, 0), (4, 0), (4, 4), (0, 4)]
print(point_in_polygon((2, 2), square))   # True
print(point_in_polygon((5, 2), square))   # False

Read it slowly and it matches the picture: for each edge, check whether it straddles the point's height, and if so whether the crossing is to the right; every valid crossing flips an inside/outside switch. It works for concave and oddly-shaped polygons, not just convex ones, which is why it is the standard. The inside = not inside line is the whole trick in miniature - it toggles a light on and off with each crossing, and where the light ends up is your answer.

This single function unlocks a lot: filter a cloud of points to those inside a boundary, assign furniture to rooms, count trees per plot, test whether a click landed in a zone. For heavy or repeated use, shapely provides a fast, battle-tested contains, but writing it once yourself means you understand what that library call is doing - and can trust it.

Two more everyday tools round out the kit. Nearest point answers which of many candidates is closest to a target - the nearest fire exit, socket, tree or gridline - and it is a one-liner with min and the distance function from Lesson 5.1.

import math

def nearest(target, candidates):
    return min(candidates, key=lambda p: math.hypot(p[0] - target[0], p[1] - target[1]))

sockets = [(1, 1), (8, 2), (4, 6)]
print(nearest((5, 5), sockets))   # (4, 6)

The key= argument tells min to compare candidates by their distance to the target rather than by their raw values - a compact, idiomatic pattern worth memorising. Extend it slightly and you can find the nearest pair, cluster points, or snap positions to a grid.

Packing - placing many items without overlap - is where these tools combine, and a simple version shows the flavour. Try to drop each new item at a candidate position, and accept it only if it clears everything placed so far (checked cheaply with distance, or bounding boxes for rectangles).

def pack_circles(candidates, radius):
    placed = []
    for c in candidates:
        if all(math.hypot(c[0]-p[0], c[1]-p[1]) >= 2 * radius for p in placed):
            placed.append(c)
    return placed

spots = [(0, 0), (1, 0), (5, 0), (5, 5), (5.5, 5)]
print(pack_circles(spots, radius=1))   # keeps non-overlapping spots

Real packing (furniture in a room, parts on a sheet, trees on a site) gets much deeper - it is an optimisation problem, previewed in Module 9 - but the building block is exactly this: propose a position, test it against what is placed with the geometry functions you now own. That is the whole shape of spatial logic in code.

Individually these are small; together they compose into genuinely useful design scripts, because most spatial tasks are combinations of inside, how big, how far and which is nearest. Consider a realistic one: given a site boundary and a scatter of proposed tree positions, keep only the trees that fall inside the plot, are at least a minimum distance from every building corner, and are spaced from each other - then report how many survived and the total planted area.

That script is nothing more than point_in_polygon to filter by boundary, distance and nearest to enforce spacing, bounding_box as a fast pre-check to skip far-apart comparisons, and polygon_area for the report. Five functions from this lesson, wired together with the loops and lists from Module 2 and the conditionals from earlier modules. Nothing exotic - just the atoms, combined.

This compositional quality is the real message of the whole module. You have not memorised a large catalogue of special cases; you have learned a handful of small, honest operations that snap together in endless ways. A layout tool, a code-compliance check, a site-analysis dashboard and a generative facade study look wildly different on screen, yet under the surface they draw on the same short list: place points, measure distance, test inside, compute area, transform, repeat. When you meet a new spatial problem, the productive question is not what exotic algorithm do I need but which of these atoms, in what order, answers it. Almost always, the answer is a combination you already own.

Two honest cautions before you build on these. First, hand-rolled geometry is perfect for learning and for modest data, but for large clouds of points, robust edge cases (points exactly on an edge, self-touching polygons) or heavy repetition, reach for shapely (2D) or NumPy and scipy.spatial - mature libraries that are faster and handle the nasty cases you would otherwise trip over. Second, floating-point arithmetic means exactly on the line is genuinely ambiguous; when it matters, test with a small tolerance rather than checking for exact equality.

A final word on trust. Because these functions are short, you can and should test them on cases whose answers you already know: the area of a 4-by-3 room is 12, the centre of a unit square is (0.5, 0.5), a point at the middle of a shape is inside, a point far outside is not. A handful of such checks, run every time you change the code, catches mistakes long before they reach a drawing - and it is exactly the debugging discipline Module 10 formalises. Small functions with small tests are how careful spatial scripts stay correct.

With that, Module 5 is complete: you can place points, move them with vectors, represent them as curves, surfaces and meshes, and now compute real spatial facts about them. That is the geometric literacy the tool-specific modules build on - scripting Rhino and Grasshopper next, where these very ideas gain a 3D canvas and a live model to act on.