2014 dxdy logo

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

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




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

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

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

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

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

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

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

 
 
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение09.06.2016, 20:15 
"Интеграл от ломаных" минус "интеграл от дуги окружности", с пределами интегрирования - точки пересечения ломанных с окружностью.

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

(Оффтоп)

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

 
 
 
 Posted automatically
Сообщение11.06.2016, 21:42 
Аватара пользователя
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Программирование»
Причина переноса: в соответствующий раздел

 
 
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение13.06.2016, 01:47 
Если не дорого анализировать принадлежность точки многоугольнику, то можно просто песка Монте-Карло сверху насыпать сколько надо.

 
 
 
 Re: Как найти процент перекрытия n-угольниками окружности?
Сообщение09.11.2016, 00:45 
Если можно немного пожертвовать точностью, то преобразуйте окружность в контур из точек и далее пересекайте два контура. Для пересечения контуров можно использовать http://www.cs.man.ac.uk/~toby/gpc/ либо другие реализации.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group