### Snap To Grid

I like Gabor Herman‘s definition of discrete Euclidean space. He defines, for any positive real number $\delta$ and any positive integer $N$:

$\delta \mathbb{Z}^N = \{ ( \delta x_1, \ldots, \delta x_N ) | x_n \in \mathbb{Z} \text{ for } 1 \leq n \leq N \}$

This chops N-space up into a square (cubic, etc.) Bravais lattice, with primitive vectors of magnitude $\delta$. Each point in the discrete space is then associated with a primitive cell (or Voronoi neighbourhood, in Herman’s parlance) consisting of all points in the associated continuous space which are closer to that discrete point than any other discrete point.

This relationship to continuous space makes discretization of otherwise continuous sets — or regions, as say the GIS people — a snap (pun intended). In the simplest case, it is equivalent to basic sampling.

In 3-space, these are essentially voxels, which are intuitive for visual thinkers like me, and allow for neat tricks from the computer graphics literature like voxel traversals.

Mar 17th, 2010
Tags: ,