How to find the closest vector to a given vector

algorithms

Let's say I have several points / vectors (in 2D to keep it simple, but could be of any dimension)

   [x1, y1]
   [x2, y2]
   [x3, y3]
   ....
   [xn, yn]

If I pick some point [x', y'], how do I find the closest point to it?

For a more concrete / practical example, imagine these are coordinates of houses. If I have thousands of houses in the database, I'd love to find the closest house to my house. Or more generally, I'd like to find the K closest houses to my house.

One brute-force way to do this is to cycle through each point and find its distance to your point/house and just pick the smallest one. But with thousands or even millions of data points it's not efficient at all.

Is there a faster algorithm at all? Or am I stuck trying to check each point one at a time?

Best Answer

If you have multiple queries, you can use a spatial datastructure to accelerate them. This typically requires preprocessing your target points, and in any case will cost you some time and space.

There are two common classes of acceleration structures: one uses spatial partitions, and the other uses overlapping regions. The k-D tree is an example of the first, while the R-tree is an example of the second.

Of course, if you have only one query, you can't do better overall than checking each point once. But, if you need the query itself to be fast, then preprocessing to build an acceleration structure can get you there.

Related Solutions

An algorithm for finding converse duplicates of ordered pairs

Just collect the pairs in a set. (In Ruby, it will be a Set of two-element Arrays.)

let Set s = {}
for each pair [a,b]
   if s contains [a,b]
      // duplicate, do nothing
   else if s contains [b,a] // converse duplicate
      ...
   else
      add [a,b] to S

If you are writing Ruby, it is already capable of using arrays

Efficient method for finding closest point to a line segment from a set of points including line segment’s vertices

You're going to have to loop through all the points and calculate the distance. There is a great question on StackOverflow about how to calculate the distance: Shortest distance between a point and a line segment

Some of the work can be precalculated, given that you have to do this more than once for a given line segment. You also don't need to figure out the smallest distance, only the smallest distance squared (since squaring is strictly increasing). I converted the top voted answer in that question to a Java version that does this precalculation (in the constructor), and is easier to read and follow. Unfortunately I don't know Python well enough to give you Python code, but you should be able to figure it out.

import java.util.Arrays;
import java.util.List;

public class LineSegment {
    public static class Point {
        public final double x;
        public final double y;

        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return "(" + x + "," + y + ")";
        }
    }

    public static void main(String[] args) {
        LineSegment segment = new LineSegment(new Point(0, 3), new Point(2, 0));
        List<Point> pointList =
                Arrays.asList(new Point[] { new Point(-5, 3), new Point(1, 1),
                        new Point(2, 3), new Point(0, 5) });

        Point answer = segment.closestPoint(pointList);
        System.out.println("The closest point is: " + answer);
    }

    private static double sqr(double x) {
        return x * x;
    }

    private static double distanceSquared(Point v, Point w) {
        return sqr(v.x - w.x) + sqr(v.y - w.y);
    }

    private final Point firstSegPoint;
    private final Point secondSegPoint;
    private final double segmentDistance;
    private double xDifference;
    private double yDifference;

    public LineSegment(Point firstSegPoint, Point secondSegPoint) {
        this.firstSegPoint = firstSegPoint;
        this.secondSegPoint = secondSegPoint;
        this.segmentDistance = distanceSquared(firstSegPoint, secondSegPoint);
        this.xDifference = secondSegPoint.x - firstSegPoint.x;
        this.yDifference = secondSegPoint.y - firstSegPoint.y;
    }

    public Point closestPoint(List<Point> pointList) {
        double minDistance = Double.POSITIVE_INFINITY;
        Point answer = null;

        for (Point point : pointList) {
            double distSquared = distToSegmentSquared(point);
            if (distSquared < minDistance) {
                answer = point;
                minDistance = distSquared;
            }
        }

        return answer;
    }

    private double distToSegmentSquared(Point input) {
        if (segmentDistance == 0)
            return distanceSquared(input, firstSegPoint);

        double xComponent = (input.x - firstSegPoint.x) * xDifference;
        double yComponent = (input.y - firstSegPoint.y) * yDifference;
        double t = (xComponent + yComponent) / segmentDistance;
        if (closestPointIsFirst(t))
            return distanceSquared(input, firstSegPoint);
        if (closestPointIsSecond(t))
            return distanceSquared(input, secondSegPoint);
        Point closestPointOnLine =
                new Point(firstSegPoint.x + t * xDifference, firstSegPoint.y
                        + t * yDifference);
        return distanceSquared(input, closestPointOnLine);
    }

    private boolean closestPointIsFirst(double t) {
        return t < 0;
    }

    private boolean closestPointIsSecond(double t) {
        return t > 1;
    }
}

See the full implementation here: http://ideone.com/fBFwda

Best Answer

Related Solutions

An algorithm for finding converse duplicates of ordered pairs

Efficient method for finding closest point to a line segment from a set of points including line segment’s vertices

Related Topic