title: Given a kd tree-like grid, how to find two nearest intersecting lines
body: <p>Say I have a grid structure like the image here:</p>
  <p><a href="https://i.stack.imgur.com/H7XL4.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/H7XL4.png" alt="enter image description here" /></a></p>
  <p>Give point <code>D</code>, I want to find the nearest points whose line intersects with the line created by <code>D</code>.</p>
  <p>I need a way to find <code>C</code> and <code>E</code>, but not <code>A</code> or <code>B</code>.</p>
  <p><code>A</code> is not a candidate because it runs parallel to <code>D</code>.</p>
  <p><code>B</code> is not a candidate because it does not intersect with <code>D</code>.</p>
  <p>I'm trying to find the best data structure to store this data, as well as the best way to design an algorithm to support this search. I've looked at KD Trees, but I need to be able to specify the line dimension for each point.</p>
  <p>I need to have a data structure also needs to work for an arbitrary combination of vertical and horizontal segments, such as this:</p>
  <p><a href="https://i.stack.imgur.com/YlSuG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/YlSuG.png" alt="enter image description here" /></a></p>
  <p>In this example, if we where searching <code>A</code>, we would return just <code>C</code>.</p>
  <p>And finally:</p>
  <p><a href="https://i.stack.imgur.com/3Mgne.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/3Mgne.png" alt="enter image description here" /></a></p>
  <p>In this example, if we where searching <code>A</code>, we would return nothing.</p>