# spatial-grid

Computes closest points to meshes and polygons

``npm install spatial-grid``

# spatial-grid

Spatial queries on simplicial complexes in arbitrary dimensions.

# Usage and Installation

First, install via npm:

``````npm install spatial-grid
``````

Then you can create grids and query them as follows:

``````var bunny = require("bunny");
var grid = require("spatial-grid")(bunny.cells, bunny.positions, 0.1);
console.log(grid.closestCells([1.0, 0.0, 0.0]));
``````

Which returns the following data:

``````{ points: [ [ 1.0520095436290573, 0.2639268057343442, 0.10221864065360134 ] ],
cells: [ 3507 ],
distance: 0.2877690079051383 }
``````

The code should work for two dimensional meshes, tetrahedral volume, and other higher dimensional structures.

## `require("spatial-grid")(cells, positions, tolerance)`

Creates a spatial grid over the simplicial complex determined by `[positions, cells]` with cell size = `tolerance`.

• `cells` is an abstract simplicial complex represented by an array of arrays of indices
• `positions` is an array of positions for the 0-cells
• `tolerance`: The resolution of the cell complex

Returns a spatial grid for the cell complex.

## `grid.closestCells(x)`

Returns information about the closest cell to the point `x` within the specified tolerance.

• `x` is a point

Returns: If no cell is within `tolerance`, returns `null`. Otherwise, returns an object with the following parameters:

• `cells`: An array of cells of approximately equal distance to `x` (within a tolerance of +/-1e-6 )
• `points`: An array of points closest to x
• `distance`: The squared distance to the surface from `x`

## `grid.neighborhood(x, radius)`

Returns all of the cells in the complex which are within `radius` distance of the point `x`.

# Notes

Currently the library is built on top of the FORTRAN code quadprog, which solves the simplex-closest point problem. If this library gets popular enough, I may eventually add faster routines for low dimensional queries. For high dimensions, the search routines used in this library become exponentially less efficient. However the performance should be "good enough" for d <= 3, and it is probably usable up to d<=5.

# Credits

(c) 2013 Mikola Lysenko. BSD

npm loves you