Формула шнурков - Shoelace formula

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

Формула была описана Мейстером (1724–1788) в 1769 году.^[4] и по Гаусс в 1795 г.^{[требуется полная цитата ]} Это можно проверить, разделив многоугольник на треугольники, и его можно рассматривать как частный случай Теорема Грина.

Формула площади получается путем взятия каждого края AB, и вычисляя площадь треугольника ABO с вершиной в начале координат О, взяв перекрестное произведение (которое дает площадь параллелограмма) и разделив его на 2. При обтекании многоугольника эти треугольники с положительной и отрицательной площадью будут перекрываться, а области между исходной точкой и многоугольником будут аннулированы. out и суммировать до 0, при этом остается только область внутри ссылочного треугольника. Вот почему формула называется формулой геодезиста, поскольку «геодезист» стоит в начале координат; при движении против часовой стрелки положительная область добавляется при движении слева направо и отрицательная область добавляется при движении справа налево с точки зрения исходной точки.^{[нужна цитата ]}

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

Заявление

Формулу можно представить выражением

${displaystyle {egin{aligned}mathbf {A} &={1 over 2}left|sum _{i=1}^{n-1}x_{i}y_{i+1}+x_{n}y_{1}-sum _{i=1}^{n-1}x_{i+1}y_{i}-x_{1}y_{n}ight|[4pt]&={1 over 2}|x_{1}y_{2}+x_{2}y_{3}+cdots +x_{n-1}y_{n}+x_{n}y_{1}-x_{2}y_{1}-x_{3}y_{2}-cdots -x_{n}y_{n-1}-x_{1}y_{n}|end{aligned}}}$

куда

• А площадь многоугольника,
• п - количество сторон многоугольника, а
• (Икс_я, у_я), я = 1, 2,..., п упорядоченные вершины (или «углы») многоугольника.

Альтернативно^[3][7][8]

${displaystyle {egin{aligned}mathbf {A} &={1 over 2}left|sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})ight|={1 over 2}left|sum _{i=1}^{n}y_{i}(x_{i+1}-x_{i-1})ight|={1 over 2}left|sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})ight|[5pt]&={1 over 2}left|sum _{i=1}^{n}(x_{i+1}+x_{i})(y_{i+1}-y_{i})ight|={1 over 2}left|sum _{i=1}^{n}det {egin{pmatrix}x_{i}&x_{i+1}y_{i}&y_{i+1}end{pmatrix}}ight|end{aligned}}}$

кудаИкс_п+1 = Икс₁ и Икс₀ = Икс_п,а такжеу_п+1 = у₁ и у₀ = у_п.

Если точки помечены последовательно против часовой стрелки, то сумма указанных выше детерминанты положительно, и знаки абсолютного значения можно опустить;^[1] если они помечены по часовой стрелке, сумма определителей будет отрицательной. Это потому, что формулу можно рассматривать как частный случай Теорема Грина.

Особенно краткое изложение формулы можно дать в терминах внешняя алгебра. Если ${displaystyle v_{1},dots ,v_{n}}$ - последовательные вершины многоугольника (рассматриваемые как векторы в декартовой плоскости), то

${displaystyle A={frac {1}{2}}cdot left|sum _{i=1}^{n}v_{i}wedge v_{i+1}ight|.}$

Доказательства

Доказательство треугольника

Зная координаты треугольника, найдите его площадь ${displaystyle mathbf {A} }$.

Ссылаясь на рисунок, пусть ${displaystyle mathbf {A} }$ - площадь треугольника, вершины которого задаются координатами ${displaystyle (x_{1},y_{1}),(x_{2},y_{2}),}$ и ${displaystyle (x_{3},y_{3}).}$ Нарисуйте прямоугольник с минимальной площадью вокруг треугольника так, чтобы его стороны были параллельны ${displaystyle x}$ или же ${displaystyle y}$ топоры. По крайней мере, одна вершина треугольника будет в углу прямоугольника. На рисунке площади трех окружающих треугольников равны ${displaystyle mathbf {C} ,mathbf {D} ,}$ и ${displaystyle mathbf {E} .}$ Очевидно ${displaystyle mathbf {A} }$ равна площади прямоугольника (назовем его ${displaystyle mathbf {R} }$) минус площади остальных трех треугольников. Уравнение, описывающее эту взаимосвязь:

${displaystyle mathbf {A} =mathbf {R} -mathbf {C} -mathbf {D} -mathbf {E} }$

При осмотре рисунка видно, что площади даны как

${displaystyle mathbf {R} =(x_{3}-x_{2})(y_{1}-y_{3})=(x_{3}y_{1}+x_{2}y_{3})-(x_{3}y_{3}+x_{2}y_{1})}$

${displaystyle -mathbf {C} =-{frac {1}{2}}(x_{3}-x_{2})(y_{2}-y_{3})={frac {1}{2}}(-x_{3}y_{2}-x_{2}y_{3})+{frac {1}{2}}(x_{3}y_{3}+x_{2}y_{2})}$

${displaystyle -mathbf {D} =-{frac {1}{2}}(x_{3}-x_{1})(y_{1}-y_{3})={frac {1}{2}}(-x_{3}y_{1}-x_{1}y_{3})+{frac {1}{2}}(x_{3}y_{3}+x_{1}y_{1})}$

${displaystyle -mathbf {E} =-{frac {1}{2}}(x_{1}-x_{2})(y_{1}-y_{2})={frac {1}{2}}(-x_{1}y_{1}-x_{2}y_{2})+{frac {1}{2}}(x_{1}y_{2}+x_{2}y_{1})}$

Сбор сроков и перестановка урожаев

${displaystyle mathbf {A} ={frac {1}{2}}((x_{2}y_{3}-x_{3}y_{2})-(x_{1}y_{3}-x_{3}y_{1})+(x_{1}y_{2}-x_{2}y_{1}))}$

который можно записать как определитель

${displaystyle mathbf {A} ={frac {1}{2}}{egin{vmatrix}1&1&1x_{1}&x_{2}&x_{3}y_{1}&y_{2}&y_{3}end{vmatrix}}}$

Если координаты записывать по часовой стрелке, то значение определителя будет ${displaystyle -mathbf {A} .}$

Переставляем по-другому

${displaystyle mathbf {A} ={frac {1}{2}}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3}|}$

которая является формой формулы шнурка. Эту формулу можно расширить, чтобы найти площадь любого многоугольника, поскольку простой многоугольник можно разделить на треугольники.

По координатам четырехугольника найдите его площадь ${displaystyle mathbf {A} _{ ext{quad.}}}$.

Доказательство для четырехугольника и общего многоугольника

Нахождение площади четырехугольника демонстрирует, как формула шнурков обобщается на любой многоугольник путем деления многоугольника на треугольники. Рассмотрим фигуру четырехугольника, координаты которого отмечены в порядке против часовой стрелки. Четырехугольник разделен на два треугольника с площадями ${displaystyle mathbf {A} }$ и ${displaystyle mathbf {B} .}$ Используя формулу треугольника для каждого треугольника, мы получаем

${displaystyle mathbf {A} ={frac {1}{2}}(x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3})}$

${displaystyle mathbf {B} ={frac {1}{2}}(x_{1}y_{3}+x_{3}y_{4}+x_{4}y_{1}-x_{3}y_{1}-x_{4}y_{3}-x_{1}y_{4})}$

Поскольку оба треугольника были начерчены против часовой стрелки, обе области положительны, и мы получаем площадь четырехугольника, складывая две области. Последний положительный член и последний отрицательный член ${displaystyle mathbf {A} }$ отменить с первым положительным членом и первым отрицательным членом ${displaystyle mathbf {B} }$ давая

${displaystyle mathbf {A} _{ ext{quad.}}={frac {1}{2}}(x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{4}+x_{4}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{4}y_{3}-x_{1}y_{4})}$

Примеры

Пользователь должен знать точки многоугольника на декартовой плоскости. Например, возьмите треугольник с координатами {(2, 1), (4, 5), (7, 8)}. Возьми первый Икс-координируйте и умножьте на секунду у-значение, затем возьмем второе Икс-координируйте и умножьте на треть у-значение, и повторите столько раз, пока это не будет сделано для всех требуемых очков. Это можно определить по следующей формуле:^[9]

${displaystyle mathbf {A} _{ ext{tri.}}={1 over 2}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{1}y_{3}|}$

за Икс_я и у_я представляющий каждую соответствующую координату. Эта формула является просто расширением приведенных выше для случая n = 3. Используя ее, можно найти, что площадь треугольника равна половине абсолютная величина из 10 + 32 + 7 - 4 - 35 - 16, что равно 3. Количество переменных зависит от количества сторон многоугольник. Например, пятиугольник будет определено до Икс₅ и у₅:

${displaystyle mathbf {A} _{ ext{pent.}}={1 over 2}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{4}+x_{4}y_{5}+x_{5}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{4}y_{3}-x_{5}y_{4}-x_{1}y_{5}|}$

А четырехугольник будет определено до Икс₄ и у₄:

${displaystyle mathbf {A} _{ ext{quad.}}={1 over 2}|x_{1}y_{2}+x_{2}y_{3}+x_{3}y_{4}+x_{4}y_{1}-x_{2}y_{1}-x_{3}y_{2}-x_{4}y_{3}-x_{1}y_{4}|}$

Более сложный пример

Рассмотрим многоугольник, определяемый точками (3,4), (5,11), (12,8), (9,5) и (5,6), который показан на следующей диаграмме:

Рисунок этого примера

Площадь этого многоугольника:

${displaystyle {egin{aligned}mathbf {A} &={1 over 2},{ig |}3 imes 11+5 imes 8+12 imes 5+9 imes 6+5 imes 4&{}qquad {}-4 imes 5-11 imes 12-8 imes 9-5 imes 5-6 imes 3{ig |}[10pt]&={60 over 2}=30end{aligned}}}$

Этимология

Причина, по которой эта формула называется формулой шнурка, заключается в том, что для ее оценки используется общий метод. Этот метод использует матрицы. В качестве примера выберите треугольник с вершинами (2,4), (3, −8) и (1,2). Затем постройте следующую матрицу, «обойдя» треугольник и закончив его начальной точкой.^[10]

${displaystyle {egin{bmatrix}2&43&-81&22&4end{bmatrix}}}$

Сначала проведите диагональ вниз и вправо косой чертой (как показано ниже),

  

и умножьте два числа, соединенных каждой косой чертой, затем сложите все произведения: (2 × −8) + (3 × 2) + (1 × 4) = −6. Сделайте то же самое с косой чертой по диагонали вниз и влево (показано ниже с косой чертой вниз):

  

(4 × 3) + (−8 × 1) + (2 × 2) = 8. Затем возьмите разность этих двух чисел: | (−6) - (8) | = 14. Уменьшение вдвое дает площадь треугольника: 7. Такая организация чисел упрощает вспоминание и оценку формулы. Матрица со всеми прорисованными косыми чертами напоминает туфлю с натянутыми шнурками, что дает название алгоритму.

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

• Планиметр
• Теорема Пика
• Формула Герона

внешняя ссылка

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

Рекомендации

1. Барт Брейден (1986). "Формула площади геодезиста" (PDF). Математический журнал колледжа. 17 (4): 326–337. Дои:10.2307/2686282. JSTOR  2686282.
2. Дальке, Карл. «Формула шнурков». Получено 9 июн 2008.
3. Ганс Преч, Динамика, прирост и урожайность леса: от измерения к модели, Springer, 2009, ISBN  3-540-88306-1, п. 232.
4. Мейстер, А. Л. Ф. (1769), "Generalia de genesi figurarum planarum et inde pendentibus earumffectionibus", Nov. Com. Gött. (на латыни), 1: 144.
5. П.В. Шор; C.J. Ван Вик (1992), "Обнаружение и разложение самоперекрывающихся кривых", Comput. Геом. Теория Appl., 2 (1): 31–50, Дои:10.1016 / 0925-7721 (92) 90019-О
6. Ральф П. Боланд; Хорхе Уррутия (2000). Проблемы с полигональной областью. 12-я Канадская конференция по вычислительной геометрии. С. 159–162.
7. Теорема шнурка, Искусство решения проблем вики.
8. Вайсштейн, Эрик В.. «Площадь полигона». Вольфрам MathWorld. Получено 24 июля 2012.
9. Ричард Роад; Георгий Милаускас; Роберт Уиппл (1991). Геометрия для удовольствия и вызова (новое изд.). Макдугал Литтел. стр.717–718. ISBN  0-86609-965-4.
10. Руководство IMSA JHMC, стр. 10 "Шнурки" Синди Си