# Nearest neighbor search in 2D to find circles that interacts with point

I need to store big number of object that every object have range, then I need to find objects that the point are in their range. So basically I need to store circles and then check who interacts with some point.

R*-tree is very slow at the insert (again I need huge number of objects). kd-tree and quadtree doesn't allow to store shapes. another problem with quadtree is that there are no bounds.

There is another algorithms that meet the requirements?

If all of your objects have the same range (say r), then the problem is to find all object centers which lie inside a given circle. In other words you can think of your original point (let's call this the target) as a circle of radius r centered at the target and your original circles (let's call them objects) as points, at their centers.

In this case you can build e.g. a kd-tree from the object centers. To find the set of object centers which lie inside the circle of radius r centered at the target (the query circle), you can traverse the kd-tree, and prune the subtrees which completely lie outside the query circle.

If you have different object ranges, I would suggest defining range buckets (e.g. close range, mid range, far range), and building different kd-trees for those buckets. The range search should be pessimistic, i.e. it should use the largest r in the bucket. You have to perform the search on the kd-trees of each bucket and consider the union of the results.

• I can't limit the range, every object can have any range from 1 to infinity. – Zilberman Rafael Jul 20 '14 at 14:54
• Then you can allocate buckets dynamically in exponentially growing fashion, i.e. the first bucket is [1,10), the second is [10, 100), and so forth. If a new object is inserted, and you have no such bucket, you create it. You can use another base, not necessarily 10. The buckets and corresponding kd-trees can be stored in e.g. a balanced tree. – zogi Jul 20 '14 at 15:19
• I didnt ubderstand, can you please give examples? – Zilberman Rafael Jul 20 '14 at 15:41
• e.g. a new object with range 114 arrives. The range is at least 100, but lesser than 1000, so it goes to bucket 3 (first bucket: 1 to 10, second bucket: 10 to 100, etc.). The kd-trees of the buckets can be stored in e.g. a balanced tree (e.g. std::map in c++). If there is no kd-tree for the key 3 in the tree, it is added, and the object is inserted into that kd-tree. kdt = KdTree(); kdt.insert(object); bucket_id = int(log10(range)) + 1; buckets[bucket_id] = kdt; – zogi Jul 20 '14 at 16:25
• What if object with range 10^(100^1000) arrives? the buckets array should be huge / unlimited. Should be better solution – Zilberman Rafael Jul 20 '14 at 16:30

sweepline, you sort the objects by the X or Y coordinate of the center and then check the objects in the range point.x-maxRange, point.x+maxRange

• in that way I should sort the objects every time object inserted, so if I inserting 10,000 objects than I should sort the array 10,000 and every time that array is growing. I understood right? – Zilberman Rafael Jul 20 '14 at 14:51
• or keep a large "main" array and a shorter unsorted array that you insert the new objects in and then sort and merge into the larger from time to time when it becomes too large (a hundred lets say), you can remove objects by "soft" deleting them and not merging them in the new larger array when a merge happens. – ratchet freak Jul 20 '14 at 15:06
• I think that should be better solution instead of this – Zilberman Rafael Jul 20 '14 at 15:44
• @ZilbermanRafael you can click the checkmark next to the answer that best helped you to mark it as accepted – ratchet freak Jul 20 '14 at 16:34

DBVH (dynamic bounding volume hierarchy) is a common approach to solving this need.

A BVH is just a tree of nodes containing one or more bounding volumes (e.g., circles/spheres) that are grouped together into a large bounding volume encompassing the children.

There are several ways to construct a BVH. Some are intended to produce optimal trees from a known set of objects while others can dynamically construct the BVH as objects are added, removed, moved, or resized (and this kind of dynamic BVH is probably what you need).

The classic resource that will cover this algorithm in detail (and many others) is [url=http://www.amazon.com/Real-Time-Collision-Detection-Interactive-Technology/dp/1558607323]Real-Time Collision Detection by Christer Ericson[/url]. Every game programmer should have a copy of this nearby for reference, IMO.

You can also consider a grid-based approach. For each circle, add an entry to all the grid locations that the circle overlaps with pointing to the detector object. When an object is added or moves, determine which grid locations it interacts with, find the set of all detector circles registered with those grid locations, and signal them. If your world is particularly large, you can consider a hash-based sparse grid rather than a 2D array.