Найти точку вдоль линии на заданном расстоянии от многоугольника

Question

Учитывая двумерный замкнутый многоугольник, определенный рядом точек и бесконечной линией, я хотел бы найти точки на этой линии на заданном расстоянии от многоугольника. Известно, что многоугольник является замкнутым, не пересекающимся и не содержащим 3 последовательных коллинеарных точки. В общем, на линии есть много возможных точек. В идеале я хотел бы найти их все или, альтернативно, ближайшую некоторую исходную точку предположения. Я использую python, но решение на любом языке было бы полезно. Я считаю, что scipy.spatial kdtree будет одним из важных компонентов, но я не вижу, как это сделать. Вот код, чтобы определить проблему, которая показывает, по крайней мере, некоторые из случаев угловых участвующих:

import numpy as np 
import matplotlib.pyplot as plt 

poly = np.array([[0, 0], 
       [10, 0], 
       [10, 3], 
       [1, 1], 
       [1, 6], 
       [0, 6], 
       [.8, 4], 
       [0, 0]]) 

line = np.array([[-2, 4.5], 
       [12, 3]]) 

plt.plot(poly[:, 0], poly[:, 1]) 
plt.plot(line[:, 0], line[:, 1]) 
plt.xlim([-1, 11]) 
plt.ylim([-1, 7]) 
plt.show() 

points = find_points_distance_from_polygon(poly, line, distance) 

Edit: Я ищу для алгоритма, чтобы найти точки.

Обновление: То, что я пробовал до сих пор, является приблизительным решением, используя расстояние до каждой точки. Я думал, что если бы я уточнил многоугольник, добавив дополнительные точки вдоль каждой линии, то этот подход может быть достаточно точным. Однако, если бы расстояние было небольшим, мне пришлось бы добавить много очков. Я думал, что, вероятно, лучший способ.

import scipy.spatial as spatial 
import scipy.optimize as opt 
import math 

def find_point_distance_from_polygon_along_line(tree, line, dist, guess_ratio): 
    def f(x): 
     pt = line[0, :] + x * (line[1, :] - line[0, :]) 
     d, i = tree.query(pt) 
     return math.fabs(d - dist) 

    res = opt.minimize(f, [guess_ratio]) 
    return line[0, :] + res.x * (line[1, :] - line[0, :]) 

tree = spatial.cKDTree(poly) 
pt = find_point_distance_from_polygon_along_line(tree, line, 1, 0) 

Для примера на графике и на расстоянии от 0,5, я ожидал найти 4 очка на приблизительно (.1, 4.2), (1.5, 4.1), (9.1, 3.3) и (10.5, 3.1). Мой текущий план найдет больше очков, особенно точек, которые находятся на некотором расстоянии от противоположного края многоугольника. Я хочу, чтобы линия, соединяющая точку на линии с полигоном, была внешней для многоугольника.

Answer 1

Если количество краев многоугольника является разумным, вы можете использовать простой линейный алгоритм.

параметрическое уравнение Давайте для линии

L(u) = L0 + u * dL 

где L0 некоторая базовая точка, дл является направление вектора, U представляет собой параметр

и параметрическое уравнение для I-й сегмент

P = P[i] + t * Dir[i] 

где P [i] - первая точка сегмента, Dir [i] - нормированный вектор направления, t - параметр в диапазоне 0..1

произвольной точке на линии имеет свою проекцию на данном сегменте в параметре

t = DotProduct(L(u) - P[i], Dir[i]) //equation 1 

и длины нормали к проекции (необходимое расстояние) является

Dist = Abs(CrossProduct(L(u) - P[i], Dir[i])) 
Abs((L0x + u * dLx - Px) * Diry - (L0y + u * dLy - Py) * Dirx) = Dist 
so 
u = (+-Dist - ((L0x- Px)*Diry -(L0y-Py)*Dirx))/(dLx * Diry - dLy * Dirx) 

заменяющие значения U в уравнение 1 и проверить, если параметр t находится в диапазоне 0..1 (проекция внутри сегмента). Если да, то L (u) - необходимая точка.

Затем проверьте расстояние до вершины - решать

(L0x + u * dLx - Px)^2 + (L0y + u * dLy - Py)^2 = Dist^2