Bin (computational geometry)

In computational geometry, the bin is a data structure that allows efficient region queries.

The data structure partitions a region of the 2D plane into uniform-sized bins.

This can be done easily by clipping the candidate against the query rectangle and comparing its lower-left corner against the current location.

Deletion is more expensive because we need to search the singly linked list of each bin the candidate intersects.

In a multithread environment, insert, delete and query are mutually exclusive.

Like a hash table, bin's efficiency depends a lot on the distribution of both location and size of candidates and queries.

Against k-d tree, the bin structure allows efficient insertion and deletion without the complexity of rebalancing.

This can be very useful in algorithms that need to incrementally add shapes to the search data structure.