НГУ

Форумы НГУ
Текущее время: Пн сен 23, 2019 10:19 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Площадь покрытия
СообщениеДобавлено: Вт ноя 15, 2011 3:41 pm 
Не в сети
Начинающий автор

Зарегистрирован: Пн апр 03, 2006 9:27 pm
Сообщения: 205
Откуда: Антон
Добрый день.
Я столкнулся с необходимостью максимально точно (и в идеале - быстро :) ) находить суммарную площадь некоторого покрытия на плоскости, состоящего из набора кругов различного радиуса. Круги могут пересекаться.
В голову приходит нечто похожее на формулу включений и исключений. Поверхностный поиск в гугле конкретных результатов не дал. Может кто-нибудь посоветовать полезную литературу, ссылки?

_________________
Спор на форуме - это как Олимпиада для умственно отсталых. Даже если ты победил - ты все равно идиот.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт ноя 15, 2011 9:20 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
А покрытие - оно покрытие чего? Какой-то выпуклой области? Или просто набор кругов на плоскости накидан и надо посчитать площадь объединения?

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт ноя 15, 2011 9:57 pm 
Не в сети
Начинающий автор

Зарегистрирован: Пн апр 03, 2006 9:27 pm
Сообщения: 205
Откуда: Антон
Коба писал(а):
А покрытие - оно покрытие чего? Какой-то выпуклой области? Или просто набор кругов на плоскости накидан и надо посчитать площадь объединения?

Второе.

_________________
Спор на форуме - это как Олимпиада для умственно отсталых. Даже если ты победил - ты все равно идиот.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср ноя 16, 2011 6:15 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Тогда, ИМХО, только включений-исключений. Ну или Монте-Карло.

Или можно ещё что-то изобрести, в зависимости от того, сколько всего кругов, что известно про их расположение и какая нужна точность.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср ноя 16, 2011 1:25 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Сб мар 15, 2003 1:40 am
Сообщения: 163
Sharir, M. Intersection and closest-pair problems for a set of planar discs. SIAM .J Comput. 14 (1985), pp. 448-468. Сложность

Aurenhammer, F. Improved algorithms for discs and balls using power diagrams. Journal of Algorithms 9 (1985), pp. 151-161. Сложность


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср ноя 16, 2011 2:46 pm 
Не в сети
Начинающий автор

Зарегистрирован: Пн апр 03, 2006 9:27 pm
Сообщения: 205
Откуда: Антон
Коба писал(а):
Тогда, ИМХО, только включений-исключений. Ну или Монте-Карло.

Или можно ещё что-то изобрести, в зависимости от того, сколько всего кругов, что известно про их расположение и какая нужна точность.

Да, я в итоге пришел тоже к таким выводам.

_________________
Спор на форуме - это как Олимпиада для умственно отсталых. Даже если ты победил - ты все равно идиот.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср ноя 16, 2011 2:46 pm 
Не в сети
Начинающий автор

Зарегистрирован: Пн апр 03, 2006 9:27 pm
Сообщения: 205
Откуда: Антон
guest писал(а):
Sharir, M. Intersection and closest-pair problems for a set of planar discs. SIAM .J Comput. 14 (1985), pp. 448-468. Сложность

Aurenhammer, F. Improved algorithms for discs and balls using power diagrams. Journal of Algorithms 9 (1985), pp. 151-161. Сложность

Спасибо, будем искать.

_________________
Спор на форуме - это как Олимпиада для умственно отсталых. Даже если ты победил - ты все равно идиот.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 5


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB