2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Как найти процент перекрытия n-угольниками окружности?
Сообщение09.06.2016, 15:11 


09/06/16
1
Добрый день.

Необходимо решить следующую задачу: есть один или несколько произвольных n-угольника(может быть не выпуклый), которые пересекаются с окружностью. Необходимо найти процент перекрытия n-угольниками окружности. Координаты всех точек n-угольника и координаты центра окружности и ее радиус известны. Для наглядности скриншот прилагается.
Мне необходим математический аппарат под эту задачу. Можно на английском языке. Можно в принципе реализацию на ЯП.
Как решить задачу по пересечению n-угольников друг с другом я знаю. А вот с окружностью нет.

Заранее спасибо.
Скрин:Изображение

 Профиль  
                  
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение09.06.2016, 16:23 
Заслуженный участник
Аватара пользователя


30/01/06
72407
По-моему, проще всего найти точки пересечения рёбер многоугольника с окружностью, и разделить фигуру пересечения на круговой сегмент и многоугольник. (Внимание, многоугольник может получиться с самопересечениями, надо считать его площадь "алгебраически", с плюсами и минусами.)

 Профиль  
                  
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение09.06.2016, 17:08 
Заслуженный участник


20/08/14
11065
Россия, Москва

(Нематематическое решение)

Если особо большая точность не нужна и многоугольников не сотни тысяч, то можно поступить по тупому: задать сетку с нужным шагом (bitmap) размерами чуть больше окружности, закрасить на ней все многоугольники (с проверкой на сверхмалые многоугольники), посчитать количество незакрашенных узлов сетки в пределах заданного радиуса. Математики немного, зато на практике приближённый результат можно получить быстрее. К тому же процессы хорошо распараллеливаются или можно вообще видеокарту нагрузить, это её родное, она и много миллионов многоугольников сдюжит за реальное время.

 Профиль  
                  
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение09.06.2016, 20:15 
Заслуженный участник


05/08/14
1564
"Интеграл от ломаных" минус "интеграл от дуги окружности", с пределами интегрирования - точки пересечения ломанных с окружностью.

 Профиль  
                  
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение09.06.2016, 21:23 
Заслуженный участник


23/07/08
10626
Crna Gora

(Оффтоп)

На карте написано Юбилейный, буква Ю скрыта под жирной линией, и я читаю: Билинейный.

 Профиль  
                  
 
 Posted automatically
Сообщение11.06.2016, 21:42 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Программирование»
Причина переноса: в соответствующий раздел

 Профиль  
                  
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение13.06.2016, 01:47 


05/09/12
2587
Если не дорого анализировать принадлежность точки многоугольнику, то можно просто песка Монте-Карло сверху насыпать сколько надо.

 Профиль  
                  
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение09.11.2016, 00:45 


09/02/13
31
Если можно немного пожертвовать точностью, то преобразуйте окружность в контур из точек и далее пересекайте два контура. Для пересечения контуров можно использовать http://www.cs.man.ac.uk/~toby/gpc/ либо другие реализации.

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group