Как найти площадь многоугольника по координатам вершин

Вычисление площади выпуклого многоугольника по координатам вершин на плоскости

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

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

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

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

Пятиугольник

должен уже получиться многоугольник ADCBE, а не ABCDE, разбитый на треугольники ADC, ACB и ABE, соответственно.

Чтобы получить правильный многоугольник, фактически требуется получить оболочку введенных точек. Для этого калькулятор использует алгоритм Джарвиса (или алгоритм обхода Джарвиса, или алгоритм заворачивания подарка), который определяет последовательность элементов множества, образующих выпуклую оболочку для этого множества. Метод можно представить как обтягивание верёвкой множества вбитых в доску гвоздей.

Алгоритм работает за время , где n — общее число точек на плоскости, h — число точек в выпуклой оболочке. Для выпуклого многоугольник соответственно будет . Не самый оптимальный алгоритм, зато очень простой, и для этого калькулятора вполне производительный.

Как пользоваться калькулятором: начинаете вводить координаты точек выпуклого многоугольника. Начиная с трех точек алгоритм Джарвиса будет стоить обтягивающий контур, затем контур будет разбиваться треугольники и подсчитываться общая площадь. Для справки также будут выводиться площади всех треугольников.

Как найти площадь многоугольника по координатам вершин

Отрезок, для которого указано, какой из его концов считается началом, а какой — концом, называется вектором. Любая точка пространства также может рассматриваться как вектор. Такой вектор называется нулевым. Начало и конец нулевого вектора совпадают, и он не имеет какого-либо определенного направления.

Скалярное произведение векторов — это число, равное произведению длин этих векторов на косинус угла между ними.
(a, b) = |a||b|cos∠(a, b)

Если векторы заданы своими координатами a(x₁, y₁), b(x₂, y₂) то скалярное произведение (a, b) = x₁x₂ + y₁y₂.

Псевдоскалярным или косым произведением векторов на плоскости называется число
[a, b] = |a||b|sinθ
где — угол вращения (против часовой стрелки) от a к b. Если хотя бы один из векторов a и b нулевой, то полагают [a, b] = 0.
Если векторы заданы своими координатами a(x₁, y₁), b(x₂, y₂) то косое произведение [a, b] = x₁y₂ — x₂y₁.
Геометрически косое произведение векторов представляет собой ориентированную площадь параллелограмма, натянутого на эти вектора.

Начнем с треугольников

Решение
С первого взгляда решение кажется очевидным: вычислить стороны треугольника и свести задачу к предыдущей. Однако поскольку расстояние между двумя точками A(x₁, y₁), B(x₂, y₂) вычисляется по формуле √(x₁-x₂) 2 +(y₁-y₂) 2 то при извлечении корня возможна потеря точности, что плохо скажется на проверке неравенства треугольника. Оказывается, что если треугольник задан координатами своих вершин, то вычислять длины его сторон и проверять неравенство треугольника не требуется. В этом случае треугольника не существует тогда и только тогда, когда данные три точки лежат на одной прямой. А это легко проверяется через косое произведение векторов. Если оно равно нулю, то векторы коллинеарные, то есть все три точки лежат на одной прямой.

1. Угол больше 90° – треугольник тупоугольный
2. Угол меньше 90°– треугольник остроугольный
3. Угол равен 90°– треугольник прямоугольный

• Если cosα > 0, то a 2 < b 2 + c 2 – треугольник остроугольный
• Если cosα = 0, то a 2 = b 2 + c 2 – треугольник прямоугольный
• Если cosα < 0, то a 2 > b 2 + c 2 – треугольник тупоугольный

Решение
Очевидно решение, заключается в применение формулы Герона.

Кстати, никого не интересовало доказательство этой формулы?

Вот и все!

Решение
Не будем говорить о решении, которое сводится к предыдущей задачи, а попробуем воспользоваться геометрическим смыслом косового произведения. Геометрически косое произведение двух векторов определяет ориентированную площадь параллелограмма натянутого на эти вектора. Поскольку диагональ параллелограмма разбивает его на два равновеликих треугольника, то можем найти площадь нашего треугольника, как половину площади параллелограмма.
Для векторов a(x₁, y₁), b(x₂, y₂)

S = (x₁y₂ — x₂y₁) / 2 — ориентированная площадь треугольника

Если сумма площадей треугольников AKB, AKC, BKC (не ориентированных, а «обычных») больше площади треугольника ABC точка лежит вне треугольника. Если же сумма первых трех площадей равна четвертой, то нужно проверить, не равна ли нулю одна из трех площадей. Если равна, то точка лежит на границе треугольника, иначе – внутри.
Вычислять площади треугольников, естественно, надо через косое произведение векторов. Этот метод не очень хороший. Поскольку здесь используются сравнение чисел с плавающей точкой, а это в свою очередь может привести к принятию неверного решения при сравнении. Второй метод опять таки опирается на вектора, он намного эффективнее во всех отношениях.

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

В первом примере сторона AB разводит вершину C и точку K по разным полуплоскостям, поэтому точка лежит снаружи.

Для того чтобы посчитать площадь многоугольника нужно разбить его на трапеции, так как это показано на рисунке, а затем сложить ориентированные площади полученных трапеций это будет ориентированной площадью исходного многоугольника.
S = S_A1A2B2B1 + S_A2A3B3B2 + S_A3A4B5B3 + S_A4A5B6B5 + S_A5A6B4B6 + S_A6A1B1B4
Площади трапеций считаем по известной формуле: полусумма оснований на высоту
S_A1A2B2B1 = 0.5 * (A₁B₁ + A₂B₂) *(B₂ — B₁)

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

Решение
Для решения этой задачи рассмотрим вспомогательную задачу: отрезок задан координатами своих концов, являющихся целыми числами. Необходимо посчитать количество целочисленных точек лежащих на отрезке. Понятно, что если отрезок вертикальный или горизонтальный, то необходимо вычесть координаты концов и добавить единицу. Интерес представляет случай, когда отрезок не является вертикальным или горизонтальным. Оказывается в этом случае необходимо достроить отрезок до прямоугольного треугольника и ответом будет число равное наибольшему общему делителю длин катетов этого треугольника плюс единица.

Для любого многоугольника с целочисленными координатами вершин справедлива формула Пика: S = n + m/2 — 1, где S – площадь многоугольника, n – количество целых точек лежащих строго внутри многоугольника, m – количество целых точек лежащих на границе многоугольника. Поскольку площадь многоугольника мы знаем как вычислять, то S известно. Так же мы можем вычислить количество целых точек лежащих на границе многоугольника, поэтому в формуле Пика остается лишь одна искомая неизвестная которую мы можем найти.
Рассмотрим пример:

S = 16 + 4 + 4,5 + 6 + 1 + 2 = 33,5
m = 15
n = 33,5 – 7,5 +1 = 27 — точек лежит строго внутри многоугольника
Вот так вот решается эта задачка!

Площадь многоугольника по координатам онлайн

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

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

Такой метод позволяет рассчитывать не только выпусклые многоугольники, но и любые другие, главное, что бы линии этого многоугольника не пересекались.

Кроме этого стоит обратить внимание на такие материалы как: Касательная к кривой второго порядка

Координаты вершин задаются в общей строке вида x1:y1 x2:y2 x3:y3 . xn:yn

Координаты вершин являются действительные числа.

Координата каждой точки (абсцисса и ордината) записывается через двоеточие(без пробелов!)

Координаты вершин вводятся ПОСЛЕДОВАТЕЛЬНО по часовой или(!) против часовой стрелки.

Формула площади Гаусса

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

Формула была описана Мейстером (1724—1788) в 1769 году и Гауссом в 1795 году. Она может быть проверена путём деления многоугольника на треугольники, но её также можно рассматривать как частный случай теоремы Грина.

Формула определения площади определяется путём взятия каждого ребра многоугольника АВ и вычисления площади треугольника АВО с вершиной в начале координат О через координаты вершин. При обходе вокруг многоугольника образуются треугольники, включающие внутреннюю часть многоугольника и расположенные снаружи его. Разница между суммой этих площадей и есть площадь самого многоугольника. Поэтому формула называется формулой геодезиста, так как «картограф» находится в начале координат; если он обходит участок против часовой стрелки, площадь добавляется, если она слева, и вычитается, если она справа с точки зрения из начала координат.

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

Содержание

Определение

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

[math]\displaystyle < \begin\mathbf &= \frac<1> <2>\left| \sum_^ x_i y_ + x_n y_1 — \sum_^ x_ y_i — x_1 y_n \right| = \\ &= \frac<1> <2>|x_1 y_2 + x_2 y_3 + \dots + x_ y_n + x_n y_1 — x_2 y_1 — x_3 y_2 — \dots — x_n y_ — x_1 y_n|, \end >[/math]

S — площадь многоугольника, n — количество сторон многоугольника, (x_i, y_i), i = 1, 2, …, n — координаты вершин многоугольника.

Другое представление этой же формулы [1] [2] :

[math]\displaystyle < \begin\mathbf &= \frac<1> <2>\left| \sum_^ x_i(y_ — y_) \right| = \\ &= \frac<1> <2>\left| \sum_^n y_i(x_ — x_) \right| = \\ &= \frac<1> <2>\left| \sum_^n x_i y_ — x_ y_i \right| = \\ &= \frac<1> <2>\left| \sum_^n \det \begin x_i & y_i \\ x_ & y_ \end \right|, \end >[/math]

Если точки пронумерованы последовательно в направлении против часовой стрелки, то детерминанты в формуле выше положительны, и модуль в ней может быть опущен; если они пронумерованы в направлении по часовой стрелке, то детерминанты будут отрицательными. Это происходит потому, что формула может рассматриваться как частный случай теоремы Грина.

Примеры

Для применения формулы необходимо знать координаты вершин многоугольника в декартовой плоскости. Для примера возьмём треугольник с координатами <(2, 1), (4, 5), (7, 8)>. Возьмём первую координату x первой вершины и умножим её на координату y второй вершины, а затем умножим х второй вершины на y третьей. Повторим эту процедуру для всех вершин. Результат может быть определён по следующей формуле [3] :

[math]\displaystyle< \mathbf_\text = \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|, >[/math]

где x_i и y_i обозначают соответствующую координату. Эту формулу можно получить, раскрыв скобки в общей формуле для случая n = 3. По этой формуле можно обнаружить, что площадь треугольника равна половине суммы 10 + 32 + 7 − 4 − 35 − 16, что даёт 3.

Число переменных в формуле зависит от числа сторон многоугольника. Например, в формуле для площади пятиугольника будут использоваться переменные до x₅ и y₅:

[math]\displaystyle< \mathbf_\text = \frac<1> <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|. >[/math]

[math]\displaystyle< \mathbf_\text = \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|. >[/math]

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

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

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

[math]\displaystyle < \begin\mathbf &= \frac<1> <2>|3 \times 11 + 5 \times 8 + 12 \times 5 + 9 \times 6 + 5 \times 4 — <> \\ &\qquad — 4 \times 5 — 11 \times 12 — 8 \times 9 — 5 \times 5 — 6 \times 3| = \\ &= \frac<60> <2>= 30. \end >[/math]

Объяснение названия

Формула называется «формулой шнурков» из-за общего метода, используемого для её вычисления. Этот метод использует матрицу. В качестве примера возьмём треугольник с вершинами (2, 4), (3, −8), (1, 2). Затем построим следующую матрицу, «обходя вокруг» треугольника и заканчивая начальной точкой:

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

и перемножим пары чисел, соединённых чертой, а затем сложим все суммы:

Сделаем то же самое, проводя косую черту по диагонали вниз и влево, как показано ниже:

Затем вычтем сумму второй группы из первой и возьмём модуль:

Деление результата на два даёт площадь. Организация чисел в матрицу с диагональными линиями упрощает запоминание формулы. В результате проделанной операции с рисованием диагональных (косых) линий матрица с числами напоминает зашнурованную обувь, отсюда и происходит название «алгоритма шнурования».

Хорошее описание «Шнуровки Гаусса» представлено в видео на канале Wild Mathing [1]

Похожие публикации:

1. No newline at end of file python как исправить
2. Nvidia продолжить установку невозможно как исправить
3. Как ограничить количество знаков после запятой в c double
4. Как сделать курсор мыши плавнее