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

Математический алгоритм

Схема шнурка для определения площади многоугольника по координатам точек ${\displaystyle (x_{1},y_{1}),...,(x_{n},y_{n})}$

Формула шнуровки , также известная как формула площади Гаусса и формула геодезиста , ^[1] представляет собой математический алгоритм для определения площади простого многоугольника , вершины которого описываются их декартовыми координатами на плоскости. ^[2] Она называется формулой шнуровки из-за постоянного перекрестного умножения координат, составляющих многоугольник, подобно продеванию шнурков. ^[2] Она применяется в геодезии и лесном хозяйстве, ^[3] среди других областей.

Формула была описана Альбрехтом Людвигом Фридрихом Мейстером (1724–1788) в 1769 году ^[4] и основана на формуле трапеции, описанной Карлом Фридрихом Гауссом и К. Г. Дж. Якоби . ^[5] Треугольную форму формулы площади можно рассматривать как частный случай теоремы Грина .

Формулу площади можно также применять к самоперекрывающимся многоугольникам, поскольку значение площади по-прежнему ясно, хотя самоперекрывающиеся многоугольники, как правило, не являются простыми . ^[6] Кроме того, самоперекрывающийся многоугольник может иметь несколько «интерпретаций», но формулу Шнурка можно использовать, чтобы показать, что площадь многоугольника остается той же независимо от интерпретации. ^[7]

Формулы площади многоугольника

Основная идея: Любое ребро многоугольника определяет площадь трапеции. Все эти площади в сумме дают площадь многоугольника.

Дано: Плоский простой многоугольник с положительно ориентированной (против часовой стрелки) последовательностью точек в декартовой системе координат . Для простоты формул ниже удобно положить . ${\displaystyle P_{i}=(x_{i},y_{i}),i=1,\dots ,n}$
${\displaystyle P_{0}=P_{n},P_{n+1}=P_{1}}$

Формулы:
Площадь заданного многоугольника может быть выражена множеством формул, которые связаны простыми операциями (см. ниже):
Если многоугольник отрицательно ориентирован , то результат формул отрицателен. В любом случае это искомая площадь многоугольника. ^[8] ${\displaystyle A}$ ${\displaystyle |A|}$

Формула трапеции

Формула трапеции суммирует последовательность ориентированных областей трапеций , имеющих в качестве одного из четырех ребер (см. ниже): ${\displaystyle A_{i}={\tfrac {1}{2}}(y_{i}+y_{i+1})(x_{i}-x_{i+1})}$ ${\displaystyle P_{i}P_{i+1}}$ $${\displaystyle {\begin{aligned}A&={\frac {1}{2}}\sum _{i=1}^{n}(y_{i}+y_{i+1})(x_{i}-x_{i+1})\\&={\frac {1}{2}}{\Big (}(y_{1}+y_{2})(x_{1}-x_{2})+\cdots +(y_{n}+y_{1})(x_{n}-x_{1}){\Big )}\end{aligned}}}$$

Формула треугольника

Формула треугольника суммирует ориентированные площади треугольников : ^[9] ${\displaystyle A_{i}}$ ${\displaystyle OP_{i}P_{i+1}}$ $${\displaystyle {\begin{aligned}A&={\frac {1}{2}}\sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})={\frac {1}{2}}\sum _{i=1}^{n}{\begin{vmatrix}x_{i}&x_{i+1}\\y_{i}&y_{i+1}\end{vmatrix}}={\frac {1}{2}}\sum _{i=1}^{n}{\begin{vmatrix}x_{i}&y_{i}\\x_{i+1}&y_{i+1}\end{vmatrix}}\\&={\frac {1}{2}}{\Big (}x_{1}y_{2}-x_{2}y_{1}+x_{2}y_{3}-x_{3}y_{2}+\cdots +x_{n}y_{1}-x_{1}y_{n}{\Big )}\end{aligned}}}$$

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

Схема шнуровки, вертикальная форма: Со всеми нарисованными косыми чертами матрица отдаленно напоминает ботинок с завязанными шнурками, что и дало название алгоритму.

Формула треугольника является основой популярной формулы шнуровки , которая представляет собой схему, оптимизирующую вычисление суммы определителей 2×2 вручную: $${\displaystyle {\begin{aligned}2A&={\begin{vmatrix}x_{1}&x_{2}\\y_{1}&y_{2}\end{vmatrix}}+{\begin{vmatrix}x_{2}&x_{3}\\y_{2}&y_{3}\end{vmatrix}}+\cdots +{\begin{vmatrix}x_{n}&x_{1}\\y_{n}&y_{1}\end{vmatrix}}\\[10mu]&={\begin{vmatrix}x_{1}&x_{2}&x_{3}\cdots &x_{n}&x_{1}\\y_{1}&y_{2}&y_{3}\cdots &y_{n}&y_{1}\end{vmatrix}}\end{aligned}}}$$

Иногда этот определитель транспонируют (записывают вертикально , в два столбца), как показано на схеме.

Другие формулы

$${\displaystyle {\begin{aligned}A&={\frac {1}{2}}\sum _{i=1}^{n}y_{i}(x_{i-1}-x_{i+1})\\&={\frac {1}{2}}{\Big (}y_{1}(x_{n}-x_{2})+y_{2}(x_{1}-x_{3})+\cdots +y_{n}(x_{n-1}-x_{1}){\Big )}\end{aligned}}}$$ $${\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})}$$

Особенно лаконичное выражение формулы можно дать в терминах внешней алгебры . Если — последовательные вершины многоугольника (рассматриваемые как векторы в декартовой плоскости), то ${\displaystyle v_{1},\dots ,v_{n}}$ $${\displaystyle A={\frac {1}{2}}\left|\sum _{i=1}^{n}v_{i}\wedge v_{i+1}\right|.}$$

Пример

Для примера возьмем горизонтальную форму шнурка.

Пример

Для площади пятиугольника получаем $${\displaystyle {\begin{aligned}&P_{1}=(1,6),P_{2}=(3,1),P_{3}=(7,2),\\&P_{4}=(4,4),P_{5}=(8,5)\end{aligned}}}$$ $${\displaystyle {\begin{aligned}2A&={\begin{vmatrix}1&3\\6&1\end{vmatrix}}+{\begin{vmatrix}3&7\\1&2\end{vmatrix}}+{\begin{vmatrix}7&4\\2&4\end{vmatrix}}+{\begin{vmatrix}4&8\\4&5\end{vmatrix}}+{\begin{vmatrix}8&1\\5&6\end{vmatrix}}\\&=(1-18)\;+(6-7)\;+(28-8)\;+(20-32)\;+(48-5)=33\\A&=16.5\end{aligned}}}$$

Преимущество формы шнурка: для вычисления 5 определителей с 10 столбцами необходимо записать всего 6 столбцов.

Вывод формул

Формула трапеции

Вывод формулы трапеции

Ребро определяет трапецию с ее ориентированной областью ${\displaystyle P_{i},P_{i+1}}$ ${\displaystyle (x_{i},y_{i}),(x_{i+1},y_{i+1}),(x_{i},0),(x_{i+1},0)}$

$${\displaystyle A_{i}={\tfrac {1}{2}}(y_{i}+y_{i+1})(x_{i}-x_{i+1})}$$

В случае, если число отрицательное, в противном случае положительное или если . На схеме ориентация ребра показана стрелкой. Цвет показывает знак : красный означает , зеленый означает . В первом случае трапеция называется отрицательной , во втором случае положительной . Отрицательные трапеции удаляют те части положительных трапеций, которые находятся вне многоугольника. В случае выпуклого многоугольника (на схеме верхний пример) это очевидно: Площадь многоугольника равна сумме площадей положительных трапеций (зеленые ребра) за вычетом площадей отрицательных трапеций (красные ребра). В невыпуклом случае нужно рассмотреть ситуацию более внимательно (см. схему). В любом случае результат будет ${\displaystyle x_{i}<x_{i+1}}$ ${\displaystyle A_{i}}$ ${\displaystyle A_{i}=0}$ ${\displaystyle x_{i}=x_{i+1}}$ ${\displaystyle A_{i}}$ ${\displaystyle A_{i}<0}$ ${\displaystyle A_{i}>0}$ $${\displaystyle A=\sum _{i=1}^{n}A_{i}={\frac {1}{2}}\sum _{i=1}^{n}(y_{i}+y_{i+1})(x_{i}-x_{i+1})}$$

Треугольная форма, детерминантная форма

Форма треугольника: цвет ребер указывает, какая площадь треугольника положительная (зеленый) и отрицательная (красный) соответственно.

Исключая скобки и используя (см. соглашение выше), получаем определительную форму формулы площади: Поскольку половина i-го определителя представляет собой ориентированную площадь треугольника, эта версия формулы площади называется треугольной формой . ${\textstyle \sum _{i=1}^{n}x_{i}y_{i}=\sum _{i=1}^{n}x_{i+1}y_{i+1}}$ ${\displaystyle P_{n+1}=P_{1}}$ $${\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})={\frac {1}{2}}\sum _{i=1}^{n}{\begin{vmatrix}x_{i}&x_{i+1}\\y_{i}&y_{i+1}\end{vmatrix}}}$$ ${\displaystyle O,P_{i},P_{i+1}}$

Другие формулы

С (см. соглашение выше) получаем Объединение обеих сумм и исключение приводит к С тождеством получаем ${\textstyle \sum _{i=1}^{n}x_{i}y_{i+1}=\sum _{i=1}^{n}x_{i-1}y_{i}\ }$ ${\displaystyle P_{0}=P_{n},P_{n+1}=P_{1}}$ $${\displaystyle 2A=\sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})=\sum _{i=1}^{n}x_{i}y_{i+1}-\sum _{i=1}^{n}x_{i+1}y_{i}=\sum _{i=1}^{n}x_{i-1}y_{i}-\sum _{i=1}^{n}x_{i+1}y_{i}}$$ ${\displaystyle y_{i}}$ $${\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}y_{i}(x_{i-1}-x_{i+1})}$$ ${\textstyle \sum _{i=1}^{n}x_{i+1}y_{i}=\sum _{i=1}^{n}x_{i}y_{i-1}}$ $${\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})}$$

С другой стороны, это частный случай теоремы Грина , в котором одна функция равна 0, а другая — x, так что площадь равна интегралу xdy вдоль границы.

Манипуляции с многоугольником

${\displaystyle A(P_{1},\dots ,P_{n})}$указывает ориентированную площадь простого многоугольника с (см. выше). является положительным/отрицательным, если ориентация многоугольника положительная/отрицательная. Из треугольной формы формулы площади или диаграммы ниже можно заметить для : В случае следует сначала сместить индексы. ${\displaystyle P_{1},\dots ,P_{n}}$ ${\displaystyle n\geq 4}$ ${\displaystyle A}$ ${\displaystyle 1<k<n}$ $${\displaystyle A(P_{1},\dots ,P_{n})=A(P_{1},\dots ,P_{k-1},P_{k+1},\dots ,P_{n})+A(P_{k-1},P_{k},P_{k+1})}$$ ${\displaystyle k=1\;{\text{or}}\;n}$

Следовательно:

1. Перемещение влияет только и оставляет неизменным. Нет никаких изменений площади, если перемещается параллельно . ${\displaystyle P_{k}}$ ${\displaystyle A(P_{k-1},P_{k},P_{k+1})}$ ${\displaystyle A(P_{1},...,P_{k-1},P_{k+1},...,P_{n})}$ ${\displaystyle P_{k}}$ ${\displaystyle {\overline {P_{k-1}P_{k+1}}}}$
2. Очистка изменяет общую площадь на величину , которая может быть положительной или отрицательной. ${\displaystyle P_{k}}$ ${\displaystyle A(P_{k-1},P_{k},P_{k+1})}$
3. Вставка точки между изменяет общую площадь на величину , которая может быть положительной или отрицательной. ${\displaystyle Q}$ ${\displaystyle P_{k},P_{k+1}}$ ${\displaystyle A(P_{k},Q,P_{k+1})}$

Пример:

${\displaystyle P_{1}=(3,1),P_{2}=(7,2),P_{3}=(4,4),}$

${\displaystyle P_{4}=(8,6),P_{5}=(1,7),\ Q=(4,3)}$

Манипуляции с многоугольником

С помощью приведенной выше записи схемы шнуровки получаем для ориентированной области

• синий многоугольник: $${\displaystyle A(P_{1},P_{2},P_{3},P_{4},P_{5})={\tfrac {1}{2}}{\begin{vmatrix}3&7&4&8&1&3\\1&2&4&6&7&1\end{vmatrix}}=20.5}$$
• зеленый треугольник: $${\displaystyle A(P_{2},P_{3},P_{4})={\tfrac {1}{2}}{\begin{vmatrix}7&4&8&7\\2&4&6&2\end{vmatrix}}=-7}$$
• красный треугольник: $${\displaystyle A(P_{1},Q,P_{2})={\tfrac {1}{2}}{\begin{vmatrix}3&4&7&3\\1&3&2&1\end{vmatrix}}=-3.5}$$
• синий многоугольник минус точка : ${\displaystyle P_{3}}$ $${\displaystyle A(P_{1},P_{2},P_{4},P_{5})={\tfrac {1}{2}}{\begin{vmatrix}3&7&8&1&3\\1&2&6&7&1\end{vmatrix}}=27.5}$$
• синий многоугольник плюс точка между : ${\displaystyle Q}$ ${\displaystyle P_{1},P_{2}}$ $${\displaystyle A(P_{1},Q,P_{2},P_{3},P_{4},P_{5})={\tfrac {1}{2}}{\begin{vmatrix}3&4&7&4&8&1&3\\1&3&2&4&6&7&1\end{vmatrix}}=17}$$

Проверяется, что выполняются следующие уравнения: $${\displaystyle A(P_{1},P_{2},P_{3},P_{4},P_{5})=A(P_{1},P_{2},P_{4},P_{5})+A(P_{2},P_{3},P_{4})=20.5}$$ $${\displaystyle A(P_{1},P_{2},P_{3},P_{4},P_{5})+A(P_{1},Q,P_{2})=A(P_{1},Q,P_{2},P_{3},P_{4},P_{5})=17}$$

Обобщение

В более высоких измерениях площадь многоугольника можно вычислить по его вершинам, используя внешнюю алгебраическую форму формулы Шнурка (например, в 3D, сумму последовательных векторных произведений ): (когда вершины не лежат в одной плоскости, вычисляется векторная площадь, заключенная в петле, т.е. проецируемая площадь или «тень» в плоскости, в которой она наибольшая). $${\displaystyle A={\frac {1}{2}}\left\|\sum _{i=1}^{n}v_{i}\wedge v_{i+1}\right\|}$$

Эту формулировку можно также обобщить для вычисления объема n-мерного многогранника из координат его вершин или, точнее, из его гиперповерхностной сетки. ^[10] Например, объем трехмерного многогранника можно найти путем триангуляции его поверхностной сетки и суммирования знаковых объемов тетраэдров , образованных каждым поверхностным треугольником и началом координат: где сумма берется по граням, и необходимо позаботиться о том, чтобы вершины были упорядочены последовательно (все по часовой стрелке или против часовой стрелки, если смотреть снаружи многогранника). В качестве альтернативы выражение в терминах площадей граней и нормалей поверхности можно вывести с помощью теоремы о расходимости (см. Polyhedron § Volume ). $${\displaystyle V={\frac {1}{6}}\left\|\sum _{F}v_{a}\wedge v_{b}\wedge v_{c}\right\|}$$

Смотрите также

• Планиметр
• Площадь полигона
• Теорема Пика
• Формула Герона

Внешние ссылки

• Видео Mathologer о формуле шнурования Гаусса

Ссылки

1. Барт Брейден (1986). «Формула площади геодезиста» (PDF) . The College Mathematics Journal . 17 (4): 326–337. doi :10.2307/2686282. JSTOR  2686282. Архивировано из оригинала (PDF) 29 июня 2014 г.
2. Dahlke, Karl. "Формула шнурка" . Получено 9 июня 2008 г.
3. Ханс Претч, Динамика, рост и урожайность леса: от измерения к моделированию , Springer, 2009, ISBN 3-540-88306-1 , стр. 232. 
4. Мейстер, ALF (1769), "Generalia de Genesi figurarum planarum et inde pendentibus Earum Faffibus", Nov. Com. Гетт. (на латыни), 1 : 144.
5. Макс Кехер, Алоис Криг: Ebene Geometrie , Springer-Verlag, 2013, ISBN 3662068095, 9783662068090, стр. 116
6. PW Shor; CJ Van Wyk (1992), «Обнаружение и разложение самоперекрывающихся кривых», Comput. Geom. Theory Appl. , 2 (1): 31–50, doi : 10.1016/0925-7721(92)90019-O
7. Ральф П. Боланд; Хорхе Уррутиа (2000). Задачи о площади многоугольника . 12-я Канадская конференция по вычислительной геометрии. С. 159–162.
8. Антти Лааксонен: Руководство по конкурентному программированию: изучение и совершенствование алгоритмов с помощью соревнований , Springer, 2018, ISBN 3319725475, 9783319725475, стр. 217
9. Маурен Абреу де Соуза, Умберто Ремихио Гамба, Элио Педрини: Мультимодальная визуализация: приложения и вычислительные методы , Springer, 2018, ISBN 331998974X, 9783319989747, стр. 229
10. Allgower, Eugene L.; Schmidt, Phillip H. (1986). "Вычисление объемов многогранников" (PDF) . Mathematics of Computation . 46 (173): 171–174. doi : 10.2307/2008221 . ISSN  0025-5718. JSTOR  2008221.