# Round random points to the nearest vertices of a regular tessellated hexagon

For a simulation I need to be able to take points that are scattered around randomly and move their point to the nearest vertex of a tessellated regular hexagon. That way each point is sitting on a vertex of the pattern.

Below is a diagram, showing a tessellated regular hexagon, and on the right is simply the vertices.

The goal is to take a bunch of random points and make them look like the picture on the right.

I dont exactly know how to define the "Start of this pattern" but perhaps we should say that the bottom left hexagon has its center at the coordinates at 0,0. And for the whole pattern we assume that each line length is n units long.

First, we note that the set of points that are closer to a particular hexagonal vertex than any other is a triangle with side length $\sqrt3n$, and that six of these triangles meet at the origin. The problem now reduces to finding where a point lies in the following lattice:

* | C |
|\|/|n|
| B | *
|/|m|/|
* | A |
|\|/|p|
| O | *


This lattice is generated by the vectors OA and OB, so write the point in question as a vector sum of them: $p=x\mathsf{OA}+y\mathsf{OB}$. p then lies in the cell $(\lfloor x\rfloor, \lfloor y\rfloor)$ (the cell (0,0) is m above, (1,0) is n, (1,-1) is p and so on).

Within this cell, which will be a translation of OACB in the diagram above, test whether $\operatorname{frac}(x)+\operatorname{frac}(y)<\frac12$. If so, the point in question should be rounded to the centre of the lower triangle in the cell (a translation of OAB); if not, to the centre of the upper triangle (translation of CBA).