Transforming a Hexagonal Grid into Triangles: Indexing Alternating Up and Down Triangles

    This article describes an indexing scheme for a single strip of triangles in a triangulated hexagonal grid, where each hexagon is split into six triangles. The triangles alternate between up and down orientations, so the vertical neighbor offset depends only on the triangle's type. The article covers the parity rule, linear storage with a sentinel border that moves boundary checks out of the inner loop, a C++ implementation, validation methods, and a comparison with axial and cube coordinates.

    Introduction: Defining the Scope

    Splitting each hexagon in a hexagonal grid into six triangles, with the center as a shared vertex, is a common technique in map rendering and grid subdivision. After splitting, the triangles inside each hexagon connect to each other and to the triangles in adjacent hexagons. This article covers only one layer of that structure: a row of triangles joined end to end, with the triangles alternating between up-pointing (△) and down-pointing (▽) orientations.

    This article does not address the polar regions, and it does not cover converting hexagon coordinates to triangle geometry. The adjacency described here is combinatorial. It identifies which triangle is next to which, not the exact position of each triangle on a plane.

    1. The Problem: Why the Vertical Offset Is Not Fixed

    In a common offset coordinate array for hexagons, the column of a cell’s south neighbor depends on whether its row is odd or even. Odd and even rows are offset by half a cell, so traversal code must branch on the row index or consult a small lookup table.

    Triangle strips behave similarly but follow a more regular pattern. The vertical neighbors of △ and ▽ point in opposite directions. The base of a △ connects to the next row, and the top edge of a ▽ connects to the previous row. If you can tell whether a triangle is △ or ▽, you immediately know its vertical neighbor. The key question is whether this check can be done with simple integer arithmetic, without relying on an extra table.

    2. Model Definition

    Let the strip have R rows, with M triangles in each row. The triangle in row r and column c is written (r, c), where 0 ≤ r < R and 0 ≤ c < M.

    The type of each triangle is determined by parity:

    • When (r + c) is even, the triangle is △.
    • When (r + c) is odd, the triangle is ▽.

    Within a row, (r, c-1) and (r, c+1) are left and right neighbors. They share a slanted edge. The vertical neighbor rules are:

    • The base of △ at (r, c) connects to (r+1, c), provided that r+1 < R.
    • The top edge of ▽ at (r, c) connects to (r-1, c), provided that r-1 ≥ 0.

    These rules are symmetric. If (r, c) is △, then the parity of (r+1) + c is opposite to that of r + c, so (r+1, c) is ▽. Its vertical neighbor is (r, c). The reverse also holds.

    3. Linear Storage and Offsets

    Store the two-dimensional array in row-major order as a one-dimensional array, with index id = r × M + c. Then:

    • The offsets for left and right neighbors are -1 and +1.
    • The offset for vertical neighbors is +M for △ and -M for ▽.

    The offsets are constants, but using this layout directly still goes out of bounds. The ▽ in row 0 gets a negative index, and the △ in the last row goes past the end of the array. The leftmost and rightmost cells in each row also read data from adjacent rows. This layout therefore still requires bounds checks.

    4. Sentinel Border: Moving Boundary Checks Out of the Inner Loop

    The fix is to add a border around the array. The logical range stays R × M, but physical storage becomes (R+2) × (M+2), with row width W = M + 2. Logical coordinate (r, c) maps to physical index (r+1) × W + (c+1). The cells in the border are called sentinels. They are never written, and they are initialized to -1.

    With the border in place:

    • The left and right offsets remain ±1. The left neighbor of the leftmost column lands on a sentinel column.
    • The vertical offsets are ±W. The ▽ in row 0 lands in the top sentinel row, and the △ in the last row lands in the bottom sentinel row.
    • The inner loop no longer needs index checks. Reading a sentinel returns -1, and the caller decides that there is no neighbor.

    This approach only moves the branch from index calculation into data checks. The caller still has to check whether the return value is -1. It reduces the branches in index calculation, but it does not remove all branches.

    The memory cost is small. For a 1000 × 1000 strip, the physical size is 1002 × 1002, which uses about 0.4% more space.

    The code below implements this layout and includes a validation function.

    1. #include <vector>
    2. // Triangle strip: R rows, with M triangles per row.
    3. // Physical storage is (R+2) x (M+2). The outer ring holds sentinels,
    4. // initialized to -1 and never written.
    5. class TriStrip {
    6. public:
    7. TriStrip(int rows, int cols)
    8. : R_(rows), M_(cols), W_(cols + 2),
    9. data_(static_cast<std::size_t>(rows + 2) * (cols + 2), -1) {}
    10. // Up-pointing (△) when (r + c) is even, otherwise down-pointing (▽)
    11. static bool is_up(int r, int c) { return ((r + c) & 1) == 0; }
    12. // Logical coordinates to physical index
    13. int index(int r, int c) const { return (r + 1) * W_ + (c + 1); }
    14. // Vertical neighbor offset: △ points to the next row, ▽ points to the previous row
    15. int vertical_offset(int r, int c) const { return is_up(r, c) ? W_ : -W_; }
    16. void set(int r, int c, int value) { data_[index(r, c)] = value; }
    17. int get(int r, int c) const { return data_[index(r, c)]; }
    18. // Neighbor values. Out-of-bounds access returns the sentinel value -1.
    19. int left_neighbor(int r, int c) const { return data_[index(r, c) - 1]; }
    20. int right_neighbor(int r, int c) const { return data_[index(r, c) + 1]; }
    21. int vertical_neighbor(int r, int c) const {
    22. return data_[index(r, c) + vertical_offset(r, c)];
    23. }
    24. int rows() const { return R_; }
    25. int cols() const { return M_; }
    26. private:
    27. int R_;
    28. int M_;
    29. int W_;
    30. std::vector<int> data_;
    31. };
    32. // Checks vertical adjacency: neighboring triangles have opposite types and point
    33. // back at each other, and the physical index difference matches the offset.
    34. bool validate_vertical(const TriStrip& s) {
    35. for (int r = 0; r < s.rows(); ++r) {
    36. for (int c = 0; c < s.cols(); ++c) {
    37. const int dir = TriStrip::is_up(r, c) ? 1 : -1;
    38. const int rn = r + dir;
    39. if (rn < 0 || rn >= s.rows()) continue; // Top or bottom edge of the strip, no vertical neighbor
    40. if (TriStrip::is_up(rn, c) == TriStrip::is_up(r, c)) return false;
    41. if (rn + (TriStrip::is_up(rn, c) ? 1 : -1) != r) return false;
    42. if (s.index(rn, c) - s.index(r, c) != s.vertical_offset(r, c)) return false;
    43. }
    44. }
    45. return true;
    46. }

    Two points about the code need attention. First, validate_vertical still uses logical bounds checks. It is a test utility and not part of the inner traversal loop. Second, users of TriStrip must make sure they write only to cells in the logical range. Otherwise they will overwrite the sentinels.

    5. Verification Methods

    Formulas alone are easy to get wrong, so complete at least the following checks.