Quadrilaterals and Polygons

OpenStreetMap stores every street as a list of coordinates. Computing the area of a district for taxation or zoning requires one formula: 0.5 * |sum(x_i * y_{i+1} - x_{i+1} * y_i)|. The Shoelace formula (Gauss, 18th century) works for any polygon - from a parking lot to a country. Land surveyors used it with paper and pen. Now it runs in every map tile renderer on the planet.

• **Object detection (YOLO, Faster-RCNN):** IoU (Intersection over Union) - the standard detection metric - computes bounding box areas via quadrilateral formulas billions of times per second
• **Convex hull and anomaly detection:** Graham scan builds the convex hull via signed triangle areas (Shoelace at n=3); points outside the hull are anomaly candidates
• **GPU rasterization (OpenGL, WebGPU):** Scanline fill works through trapezoids between polygon edges - the trapezoid formula is the basis of every rendered frame on screen

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

• Triangles: Properties and Theorems

Parallelogram and Trapezoid

**YOLO** computes IoU (Intersection over Union) for every predicted bounding box. IoU is the ratio of intersection area to union area for two rectangles. Behind it sits the parallelogram formula: S = b * h. Billions of times per second, worldwide.

A **parallelogram** is a quadrilateral with two pairs of parallel sides. Rectangle, rhombus, square - all special cases. A diagonal splits the parallelogram into two congruent triangles, so S = b * h (exactly twice the triangle with the same base and height).

Opposite sides are equal and parallel. Opposite angles are equal. Diagonals bisect each other. Sum of all angles = 360 degrees.

A **trapezoid** has exactly one pair of parallel sides (bases a and b). The midsegment m = (a+b)/2 is parallel to both bases. Area: S = 0.5*(a+b)*h = m*h. Let the top base shrink to a point (a -> 0) and the trapezoid becomes a triangle: S = 0.5*b*h. One formula, three shapes.

An **isosceles trapezoid** has equal legs. Diagonals are equal, base angles are equal, the figure is cyclic (inscribed in a circle). Scanline fill in GPU rasterization (OpenGL, WebGPU) sweeps horizontal spans across a polygon - each span is a cross-section of the trapezoid between two edges.

The Shoelace Formula

OpenStreetMap stores every street as a list of coordinates. Computing the area of a district for taxation or zoning requires one formula: 0.5 * |sum(x_i * y_{i+1} - x_{i+1} * y_i)|. This is the Shoelace formula (also attributed to Gauss), and it works for any polygon - from a parking lot to a country. Gauss derived it for land surveyors in the 18th century. Now it runs in every map tile renderer on the planet.

The mechanism: traverse vertices in order, multiply coordinates cross-wise, take half the absolute difference. The **signed** version (without the absolute value) encodes orientation - positive for counter-clockwise traversal, negative for clockwise. In GPU face culling this sign determines whether a triangle's normal points toward the camera or away from it.

Convex hull algorithms (Graham scan, Jarvis march) are core to anomaly detection: points outside the convex hull of a normal data cloud are candidates for anomalies. Graham scan sorts points by polar angle and admits each one via a signed triangle area check - the same Shoelace with n=3. Complexity: O(n log n).

The formula works for any **simple** (non-self-intersecting) polygon - convex and concave alike. A self-intersecting boundary produces incorrect output: sub-areas accumulate with opposite signs and cancel out. GIS systems verify topological validity before computing area - exactly because Shoelace silently misfires on degenerate input.

Polygon Properties

A **polygon** is a closed figure with n sides. Any n-gon decomposes into (n-2) triangles - triangulation. This directly gives the interior angle sum: (n-2) * 180 degrees. The exterior angles always sum to 360 degrees, regardless of n and shape: one full turn, every time.

Only three regular polygons tile the plane without gaps: triangle (60 * 6 = 360), square (90 * 4 = 360), hexagon (120 * 3 = 360). Bees chose the hexagon: for a fixed cell area, the hexagonal perimeter is minimal - minimum wax, maximum honey. The honeycomb conjecture was proved by Thomas Hales in 1999.

D = n*(n-3)/2. From each vertex, (n-3) diagonals are drawn (to all vertices except itself and its two neighbors). Multiply by n vertices and divide by 2 - each diagonal is counted from both endpoints.

Polygon rasterization is the foundation of GPU rendering in OpenGL and WebGPU. The scanline fill algorithm sweeps horizontal lines through the polygon, finding edge intersections per row. Each triangle in a mesh is the simplest possible polygon: three vertices, three edges, zero diagonals. The GPU is optimized exactly for triangles - a direct consequence of D = n*(n-3)/2 at n=3: minimum structural complexity, maximum hardware throughput.

Key Ideas

• **Parallelogram:** S = b*h; rectangle, rhombus, square are special cases with additional diagonal properties
• **Trapezoid:** S = 0.5*(a+b)*h; generalizes rectangle (a=b) and triangle (a=0); midsegment m = (a+b)/2
• **Shoelace (Gauss):** area of any simple polygon from coordinates; sign = contour orientation; foundation of GIS, GPU culling, convex hull algorithms
• **n-gon:** angle sum = (n-2)*180; diagonals = n*(n-3)/2; only triangle, square, hexagon tile the plane

Related Topics

Quadrilaterals and polygons bridge basic geometry with computational algorithms:

• Triangles — Every polygon triangulates; the angle formula (n-2)*180 follows from decomposition into triangles
• Points, Lines, Angles — Parallelism and perpendicularity define rectangles and rhombuses
• Vectors — Shoelace is the 2D cross product; signed area and orientation are unified by vector algebra

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

• OpenStreetMap uses Shoelace for every building, district, and country boundary. A land-surveying formula from the 18th century now runs in every map tile renderer - what does this say about the lifespan of mathematical tools?
• The GPU is optimized for triangles (n=3, zero diagonals). Why exactly the triangle, and not the square, as the minimal rasterization unit?
• Shoelace produces incorrect output for self-intersecting contours. How would the formula need to change to handle them correctly?

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

• geo-02 — Every polygon is a triangulation; parallelogram area = 2 triangles with same base and height
• geo-04 — Circles and inscribed figures build on quadrilateral properties
• la-01-vectors-intro — Shoelace is signed area via cross product of coordinate pairs
• la-02-dot-product — IoU in object detection computes bounding box areas via quadrilateral formulas
• alg-01-big-o — Graham scan (convex hull) uses triangle signed areas - O(n log n)
• trig-01