Четырёхугольники и многоугольники

OpenStreetMap хранит каждую улицу как список координат. Чтобы посчитать площадь района для налогов или зонирования - нужна одна формула: 0.5 * |sum(x_i * y_{i+1} - x_{i+1} * y_i)|. Это формула шнурка (Shoelace / Гаусса), и она работает для любого многоугольника - от парковки до округа. Гаусс вывел её для землемеров. Сейчас она в каждом map tile render на планете.

• **Object detection (YOLO, Faster-RCNN):** IoU (Intersection over Union) - метрика качества детектора - вычисляет площади боксов через формулы четырёхугольников миллиарды раз в секунду
• **Convex hull и anomaly detection:** Graham scan строит выпуклую оболочку через знаковую площадь треугольников (Shoelace для n=3); точки вне оболочки - кандидаты на аномалию
• **GPU растеризация (OpenGL, WebGPU):** Scanline fill работает через трапеции между рёбрами полигона - математика трапеции в основе каждого кадра на экране

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

• Треугольники: свойства и теоремы

Параллелограмм и трапеция

**YOLO** вычисляет IoU (Intersection over Union) для каждого предсказанного бокса. IoU - отношение площади пересечения к площади объединения двух прямоугольников. За этим стоит формула параллелограмма: S = b * h. Миллиарды раз в секунду по всему миру.

**Параллелограмм** - четырёхугольник с двумя парами параллельных сторон. Прямоугольник, ромб, квадрат - его частные случаи. Диагональ делит параллелограмм на два равных треугольника, поэтому S = b * h (ровно вдвое больше треугольника с теми же основанием и высотой).

Противоположные стороны равны и параллельны. Противоположные углы равны. Диагонали точкой пересечения делятся пополам. Сумма всех углов = 360 градусов.

**Трапеция** - четырёхугольник ровно с одной парой параллельных сторон (основания a и b). Средняя линия m = (a+b)/2 параллельна основаниям. Площадь: S = 0.5*(a+b)*h = m*h. Если верхнее основание стянуть в точку (a -> 0), трапеция становится треугольником: S = 0.5*b*h. Формула обобщает обе фигуры.

**Равнобедренная трапеция** - частный случай с равными боковыми сторонами. Диагонали равны, углы при каждом основании равны, и фигура вписывается в окружность. Scanline-рендеризация в GPU (OpenGL, WebGPU) проходит по горизонтальным строкам пикселей: каждая строка - срез трапеции между двумя рёбрами полигона.

Формула шнурка

OpenStreetMap хранит каждую улицу как список координат. Площадь района для налогов, зонирования, логистики - одна формула: 0.5 * |sum(x_i * y_{i+1} - x_{i+1} * y_i)|. Это формула шнурка (Shoelace / Гаусса), и она работает для любого многоугольника - от парковки до страны. Гаусс вывел её для землемеров в 18 веке. Сейчас она исполняется в каждом map tile render.

Идея проста: обходим вершины по порядку, перемножаем координаты крест-накрест, берём полуразность. Знак без модуля кодирует **ориентацию** - положительный при обходе против часовой стрелки, отрицательный при обходе по часовой. В GPU face culling этот знак определяет, смотрит ли нормаль к камере или от неё.

Convex hull (Graham scan, Jarvis march) используется в anomaly detection: если точка данных лежит вне выпуклой оболочки нормального облака - она аномалия. Graham scan сортирует точки по полярному углу и добавляет их через проверку знаковой площади треугольника (та же Shoelace для трёх вершин). Сложность - O(n log n).

Формула работает для любого **простого** (без самопересечений) многоугольника - выпуклого и невыпуклого. Самопересекающийся контур даст некорректный результат: части площади сложатся с разными знаками и взаимоуничтожатся. GIS-системы обязательно проверяют топологическую корректность полигона перед вычислением площади.

Свойства многоугольников

**Многоугольник** - замкнутая фигура с n сторонами. Любой n-угольник разбивается на (n-2) треугольника - триангуляция. Отсюда сумма внутренних углов: (n-2) * 180 градусов. Для внешних углов - всегда 360 градусов, независимо от n и формы: это следует из того, что полный оборот в любую сторону = 360 градусов.

Только три правильных многоугольника покрывают плоскость без зазоров: треугольник (60 * 6 = 360), квадрат (90 * 4 = 360), шестиугольник (120 * 3 = 360). Пчёлы выбрали шестиугольник: при одинаковой площади ячейки периметр (расход воска) минимален. Гипотеза сот доказана Томасом Хейлсом в 1999 году.

D = n*(n-3)/2. Из каждой вершины выходит (n-3) диагонали (ко всем вершинам, кроме себя и двух соседних). Умножаем на n вершин и делим на 2 - каждая диагональ считается дважды.

Polygon rasterization - основа GPU-растеризации в OpenGL/WebGPU. Алгоритм scanline fill проходит горизонтальными строками через полигон, находя пересечения с рёбрами. Каждый треугольник в mesh обрабатывается как простейший многоугольник: три вершины, три ребра, никаких диагоналей. Поэтому GPU оптимизирован именно под треугольники - непосредственная связь с формулой D = n*(n-3)/2 при n=3: нулевые диагонали, минимальная сложность.

Ключевые идеи

• **Параллелограмм:** S = b*h; прямоугольник, ромб, квадрат - частные случаи с дополнительными свойствами диагоналей
• **Трапеция:** S = 0.5*(a+b)*h; обобщает прямоугольник (a=b) и треугольник (a=0); средняя линия m = (a+b)/2
• **Shoelace (Гаусс):** площадь любого простого многоугольника по координатам; знак = ориентация контура; основа GIS, GPU culling, convex hull
• **n-угольник:** сумма углов = (n-2)*180; диагонали = n*(n-3)/2; тесселируют плоскость только треугольник, квадрат, шестиугольник

Связанные темы

Четырёхугольники и многоугольники - мост между базовой геометрией и вычислительными алгоритмами:

• Треугольники — Любой многоугольник триангулируется; формула углов (n-2)*180 следует из разбиения на треугольники
• Точки, прямые, углы — Параллельность и перпендикулярность определяют прямоугольники и ромбы
• Векторы — Shoelace - частный случай векторного произведения в 2D; знак = ориентация

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

• OpenStreetMap использует Shoelace для каждого здания, района, страны. Формула землемеров 18 века в каждом map tile render - что это говорит о природе математических инструментов?
• GPU оптимизирован под треугольники (n=3, нулевые диагонали). Почему именно треугольник, а не квадрат - минимальная единица растеризации?
• Shoelace для самопересекающегося контура даёт некорректный результат. Как бы изменилась формула, чтобы считать площадь правильно?

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

• geo-02 — Любой многоугольник - триангуляция треугольников; площадь параллелограмма = 2 треугольника
• geo-04 — Окружности и вписанные фигуры строятся поверх свойств четырёхугольников
• la-01-vectors-intro — Shoelace - это знаковая площадь через векторное произведение координат
• la-02-dot-product — IoU в object detection считает площади боксов через формулы четырёхугольников
• alg-01-big-o — Graham scan (convex hull) работает с площадями треугольников - O(n log n)
• trig-01