Skip to content

S3Q1 · Polygon Analysis

📁 GitHub
⚡ Quick Reference

Four functions on a polygon given as a list of (x, y) vertex tuples:

def perimeter(points):
    n = len(points)
    return sum(distance(points[i], points[(i+1) % n]) for i in range(n))

def bounding_box(points):
    xs = [p[0] for p in points]
    ys = [p[1] for p in points]
    return (min(xs), min(ys)), (max(xs), max(ys))

def area(points):
    n = len(points)
    return abs(sum(det_2x2([points[i], points[(i+1) % n]])
                   for i in range(n))) / 2

def is_convex(points):
    n = len(points)
    return all(zcross(points[i], points[(i+1) % n], points[(i+2) % n]) > 0
               for i in range(n))

Key rules: - All functions use modular indexing % n to wrap around (last vertex connects to first) - perimeter: sum of Euclidean distances between consecutive pairs - bounding_box: (min_x, min_y) bottom-left, (max_x, max_y) top-right - area: Shoelace formula - ½ |Σ det([pᵢ, pᵢ₊₁])| - is_convex: all zcross > 0 for anti-clockwise polygon

Problem Statement

Problem

Implement four polygon analysis functions using the provided helper functions det_2x2, distance, and zcross.

Sample data: 

points = [(2,1), (5,1), (7,3), (4,6), (1,4)]

Helper functions (provided)

import math

def det_2x2(m) -> float:
    a, b, c, d = *m[0], *m[1]
    return a*d - b*c              # ad - bc

def distance(p1, p2) -> float:
    x1, y1, x2, y2 = *p1, *p2
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)

def zcross(A, B, C):
    ax,ay,bx,by,cx,cy = *A, *B, *C
    ab = (bx-ax, by-ay)
    bc = (cx-bx, cy-by)
    return det_2x2([ab, bc])

Function 1 - perimeter

Sum distances between consecutive vertices, wrapping from last back to first:

def perimeter(points: list) -> float:
    n = len(points)
    return sum(distance(points[i], points[(i+1) % n]) for i in range(n))

From sample: dist((2,1),(5,1)) + dist((5,1),(7,3)) + dist((7,3),(4,6)) + dist((4,6),(1,4)) + dist((1,4),(2,1)) = 3 + 2.83 + 4.24 + 3.61 + 3.16 = 16.84 ✓

Function 2 - bounding_box

Min and max of x and y coordinates:

def bounding_box(points: list) -> tuple:
    xs = [p[0] for p in points]
    ys = [p[1] for p in points]
    return (min(xs), min(ys)), (max(xs), max(ys))

From sample: x values = {2,5,7,4,1}, y values = {1,1,3,6,4} → bottom-left = (1,1), top-right = (7,6) → ((1,1),(7,6)) ✓

Function 3 - area (Shoelace Formula)

Area = ½ |Σ det([pᵢ, pᵢ₊₁])|

where det([pᵢ, pᵢ₊₁]) = xᵢ×yᵢ₊₁ − yᵢ×xᵢ₊₁

def area(points: list):
    n = len(points)
    return abs(sum(det_2x2([points[i], points[(i+1) % n]])
                   for i in range(n))) / 2

From sample: determinants = [-3, 8, 30, 10, -7], sum = 38, area = 19 ✓

Why abs()?

For anti-clockwise polygons the sum is positive, so abs() isn't strictly needed here. Including it makes the function correct for clockwise polygons too.

Function 4 - is_convex

A polygon is convex if zcross > 0 for every triple of consecutive vertices (anti-clockwise):

def is_convex(points: list) -> bool:
    n = len(points)
    return all(zcross(points[i], points[(i+1) % n], points[(i+2) % n]) > 0
               for i in range(n))

From sample: all zcross values = {6, 12, 15, 11, 9} - all positive → True ✓

Complete solution approaches

import math

def perimeter(points: list) -> float:
    n = len(points)
    return sum(distance(points[i], points[(i+1) % n]) for i in range(n))

def bounding_box(points: list) -> tuple:
    xs = [p[0] for p in points]
    ys = [p[1] for p in points]
    return (min(xs), min(ys)), (max(xs), max(ys))

def area(points: list):
    n = len(points)
    return abs(sum(det_2x2([points[i], points[(i+1) % n]])
                   for i in range(n))) / 2

def is_convex(points: list) -> bool:
    n = len(points)
    return all(zcross(points[i], points[(i+1) % n], points[(i+2) % n]) > 0
               for i in range(n))

import math

def perimeter(points: list) -> float:
    n      = len(points)
    total  = 0.0
    for i in range(n):
        total += distance(points[i], points[(i+1) % n])
    return total

def bounding_box(points: list) -> tuple:
    xs = [p[0] for p in points]
    ys = [p[1] for p in points]
    bottom_left = (min(xs), min(ys))
    top_right   = (max(xs), max(ys))
    return bottom_left, top_right

def area(points: list):
    n       = len(points)
    total   = 0.0
    for i in range(n):
        total += det_2x2([points[i], points[(i+1) % n]])
    return abs(total) / 2

def is_convex(points: list) -> bool:
    n = len(points)
    for i in range(n):
        if zcross(points[i], points[(i+1) % n], points[(i+2) % n]) <= 0:
            return False
    return True

import math

def perimeter(points: list) -> float:
    pairs = zip(points, points[1:] + [points[0]])
    return sum(distance(a, b) for a, b in pairs)

def bounding_box(points: list) -> tuple:
    return (min(p[0] for p in points), min(p[1] for p in points)), \
           (max(p[0] for p in points), max(p[1] for p in points))

def area(points: list):
    pairs = zip(points, points[1:] + [points[0]])
    return abs(sum(det_2x2([a, b]) for a, b in pairs)) / 2

def is_convex(points: list) -> bool:
    n      = len(points)
    triples = zip(points, points[1:] + [points[0]], points[2:] + points[:2])
    return all(zcross(a, b, c) > 0 for a, b, c in triples)

Key takeaways

01

% n - wrap-around indexing for polygons

points[(i+1) % n] connects the last vertex back to the first. Without % n, you'd need a special case for the final edge. Modular indexing keeps all vertices uniform.

02

Shoelace formula - det_2x2 computes each term

det_2x2([pᵢ, pᵢ₊₁]) = xᵢ×yᵢ₊₁ − yᵢ×xᵢ₊₁. Summing these and halving gives the signed area. Taking abs() handles both winding directions.

03

is_convex - zcross > 0 for all consecutive triples

For an anti-clockwise polygon, a positive z-component of the cross product at every vertex means every turn is a left turn - the definition of convexity. One non-positive value makes it concave.