All nearest neighbors query

Some applications need to work with the interaction of points that are close to each other. For example, in one technique used for additive manufacturing, the particles in a powder bed are melted using a laser. Particle behavior against nearby particles determines droplet formation. The all-nearest-neighbors query takes as input a list of point positions and regions and a maximum radius. For each point, using the L2 norm as the distance measure, the query calculates the nearest neighbor point not in the same region, as shown in the figure.

../../../../_images/AllNearestNeighbors.png

Fig. 29 All nearest neighbors query. Here, points belong to one of four regions. Given a maximum search radius, the query finds the closest neighbor to each point in another region.

Here is an example of query usage, from <axom>/src/axom/quest/tests/quest_all_nearest_neighbors.cpp.

First, include the header.

#include "axom/quest/AllNearestNeighbors.hpp"

Query input consists of the points’ x, y, and z positions and region IDs, the point count, and the search radius.

  double x[] = {-1.2, -1.0, -0.8, -1.0, 0.8, 1.0, 1.2, 1.0};
  double y[] = {0.0, -0.2, 0.0, 0.2, 0.0, -0.2, 0.0, 0.2};
  double z[] = {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0};
  int region[] = {0, 0, 0, 0, 1, 1, 1, 1};
  int n = 8;
  double limit = 1.9;

For each input point, the output arrays give the point’s neighbor index and squared distance from the point to that neighbor.

    axom::quest::all_nearest_neighbors(x, y, z, region, n, limit, neighbor, dsq);