|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Saveliev 2:5020/400 29 May 2001 17:13:38
To : All
Subject : Re: Определение площади фигуры
--------------------------------------------------------------------------------
Fyodor Korzhov wrote:
> Как поживаете, All ?
>
> Hе подскажете ли, как можно опpеделить площадь фигypы, полyчаемой из кpyгов на
> плоскости? Есть таблица {X,Y,R}. Кpyги пеpесекаются, накладываются дpyг на
> дpyга, одни полностью закpывают дpyгие. Hyжно как можно более точно опpеделить
> площадь полyчаемой фигypы. Кpyгов - 5000, таких фигyp полyчается несколько
> (кpyг котоpый никого не касается тоже самостоятельная фигypа), но пpи нынешнем
> алгоpитме машинное вpемя очень велико.
>
> Интеpесyет все: алгоpитмы, идеи, домыслы...
>
> Желаем всех-с, Fyodor Korzhov.
1. Берем для каждого круга охватывающий прямоугольник (точнее квадрат)
2. Сортируем квадраты лексикографически по лувому нижнему углу (если круги
разбросаны равномерно, при 5000 объектов достаточно сортировки по X)
3. Для каждого круга находим сначала потенциальных "пересеченцев" (по квадратам,
сначала дихотомический поиск первого, потом просмотр списка, пока не вылезем за
границу своего квадрата), затем реальных. Сохраняем факт пересечения и его
площадь
в списке.
4. Рассматривая список как ребра графа, определяем его компоненты связности
(алгоритм есть в Кнуте и Ахо, Ульмане).
5. Идем по компоненте связности, складывая площади кругов и вычитая пересечения.
При равномерном распределении кругов время поиска "пересеченцев" почти константа
(по нашему опыту), общее время О(N)log(N) за счет сортировки (компонеты
связности
определяются за линейное время при наличии дополнительного массива их индексов,
определение площади линейна относительно числа кругов и пересечений)
Анатолий Савельев
Казанский университет
--- ifmail v.2.15dev5
* Origin: Kazan State University (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
