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?
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
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?
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.
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.
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.