|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Betke 154816751 2:5032/6 07 Feb 2002 11:14:34
To : Uriy Iovkov
Subject : Re: Площадь многоугольника
--------------------------------------------------------------------------------
Ты писал (Mon, 04 Feb 2002 00:27:38 +0300):
UI> Люди! Скажите плз, как посчитать площадь *невыпуклого*
UI> многоугольника?
UI> Известны его вершины.
У меня была когда то такая задача. Самое простое решение:
1. Берём некоторую произвольную вершину в качестве базовой
2. Hачинаем обходить остальные вершины по парам в некотором направлении (в
каком - не важно, главное - в каком либо конкретном). Hу, например: взяли за
базовую вершину номер 1. Первая итерация - берём пару 2 и 3, вторая
итерация - пару 3 и 4, далее - 4 и 5 и так далее, до n-1, n.
Hа каждом шаге мы имеем некоторый треугольник. Его площадь считается
элементарно.
Теперь самое интересное. В случае выпуклого многоугольника мы бы просто
сложили площади всех треугольников. В случае невыпуклого - некоторые должны
вычитаться! Как определить? Очень просто:
Hа первом шаге: находим угловую координату вектора 1-2 и вектора 1-3. Если у
1-3 больше, чем у 1-2 - значит площадь 1-2-3 добавляем к площади
многоульника, если меньше - значит вычитаем. Собственно говоря, вовсе не
обязательно определять саму угловую координату, достаточно просто сравнить
тангенсы этой величины (это отношение координат вектора), а потом просто
проанализировать знак одной из координат.
Hу и в самом конце: знак полученной величины неопределён (зависит от
выбранного направления обхода). Можно, конечно, строго потребовать обход
против часовой стрелки, но это дополнительный анализ на старте. Проще и
быстрее просто взять модуль полученной в конце величины.
Вот и весь алгоритм. Буду рад замечаниям.
С большим приветом, Sergey Betke.
--- Tearline sample
* Origin: HЗ ГАРО (2:5032/6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Площадь многоугольника