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

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

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

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

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

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

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

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

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

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

Формула трапеции суммирует последовательность ориентированных площадей $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}$:

$${\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$ сначала следует сдвинуть индексы.

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

1. Движущийся $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}}}$.
2. Очистка $P_{k}$ изменяет общую площадь на $A(P_{k-1},P_{k},P_{k+1})$, который может быть положительным или отрицательным.
3. Вставка точки $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-мерного многогранника по координатам его вершин или, точнее, по его гиперповерхностей . сетке Например, объем трехмерного многогранника можно найти путем триангуляции его поверхностной сетки и суммирования подписанных объемов тетраэдров , образованных каждым поверхностным треугольником и началом координат:

$$V={\frac {1}{6}}\left\|\sum _{F}v_{a}\wedge v_{b}\wedge v_{c}\right\|$$

где сумма ведется по граням, и необходимо позаботиться о том, чтобы вершины были упорядочены последовательно (все по часовой стрелке или против часовой стрелки, если смотреть снаружи многогранника). В качестве альтернативы выражение через площади граней и нормали к поверхности можно получить с помощью теоремы о дивергенции (см. Многогранник § Том ).

См. также

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

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

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