Форум на Исходниках.RU

Нахождение площади многоугольника

Mikle — Wed, 14 Dec 2022 14:28:17 +0000

Mikle:

Цитата Profi @ 14.12.22, 13:15

все методы работают только для отсортированного списка вершин

Так без сортировки выходит неоднозначно, ответы разные.

Цитата Profi @ 14.12.22, 13:15

все же подход разный

Я ж написал, что "практически к тому же". Не совсем, да.

Нахождение площади многоугольника

Profi — Wed, 14 Dec 2022 13:15:42 +0000

Profi: Можно даже избавиться от надоедливого if:

public static double Shoelace(IList<Point> points)

{

var redundantPoints = points.Concat(new [] {points[0]}).ToList();

var sum = 0;

for (int i = 0; i < redundantPoints.Count - 1; i++)

{

var firstPoint = redundantPoints[i];

var secondPoint = redundantPoints[i + 1];

sum += firstPoint.X*secondPoint.Y - firstPoint.Y*secondPoint.X;

}

return Math.Abs(sum)/2.0;

}

Добавлено 14.12.22, 13:17

Цитата OpenGL @ 14.12.22, 13:14

Цитата Profi @ 14.12.22, 12:56

Парни, а как же формула Гаусса?

Это то, что я векторным произведением назвал.

Ну, она из него вытекает, да. Просто не видел кода, думал никто и не предложил.

Добавлено 14.12.22, 13:18

Цитата Mikle @ 14.12.22, 13:15

Цитата Profi @ 14.12.22, 12:56

а как же формула Гаусса?

Трапеции сводятся практически к тому же. Строка из моего поста с прошлой страницы:

s = s + (V(i1).y - V(i).y) * (V(i1).x + V(i).x)

Ну, как бы нет. Сложность такая же, но все же подход разный.

Добавлено 14.12.22, 13:20
Кстати, все методы работают только для отсортированного списка вершин. Но накидать сортировку по центроиду - не сложно.

Нахождение площади многоугольника

Mikle — Wed, 14 Dec 2022 13:15:19 +0000

Mikle:

Цитата Profi @ 14.12.22, 12:56

а как же формула Гаусса?

Трапеции сводятся практически к тому же. Строка из моего поста с прошлой страницы:

s = s + (V(i1).y - V(i).y) * (V(i1).x + V(i).x)

Нахождение площади многоугольника

OpenGL — Wed, 14 Dec 2022 13:14:07 +0000

OpenGL:

Цитата Profi @ 14.12.22, 12:56

Парни, а как же формула Гаусса?

Это то, что я векторным произведением назвал.

Нахождение площади многоугольника

Profi — Wed, 14 Dec 2022 12:56:59 +0000

Profi: Парни, а как же формула Гаусса?

public static double Shoelace(IList<Point> points)

{

var sum = 0;

for (int i = 0; i < points.Count; i++)

{

var nextPointIndex = i + 1;

if (nextPointIndex == points.Count)

{

nextPointIndex = 0;

}

var firstPoint = points[i];

var secondPoint = points[nextPointIndex];

sum += firstPoint.X*secondPoint.Y - firstPoint.Y*secondPoint.X;

}

return Math.Abs(sum)/2;

}

Добавлено 14.12.22, 13:04
Только надо:

return Math.Abs(sum)/2.0;

Нахождение площади многоугольника

FasterHarder — Wed, 14 Dec 2022 08:02:43 +0000

FasterHarder:

Цитата OpenGL @ 14.12.22, 04:01

Вот это не понял. Если сторона параллельна OY, тогда да, можно брать как +, так и -, т.к. площадь соответствующей трапеции нулевая. А если параллельно OX, то никаких нет нюансов.

все, теперь я точно понял
чего-то я тупо ступил, посчитав, что, когда линия || Ox, то координата по Х НЕ меняется, ужс...( она не меняется для || Oy )

Нахождение площади многоугольника

OpenGL — Wed, 14 Dec 2022 07:42:08 +0000

OpenGL:

Цитата Mikle @ 14.12.22, 07:00

Да ну? Трапециями - самое простое. Вот вся функция:

Да, я потом сообразил, что у трапеций формула достаточно лаконичная, так что так же просто как и с векторным произведением получается.

Нахождение площади многоугольника

Mikle — Wed, 14 Dec 2022 07:35:03 +0000

Mikle:

Цитата FasterHarder @ 14.12.22, 07:13

кроме треугольников др.фигуры возможны?

Там в ReamMe написано (используй СКМ и ПКМ).

Цитата FasterHarder @ 14.12.22, 07:13

иногда пл. отриц. показывает ( я так понял она стоит в заголовке формы )

Всё верно.

Цитата kopilov @ 14.12.22, 07:29

знак площади зависеть от «спина» фигуры

Да, можно в формулу добавить модуль.

Нахождение площади многоугольника

kopilov — Wed, 14 Dec 2022 07:29:59 +0000

kopilov:

Цитата FasterHarder @ 14.12.22, 07:13

2. иногда пл. отриц. показывает

А может знак площади зависеть от «спина» фигуры (перечисление вершин по/против часов)?

Нахождение площади многоугольника

FasterHarder — Wed, 14 Dec 2022 07:13:29 +0000

FasterHarder: Mikle, прикольно, конечно, смотрится, но:
1. кроме треугольников др.фигуры возможны?
2. иногда пл. отриц. показывает ( я так понял она стоит в заголовке формы )
--------------------------------------

я так и не понял, надо сравнивать на строго или строго+равно, если линия многоугольника || Ox; сейчас стоит со знаком "-", если px1 < px2 ---> s = -s

Нахождение площади многоугольника

Mikle — Wed, 14 Dec 2022 07:00:49 +0000

Mikle:

Цитата FasterHarder @ 13.12.22, 10:37

понимаю, странное требование, т к гораздо проще ( и точнее ) можно найти площадь, разбив его на треугольники и там все изи посчитать

Цитата OpenGL @ 13.12.22, 11:27

Гораздо проще это через векторное произведение считать

Да ну? Трапециями - самое простое. Вот вся функция:

Private Function Area() As Single

Dim i As Long, i1 As Long

Dim s As Single

s = 0

For i = 0 To vCnt - 1

i1 = (i + 1) Mod vCnt

s = s + (V(i1).y - V(i).y) * (V(i1).x + V(i).x)

Next i

Area = s / 2

End Function

Что-то я завёлся, даже программу с удобным интерфейсом сделал:

Area.zip (, : 102)

Нахождение площади многоугольника

OpenGL — Wed, 14 Dec 2022 04:01:17 +0000

OpenGL:

Цитата FasterHarder @ 13.12.22, 21:22

у меня такое чувство, что здесь какой-то лютый нюанс может быть, когда одна из линий || Ox, причем эта линия снизу фигуры где-нибудь, а может и нет

Почему тут нюанс должен быть? В этом случае трапеция вырождается в прямоугольник, и всё. Ни на что это не влияет.

Добавлено 14.12.22, 04:03

Цитата FasterHarder @ 13.12.22, 14:12

единственный момент в алго: когда сторона многоугольника || оси Ox, в этом случае пробовал и + и - - все равно вроде ответ правильный, хм...ну ладно...оставил знак "-", когда строго уменьшается

Нахождение площади многоугольника

FasterHarder — Tue, 13 Dec 2022 21:22:47 +0000

FasterHarder:

Цитата Akina @ 13.12.22, 20:16

Проверь на (2,1)-(3,1)-(2,2)-(3,3)-(2,3)-(1,2)-(2,1)

сначала проверил в онлайне, чтобы понимать, правильно или нет посчитает)
онлайн выдал ответ "-2", но, возможно, "-" типа тире

прожка выдала 20 000 ( но это норм, т к координаты умножаю все на 100 ) ( фигура - наконечник стрелки влево )

вроде бы все правильно посчиталось)
-------------------
у меня такое чувство, что здесь какой-то лютый нюанс может быть, когда одна из линий || Ox, причем эта линия снизу фигуры где-нибудь, а может и нет

Нахождение площади многоугольника

Akina — Tue, 13 Dec 2022 20:16:50 +0000

Akina:

Цитата FasterHarder @ 13.12.22, 18:39

без самопересечений вроде все хорошо работает

Проверь на (2,1)-(3,1)-(2,2)-(3,3)-(2,3)-(1,2)-(2,1)

Нахождение площади многоугольника

FasterHarder — Tue, 13 Dec 2022 18:39:36 +0000

FasterHarder:

Цитата Akina @ 13.12.22, 17:05

Проверь на самопересекающемся многоугольнике. Например, (1,1)-(3,2)-(1,3)-(3,3)-(1,2)-(3,1)-(1,1).

проверил, только все координаты умножил на 100, чтобы видно было хорошо на форме
ответ пишет: 0 ))

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

Нахождение площади многоугольника

Akina — Tue, 13 Dec 2022 17:05:49 +0000

Akina: FasterHarder
Проверь на самопересекающемся многоугольнике. Например, (1,1)-(3,2)-(1,3)-(3,3)-(1,2)-(3,1)-(1,1).

Нахождение площади многоугольника

FasterHarder — Tue, 13 Dec 2022 14:12:56 +0000

FasterHarder: OpenGL, спс, все отлично считает

единственный момент в алго: когда сторона многоугольника || оси Ox, в этом случае пробовал и + и - - все равно вроде ответ правильный, хм...ну ладно...оставил знак "-", когда строго уменьшается
хотя я вот не уверен, что прогнал для всех возможных типов многоугольников и здесь что-то может пойти не так...вот тут не знаю

Нахождение площади многоугольника

OpenGL — Tue, 13 Dec 2022 12:34:24 +0000

OpenGL:

Цитата FasterHarder @ 13.12.22, 12:15

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

Будет работать.

Нахождение площади многоугольника

FasterHarder — Tue, 13 Dec 2022 12:15:04 +0000

FasterHarder: ааа, да, я кажись понял
действительно, трапеция образуется гораздо проще

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

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

Добавлено 13.12.22, 12:16
т е под методом трапеций подразумевается способ решения именно такой, как ты описал
ну ок

Нахождение площади многоугольника

OpenGL — Tue, 13 Dec 2022 11:27:08 +0000

OpenGL:

Цитата FasterHarder @ 13.12.22, 10:37

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

Гораздо проще это через векторное произведение считать. В чём-то даже на интергирование будет походить. В полярных координатах, и не методом трапеций, но тем не менее на интегрирование.

Цитата FasterHarder @ 13.12.22, 10:37

основная моя мысль была провести через каждую вершину линии || оси Ох, затем спроцеировать точку на эту линию и вычислить площадь маленьких тр-ков, которые не входят в состав многоугольника

Как-то сложно.
У тебя сторона многоугольника, ось OX и отрезки, идущие из вершин, смежной со стороной и параллельные оси Y образуют трапецию. Просто считай ориентированную площадь этой трапеции и прибавляй к результату. "Ориентированную" означает, что ты должен брать её со знаком + если координата x уменьшается при движении вдоль этой стороны, и со знаком минус - иначе.
Например, если у тебя на рисунке вершины в порядке обхода это ABCDE, трапеции на сторонах AB и EA должны браться со знаком минус, а BC, CD, DE со знаком плюс.

Нахождение площади многоугольника

FasterHarder — Tue, 13 Dec 2022 10:37:24 +0000

FasterHarder: Всем хай! Сходу к делу!

На плоскости задан многоугольник ( необязательно выпуклый ) координатами своих вершин и необходимо найти его площадь.
Например, такой:
__________________________.png (, : 354)

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

Как работает метод трапеций в принципе знаю + есть куча описаний в инете.

Но как этот метод трапеций наложить на многоугольник?? У меня есть какие-то мысли, но это все как-то тупо мне кажется))

спс за внимание

Добавлено 13.12.22, 10:40
основная моя мысль была провести через каждую вершину линии || оси Ох, затем спроцеировать точку на эту линию и вычислить площадь маленьких тр-ков, которые не входят в состав многоугольника
и затем из площади прямоугольника ( в который "вписан" заданный многоугольник ) вычесть эти маленькие "угловые" треугольники и в результате останется искомая площадь...