|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Kanilo 2:5020/400 31 May 2001 07:09:32
To : All
Subject : Re: Определение площади фигуры
--------------------------------------------------------------------------------
"Fyodor Korzhov" <Fyodor.Korzhov@p17.f61.n5045.z2.fidonet.org> 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емя очень велико.
>
> Интеpесyет все: алгоpитмы, идеи, домыслы...
Для точного решения можно использовать списки дуг.
Идея такова - при пересечении кругов получается фигура,
ограниченная дугами. Что-то типа многогранника, но с дугами
вместо граней.
Hадо написать преобразование контура этой фигуры после
добавления еще одного круга. Определить попадает ли круг
внутрь (тогда ничего не делаем), или пересекается - тогда
соответственно изменяем границу, или не пересекается,
образуя отдельную новую фигуру. Будут конечно проблемы
когда добавляющийся круг пересекается с несколькими
имеющимися фигурами. Hо это решаемо. Также особо надо
будет рассматривать "отрицательные" фигуры - дырки.
Если не стоит проблема скорости, то это все очень легко
реализуется в лоб.
Площадь полученной таким образом фигуры легко считается
через интеграл по границе.
Второй вариант - приближенный расчет площади простой отрисовкой
кругов на черно-белой битмапе с последующим подсчетом закрашенных
точек.
Возможен также вариант с уточнением - использовать предыдущий
вариант, но с разделением внутренних и прилегающих к границе
круга точек.
Затем после полной закраски отдельно рассматривать каждую
приграничную точку (квадратик). Если она пересекается
одним-двумя кругами, то площадь определить несложно,
если большим количеством - то использовать дополнительное
деление.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
