Algorithm for finding closest point to another

I want to find the closest point to my character among a set of points. I must not be searching for the right keywords because I can’t find an answer to this seemingly simple problem.

Linear search is obviously off the table. In my research I’ve found octrees, but I don’t think they’re directly applicable to this. What algorithms exist for this problem?

1 Like

You can get the distance between two points by using subtraction and then getting the magnitude.
Getting the closest point shouldn’t be too hard.

local points = {
    Vector3.new() --example vector3s
    Vector3.new(0,10,10)
    Vector3.new(100,10,100)
}
local function getclosestpoint(v3)
    local closest
    local distance = math.huge
    for i=1,#points do
        local point = points[i]
        local dist = (point-v3).Magnitude
        if dist < distance then
            closest = point
            distance = dist
        end
    end
    return closest
end
1 Like

This is a linear search. I’m looking for something faster.

EDIT: One approach I’ve found is to create a 3D Voronoi diagram and then find which polyhedron the point is located in. My next question is now: How do you do that?

Why is linear search not acceptable? How many points are you concerned with? O(n) is not that bad in most cases.

The algorithm will be performed once per frame on a set of thousands of points.

EDIT: @Halalaluyafail3’s algorithm takes about 10% of a frame used on a set of 5000 points. This is why linear search isn’t ideal.

This sounds like a search problem. I’m not sure what your purposes are exactly, but you’ll likely just want to find a way to create a useful index on this for faster look-ups.

Do the points move? Do you really have to find the nearest one every frame, or is it usually the same?

The points in the set don’t move, but the input point does.

For context: I need to find the closest flower to your character (a bee) in my game. The bees can move hundreds of studs per second, so the closest flower must be found often.

are the points all on a plane? a quadtree would be better than an octree.

It’s three dimensional, meaning an octree, but I still don’t know how I’d use it. A 3D Voronoi might work well because it would need to be calculated when the player joins and never again. But beyond that, I don’t know anything.

I don’t really know how a 3D voronoi tesselation would make this faster. You would have to do a ton of ray/plane intersection calculations, and you would probably need an octree anyway just to optimize that process. It seems more convoluted than just finding the nearest point directly because now you have to check each surface of each polyhedron to see if the point is inside or not using a raycasting algorithm.

An alternative to an octree is to just have a 3D grid where you put points in a corresponding cell, and then only search through the set of points that are in cells near the cell that corresponds to the point.

Your 3D grid approach would only work if a point were in a cell within the defined boundary around the query point’s cell. Otherwise, it won’t find anything. However, because a bee can’t pollinate more than 10 studs away, this approach should work well for my application; it’s basically a spherical Region3 done manually.

If that’s the case then just use https://developer.roblox.com/api-reference/function/Workspace/FindPartsInRegion3WithWhiteList

You might enjoy this module.

1 Like