Equilateral triangular grid generation algorithm

Question

In a research that I'm doing I need to generate an equilateral triangular grid and use this grid to mesh a region of space represented as a polygon to solve a PDE on this mesh. The problem is I need an algorithm to generate the grid and numbering the nodes and the connection table of this nodes, I searched out there in web without any good result. If someone know a good algorithm or had worked on this kind of grids and can help me to figure out a solution it will be highly appreciated.

Answer 1

I would first generate a square grid $ℤ×ℤ$, add all diagonals which go from the bottom left corner to the top right corner (i.e. they are parallel to the line from $(0,0)$ to $(1,1)$) and then apply a linear map which deforms this into a triangular grid.

A possible deformation matrix for this is given by: $\left(\begin{matrix} 1 & \frac{-1}{2} \\ 0 & \frac{\sqrt{3}}{2} \end{matrix}\right)$.

The coefficients are $\frac{1}{2}$ and $\frac{\sqrt{3}}{2}$ because those are height and half width respectively of an unit equilateral triangle.