Перекрестки между полигонами

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

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

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

enter image description here

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

Я только что реализовал метод Circle--Line-Segment Intersection на основе найденного алгоритма [здесь]. Фактически я адаптировал его для работы с линейными сегментами. Эталон алгоритма, реализованного на Python, выглядит следующим образом:
enter image description here
enter image description here
Количество сегментов линии: 100,000, а система - обычный рабочий стол. Истекшее время: 15 seconds. Надеемся, что это полезно, чтобы дать некоторое представление о стоимости вычислений. Реализация ядра в Fortan может значительно повысить производительность.
Однако перевод является последним.

Ответы

Ответ 1

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

Ответ 2

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

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

  • Если d (P0, A) r и d (P0, B) r: Нет пересечений

  • если d (P0, A) == r: пересечение при A

  • если d (P0, B) == r: пересечение при B
  • Если d (P0, A) r и d (P0, B) > r: 1, выполнить circle--line-intersection

  • Если d (P0, A) > r и d (P0, B) r: 1, выполнить circle--line-intersection

  • Если d (P0, A) > r и d (P0, B) > r: существует либо 0, 1, либо 2 пересечения - > Если минимальное расстояние до строки (A, B) > r: нет пересечений - > Если минимальное расстояние до пересечения линии (A, B) == r: 1 - > Если минимальное расстояние до строки (A, B) < r: 2 пересечения