CODEWITHSUNDEEP
javascriptmathgeometry
FatalKeystroke
FatalKeystroke

Reputation: 3052

Find 2d data points which fall within certain area

I have a large set of data which represents coordinates on a two dimensional plane. What would be an effective and efficient method to find all of the x,y pairs that fall within a variable radius based around a variable point? (Any tips for storing the data that would make processing it easier is also very welcome)

EDIT

Final application is being written in Javascript, specifically Node.

EDIT

I've found that a rectangular area is also allowable rather than a radius, the borders of the rectangle would still be variable however. A I've stated in a comment below, I should specify that the final data set will have millions of entries and traversing the entire set for each request is not feasible.

Upvotes: 0

Views: 129

Answers (2)

Justin L.
Justin L.

Reputation: 387

@Ayan's approach is very straighforward, but here are some other techniques to consider. You're going to have to measure with your actual data to know what really works, though.

If you have a very large number of points, step one is to get rid of all points outside of a bounding box that contains your circle. Let's say the circle is centered at (ox, oy) with a radius of r. Then you can discard all points who's x value is outside of ox+/-r (and same for y value). If your points are sorted by the x coordinate, you should be able to use a binary search to narrow it down on the x coordinate, and then do a linear scan on the remaining points candidates with a plausible y value.

Then, the most straightforward approach is to compare the square of the euclidian distance with r^2. This avoids doing the square root in the standard distance formula that @Ayan is doing above, which is quite expensive. So just calculate whether r^2 is less than (ox - px)^2 + (oy - py)^2. Since the latter is just addition and multiplication, should be reasonably quick.

If you can accept some approximation, you might consider sampling the -y and +y of the circle along certain buckets on the circle, and storing those in a lookup table. Then, for a given point (x, y), you look up the appropriate bucket for that x and see if y is in between the points you've precalculated. You'd really have to have a lot of points for this to be faster though.

Upvotes: 0

Ayan
Ayan

Reputation: 2380

The point to point distance should be less than the radius of the circle being searched. To improve the search, one might also implement binary search or kd-tree.

var getPoints = (function() {
  var points = [{
    x: 90,
    y: 70
  }, {
    x: 100,
    y: 80
  }, {
    x: 20,
    y: 40
  }]
  return function() {
    return points;
  }
})();

function dist(point1, point2) {
  var pow = Math.pow;
  return Math.sqrt(pow((point2.x - point1.x), 2) + pow((point2.y - point1.y), 2));
}

function drawCircle(centerX, centerY, radius, fill) {
  var canvas = document.getElementById('myCanvas');
  var context = canvas.getContext('2d');

  context.beginPath();
  context.arc(centerX, centerY, radius, 0, 2 * Math.PI, false);
  if (fill) {
    context.fillStyle = 'green';
    context.fill();
  }
  context.lineWidth = 2;
  context.strokeStyle = '#003300';
  context.stroke();
}

function spatialSearch(centerX, centerY, radius) {
  var points = getPoints(),
    res = [],
    len,
    r = 5,
    fill,
    i;

  drawCircle(centerX, centerY, radius);

  for (i = 0, len = points.length; i < len; i += 1) {
    ele = points[i];
    fill = undefined;
    if (dist({
      x: centerX,
      y: centerY
    }, ele) <= radius) {
      res.push(ele);
      fill = 'green';
    }
    drawCircle(ele.x, ele.y, r, fill);
  }
  return res;
}

spatialSearch(100, 75, 50);
<canvas id="myCanvas" width="300" height="150" style="border:1px solid #d3d3d3;">
  Your browser does not support the HTML5 canvas tag.</canvas>

Upvotes: 1

Related Questions