Bounding box of an SVG path with curves
Your task
An icon editor draws a selection box around each path, and the box has to hug the drawn shape, not the curve handles. The paths are already parsed into commands with absolute coordinates.
Write path_bbox(commands) that returns the smallest axis-aligned box that holds every point the path draws, as [min_x, min_y, max_x, max_y].
Input and output:
commands: 1 to 1,000 commands, and the first one is alwaysM. Each command is a list that starts with its letter:["M", x, y]moves the pen to (x, y) without drawing. That point counts as part of the path.["L", x, y]draws a straight line from the pen to (x, y).["Q", x1, y1, x, y]draws a quadratic Bézier curve from the pen to (x, y), with control point (x1, y1).["C", x1, y1, x2, y2, x, y]draws a cubic Bézier curve from the pen to (x, y), with control points (x1, y1) and (x2, y2).["Z"]draws a straight line from the pen back to the point of the most recentM.
- After each command the pen sits at the command's last point. After
Zit sits at the point of the most recentM. - Coordinates are integers from -100,000 to 100,000.
- Returns 4 numbers. The tests accept any value within 0.000001 of the exact one, or within one billionth of it when that is larger.
Rules:
- A quadratic curve from P0 to P2 with control point P1 is every point
(1 - t)^2 P0 + 2 (1 - t) t P1 + t^2 P2for t from 0 to 1. - A cubic curve from P0 to P3 with control points P1 and P2 is every point
(1 - t)^3 P0 + 3 (1 - t)^2 t P1 + 3 (1 - t) t^2 P2 + t^3 P3for t from 0 to 1. - A control point is part of the path only where the curve actually passes through it.
Examples
path_bbox(commands: list[list]) -> list[float]Example 1
Input
path_bbox([["M", 0, 0], ["C", 0, 100, 100, 100, 100, 0]])Output
[0, 0, 100, 75]Example 2
Input
path_bbox([["M", 0, 0], ["Q", 50, -100, 100, 0], ["L", 100, 20]])Output
[0, -50, 100, 20]Example 3
Input
path_bbox([["M", 10, 10], ["L", 60, 10], ["L", 60, 40], ["Z"], ["C", 10, -50, 40, -50, 40, 10]])Output
[10, -35, 60, 40]