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

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

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

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

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

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

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

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

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

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

Формула трапеции суммирует последовательность ориентированных площадей $A_{i}={\tfrac {1}{2}}(y_{i}+y_{i+1})(x_{i}-x_{i+1})$ трапеций с $P_{i}P_{i+1}$ как одно из четырех его ребер (см. ниже): ${\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}}$

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

Формула треугольника суммирует ориентированные площади $A_{i}$ треугольников $OP_{i}P_{i+1}$ : ^[9] ${\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 вручную: ${\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}}$

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

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

${\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}}$ $A={\frac {1}{2}}\sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})$

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

Пример

Для площади пятиугольника с ${\begin{aligned}&P_{1}=(1,6),P_{2}=(3,1),P_{3}=(7,2),\\&P_{4}=(4,4),P_{5}=(8,5)\end{aligned}}$ каждый получает ${\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 столбцов.

Вывод формул

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

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

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

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

Форма треугольника, определяющая форма

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

Убираем скобки и используем ${\textstyle \sum _{i=1}^{n}x_{i}y_{i}=\sum _{i=1}^{n}x_{i+1}y_{i+1}}$ (см. конвенцию $P_{n+1}=P_{1}$ выше), получаем детерминантную форму формулы площади: $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}}$ Поскольку половина i-го определителя — это ориентированная площадь треугольника $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}\ }$ (см. конвенцию $P_{0}=P_{n},P_{n+1}=P_{1}$ выше) получается $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}$ Объединив обе суммы и исключив $y_{i}$ приводит к $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}}$ каждый получает $A={\frac {1}{2}}\sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})$

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

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

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

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

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

Пример:

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

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

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

синий многоугольник: $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$
зеленый треугольник: $A(P_{2},P_{3},P_{4})={\tfrac {1}{2}}{\begin{vmatrix}7&4&8&7\\2&4&6&2\end{vmatrix}}=-7$
красный треугольник: $A(P_{1},Q,P_{2})={\tfrac {1}{2}}{\begin{vmatrix}3&4&7&3\\1&3&2&1\end{vmatrix}}=-3.5$
Синий многоугольник минус точка $P_{3}$ : $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$
синий многоугольник плюс точка $Q$ между $P_{1},P_{2}$ : $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$

Проверяют, что выполняются следующие уравнения: $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$ $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, сумму последовательных векторных произведений ): $A={\frac {1}{2}}\left\|\sum _{i=1}^{n}v_{i}\wedge v_{i+1}\right\|$ (когда вершины не копланарны, вычисляется векторная площадь, заключенная в цикле, т.е. проецируемая область или «тень» в той плоскости, в которой она наибольшая).

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

См. также

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

Видео матолога о формуле шнурков Гаусса

Ссылки

^ Барт Брейден (1986). «Формула площади геодезиста» (PDF) . Математический журнал колледжа . 17 (4): 326–337. дои : 10.2307/2686282 . JSTOR 2686282 . Архивировано из оригинала (PDF) 29 июня 2014 года.
↑ Перейти обратно: Перейти обратно: ^а ^б Дальке, Карл. «Формула шнурков» . Проверено 9 июня 2008 г.
^ Ханс Преч, Динамика леса, рост и урожайность: от измерения к модели , Springer, 2009, ISBN 3-540-88306-1 , с. 232.
^ Мейстер, Альф (1769), «Общие сведения о происхождении плоских фигур и их последующих проявлениях» , ноябрь. Ком. Гетт. (на латыни), 1 :144 .
^ Макс Кехер, Алоис Криг: Плоская геометрия , Springer-Verlag, 2013, ISBN 3662068095, 9783662068090, стр. 116
^ П.В. Шор; CJ Ван Вик (1992), «Обнаружение и разложение самоперекрывающихся кривых», Comput. Геом. Теория Прикл. , 2 (1): 31–50, doi : 10.1016/0925-7721(92)90019-О
^ Ральф П. Боланд; Хорхе Уррутиа (2000). Задачи о полигонах . 12-я Канадская конференция по вычислительной геометрии. стр. 159–162.
^ Антти Лааксонен: Руководство по соревновательному программированию: изучение и улучшение алгоритмов посредством соревнований , Springer, 2018, ISBN 3319725475, 9783319725475, стр. 217
^ Маурен Абреу де Соуза, Умберто Ремиджио Гамба, Хелио Педрини: Мультимодальная визуализация: приложения и вычислительные методы , Springer, 2018, ISBN 331998974X, 9783319989747, стр. 229
^ Аллгоуэр, Юджин Л.; Шмидт, Филип Х. (1986). «Вычисление объемов многогранников» (PDF) . Математика вычислений . 46 (173): 171–174. дои : 10.2307/2008221 . ISSN 0025-5718 . JSTOR 2008221 .

[Braden-1] Барт Брейден (1986). «Формула площади геодезиста» (PDF) . Математический журнал колледжа . 17 (4): 326–337. дои : 10.2307/2686282 . JSTOR 2686282 . Архивировано из оригинала (PDF) 29 июня 2014 года.

[mathreference-2] Перейти обратно: Перейти обратно: ^а ^б Дальке, Карл. «Формула шнурков» . Проверено 9 июня 2008 г.

[Pretzsch-3] Ханс Преч, Динамика леса, рост и урожайность: от измерения к модели , Springer, 2009, ISBN 3-540-88306-1 , с. 232.

[4] Мейстер, Альф (1769), «Общие сведения о происхождении плоских фигур и их последующих проявлениях» , ноябрь. Ком. Гетт. (на латыни), 1 :144 .

[5] Макс Кехер, Алоис Криг: Плоская геометрия , Springer-Verlag, 2013, ISBN 3662068095, 9783662068090, стр. 116

[6] П.В. Шор; CJ Ван Вик (1992), «Обнаружение и разложение самоперекрывающихся кривых», Comput. Геом. Теория Прикл. , 2 (1): 31–50, doi : 10.1016/0925-7721(92)90019-О

[7] Ральф П. Боланд; Хорхе Уррутиа (2000). Задачи о полигонах . 12-я Канадская конференция по вычислительной геометрии. стр. 159–162.

[8] Антти Лааксонен: Руководство по соревновательному программированию: изучение и улучшение алгоритмов посредством соревнований , Springer, 2018, ISBN 3319725475, 9783319725475, стр. 217

[9] Маурен Абреу де Соуза, Умберто Ремиджио Гамба, Хелио Педрини: Мультимодальная визуализация: приложения и вычислительные методы , Springer, 2018, ISBN 331998974X, 9783319989747, стр. 229

[10] Аллгоуэр, Юджин Л.; Шмидт, Филип Х. (1986). «Вычисление объемов многогранников» (PDF) . Математика вычислений . 46 (173): 171–174. дои : 10.2307/2008221 . ISSN 0025-5718 . JSTOR 2008221 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]