Нахождение площади многоугольника , численное интегрирование

[FasterHarder]

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

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

Прикреплённая картинка

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

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

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

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

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

[OpenGL]

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

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

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

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

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

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

[FasterHarder]

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

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

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

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

[OpenGL]

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

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

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

[FasterHarder]

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

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

[Akina]

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

[FasterHarder]

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

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

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

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

[Akina]

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

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

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

[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, причем эта линия снизу фигуры где-нибудь, а может и нет

[OpenGL]

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

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

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

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

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

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

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

[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 (7,09 Кбайт, скачиваний: 45)

[FasterHarder]

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

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

Сообщение отредактировано: FasterHarder - 14.12.22, 07:14

[kopilov]

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

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

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

[Mikle]

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

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

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

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

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

Всё верно.

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

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

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

Сообщение отредактировано: Mikle - 14.12.22, 07:35

[OpenGL]

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

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

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

[FasterHarder]

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

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

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

[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;

[OpenGL]

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

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

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

[Mikle]

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

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

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

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

[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]

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

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

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

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

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

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