Find Nearby Points

I’m having trouble efficiently getting nearby points within a certain distance. I have a large collection of points (Vector3’s) which tops out at around 500,000. I’ve found some solutions for finding the nearest point (nearest-neighbor search) with a KD-Tree. However, I cannot find anything that has range-searching. Are there any other methods I could use for this, or will I need to roll my own KD-Tree with range-searching? The “problem” is sort of like this: for every point, get points within a range of the point, and modify those points. The abstract idea has to do with changing colors and other properties based on proximity to other points.

The most efficient solution I can think of is just plain sort the list of vectors by their sqrMagnitude to the point being compared to. Sorting is relatively fast; the fastest comparison sorts (e.g. MergeSort or QuickSort) can be done in O( n*log(n) ). If you save the sqrMagnitudes, finding the set of points within a given range is a matter of selecting an appropriate amount of elements from the beginning with a sqrMagnitude smaller than searchedDistance^2. Using binary search, this can be done in O( log(n) ) time.

However, with a large dataset even the fastest methods will take a while, so if you’re looking for performance, you should first and foremost figure out a way to make your dataset smaller.

EDIT:

Some kind of a data structure would be preferable if searches are frequent. The sorting would have to be redone on each Vector3 whose nearest neighbors must be found.

Originally I was thinking of a spherical radius, which was the vibe I got from the question. However, if a cube works too, it is even simpler to find the Vectors:

List allVectors of Vector3
List neighbors of Vector3
Vector3 origin
float distance

foreach (vector in allVectors){
    if (CheckDistance(origin.x, vector.x) && 
        CheckDistance(origin.y, vector.y) &&
        CheckDistance(origin.z, vector.z)){
            neighbors.Add(vector);
    }
}

bool CheckDistance(float origin, float otherPoint){
    return (otherPoint > origin-distance && 
            otherPoint < origin+distance)
}

If a spherical distance is required, this method could be used to pre-compute suitable vectors to minimize the work done when sorting.

Interesting problem. You could throw a cube down your kd tree and see what it catches. Been a while since I used a kd tree but I remember passing a line segment down the tree to catch triangle intersections so I think throwing a cube down there should be relatively fast. You could use a sphere as well but the calculations at each node might bog you down. You can just test the sphere intersection at leaf nodes. It would probably work out quicker if you’re working with small distances. I haven’t checked this code for correctness but hopefully it will give you the general idea and of course I have no idea how you implemented your tree so adapt as needed

List<Vector3> GetVerticesInRange(Vector3 point, float range, KdTreeNode node)
	{
		List<Vector3> vertices = new List<Vector3>();
		if(node.isLeafNode())
		{
			foreach(Vector3 v in node.verticeList)
			{
				float xd = point.x - v.x;
				float yd = point.y - v.y;
				float zd = point.z - v.z;
				
				if((xd*xd + yd*yd + zd*zd) <= range*range )
				{
					vertices.Add(v);
				}
			}
		
			return vertices;	
 		}
		
		if(point[axis]- range <= median)
		{
			vertices.AddRange(GetVerticesInRange(point, range, node.left));
		}
		
		if(point[axis]+ range > median)
		{
			vertices.AddRange(GetVerticesInRange(point, range, node.right));
		}
		
		return vertices;
	}