javascript - Query set of points in AREA within distance from line segment -

i have line segments , points stored in db. how query db in order retrieve points within distance of multiple line segments. purpose when user clicks on path (road), objects within distance path should highlighted.

thank you.

update: example... have path goes (0,0) (0, 10). program should find , highlight objects within x-distance of path. suppose x-distance "2"... then, program should highlight objects within rectangle (0,2)(10,-2). basically, same finding objects proximity line (not single point).

it easy when line horizontal... don't know how solve cases, including line may slope.

update: points stored in large database, cannot check each , every 1 of them proximity. i'm trying find way retrieve ones close enough without overlapping requests much... once retrieved, can refine search using method described in "distance between point , line segment". (i think!) thanks!

this give distance point p line segment v,w. (based on question: shortest distance between point , line segment). you'll have run through points , calculate distance line segments find ones close enough route.
if it's slow, you'll have make kind of simplification doesn't need square roots.

function distancetolinesegment(p, v, w)  {      var len2 = dist2(v, w);      if (len2 == 0) return math.sqrt(dist2(p, v));      var s = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / len2;      if (s < 0) return math.sqrt(dist2(p, v));      if (s > 1) return math.sqrt(dist2(p, w));      var = {x: v.x + s * (w.x - v.x), y: v.y + s * (w.y - v.y)};      return math.sqrt(dist2(p, i));        function dist2(p, q) {          return math.pow(p.x - q.x, 2) + math.pow(p.y - q.y, 2);      }  }    alert(distancetolinesegment({x:2, y:3}, {x:-1, y:4}, {x:3, y:8}));

this optimized implementation checks list of points against route.
points check stored array far[] of points x , y values , id string. there second, empty array close[] points moved if found close route, points aren't checked twice. these 2 arrays stored in object points, can passed reference between functions, instead of being copied. i've removed square root functions efficiency.
further optimization possible changing distance calculation coarser approximation (maybe using rectangles) instead of mathematically correct one.

function isclosetoroute(points, route, distance) {      var distance2 = math.pow(distance, 2);      (var = 0; < route.length - 1; i++) {          isclosetolinesegment(points, route[i], route[i + 1], distance2);      }        function isclosetolinesegment(points, v, w, distance2) {          (var = points.far.length - 1; >= 0; i--) {              if (distancetolinesegment2(points.far[i], v, w) <= distance2) {                  points.close.push(points.far.splice(i, 1)[0]);              }          }      }        function distancetolinesegment2(p, v, w) {          var len2 = dist2(v, w);          if (len2 == 0) return dist2(p, v);          var q = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / len2;          if (q < 0) return dist2(p, v);          if (q > 1) return dist2(p, w);          var = {x: v.x + q * (w.x - v.x), y: v.y + q * (w.y - v.y)};          return dist2(p, i);                function dist2(p, q) {              return math.pow(p.x - q.x, 2) + math.pow(p.y - q.y, 2);          }      }  }    var points = {close: [], far: [{x: 1, y: 0, id: "a"},                                  {x: 2, y: 1, id: "b"},                                  {x:-1, y: 8, id: "c"},                                  {x:-3, y: 4, id: "d"}]};  var route = [{x: 0, y: 0}, {x: 1, y: 2}, {x:-1, y: 4}, {x: 2, y: 8}];    isclosetoroute(points, route, 2);  alert(points.close.length + " points found near route");  (i in points.close) console.log(points.close[i].id);

if divide map grid, can use isclosetoroute() check grid cells near route. return list of grid cells have key "6,4"; if give each point in database key indicates in grid cells it's located, can them without having math on coordinates.
make input object when checking list of points, fill far[] array center points of grid cells, , run isclosetoroute() on distance of (distance + gridsize*sqrt(2)/2).
in example, map 1000 x 1000 square, divided 64 grid cells each sized 125 x 125.

function isclosetoroute(points, route, distance) {      var distance2 = math.pow(distance, 2);      (var = 0; < route.length - 1; i++) {          isclosetolinesegment(points, route[i], route[i + 1], distance2);      }        function isclosetolinesegment(points, v, w, distance2) {          (var = points.far.length - 1; >= 0; i--) {              if (distancetolinesegment2(points.far[i], v, w) <= distance2) {                  points.close.push(points.far.splice(i, 1)[0]);              }          }      }        function distancetolinesegment2(p, v, w) {          var len2 = dist2(v, w);          if (len2 == 0) return dist2(p, v);          var q = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / len2;          if (q < 0) return dist2(p, v);          if (q > 1) return dist2(p, w);          var = {x: v.x + q * (w.x - v.x), y: v.y + q * (w.y - v.y)};          return dist2(p, i);                function dist2(p, q) {              return math.pow(p.x - q.x, 2) + math.pow(p.y - q.y, 2);          }      }  }    var route = [{x: 210, y: 190}, {x: 820, y: 480}, {x:530, y: 470}, {x: 440, y: 760}];  var distance = 100;  var mapsize = 1000;  var gridsize = 125;  var gridcells = math.floor(mapsize / gridsize);  var grid = {close: [], far: []};    (x = 0; x < gridcells; x++) {      (y = 0; y < gridcells; y++) {          grid.far[y * (gridcells) + x] = {x: (x + 0.5) * gridsize,                                            y: (y + 0.5) * gridsize,                                          key: x + "," + y};      }  }    isclosetoroute(grid, route, distance + 0.707107 * gridsize);  alert(grid.close.length + " grid cells near route");  (i in grid.close) console.log(grid.close[i].key);

i've optimized isclosetoroute() bit more. example runs test 1000 random points checked against 1000-segment random route.

function isclosetoroute(points, route, distance) {      var distance2 = math.pow(distance, 2);      (var = 0; < route.length - 1; i++) {          isclosetolinesegment(route[i], route[i + 1]);      }        function isclosetolinesegment(v, w) {          var len2 = distancetopoint2(v, w);          var lenx = w.x - v.x, leny = w.y - v.y;          (var = points.far.length - 1; >= 0; i--) {              if (distancetolinesegment2(points.far[i]) <= distance2) {                  points.near.push(points.far.splice(i, 1)[0]);              }          }            function distancetolinesegment2(p) {            if (len2 == 0) return distancetopoint2(p, v);   // enable if zero-length segments possible              var q = ((p.x - v.x) * lenx + (p.y - v.y) * leny) / len2;              if (q < 0) return distancetopoint2(p, v);              if (q > 1) return distancetopoint2(p, w);              var r = {x: v.x + q * lenx, y: v.y + q * leny};              return distancetopoint2(p, r);          }            function distancetopoint2(p, q) {              return math.pow(p.x - q.x, 2) + math.pow(p.y - q.y, 2);          }      }  }    // generate random test data  var points = {near: [], far: [{x: 500, y: 500}]};  var route = [{x: 200, y: 200}];  var distance = 100;  (var = 1; < 1000; i++) {      points.far[i] = {x: math.random() * 1000, y: math.random() * 1000};      route[i] = {x: route[i - 1].x + 3 * math.random() - 1, y: route[i - 1].y + 3 * math.random() - 1};  }    var t = new date().gettime();  isclosetoroute(points, route, distance);  t = new date().gettime() - t;  alert(points.near.length + " points found near route.\n(1000 points checked against 1000 segments in " + t + " ms)");  (i in points.near) console.log(points.near[i].x + "," + points.near[i].y);