|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Zhmur 2:5030/638.12 02 Jun 2001 09:49:40
To : Fyodor Korzhov
Subject : Определение площади фигуры
--------------------------------------------------------------------------------
Пятница Июнь 01 2001, Fyodor Korzhov писал(а) Alex Cvetkov:
FK> Именно Монте-Каpло я сейчас и пользyю. Пpи yвеличении точности вpемя
FK> пpосчета ой как yвеличивается. Совсем он неоптимальный - нyжно
FK> что-нить лyчшее. Я пытался что-нить пpидyмать типа: два кpyга -> два
FK> сектоpа + два тpеyгольника (все площади считаются элементаpно), с
FK> пpедваpительной соpтиpовкой и выкидыванием пеpекpывающихся. Hо там
FK> сложности с пеpесечением нескольких кpyгов...
Читал доказательство одной теоремы в матанализе, по ходу дела родился
алгоритм решения решения этой задачи. Похоже его сходимость к решению близка к
экспоненциальной.
Данные:
Счетчик занятой площади(ЗП)
Счетчик свободной площади(СП)
Общая площадь(ОП)
Очередь для хранения ячеек
Ячейка содержит координаты левого нижнего и правого верхнего угла, а так же
массив указателей на шары(МУШ), которые имеют с ячейкой общие точки.
Массив шаров.
EPS - требуемая точность.
Инициализация:
Загрузить массив шаров.
Создать ячейку которая включает все шары(и заполнить ее МУШ).
ОП = площадь этой ячейки.
Поместить ячейку в очередь.
ЗП = 0; СП = 0;
Главный цикл:
пока (ОП - ЗП - СП>=EPS) делать
взять из очереди ячейку
Возможны следующие случаи(дизъюнктные):
а) ячейка имеет пустой МУШ, тогда добавить ее площадь к СП.
б) ячейка полность накрыта одним из шаров ее МУШ, тогда добавить ее площадь к
ЗП.
в) ячека имеет всего один шар в МУШ который ее полностью не накрывает, тогда
можно точно(аналитически) вычислить часть закрытую шаром и соответсвенно
увеличить СП и ЗП.
г) иначе разбить ячейку на четыре ячейки, вычисить их МУШ на основе МУШ текущей
ячейки и поместить их в очередь.
Плохими точками для этого алгоритма являются точки пересечения окружностей, но
этих точек скорее всего не много и в их окрестности алгоритм хорошо сходится.
PS О том как эффективно организовать выполнения вычислений и проверок, а так же
как организовать очередь сознательно не пишу. Разберешься сам.
SY, Anatoly.
--- GoldED/W32 3.0.1
* Origin: none (2:5030/638.12)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Определение площади фигуры