Подход
Рассмотрим ссылку
[a, b]
, где a и b - двухэлементные массивы, которые соответствуют x-y координатам в евклидовом формате. пространство. Я предполагаю a != b.
В векторной терминологии каждая точка на линии, которая проходит через точки a и b, может быть выражена как:
αa + (1-α)b
для некоторых значение скаляра α. α удовлетворяет 0 <= α <= 1 для точек, попадающих на сегмент линии между a и b. Утверждается, что эти точки составляют выпуклую комбинацию из a и b. Я вычислю значение α (alpha), которое соответствует точке, которая находится как на линии, проходящей через a и b, так и на линии, перпендикулярной этой линии и проходящей через данную точку p.
Сначала вычислите наклон линии, проходящей между a и b. Пусть
a = [ax,ay]
b = [bx,by]
Точки c = [cx,cy] на линии, проходящей через a и b, выражаются:
cx = alpha*ax + (1-alpha)*bx
cy = alpha*ay + (1-alpha)*by
, которые мы можем упростить до:
cx = alpha*(ax-bx) + bx
cy = alpha*(ay-by) + by
Обратите внимание, что cx и cy равны bx и by, когда alpha равно нулю и равно ax и ay, когда alpha равно 1.
Предположим, теперь нам дана точка:
p = [px,py]
и wi sh, чтобы найти точку на линии (не обязательно отрезок линии), которая проходит через a и b, т.е. ближайшая точка к p. Мы можем сделать это следующим образом.
Сначала вычислите наклон линии, проходящей через a и b (предполагая bx != ax, что соответствует вертикальной линии):
slope = (by-ay)/(bx-ax)
Линии, перпендикулярные этой линии, имеют наклон, равный:
pslope = -1/slope
Давайте вычислим точку пересечения такой линии, которая проходит через точку p:
intercept + pslope*px = py
Итак
intercept = py - pslope*px
Теперь давайте посмотрим, где эта линия пересекает линию, проходящую через a и b с точки зрения значения alpha:
intercept + pslope(alpha*(ax-bx) + bx) = alpha*(ay-by) + by
Решение для альфа :
alpha = (by - pslope*bx - intercept)/(pslope*(ax-bx) - (ay-by))
Давайте попробуем это на примере. Рассмотрим всего две связи графика, как показано на профессионально подготовленном рисунке ниже. (Упс! Я вижу, что моя служба graphi c пренебрегла пометкой точки [2,3] как «A».) Сначала рассмотрите ссылку или сегмент линии A-B и точку P.
введите описание изображения здесь
ax = 2
ay = 3
bx = 5
by = 7
px = 5
py = 2
slope = (by-ay).fdiv(bx-ax)
#=> (7-3).fdiv(5-2) => 1.333..
pslope = -1.0/slope
#=> -0.75
intercept = py - pslope*px
#=> 5.75
alpha = (by - pslope*bx - intercept)/(pslope*(ax-bx) - (ay-by))
#=> 0.8
cx = alpha*(ax-bx) + bx
#=> 2.6
cy = alpha*(ay-by) + by
#=> 3.8
Потому что 0 <= alpha (0.8) <= 1, (cx,cy) попадает в линейный сегмент A-B, поэтому эта точка является ближайшей точкой на линейном сегменте к P, а не только точка на линии, проходящей через A и B, ближайшая к P.
Квадрат расстояния от P до C оказывается равным
(cx-px)**2 + (cy-py)**2
#=> (2.6-5.0)**2 + (3.8-2.0)**2 => 9
Если мы хотим включить все ссылки не дальше, чем, скажем, 3.5 от P, это эквивалентно включению всех ссылок, квадрат расстояния которых до P не превышает:
max_dist_sqrd = 3.5**2
#=> 12.25
Как 9.0 <= max_dist_sqrd (12.25), эта ссылка будет включена.
Теперь рассмотрим ссылку D-E.
dx = 7
dy = 6
ex = 6
ey = 9
px = 5
py = 2
slope = (ey-dy).fdiv(ex-dx)
#=> (9-6).fdiv(6-7) => -3.0
pslope = -1.0/slope
#=> 1.0/3.0 => 0.333
intercept = py - pslope*px
#=> 2 - (0.333)*5 => 0.333..
alpha = (ey - pslope*ex - intercept)/(pslope*(dx-ex) - (dy-ey))
#=> (9 - 0.333*6 - 0.333)/(0.333*(7-6) - (6-9)) #=> 2.0
Потому что alpha > 1.0 мы знайте, что точка F не находится на отрезке линии D-E. Давайте сделаем небольшой экскурс, чтобы увидеть, где находится точка:
fx = alpha*(dx-ex) + ex
#=> 2.0(7-6) + 6 => 8.0
fy = alpha*(dy-ey) + ey
#=> 2.0(6-9) + 9 => 3.0
Потому что alpha > 1.0 мы знаем, что ближайшая точка к P на отрезке линии D-E - D. Если бы alpha > 1.0, ближайшей точкой было бы E.
Таким образом, мы находим, что ближайший квадрат расстояния от точки P до отрезка линии D-E равен:
(dx-px)**2 + (dy-py)**2
#=> (7-5)**2 + (6-2)**2 => 20
Начиная с 20.0 > max_dist_sqrd (12.25), эта ссылка не будет включена.
Код
def links_in_point_circle(links, point, max_dist)
max_dist_sqrd = max_dist**2
links.select { |link| sqrd_dist_to_link(link, point) <= max_dist_sqrd }
end
def sqrd_dist_to_link( ((xlow,ylow),(xhigh,yhigh)),(px,py) )
return vert_link_dist(xlow,ylow,yhigh,px,py) if xlow == xhigh
slope = -1.0/((yhigh-ylow).fdiv(xhigh-xlow))
intercept = py - slope*px
alpha = (yhigh - slope*xhigh - intercept)/(slope*(xlow-xhigh) - (ylow-yhigh))
closest_x, closest_y =
case alpha
when -Float::INFINITY...0
[xhigh, yhigh]
when 0..1.0
[alpha*(xlow-xhigh) + xhigh, alpha*(ylow-yhigh) + yhigh]
else
[xlow, ylow]
end
(closest_x-px)**2 + (closest_y-py)**2
end
def vert_link_dist(xlow, ylow, yhigh, px, py)
return Float::INFINITY if px != xlow
case
when py < ylow then (ylow-py)**2
when ylow..yhigh then 0
else (py-yhigh)**2
end
end
Пример
links = [[[2,3],[5,7]], [[7,6], [6,9]]]
point = [5,2]
max_dist = 3.5
links_in_point_circle(links, point, max_dist)
#=> [[[2, 3], [5, 7]]]