Areas and Perimeters

YOLO computes IoU - Intersection over Union - thousands of times per frame. IoU = area of intersection / area of union. The areas come from the Gauss shoelace formula in O(n). The same formula an 18-year-old Gauss wrote down in 1795 now runs inside every real-time object detector - from Tesla Autopilot to surveillance systems.

• **Object detection (YOLO, Faster R-CNN):** IoU is a ratio of polygon areas computed via shoelace; non-maximum suppression filters overlapping bounding boxes by IoU > 0.5
• **GIS and PostGIS:** ST_Area, ST_Intersection - shoelace for territory polygons, national borders, flood zone maps
• **Computer vision:** circularity = 4piA/P^2 in OpenCV for cell segmentation, defect detection, roundness quality control
• **Monte Carlo integration:** random sampling to estimate area of irregular regions - naturally parallelizes on GPU, used in ray tracing and physics engines

Предварительные знания

• Circles and Ellipses

Area Formulas

1795. Carl Friedrich Gauss, age 18, writes down a formula for the area of a polygon given its vertex coordinates. Two hundred years later, the same formula ships in every computational geometry library - from PostScript to PyTorch3D. It all starts with basic shapes.

Area is a scalar measure of a planar region. Simple shapes have closed-form formulas; arbitrary polygons require algorithmic methods. One key fact: the circle as the limit of a regular $n$-gon as $n \to \infty$ is not a metaphor - it is an exact limit.

**Why Heron?** The formula $\tfrac{1}{2}bh$ requires a height - which must be computed separately. Heron works from three sides alone. This matters in computational geometry, where vertices are given as coordinates and dropping a perpendicular is inconvenient.

Gauss Shoelace Formula and IoU in ML

Tesla FSD processes 8 cameras at 30 frames per second. Each frame holds hundreds of bounding boxes. Each bbox requires an IoU computation (Intersection over Union). IoU = area of intersection / area of union. Both areas use the shoelace formula. That is 240 area computations per second per camera.

**Gauss shoelace formula** for polygon with vertices $(x_1,y_1), \ldots, (x_n,y_n)$: $$S = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right|$$ indices are taken mod $n$. **Signed area** (without absolute value): positive = CCW traversal, negative = CW. This determines polygon orientation.

Signed area is not a technical detail - it is the orientation of the polygon. In 3D graphics it determines the surface normal direction (front-face vs back-face culling). In GIS it determines the traversal order of a territory boundary. YOLO and Faster R-CNN use signed area in non-maximum suppression to filter overlapping detections by IoU > 0.5.

Shoelace is O(n). For a convex hull on $n$ points: O(n log n) to sort, then O(n) for area. PostGIS, Shapely, CGAL, PyTorch3D - everywhere the same 8-line function.

Composite Shapes and Monte Carlo

Complex shapes are not a problem: any region can be decomposed into simple parts (inclusion-exclusion) or estimated numerically via Monte Carlo. These are two opposing strategies - analytical and statistical.

**Inclusion-exclusion for areas:** $$S(A \cup B) = S(A) + S(B) - S(A \cap B)$$ For disjoint regions the intersection is empty and areas sum directly. For overlapping regions subtract the intersection area. IoU = $S(A \cap B) / S(A \cup B)$ is a direct application of this formula.

Monte Carlo is the fallback when analytic methods are unavailable. Scatter random points across a bounding box and count how many land inside the shape. Convergence is $O(1/\sqrt{n})$ - slow, but applicable to any shape including fractals and irregular contours. In computer vision this estimates area for arbitrarily shaped segmentation masks.

Monte Carlo parallelizes perfectly: each sample is independent. On a GPU one can run billions of samples in parallel - this is why Monte Carlo lives inside physics engines, ray tracing, and RLHF reward estimation.

Isoperimetric Inequality

Bees have known the answer for thousands of years. Mathematicians proved it in the 19th century. Among all shapes with a fixed perimeter, the circle encloses the maximum area. This is the isoperimetric inequality, and it lives in computer vision as the roundness metric.

**Isoperimetric inequality:** $$4\pi A \leq P^2$$ where $A$ is area and $P$ is perimeter. Equality holds only for the circle. **Circularity (shape descriptor):** $C = 4\pi A / P^2 \in (0, 1]$. Circle: $C=1$, square: $C=\pi/4 \approx 0.785$, elongated ellipse: $C \ll 1$.

In biomedical computer vision, circularity is a standard cell descriptor. Cancer cells change shape as they become malignant: $C$ drops. In OpenCV: `4 * pi * cv2.contourArea(cnt) / cv2.arcLength(cnt, True)**2`. The same shoelace formula, the same isoperimetric bound.

Perimeter of a regular $n$-gon inscribed in a circle of radius $r$: $P = n \cdot 2r \sin(\pi/n)$. As $n \to \infty$ this converges to $2\pi r$. Archimedes used this approach with $n=96$ to bound $\pi$ to within 0.04%.

Key Ideas

• **Heron:** $S = \sqrt{s(s-a)(s-b)(s-c)}$ - triangle area from sides alone, no height needed
• **Shoelace:** $S = \tfrac{1}{2}|\sum(x_i y_{i+1} - x_{i+1} y_i)|$ - arbitrary polygon area in $O(n)$; signed version encodes CCW/CW orientation
• **IoU = shoelace:** real-time object detection is a direct application of the Gauss formula
• **Monte Carlo:** random points for complex shapes, error $O(1/\sqrt{n})$, parallelizes on GPU
• **Isoperimetric:** $4\pi A \leq P^2$, equality only for the circle; circularity is a standard CV descriptor

Related Topics

Areas connect planimetry to vector algebra, computational geometry, and numerical methods:

• Coordinate Geometry — Shoelace derives from the 2D cross product
• Vector Geometry — Parallelogram area = |a x b|
• Geometry in CS — Shoelace is a primitive for convex hull and polygon algorithms

Вопросы для размышления

• The signed shoelace sum determines polygon orientation (CCW vs CW) without extra checks. What physical meaning does this have in 3D rendering?
• Monte Carlo converges as $1/\sqrt{n}$. Why is it still fast on a GPU despite this slow convergence rate?
• The isoperimetric inequality says the circle maximizes area for fixed perimeter. How does this relate to why soap bubbles are always spherical?

Связанные уроки

• geo-06 — Shoelace derives from the 2D cross product in coordinate geometry
• geo-11 — Parallelogram area = |a x b|, the vector interpretation of shoelace
• geo-13 — Shoelace is the core primitive in convex hull, polygon clipping, computational geometry
• calc-11-definite — Riemann integral as limit of area sums - the same mindset at continuous scale
• trig-05 — Isoperimetric inequality connects area and perimeter via trigonometry
• trig-01