algorithm to generate 2D magic hexagon lattice

Question

I'm trying to generate a 2D magic hexagonal lattice ,(i.e i need to generate the coordinates of the points in C language) see attached image, the figure look like an onion structure where theres hexagons inside larger one and so on.

Does anyone have an idea?

note:its okay if anyone have an answer in other laguages I just need to have a look so I can start building my own code. thanks in advance.

      void generate_particles(void)
      {/* Generates the particle - positions and charge
      Here it indicated to use the hexagonal referential !!*/
      int    i,j;
      int    n=3; /*n represent the nth centered hex number given by the formula 3*n(n- )+1*/
      double b;
      b=(1.0/sqrt(sqrt(3)))*sqrt(2.0/par.NA);
      /* b=1.0;*/


      fprintf(stderr,"Distributing %d particles  on the hexagonal lattice'...", par.N);

      for (i=0;i<n-1;i++)
     {
      coo[i][0]= (sqrt(3)*i*b)/2.0;
       for (j=0;j<(2*n-i-1);j++)
       {
        coo [i][1]= (-(2*n-i-2)*b)/2.0 + j*b;

       fprintf(stderr," %lf    %lf\n",coo[i][0],coo[i][1]);

        /*plot the points with coordinate (x,y) here*/
       if(coo[i][0]!=0)
           {     
       fprintf(stderr," %lf    %lf\n",-coo[i][0],coo[i][1]);
              /*plot the points with coordinates (-x,y)*/
         }
        }

        }fprintf(stderr," done\n\n");
       }  



        void write_configuration_file(void)
    {/* Writes the binary configuration file '<prefix>_config.<postfix>'
     i.e velocities and coordinates. */

     FILE *fp;
     char  filename[100];
      char  postfix_string[100];
      int   i;

      fprintf(stderr,"Writing configuration file");

     if (postfix >=0 ) {
    if      (postfix <   10) sprintf(postfix_string,"000%d",postfix);
    else if (postfix <  100) sprintf(postfix_string, "00%d",postfix);
    else if (postfix < 1000) sprintf(postfix_string,  "0%d",postfix);
    else if (postfix <10000) sprintf(postfix_string,   "%d",postfix);
    else                     sprintf(postfix_string,  "_%d",postfix);
    } else {
    fprintf(stderr,"\nThe internal postfix is negative.\n\n");
    exit(1);
    }

    sprintf(filename,"%s_config.%s",prefix,postfix_string); 

    fprintf(stderr," %s...", filename);

    if ((fp = fopen(filename,"r")) != NULL) {
    fprintf(stderr,"\nFile '%s' already exists. Don't want to overwrite it.\n\n",filename);
    fclose(fp);
    exit(1);
    }

     if ((fp = fopen(filename,"w")) == NULL) {
      fprintf(stderr,"Could not create file '%s'.\n\n",filename);
     exit(1);
     }

     /* postfix */
      if (fwrite(&postfix,sizeof(int),1,fp) != 1)
     { fprintf(stderr,"fwrite error 1.\n\n"); exit(1); }

     /* time */
     if (fwrite(&ti,sizeof(int),1,fp) != 1)
     { fprintf(stderr,"fwrite error 2.\n\n"); exit(1); }


     /* x,y coordinates of all particles/charges */

      if (fwrite(coo,sizeof(double) ,2*par.N,fp) != 2*par.N)
       { 
        fprintf(stderr,"fwrite error 4.\n\n"); exit(1); }

        fclose(fp);

        fprintf(stderr," done\n");
        }


and the main program is:

     int main()
    {
    int i;



         printf("\n");
         printf("\n");
          printf("***************************************************************\n");
      printf("* OK LETS GENERATE THE CONFIG FILE FOR MONTE CARLO SIMULATION *\n");
      printf("***************************************************************\n\n");

      read_wishlist();

      init_ran1();

      for (i=0; i<seed; i++) ran1_fast();


      if (par.N > 0) generate_particles();


      write_parameter_file();
      write_configuration_file();
      write_task_file();

      /*final_test();*/

      fprintf(stderr,"\n\nConfiguration successfully generated.\n\n");
    }

ok let me explain my problem,in fact the code you give me before is perfect and I was able to plot the particles in the hexagon in C and matlab but that was just plotting;when I come to simulation things were problamatic each particle have a lable starting from 0 to par.N in my code but the way I write this it was only reading 13 particles which are on the layer 13,so please would you help me find a solution on how to modify this so that each particle have one coordinate thanks in advance.

@MohamedKALLEL first of all in function generate_particles

the coo[i][0] represent the x coordinate and the coo i the y coordinate,just see the generate_particles part forget about the rest it is similar to the one you gave me before but I wrote it with my own language and other variables when I excuate this file the coordinate plotted on the screen are exactly the one I want to start the intial configuration,but here what we do is writing these coordinates in a configuration binary file the problem is that when I'm reading this binary file it seems that the only coordinates printed are from 0 to n-1 n is the layer order,there is a problem which I'm not able to solve maybe in the way I wrote my code,because I have 547 particles but this code is giving me only 13 coordinates I should give every particle a label i.e the 547 particles should have each its own coordinate is this clear ??

Answer 1

int i, j;
float y,x;
float d=1.0;// d is the distance between 2 points as indicated in your schema
for(i=0; i<=(n-1); i++) {
    y = (sqrt(3)*i*d)/2.0;
    for (j = 0; j < (2*n-1-i); j++) {
        x = (-(2*n-i-2)*d)/2.0 + j*d;
        //plot the point with coordinate (x,y) here
        if (y!=0) {
            // plot the point with coordinate (x,-y) here
        }
    }

}

Explanation with schema:

as indicated in your wikipedia link http://en.wikipedia.org/wiki/Centered_hexagonal_number The nth centered hexagonal number is given by the formula

• So for n = 1 the number of points in the hexagon is 1.
• and for n = 2 the number of points in the hexagon is 7.
• and for n = 3 the number of points in the hexagon is 19
• ...

Answer 2

Mathematically, the points are

(j + 2k, sqrt(3)j) L/2

Where j and k are integers, and L is the distance between two of the points (the blue lines in your image).

EDIT:

Here is code to print the (i,j) pairs for the n^th layer:

for(int t=0; t<n ; ++t)
    {
      cout << " (" << t << ", " << n-t << ")" << endl;
      cout << " (" << n << ", " << -t << ")" << endl;
      cout << " (" << n-t << ", " << -n << ")" << endl;
      cout << " (" << -t << ", " << -n+t << ")" << endl;
      cout << " (" << -n << ", " << t << ")" << endl;
      cout << " (" << -n+t << ", " << n << ")" << endl;
    }

Answer 3

The coordinates in polar form are R*exp(i*n*pi/3); where n=0..5.

This maps to x=R*cos(n); y=R*sin(n); n = 0..5 * pi / 3;

This centers the hexagon to origin (x=0, y=0).

The centers of corners of next level hexagons are surprisingly:

a = n*R*( exp(i*n*pi/3) + exp(i*(n+1)*pi/3);
            ___
           /   \
       ___/  b  \
      /   \     /
  ___/  a  \___/
 /   \     /   \
/  x  \___/  b1 \
\     /   \     /
 \___/ a1  \___/
           /   \
          /  b2 \
          \     /
           \___/

From the point 'a' or 'b' one has to iterate down n-1 steps. Those coordinate are then center_a + m*R*exp(i*(n+4)/3) + m*R*exp(i*(n+5)/3)

Answer 4

If you just want the lattice, well, the coordinates are simply those of the first hexagon repeated by horizontal rows and shifted. Draw a couple dozens hexagons and it will be apparent.

The onion reference makes me think that you want to construct a hexagon and then build new hexagons on all of its vertices, and then build another generation (the third) of hexagons on the outer border of the second.

You can do it by brute force.

• Draw the first hexagon (see e.g. Aki Suihkonen's answer).
• Place all of its vertices in a closed list.
• For all couples of consecutive vertices (when you are at the last point, the "next" is the first), build an equilateral triangle by subtracting (or adding, depending if you walk your hexagon sunwise or widdershins) 120 degrees to the baseline made by the first two points.
• You get as many points as there were edges (couples of vertices).
• These points are the centers of a new generation of hexagons. You still have the old list of edges to avoid redrawing already extant edges. Draw these hexagons and store their vertices (watch for duplicates on joined edges).
• The new list of vertices replaces the first.
• Wash, rinse, repeat.

There might also be possibly a formula - try looking for "hexagon tessellations".

UPDATE: Another possibility is to build with the same method a grid of triangles and combine them in hexagons (see here for the pretty graphics). Once you have the six triangles that make up a hexagon, there are quick algorithms to floodfill triangles; you may adapt those to enumerate the inner points. There are also quick methods to check whether a point is inside a triangle.