Как найти процент перекрытия n-угольниками окружности?

[razumovsu]

Добрый день.

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

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

[Munin]

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

[Dmitriy40]

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

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

[dsge]

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

[svv]

(Оффтоп)

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

[Deggial]

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

[_Ivana]

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

[AndrewSu]

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