This document presents an implementation of two algorithms, Voronoi Neighbors and Binary Space Partition (BSP) Neighbors. These algorithms find neighbors of a point in a point set that are somehow “better” than a “K nearest neighbors” or a “all neighbors within a radius” query. This type of nearest neighbor query is more computationally expensive, but results in set of neighbors with more desirable properties. The BSP Neighbors search ensures that there is less local duplication, while the Voronoi Neighbors search ensures that the spatial arrangement of the neighbors is as uniform as possible.

These algorithms are explained in “Point Primitives for Interactive Modeling and Processing of 3D Geometry”.

This work was published in the VTK Journal.  Please click here to see it.

The code is available here.