Algorithm to generate a hexagonal grid with coordinate system

Question

I am trying to roll up 19 lines of code into a single for loop, but I am feeling a bit stumped. The reason I ask, is because I want the grid to be other sizes instead of 5.

In Main::drawHexGridAdvanced(), I am trying to deduce the similarities between each line as opposed to Main::drawHexGridBasic() where I am hard-coding values.

I am not sure how to determine the start of the x for each column in each row, because the pattern for n == 5 is 0, -1 -2 -2 -2 after that each consecutive column is just incremented except when the loop reaches the halfway point...

Information and Understanding

`n` must be odd

n | columns-per row sequence
--+-------------------------
3 | 2 3 2
5 | 3 4 5 4 3
7 | 4 5 6 7 6 5 4
9 | 5 6 7 8 9 8 7 6 5

int[] columns(int n) {
    int[] columns = new int[n];
    int h = (int) java.lang.Math.floor(n / 2);
        
    for (int i = 0; i < n; i++) {
        columns[i] = n - java.lang.Math.abs(i - h);
    }

    return columns;
}

// Prints [5, 6, 7, 8, 9, 8, 7, 6, 5]       
System.out.println(java.util.Arrays.toString(columns(n)));

Python looks so much more elegant:

def hex(n):
    for x in [(n-abs(x-int(n/2))) for x in range(n)]:
        for y in range(n-x):
            print(' ', end=''),
        for y in range(x):
            print(' * ', end=''),
        print('')
    
#     *   *   *  
#   *   *   *   *  
# *   *   *   *   *  
#   *   *   *   *  
#     *   *   *

Here is my expected output:

enter image description here

Main.java

package Foo.Bar.Hexagon;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Stroke;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class Main extends JPanel {

    private static final long serialVersionUID = 1L;
    private final int WIDTH = 1200;
    private final int HEIGHT = 800;

    private final int W2 = WIDTH / 2;
    private final int H2 = HEIGHT / 2;
    
    private Font font = new Font("Arial", Font.BOLD, 24);
    FontMetrics metrics;
    
    public Main() {
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
    }

    @Override
    public void paintComponent(Graphics g) {
        Graphics2D g2d = (Graphics2D) g;

        g2d.setStroke(new BasicStroke(4.0f, BasicStroke.CAP_SQUARE, BasicStroke.JOIN_MITER));
        g2d.setFont(font);
        metrics = g.getFontMetrics();
        
        drawCircle(g2d, W2, H2, 660, true, true, 0x4488FF, 0);
        
        drawHexGridAdvanced(g2d, 5, 60);
    }
    
    private void drawHexGridAdvanced(Graphics g, int n, int r) {
        double ang30 = Math.toRadians(30);
        double xOff = Math.cos(ang30) * r;
        double yOff = Math.sin(ang30) * r;
        int h = n / 2;
        int cols = 0;
        int row = 0;
        int col = 0;
        
        cols = 3;
        row = 0; col = 0;
        drawHex(g, +0, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);
        row = 0; col = 1;
        drawHex(g, +1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);
        row = 0; col = 2;
        drawHex(g, +2, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);
        
        cols = 4;
        row = 1; col = 0;
        drawHex(g, -1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);
        row = 1; col = 1;
        drawHex(g, +0, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);
        row = 1; col = 2;
        drawHex(g, +1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);
        row = 1; col = 3;
        drawHex(g, +2, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);
        
        cols = 5;
        row = 2; col = 0;
        drawHex(g, -2, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 2; col = 1;
        drawHex(g, -1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 2; col = 2;
        drawHex(g, +0, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 2; col = 3;
        drawHex(g, +1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 2; col = 4;
        drawHex(g, +2, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        
        cols = 4;
        row = 3; col = 0;
        drawHex(g, -2, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 3; col = 1;
        drawHex(g, -1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 3; col = 2;
        drawHex(g, +0, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 3; col = 3;
        drawHex(g, +1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        
        cols = 3;
        row = 4; col = 0;
        drawHex(g, -2, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 4; col = 1;
        drawHex(g, -1, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
        row = 4; col = 2;
        drawHex(g, +0, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);
    }
    
    private void drawHexGridBasic(Graphics g, int n, int r) {
        double ang30 = Math.toRadians(30);
        double xOff = Math.cos(ang30) * r;
        double yOff = Math.sin(ang30) * r;
        int h = n / 2;
        
        drawHex(g, +0, -2,  W2 - (int) (xOff * 2), H2 - (int) (yOff * 6), r);
        drawHex(g, +1, -2,  W2 - (int) (xOff * 0), H2 - (int) (yOff * 6), r);
        drawHex(g, +2, -2,  W2 + (int) (xOff * 2), H2 - (int) (yOff * 6), r);
        
        drawHex(g, -1, -1,  W2 - (int) (xOff * 3), H2 - (int) (yOff * 3), r);
        drawHex(g, +0, -1,  W2 - (int) (xOff * 1), H2 - (int) (yOff * 3), r);
        drawHex(g, +1, -1,  W2 + (int) (xOff * 1), H2 - (int) (yOff * 3), r);
        drawHex(g, +2, -1,  W2 + (int) (xOff * 3), H2 - (int) (yOff * 3), r);
        
        drawHex(g, -2, +0,  W2 - (int) (xOff * 4), H2 - (int) (yOff * 0), r);
        drawHex(g, -1, +0,  W2 - (int) (xOff * 2), H2 - (int) (yOff * 0), r);
        drawHex(g, +0, +0,  W2 - (int) (xOff * 0), H2 - (int) (yOff * 0), r);
        drawHex(g, +1, +0,  W2 + (int) (xOff * 2), H2 - (int) (yOff * 0), r);
        drawHex(g, +2, +0,  W2 + (int) (xOff * 4), H2 - (int) (yOff * 0), r);
        
        drawHex(g, -2, +1,  W2 - (int) (xOff * 3), H2 + (int) (yOff * 3), r);
        drawHex(g, -1, +1,  W2 - (int) (xOff * 1), H2 + (int) (yOff * 3), r);
        drawHex(g, +0, +1,  W2 + (int) (xOff * 1), H2 + (int) (yOff * 3), r);
        drawHex(g, +1, +1,  W2 + (int) (xOff * 3), H2 + (int) (yOff * 3), r);
        
        drawHex(g, -2, +2,  W2 - (int) (xOff * 2), H2 + (int) (yOff * 6), r);
        drawHex(g, -1, +2,  W2 - (int) (xOff * 0), H2 + (int) (yOff * 6), r);
        drawHex(g, +0, +2,  W2 + (int) (xOff * 2), H2 + (int) (yOff * 6), r);
    }
    
    private void drawHex(Graphics g, int posX, int posY, int x, int y, int r) {
        Hexagon hex = new Hexagon(x, y, r);
        String text = String.format("%s : %s", coord(posX), coord(posY));
        int w = metrics.stringWidth(text);
        int h = metrics.getHeight();
        
        g.setColor(new Color(0x008844));
        g.fillPolygon(hex);
        g.setColor(new Color(0xFFDD88));
        g.drawPolygon(hex);
        g.setColor(new Color(0xFFFFFF));
        g.drawString(text, x - w/2, y + h/2);
    }
    
    private String coord(int value) {
        return (value > 0 ? "+" : "") + Integer.toString(value);
    }
 
    public void drawCircle(Graphics2D g, int x, int y, int diameter,
            boolean centered, boolean filled, int colorValue, int lineThickness) {
        drawOval(g, x, y, diameter, diameter, centered, filled, colorValue, lineThickness);
    }

    public void drawOval(Graphics2D g, int x, int y, int width, int height,
            boolean centered, boolean filled, int colorValue, int lineThickness) {
        // Store before changing.
        Stroke tmpS = g.getStroke();
        Color tmpC = g.getColor();

        g.setColor(new Color(colorValue));
        g.setStroke(new BasicStroke(lineThickness, BasicStroke.CAP_ROUND,
                BasicStroke.JOIN_ROUND));

        int x2 = centered ? x - (width / 2) : x;
        int y2 = centered ? y - (height / 2) : y;

        if (filled)
            g.fillOval(x2, y2, width, height);
        else
            g.drawOval(x2, y2, width, height);

        // Set values to previous when done.
        g.setColor(tmpC);
        g.setStroke(tmpS);
    }

    public static void main(String[] args) {
        JFrame f = new JFrame();
        Main p = new Main();

        f.setContentPane(p);
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.pack();
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }
}

Haxagon.java

package Foo.Bar.Hexagon;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.Polygon;
import java.awt.Stroke;

public class Hexagon extends Polygon {

    private static final long serialVersionUID = 1L;

    public static final int SIDES = 6;

    private Point[] points = new Point[SIDES];
    private Point center = new Point(0, 0);
    private int radius;
    private int rotation = 90;

    public Hexagon(Point center, int radius) {
        npoints = SIDES;
        xpoints = new int[SIDES];
        ypoints = new int[SIDES];
        
        this.center = center;
        this.radius = radius;
        
        updatePoints();
    }
    
    public Hexagon(int x, int y, int radius) {
        this(new Point(x, y), radius);
    }
    
    public int getRadius() {
        return radius;
    }

    public void setRadius(int radius) {
        this.radius = radius;

        updatePoints();
    }
    
    public int getRotation() {
        return rotation;
    }
    
    public void setRotation(int rotation) {
        this.rotation = rotation;
        
        updatePoints();
    }
    
    public void setCenter(Point center) {
        this.center = center;
        
        updatePoints();
    }
    
    public void setCenter(int x, int y) {
        setCenter(new Point(x, y));
    }

    private double findAngle(double fraction) {
        return fraction * Math.PI * 2 + Math.toRadians((rotation + 180) % 360);
    }
    
    private Point findPoint(double angle) {
        int x = (int) (center.x + Math.cos(angle) * radius);
        int y = (int) (center.y + Math.sin(angle) * radius);
        
        return new Point(x, y);
    }
    
    protected void updatePoints() {
        for (int p = 0; p < SIDES; p++) {
            double angle = findAngle((double) p / SIDES);
            Point point = findPoint(angle);
            xpoints[p] = point.x;
            ypoints[p] = point.y;
            points[p] = point;
            System.out.printf("%d. (%d, %d)\n", p, point.x, point.y);
        }
    }
    
    public void drawPolygon(Graphics2D g, int x, int y, int lineThickness, int colorValue, boolean filled) {
        // Store before changing.
        Stroke tmpS = g.getStroke();
        Color tmpC = g.getColor();

        g.setColor(new Color(colorValue));
        g.setStroke(new BasicStroke(lineThickness, BasicStroke.CAP_SQUARE, BasicStroke.JOIN_MITER));

        if (filled)
            g.fillPolygon(xpoints, ypoints, npoints);
        else
            g.drawPolygon(xpoints, ypoints, npoints);

        // Set values to previous when done.
        g.setColor(tmpC);
        g.setStroke(tmpS);
    }
}

by convention in Java package names should be in lowercase. package Foo.Bar.Hexagon would be more idiomatic if it was package foo.bar.hexagon — TacticalCoder
– TacticalCoder, Commented Dec 23, 2013 at 17:19

Community · Accepted Answer · 2017-05-23 12:34:06Z

I have figured it out, thanks for the feedback Tanmay.

I noticed that the y-offset was incorrect for n - cols and should be row - half instead.

Below is the most comprehensive and compact code I could obtain. Although it is preferred to enter an odd integer for the size, you could enter a positive value. I also added a padding to the offset.

This if-conditional still troubles me: int xLbl = row < half ? col - row : col - half;

private void drawHexGridLoop(Graphics g, Point origin, int size, int radius, int padding) {
    double ang30 = Math.toRadians(30);
    double xOff = Math.cos(ang30) * (radius + padding);
    double yOff = Math.sin(ang30) * (radius + padding);
    int half = size / 2;

    for (int row = 0; row < size; row++) {
        int cols = size - java.lang.Math.abs(row - half);

        for (int col = 0; col < cols; col++) {
            int xLbl = row < half ? col - row : col - half;
            int yLbl = row - half;
            int x = (int) (origin.x + xOff * (col * 2 + 1 - cols));
            int y = (int) (origin.y + yOff * (row - half) * 3);

            drawHex(g, xLbl, yLbl, x, y, radius);
        }
    }
}

enter image description here

Main.java

import java.awt.*;
import javax.swing.*;

public class Main extends JPanel {
    private static final long serialVersionUID = 1L;
    private final int WIDTH = 1200;
    private final int HEIGHT = 800;

    private Font font = new Font("Arial", Font.BOLD, 18);
    FontMetrics metrics;

    public Main() {
        setPreferredSize(new Dimension(WIDTH, HEIGHT));
    }

    @Override
    public void paintComponent(Graphics g) {
        Graphics2D g2d = (Graphics2D) g;
        Point origin = new Point(WIDTH / 2, HEIGHT / 2);

        g2d.setStroke(new BasicStroke(4.0f, BasicStroke.CAP_SQUARE, BasicStroke.JOIN_MITER));
        g2d.setFont(font);
        metrics = g.getFontMetrics();

        drawCircle(g2d, origin, 380, true, true, 0x4488FF, 0);
        drawHexGridLoop(g2d, origin, 7, 50, 8);
    }

    private void drawHexGridLoop(Graphics g, Point origin, int size, int radius, int padding) {
        double ang30 = Math.toRadians(30);
        double xOff = Math.cos(ang30) * (radius + padding);
        double yOff = Math.sin(ang30) * (radius + padding);
        int half = size / 2;

        for (int row = 0; row < size; row++) {
            int cols = size - java.lang.Math.abs(row - half);

            for (int col = 0; col < cols; col++) {
                int xLbl = row < half ? col - row : col - half;
                int yLbl = row - half;
                int x = (int) (origin.x + xOff * (col * 2 + 1 - cols));
                int y = (int) (origin.y + yOff * (row - half) * 3);

                drawHex(g, xLbl, yLbl, x, y, radius);
            }
        }
    }

    private void drawHex(Graphics g, int posX, int posY, int x, int y, int r) {
        Graphics2D g2d = (Graphics2D) g;

        Hexagon hex = new Hexagon(x, y, r);
        String text = String.format("%s : %s", coord(posX), coord(posY));
        int w = metrics.stringWidth(text);
        int h = metrics.getHeight();

        hex.draw(g2d, x, y, 0, 0x008844, true);
        hex.draw(g2d, x, y, 4, 0xFFDD88, false);

        g.setColor(new Color(0xFFFFFF));
        g.drawString(text, x - w/2, y + h/2);
    }

    private String coord(int value) {
        return (value > 0 ? "+" : "") + Integer.toString(value);
    }

    public void drawCircle(Graphics2D g, Point origin, int radius,
            boolean centered, boolean filled, int colorValue, int lineThickness) {
        // Store before changing.
        Stroke tmpS = g.getStroke();
        Color tmpC = g.getColor();

        g.setColor(new Color(colorValue));
        g.setStroke(new BasicStroke(lineThickness, BasicStroke.CAP_ROUND,
                BasicStroke.JOIN_ROUND));

        int diameter = radius * 2;
        int x2 = centered ? origin.x - radius : origin.x;
        int y2 = centered ? origin.y - radius : origin.y;

        if (filled)
            g.fillOval(x2, y2, diameter, diameter);
        else
            g.drawOval(x2, y2, diameter, diameter);

        // Set values to previous when done.
        g.setColor(tmpC);
        g.setStroke(tmpS);
    }

    public static void main(String[] args) {
        JFrame f = new JFrame();
        Main p = new Main();

        f.setContentPane(p);
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.pack();
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }
}

Hexagon.java

import java.awt.*;

public class Hexagon extends Polygon {

    private static final long serialVersionUID = 1L;

    public static final int SIDES = 6;

    private Point[] points = new Point[SIDES];
    private Point center = new Point(0, 0);
    private int radius;
    private int rotation = 90;

    public Hexagon(Point center, int radius) {
        npoints = SIDES;
        xpoints = new int[SIDES];
        ypoints = new int[SIDES];

        this.center = center;
        this.radius = radius;

        updatePoints();
    }

    public Hexagon(int x, int y, int radius) {
        this(new Point(x, y), radius);
    }

    public int getRadius() {
        return radius;
    }

    public void setRadius(int radius) {
        this.radius = radius;

        updatePoints();
    }

    public int getRotation() {
        return rotation;
    }

    public void setRotation(int rotation) {
        this.rotation = rotation;

        updatePoints();
    }

    public void setCenter(Point center) {
        this.center = center;

        updatePoints();
    }

    public void setCenter(int x, int y) {
        setCenter(new Point(x, y));
    }

    private double findAngle(double fraction) {
        return fraction * Math.PI * 2 + Math.toRadians((rotation + 180) % 360);
    }

    private Point findPoint(double angle) {
        int x = (int) (center.x + Math.cos(angle) * radius);
        int y = (int) (center.y + Math.sin(angle) * radius);

        return new Point(x, y);
    }

    protected void updatePoints() {
        for (int p = 0; p < SIDES; p++) {
            double angle = findAngle((double) p / SIDES);
            Point point = findPoint(angle);
            xpoints[p] = point.x;
            ypoints[p] = point.y;
            points[p] = point;
        }
    }

    public void draw(Graphics2D g, int x, int y, int lineThickness, int colorValue, boolean filled) {
        // Store before changing.
        Stroke tmpS = g.getStroke();
        Color tmpC = g.getColor();

        g.setColor(new Color(colorValue));
        g.setStroke(new BasicStroke(lineThickness, BasicStroke.CAP_SQUARE, BasicStroke.JOIN_MITER));

        if (filled)
            g.fillPolygon(xpoints, ypoints, npoints);
        else
            g.drawPolygon(xpoints, ypoints, npoints);

        // Set values to previous when done.
        g.setColor(tmpC);
        g.setStroke(tmpS);
    }
}

You aren't by chance developing a Settlers Of Catan-style game, are you? That's how I found this... lol.
@ShoeLace1291 Yeah, I was trying to some up with an algorithm :)

Tanmay Patil · Accepted Answer · 2013-12-24 00:33:57Z

5

Even more compact code is possible, but this gives output without repetition and without if branching.

for (row = 0; row < h; row ++) {
    cols = h + row + 1;
    for (col = 0; col < cols; col++) {
        drawHex(g, col - row, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 - yOff * (n - cols) * 3), r);                
    }
}
for (row = h; row < n; row++) {
    cols = n - row + h;
    for (col = 0; col < cols; col++) {
        drawHex(g, -h + col, -h + row, (int) (W2 + xOff * (-cols + (col * 2 + 1))), (int) (H2 + yOff * (n - cols) * 3), r);                
    }
}

Hope this helps.

edited Dec 24, 2013 at 0:33

answered Dec 23, 2013 at 0:14

Tanmay Patil

7,0772 gold badges27 silver badges45 bronze badges

2 Comments

Mr. Polywhirl Over a year ago

I edited my post, I finally came up with the series for columns... Do you want to revise your answer?

Mr. Polywhirl Over a year ago

Thanks for your help, I figured it out.

jwize · Accepted Answer · 2022-10-01 06:26:34Z

Here is a simple answer for achieving the same shape in typescript

   const rings = 5;
   const w = this.hexagons.width;
   const h = this.hexagons.height;


   const funcs = [
    (x:number, y:number) => new fabric.Point( x + ( w / 2 ) ,  y + h * .75),
    (x:number, y:number) => new fabric.Point( x - ( w / 2 ), y + h * .75),
    (x:number, y:number) => new fabric.Point( x - w , y),
    (x:number, y:number) => new fabric.Point( x - ( w / 2), y + h * -.75),
    (x:number, y:number) => new fabric.Point( x + ( w / 2) ,  y + h * -.75),
    (x:number, y:number) => new fabric.Point( x + w , y)
   ];

   for (let i = 0; i < rings; i++)
   {
       let current = new fabric.Point(w / 2 * i, h * i * -.75);
       // draw or add to a collection
       this.drawHexagonService.drawHexagon(current); 
       for (let func of funcs )
       {
           for (let j = 0; j < i; j++)
           {
               current = func(current.x, current.y);
               // draw or add to a collection
               this.drawHexagonService.drawHexagon(current); 
           }
       }
   }

Collectives™ on Stack Overflow

Algorithm to generate a hexagonal grid with coordinate system

Information and Understanding

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Information and Understanding

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related