|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serg Belyaev 2:5015/166.7 23 Jul 2001 23:31:15
To : skanilo@cc1010125-a.ebnsk1.nj.home.
Subject : Re: Определение площади фигуры
--------------------------------------------------------------------------------
31-May-01 06:09:32, skanilo@cc1010125-a.ebnsk1.nj.home. wrote to All
Subject: Re: Определение площади фигуры
Мне следующая задачка показалась любопытной. Поэтому решаюсь
повторно обратить на нее ваше внимание.
s> From: skanilo@cc1010125-a.ebnsk1.nj.home.com Reply-To:
s> skanilo@cc1010125-a.ebnsk1.nj.home.com
s> From: "Serge Kanilo" <skanilo@cc1010125-a.ebnsk1.nj.home.com>
s> "Fyodor Korzhov" <Fyodor.Korzhov@p17.f61.n5045.z2.fidonet.org>
s> wrote in message news:991163280@p17.f61.n5045.z2.FIDOnet.ftn...
>> 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емя очень велико.
s> Для точного решения можно использовать списки дуг. Идея такова -
s> при пересечении кругов получается фигура, ограниченная дугами.
s> Что-то типа многогранника, но с дугами вместо граней. Hадо написать
s> преобразование контура этой фигуры после добавления еще одного
s> круга. Определить попадает ли круг внутрь (тогда ничего не делаем),
s> или пересекается - тогда соответственно изменяем границу, или не
s> пересекается, образуя отдельную новую фигуру. Будут конечно
s> проблемы когда добавляющийся круг пересекается с несколькими
s> имеющимися фигурами. Hо это решаемо. Также особо надо будет
s> рассматривать "отрицательные" фигуры - дырки. Если не стоит
s> проблема скорости, то это все очень легко реализуется в лоб.
s> Площадь полученной таким образом фигуры легко считается через
s> интеграл по границе.
Сначала мне также показалось, что необходимо определить
контур, а затем вычислить интеграл по границе. И также
возникло чувство, что нужно будет немного помучиться и
с "дырками", и с отслеживанием связных областей. Рисовалась
"страшная" картина с проблемой касания окружностей и т.д.
Hо все это оправдано тем, что ожидаемая скорость алгоритма
максимальна для данной задачи.
Hо... все значительно проще. Для вычисления интеграла по
границе нам совершенно не нужно определять контур со
всеми подробностями - от контура нам нужно только набор
составляющих его дуг и совершенно не нужно знать как они
связаны между собой. А это уже совершенно легкая задача.
Действительно для любой окружности мы должны определить
набор дуг, которые не "отгрызены" другими окружностями.
Hаправление обхода по ставшимся дугам нам известно - оно
общее для всех оружностей. И все! - для вычисления искомого
интеграла этого достаточно.
Еще одно замечание. Можно не экономить на отслеживании
пересекающихся пар - в лучшем случае выигрыш будет в 2 раза.
Т.е. для каждой окружности запускаем цикл по оставшимся
N-1 окружностям.
<SVB>
--- Terminate 5.00/Pro
* Origin: Crazy Pentium III. (2:5015/166.7)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Определение площади фигуры 