На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Нахождение площади многоугольника , численное интегрирование
    Всем хай! Сходу к делу!

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


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

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

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

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

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

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

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

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

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

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

        Добавлено
        т е под методом трапеций подразумевается способ решения именно такой, как ты описал
        ну ок
          Цитата FasterHarder @

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

          Будет работать.
            OpenGL, спс, все отлично считает

            единственный момент в алго: когда сторона многоугольника || оси Ox, в этом случае пробовал и + и - - все равно вроде ответ правильный, хм...ну ладно...оставил знак "-", когда строго уменьшается
            хотя я вот не уверен, что прогнал для всех возможных типов многоугольников и здесь что-то может пойти не так...вот тут не знаю
              FasterHarder
              Проверь на самопересекающемся многоугольнике. Например, (1,1)-(3,2)-(1,3)-(3,3)-(1,2)-(3,1)-(1,1).
                Цитата Akina @
                Проверь на самопересекающемся многоугольнике. Например, (1,1)-(3,2)-(1,3)-(3,3)-(1,2)-(3,1)-(1,1).

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

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

                  Проверь на (2,1)-(3,1)-(2,2)-(3,3)-(2,3)-(1,2)-(2,1)
                    Цитата Akina @
                    Проверь на (2,1)-(3,1)-(2,2)-(3,3)-(2,3)-(1,2)-(2,1)

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

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

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

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

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

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

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

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

                        ExpandedWrap disabled
                          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 Кбайт, скачиваний: 33)
                          Mikle, прикольно, конечно, смотрится, но:
                          1. кроме треугольников др.фигуры возможны?
                          2. иногда пл. отриц. показывает ( я так понял она стоит в заголовке формы )
                          --------------------------------------

                          я так и не понял, надо сравнивать на строго или строго+равно, если линия многоугольника || Ox; сейчас стоит со знаком "-", если px1 < px2 ---> s = -s
                          Сообщение отредактировано: FasterHarder -
                            Цитата FasterHarder @
                            2. иногда пл. отриц. показывает

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

                              Там в ReamMe написано (используй СКМ и ПКМ).
                              Цитата FasterHarder @
                              иногда пл. отриц. показывает ( я так понял она стоит в заголовке формы )

                              Всё верно.
                              Цитата kopilov @
                              знак площади зависеть от «спина» фигуры

                              Да, можно в формулу добавить модуль.
                              Сообщение отредактировано: Mikle -
                                Цитата Mikle @

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

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


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0790 ]   [ 19 queries used ]   [ Generated: 2.12.23, 14:33 GMT ]