Finding Nearest Point in an Efficient Way

Finding nearest point in an efficient way

Use a quad-tree for 2D
http://en.wikipedia.org/wiki/Quadtree

What is the fastest way to find the closest point to a given point?

You may organize your points in an Octree. Then you only need to search a small subset.

A Octree is a fairly simple data structure you can implement yourself (which would be a valuable learning experience), or you may find some helpful libraries to get you going.

What's an efficient way of calculating the nearest point?

From what I can gather, it looks as though the best approach in this case is to return an array of points using a bounding box around the current location.

You can retrieve points within a certain range of the current location, if the returned array is empty, then increase the size of the box. Once some results come back, calculate the nearest in the array and use that point.

Efficient way of finding the closest point?

The best algorithm depends on the number of points you expect to compare, how often these points are moved and searched, how important speed of re-indexing and searching are, and what language you're using. As @Sylvanus pointed out, there may be language or library calls that can help. In all likelihood a quad tree will be the easiest to understand, while being about as efficient all round as possible. @Shiva Kumar gives an excellent comprehensive set of possibilities (although there are still more ways.) You should do a google search to see how the problem has been solved for the language and environment you're programming for.

efficient algorithm to find nearest point in a graph that does not have a known equation

If you can use a data structure, some common data structures for spacial searching (including nearest neighbour) are...

• quad-tree (and octree etc).
• kd-tree
• bsp tree (only practical for a static set of points).
• r-tree

The r-tree comes in a number of variants. It's very closely related to the B+ tree, but with (depending on the variant) different orderings on the items (points) in the leaf nodes.

The Hilbert R tree uses a strict ordering of points based on the Hilbert curve. The Hilbert curve (or rather a generalization of it) is very good at ordering multi-dimensional data so that nearby points in space are usually nearby in the linear ordering.

In principle, the Hilbert ordering could be applied by sorting a simple array of points. The natural clustering in this would mean that a search would usually only need to search a few fairly-short spans in the array - with the complication being that you need to work out which spans they are.

I used to have a link for a good paper on doing the Hilbert curve ordering calculations, but I've lost it. An ordering based on Gray codes would be simpler, but not quite as efficient at clustering. In fact, there's a deep connection between Gray codes and Hilbert curves - that paper I've lost uses Gray code related functions quite a bit.

EDIT - I found that link - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7490

Efficient way to find the nearest point from a set of points to the touched point inbetween a range?

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event{
    CGPoint touchedPoint = [[touches anyObject]locationInView:self];
    CGPoint discoveryPoint;
    CGFloat tolerance = 20;
    // Had to Create these two arrays because there's no such thing as [NSDictionary objectAtIndex:]
    NSArray *pointsArray;

    CGFloat keyOfPointWithMinDistance = -1;
    CGPoint nearestPointToTouchedPoint = CGPointZero;
    Int index = 0;
    Int keyIndex = NSNotFound;

    for (NSValue * cgpointVal in self.pointsArray){

        discoveryPoint = cgpointVal.CGPointValue;

        if (fabs(touchedPoint.x - discoveryPoint.x)<tolerance && fabs(touchedPoint.y - discoveryPoint.y)<tolerance) {
            //Calculating the distance between points with touchedPoint in their range(Square) and adding them to an array.
            CGFloat distance = hypotf(touchedPoint.x - discoveryPoint.x, touchedPoint.y - discoveryPoint.y);

            if (keyOfPointWithMinDistance == -1 || keyOfPointWithMinDistance < distance) {
                keyOfPointWithMinDistance = distance;
                nearestPointToTouchedPoint = discoveryPoint;
                keyIndex = index;
            }

            index++;
        }
    }

    //Update self.pointsArray using keyIndex

    if keyIndex != NSNotFound {

    }

}

---

Related Topics