Bounding box of an SVG path with curves

Write codeMedium25 min

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 always M. 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 recent M.
  • After each command the pen sits at the command's last point. After Z it sits at the point of the most recent M.
  • 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 P2 for 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 P3 for 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
Inputpath_bbox([["M", 0, 0], ["C", 0, 100, 100, 100, 100, 0]])
Output[0, 0, 100, 75]
Example 2
Inputpath_bbox([["M", 0, 0], ["Q", 50, -100, 100, 0], ["L", 100, 20]])
Output[0, -50, 100, 20]
Example 3
Inputpath_bbox([["M", 10, 10], ["L", 60, 10], ["L", 60, 40], ["Z"], ["C", 10, -50, 40, -50, 40, 10]])
Output[10, -35, 60, 40]