 |
|
|
 
|
|
Алгоритм вычисления площади многоугольника 
| Ground |
|
|||
 Опытный  Профиль Группа: Участник Сообщений: 321 Регистрация: 27.2.2006 Где: Комсомольск Репутация: нет Всего: 1 |
Всем снова привет
 Данная тема напрямую связана с http://forum.vingrad.ru/forum/s/402de66db3...pic-252010.html. У нас есть фигура. Сверху ломаная (красная), снизу прямая (синяя). Необходимо вычислить площадь этой фигуры. Точек у ломанной может быть до 10к.  Координаты по Х образуют ряд: x0 < x1 < x2 < ... < xn. Попробовал вот такой способ, но он, увы, не дает верного результата. Еще и количество точек лимитировано - всего 100. Также пробовал способ, делить на прямоугольные треугольнички и прямоугольники между точками i, i+1, но слишком много описывать в коде. Возможно есть какие либо еще способы вычисления площади? Это сообщение отредактировал(а) Ground - 23.3.2009, 11:11 |
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Делишь вертикально на куски, каждый - на 2 прямоугольных треугольника и прямоугольник. Считаешь.
Присоединённый файл ( Кол-во скачиваний: 20 ) 
T14UEUT1V4.jpg 18,64 Kb-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Так есть же очень простая формула для вычисления площади произвольного многоугольника, в которой к тому же всё будет в целых числах:
S = ABS( СУММА по i=1..N (X[i]-X[i+1]) * (Y[i]+Y[i+1]) ) / 2 Добавлено через 8 минут и 55 секунд Она очень легко получается: возьмём каждый отрезок (P[i], P[i+1]), каждый такой отрезок (вместе с осью ox) ограничивает трапецию ((X[i],Y[i]), (X[i+1],Y[i+1]), (X[i+1],0), (X[i],0)). Заметим, что если мы просуммируем площади всех таких трапеций, беря со знаком минус те из них, в которых X[i+1]<X[i], то в результате вся "лишняя" площадь сократится, и останется только площадь многоугольника, или она со знаком минус (зависит от направления обхода). А знаковую площадь такой трапеции легко получить: это полусумма оснований (Y[i] и Y[i+1]) на высоту с нужным знаком (а это как раз в точности X[i+1]-X[i]). Итак, просуммировав площади таких трапеций, и взяв модуль, мы получим площадь многоугольника. |
|||
|
||||
| Ground |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 321 Регистрация: 27.2.2006 Где: Комсомольск Репутация: нет Всего: 1 |
Эта формула справедлива для любого количества вершин многоугольника? Вот тут указано, что эта формула используется только для многоугольников до 100 вершин (хотя они и формулу неверно вывели). Это сообщение отредактировал(а) Ground - 23.3.2009, 13:27 |
|||
|
||||
| maxdiver |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 16 Всего: 18 |
Да хоть миллион  Ну разве что инты переполнятся |
|||
|
||||
| Ground |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 321 Регистрация: 27.2.2006 Где: Комсомольск Репутация: нет Всего: 1 |
Ну тогда вопрос закрываю, всем спасибо за помощь!
maxdiver, держи плюсик! |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0449 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |