How to search for objects within a specified radius of an XY coordinate (without gems)?

Approach

Consider the link

[a, b]

where a and b are two-element arrays that correspond to x-y coordinates in Euclidean space. I will assume a != b.

In vector terminology, every point on the line that goes through the points a and b can be expressed as:

αa + (1-α)b

for some value of the scalar α. α satisfies 0 <= α <= 1 for points falling on the line segment between a and b. Those points are said to comprise a convex combination of a and b. I will compute the value of α (alpha) that corresponds to a point that is on both the line that passes through a and b and line that is perpendicular to that line and passes through a given point p.

First calculate the slope of the line that passes between a and b. Let

a = [ax,ay]
b = [bx,by]

Points c = [cx,cy] on the line that passes through a and b are expressed:

cx = alpha*ax + (1-alpha)*bx
cy = alpha*ay + (1-alpha)*by

which we can simplify to:

cx = alpha*(ax-bx) + bx
cy = alpha*(ay-by) + by

Note that cx and cy equal bx and by when alpha is zero and equal ax and ay when alpha equals 1.

Suppose now we are given a point:

p = [px,py]

and wish to find the point on the line (not necessarily the line segment) that passes through a and b that is the closest point to p. We can do that as follows.

First calculate the slope of the line that passes through a and b (assuming bx != ax, which would correspond to a vertical line):

slope = (by-ay)/(bx-ax)

Lines perpendicular to this line have a slope equal to:

pslope = -1/slope

Let's compute the intercept of such a line that passes through point p:

intercept + pslope*px = py

So

intercept = py - pslope*px
    

Now let's see where this line intersects the line that passes through a and b in terms of the value of alpha:

intercept + pslope(alpha*(ax-bx) + bx) = alpha*(ay-by) + by

Solving for alpha:

alpha = (by - pslope*bx - intercept)/(pslope*(ax-bx) - (ay-by))

Let's try this with an example. Consider just two links of a graph, as shown in the professionally-prepared drawing below. (Whoops! I see my graphic service neglected to label the point [2,3] as "A".) First consider the link, or line segment, A-B and the point 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

Because 0 <= alpha (0.8) <= 1, (cx,cy) falls in the line segment A-B, so that point is the closest point on the line segment to P, not just the point on the line going through A and B that is closest to P.

The square of the distance from P to C is found to equal

(cx-px)**2 + (cy-py)**2
  #=> (2.6-5.0)**2 + (3.8-2.0)**2 => 9

If we wished to include all links no farther than, say, 3.5 from P, that is equivalent to including all links whose squared distance to P is no more than:

max_dist_sqrd = 3.5**2
  #=> 12.25

As 9.0 <= max_dist_sqrd (12.25), this link would be included.

Now consider the link 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

Because alpha > 1.0 we know that the point F is not on the line segment D-E. Let's take a brief excursion to see where the point is:

fx = alpha*(dx-ex) + ex
  #=> 2.0(7-6) + 6 => 8.0
fy = alpha*(dy-ey) + ey
  #=> 2.0(6-9) + 9 => 3.0

Because alpha > 1.0 we know that the closest point to P on the line segment D-E is D. Had alpha > 1.0, the closest point would have been E.

We therefore find that the closest distance squared from the point P to the line segment D-E equals:

(dx-px)**2 + (dy-py)**2
  #=> (7-5)**2 + (6-2)**2 => 20

Since 20.0 > max_dist_sqrd (12.25), this link would not be included.

Code

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

Example

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]]]

1. Create an AABB-Tree: AABB-Tree is an spatial index i.e., it accelerate spatial queries. You can use other index datastructure like kd-tree, uniform grid, quad-tree, R-tree, etc. But I found AABB-tree simpler and near optimal for range queries (what you want to do is a range query e.g., like nearest neighbors)

   1.1) First put each and every link into an AABB. Compute the centroid of each AABB.

   1.2) Put all your AABBs into a big AABB that contains all of them. Make that big AABB the tree root node.

   1.3) Find the largest side of the big AABB (it can be X or Y).

   1.4) Sort all the AABBs by centroid coordinate (X or Y) corresponding to the largest side.

   1.5) Find the middle of the sorted list and split it in two lists.

   1.6) Create two child nodes attached to the root node and assign one list to each node.

   1.7) Call step 1.2) recursively to build each child node into a subtree.

   1.8) Stop the recursion when the list is of size <= N. Then assign all AABBs to that node.

2. Do a range query to find the closest link to a point (i.e., traverse the tree recursively).

   2.1) Define a circle of infinite radius centered at the point you want to query. Pass the circle as parameter to the traverse function.

   2.2) If the root node's AABB intersect with the circle, then call recursively the traverse function with the left and the right children. The order is important, so you should choose first the child closer to the circle center.

   2.3) If the node is a leaf node (i.e., no children, it hold the list of AABBs of links) then check if circle intersect the AABBs of the links, if it does then compute the distance of point to each link and keep the shortest distance. While you compute the distance to each link compare it with the radius of the circle. If the distance is smaller than the radius update the radius if the circle to the shortest distance, and keep the ID of the link with shortest distance.

3. Once traverse function finish, you will get the shortest distance in logarithmic time.

Using methods provided by Cary Swoveland above, the answer is almost there. Using an example below:

class Link
  attr_accessor :bends
  def initialize(bends)
    @bends = bends
  end
end

link_1 = Link.new([1, 1, 2, 2, 3, 3, 4, 4])
link_2 = Link.new([5, 5, 6, 6, 7, 7, 8, 8])
link_3 = Link.new([11, 11, 14, 14, 17, 17, 22, 22, 25, 25])

valid_links = Array.new
links = [link_1, link_2, link_3]
links.each do |link|
  # Conditional goes here, to populate valid_links
  valid_links << link
end

point = [1.1, 1.1]

def link_coordinates(link)
  # To get the link XYs in desired format:
  # [[[x1, y1], [x2, y2]], [[x2, y2], [x3, y3]], [[x3, y3], [x4, y4]]]  (1)
  link = link.bends.each_slice(2).each_cons(2).to_a 
  #=> [[[1, 1], [2, 2]], [[2, 2], [3, 3]], [[3, 3], [4, 4]]]  (for first link)
end

closest_segment = valid_links.min_by { |link| sqrd_dist_to_link(link_coordinates(link), point)}

The above yields an error within sqrd_dist_to_link. Where before when "links" was only using values and in the format:

links = [[[x1, y1], [x2, y2]], [[x2, y2], [x3, y3]], [[x3, y3], [x4, y4]]]  (2)

@closest_segment = links.min_by { |link| sqrd_dist_to_link(link, point)}

succeeded in returning the nearest XY coordinates of the segment in the format: [[x1, y1], [x2, y2]].

Considering the "links" labelled "(1)" and the links labelled "(2)" output the same format, I'm uncertain how to tweak things so that valid_links.min_by { |link| sqrd_dist_to_link(link_coordinates(link), point)} will retrieve the link object of the nearest XY segment as desired.

Note:

I will update this when I have it working correctly so that it qualifies correctly as an answer.