Какой алгоритм может эффективно найти набор точек на определенном расстоянии пути?

Question

Учитывая набор точек s (набор координат x, y) и путь, который состоит из отрезков, соединяющих набор точек l , описывают эффективное алгоритм, который можно использовать для поиска подмножества точек из s , которые находятся в пределах указанного расстояния d пути l .

Практическое применение этого может состоять в том, чтобы найти список ресторанов в пределах 10 миль в любом месте вдоль дорожной поездки между городами.

Например, на следующей диаграмме точки зеленого цвета будут включены в результаты поиска.

Решения предпочтительнее в C #, но бонусные баллы могут быть предоставлены для подхода на основе SQL: -)

Answer 1

Вы должны быть в состоянии сделать это с помощью векторной математики и триггера, хотя точные методы избегают меня.

Для каждого отрезка линии рассчитайте значения, необходимые для преобразования точки из мировых координат в локальные координаты относительно отрезка (поэтому любая точка, проходящая через вычисление, будет относиться к системе координат, где отрезок линии является осью x )

Для каждой точки выполните следующие проверки:

1- Если точка находится в пределах расстояния от любой конечной точки, мы знаем, что она должна быть включена. Это достигается простым вычислением расстояния ^ 2 <= (x2 - x1) ^ 2 + (y2 - y1) ^ 2 между каждой конечной точкой и целевой точкой. </p>

2- Проведите целевую точку через трансформацию. После преобразования, если x> = 0 и x <= (длина отрезка) и | y | <= расстояние, то целевая точка должна быть включена, в противном случае она должна быть исключена. </p>

Моя векторная математика немного ржавая, поэтому я не могу предоставить лучший код / ​​примеры, извините! Но, возможно, мой пост вдохновит кого-то еще написать правильный способ сделать это.

Answer 2

Не могли бы вы использовать четырехугольное дерево, чтобы разделить пространство на сегменты, и тогда только для точек в сегментах, близких к вашему пути?