Круг-Многоугольник Пересечения

Question

Вычислительная геометрия проблема:
Точка P0 выбирается случайным образом на кромке (например, EB) многоугольника (например, BCDE), чтобы найти возможные точки (т.е. P1,P2,P3,...) на другом края на основе заданного расстояния (т. е. r). Следующая демонстрация показывает решение путем нахождения пересечений между окружностью с центром в точке P0 и краями многоугольника. Таким образом, проблема в основном может быть решена путем анализа пересечения Circle--Line-Segment.

Интересно, Есть ли более эффективный метод для этой очень простой проблемы с точки зрения стоимости вычислений? Процесс будет оценен несколько million times, поэтому любой интерес представляет интерес.

• окончательное решение будет извлечь выгоду из Python мощности;
• расчет ядра будет в Fortran при необходимости.

Обновления:
спасибо за ваши комментарии. Пожалуйста, рассмотрите мои комментарии к комментариям, которые помогают уточнить этот вопрос. Не желая повторять их здесь, поощряя рассмотрение всех комментариев и ответов;).

Я только что реализовал метод Circle--Line-Segment Intersection на основе найденного алгоритма [here]. Фактически я адаптировал его для работы с линейными сегментами. Эталон алгоритма, реализованный в Python выглядит следующим образом:


количества сегментов линии: 100,000 и система обычно рабочий стол. Истекшее время: 15 seconds. Надеемся, что это полезно, чтобы дать некоторое представление о стоимости вычислений. Реализация ядра в Fortan может значительно улучшить производительность.
Однако перевод является последним шагом.

Answer 1

Для пересечения между line (или line-segment) и circle (sphere в 3D) есть немного больше объяснений, детали реализации, а также Python, C и т.д. образцы кодов в [this link]. Вы можете попробовать их для своей проблемы.
Идея в основном такая же, как вы уже нашли в [here].

Answer 2

Предполагая, что circle--line-intersection оптимизирован, вы можете быть в состоянии получить что-то, различая разные случаи:

для точки A, B:

• Если d (P0, A) < г и д (Р0, Б) < г: Нет пересечения

• , если д (Р0, А) == г: пересечения в

• если d (Р 0, В) == г: Пересечение в точке В
• Если д (Р0, А) < г и д (Р0, В)> г: 1 пересечение, выполнить circle--line-intersection

• Если д (Р0, А)> г и д (Р0, Б) < г: 1 пересечение, выполнение circle--line-intersection

• Если д (Р0, а)> г и д (Р0, В)> г: Существует либо 0, 1 или 2 пересечениями -> Если minimum distance к линии (A, B)> r: Нет перекрестков -> Если minimum distance в линию (A, B) == r: 1 пересечение -> Если minimum distance в линию (A, B) < r: 2 intersectio нс