Круг-полигональные пересечения - PullRequest
Новая
       3

Круг-полигональные пересечения

12 голосов
/ 23 января 2012

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

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

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

enter image description here

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

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

Ответы [ 2 ]

2 голосов
/ 23 января 2012

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

0 голосов
/ 23 января 2012

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

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

  • Если d (P0, A)

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

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

  • Если d (P0, A)> r и d (P0, B) circle--line-intersection

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

...