grid.c

   1 /*
   2  * (c) Lambros Lambrou 2008
   3  *
   4  * Code for working with general grids, which can be any planar graph
   5  * with faces, edges and vertices (dots).  Includes generators for a few
   6  * types of grid, including square, hexagonal, triangular and others.
   7  */
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <assert.h>
  13 #include <ctype.h>
  14 #include <math.h>
  15
  16 #include "puzzles.h"
  17 #include "tree234.h"
  18 #include "grid.h"
  19
  20 /* Debugging options */
  21
  22 /*
  23 #define DEBUG_GRID
  24 */
  25
  26 /* ----------------------------------------------------------------------
  27  * Deallocate or dereference a grid
  28  */
  29 void grid_free(grid *g)
  30 {
  31     assert(g->refcount);
  32
  33     g->refcount--;
  34     if (g->refcount == 0) {
  35         int i;
  36         for (i = 0; i < g->num_faces; i++) {
  37             sfree(g->faces[i].dots);
  38             sfree(g->faces[i].edges);
  39         }
  40         for (i = 0; i < g->num_dots; i++) {
  41             sfree(g->dots[i].faces);
  42             sfree(g->dots[i].edges);
  43         }
  44         sfree(g->faces);
  45         sfree(g->edges);
  46         sfree(g->dots);
  47         sfree(g);
  48     }
  49 }
  50
  51 /* Used by the other grid generators.  Create a brand new grid with nothing
  52  * initialised (all lists are NULL) */
  53 static grid *grid_new(void)
  54 {
  55     grid *g = snew(grid);
  56     g->faces = NULL;
  57     g->edges = NULL;
  58     g->dots = NULL;
  59     g->num_faces = g->num_edges = g->num_dots = 0;
  60     g->middle_face = NULL;
  61     g->refcount = 1;
  62     g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
  63     return g;
  64 }
  65
  66 /* Helper function to calculate perpendicular distance from
  67  * a point P to a line AB.  A and B mustn't be equal here.
  68  *
  69  * Well-known formula for area A of a triangle:
  70  *                             /  1   1   1 \
  71  * 2A = determinant of matrix  | px  ax  bx |
  72  *                             \ py  ay  by /
  73  *
  74  * Also well-known: 2A = base * height
  75  *                     = perpendicular distance * line-length.
  76  *
  77  * Combining gives: distance = determinant / line-length(a,b)
  78  */
  79 static double point_line_distance(long px, long py,
  80                                   long ax, long ay,
  81                                   long bx, long by)
  82 {
  83     long det = ax*by - bx*ay + bx*py - px*by + px*ay - ax*py;
  84     double len;
  85     det = max(det, -det);
  86     len = sqrt(SQ(ax - bx) + SQ(ay - by));
  87     return det / len;
  88 }
  89
  90 /* Determine nearest edge to where the user clicked.
  91  * (x, y) is the clicked location, converted to grid coordinates.
  92  * Returns the nearest edge, or NULL if no edge is reasonably
  93  * near the position.
  94  *
  95  * This algorithm is nice and generic, and doesn't depend on any particular
  96  * geometric layout of the grid:
  97  *   Start at any dot (pick one next to middle_face).
  98  *   Walk along a path by choosing, from all nearby dots, the one that is
  99  *   nearest the target (x,y).  Hopefully end up at the dot which is closest
 100  *   to (x,y).  Should work, as long as faces aren't too badly shaped.
 101  *   Then examine each edge around this dot, and pick whichever one is
 102  *   closest (perpendicular distance) to (x,y).
 103  *   Using perpendicular distance is not quite right - the edge might be
 104  *   "off to one side".  So we insist that the triangle with (x,y) has
 105  *   acute angles at the edge's dots.
 106  *
 107  *     edge1
 108  *  *---------*------
 109  *            |
 110  *            |      *(x,y)
 111  *      edge2 |
 112  *            |   edge2 is OK, but edge1 is not, even though
 113  *            |   edge1 is perpendicularly closer to (x,y)
 114  *            *
 115  *
 116  */
 117 grid_edge *grid_nearest_edge(grid *g, int x, int y)
 118 {
 119     grid_dot *cur;
 120     grid_edge *best_edge;
 121     double best_distance = 0;
 122     int i;
 123
 124     cur = g->middle_face->dots[0];
 125
 126     for (;;) {
 127         /* Target to beat */
 128         long dist = SQ((long)cur->x - (long)x) + SQ((long)cur->y - (long)y);
 129         /* Look for nearer dot - if found, store in 'new'. */
 130         grid_dot *new = cur;
 131         int i;
 132         /* Search all dots in all faces touching this dot.  Some shapes
 133          * (such as in Cairo) don't quite work properly if we only search
 134          * the dot's immediate neighbours. */
 135         for (i = 0; i < cur->order; i++) {
 136             grid_face *f = cur->faces[i];
 137             int j;
 138             if (!f) continue;
 139             for (j = 0; j < f->order; j++) {
 140                 long new_dist;
 141                 grid_dot *d = f->dots[j];
 142                 if (d == cur) continue;
 143                 new_dist = SQ((long)d->x - (long)x) + SQ((long)d->y - (long)y);
 144                 if (new_dist < dist) {
 145                     new = d;
 146                     break; /* found closer dot */
 147                 }
 148             }
 149             if (new != cur)
 150                 break; /* found closer dot */
 151         }
 152
 153         if (new == cur) {
 154             /* Didn't find a closer dot among the neighbours of 'cur' */
 155             break;
 156         } else {
 157             cur = new;
 158         }
 159     }
 160     /* 'cur' is nearest dot, so find which of the dot's edges is closest. */
 161     best_edge = NULL;
 162
 163     for (i = 0; i < cur->order; i++) {
 164         grid_edge *e = cur->edges[i];
 165         long e2; /* squared length of edge */
 166         long a2, b2; /* squared lengths of other sides */
 167         double dist;
 168
 169         /* See if edge e is eligible - the triangle must have acute angles
 170          * at the edge's dots.
 171          * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
 172          * so detect acute angles by testing for h^2 < a^2 + b^2 */
 173         e2 = SQ((long)e->dot1->x - (long)e->dot2->x) + SQ((long)e->dot1->y - (long)e->dot2->y);
 174         a2 = SQ((long)e->dot1->x - (long)x) + SQ((long)e->dot1->y - (long)y);
 175         b2 = SQ((long)e->dot2->x - (long)x) + SQ((long)e->dot2->y - (long)y);
 176         if (a2 >= e2 + b2) continue;
 177         if (b2 >= e2 + a2) continue;
 178
 179         /* e is eligible so far.  Now check the edge is reasonably close
 180          * to where the user clicked.  Don't want to toggle an edge if the
 181          * click was way off the grid.
 182          * There is room for experimentation here.  We could check the
 183          * perpendicular distance is within a certain fraction of the length
 184          * of the edge.  That amounts to testing a rectangular region around
 185          * the edge.
 186          * Alternatively, we could check that the angle at the point is obtuse.
 187          * That would amount to testing a circular region with the edge as
 188          * diameter. */
 189         dist = point_line_distance((long)x, (long)y,
 190                                    (long)e->dot1->x, (long)e->dot1->y,
 191                                    (long)e->dot2->x, (long)e->dot2->y);
 192         /* Is dist more than half edge length ? */
 193         if (4 * SQ(dist) > e2)
 194             continue;
 195
 196         if (best_edge == NULL || dist < best_distance) {
 197             best_edge = e;
 198             best_distance = dist;
 199         }
 200     }
 201     return best_edge;
 202 }
 203
 204 /* ----------------------------------------------------------------------
 205  * Grid generation
 206  */
 207
 208 #ifdef DEBUG_GRID
 209 /* Show the basic grid information, before doing grid_make_consistent */
 210 static void grid_print_basic(grid *g)
 211 {
 212     /* TODO: Maybe we should generate an SVG image of the dots and lines
 213      * of the grid here, before grid_make_consistent.
 214      * Would help with debugging grid generation. */
 215     int i;
 216     printf("--- Basic Grid Data ---\n");
 217     for (i = 0; i < g->num_faces; i++) {
 218         grid_face *f = g->faces + i;
 219         printf("Face %d: dots[", i);
 220         int j;
 221         for (j = 0; j < f->order; j++) {
 222             grid_dot *d = f->dots[j];
 223             printf("%s%d", j ? "," : "", (int)(d - g->dots));
 224         }
 225         printf("]\n");
 226     }
 227     printf("Middle face: %d\n", (int)(g->middle_face - g->faces));
 228 }
 229 /* Show the derived grid information, computed by grid_make_consistent */
 230 static void grid_print_derived(grid *g)
 231 {
 232     /* edges */
 233     int i;
 234     printf("--- Derived Grid Data ---\n");
 235     for (i = 0; i < g->num_edges; i++) {
 236         grid_edge *e = g->edges + i;
 237         printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
 238             i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots),
 239             e->face1 ? (int)(e->face1 - g->faces) : -1,
 240             e->face2 ? (int)(e->face2 - g->faces) : -1);
 241     }
 242     /* faces */
 243     for (i = 0; i < g->num_faces; i++) {
 244         grid_face *f = g->faces + i;
 245         int j;
 246         printf("Face %d: faces[", i);
 247         for (j = 0; j < f->order; j++) {
 248             grid_edge *e = f->edges[j];
 249             grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1;
 250             printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1);
 251         }
 252         printf("]\n");
 253     }
 254     /* dots */
 255     for (i = 0; i < g->num_dots; i++) {
 256         grid_dot *d = g->dots + i;
 257         int j;
 258         printf("Dot %d: dots[", i);
 259         for (j = 0; j < d->order; j++) {
 260             grid_edge *e = d->edges[j];
 261             grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1;
 262             printf("%s%d", j ? "," : "", (int)(d2 - g->dots));
 263         }
 264         printf("] faces[");
 265         for (j = 0; j < d->order; j++) {
 266             grid_face *f = d->faces[j];
 267             printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1);
 268         }
 269         printf("]\n");
 270     }
 271 }
 272 #endif /* DEBUG_GRID */
 273
 274 /* Helper function for building incomplete-edges list in
 275  * grid_make_consistent() */
 276 static int grid_edge_bydots_cmpfn(void *v1, void *v2)
 277 {
 278     grid_edge *a = v1;
 279     grid_edge *b = v2;
 280     grid_dot *da, *db;
 281
 282     /* Pointer subtraction is valid here, because all dots point into the
 283      * same dot-list (g->dots).
 284      * Edges are not "normalised" - the 2 dots could be stored in any order,
 285      * so we need to take this into account when comparing edges. */
 286
 287     /* Compare first dots */
 288     da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2;
 289     db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2;
 290     if (da != db)
 291         return db - da;
 292     /* Compare last dots */
 293     da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1;
 294     db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1;
 295     if (da != db)
 296         return db - da;
 297
 298     return 0;
 299 }
 300
 301 /* Input: grid has its dots and faces initialised:
 302  * - dots have (optionally) x and y coordinates, but no edges or faces
 303  * (pointers are NULL).
 304  * - edges not initialised at all
 305  * - faces initialised and know which dots they have (but no edges yet).  The
 306  * dots around each face are assumed to be clockwise.
 307  *
 308  * Output: grid is complete and valid with all relationships defined.
 309  */
 310 static void grid_make_consistent(grid *g)
 311 {
 312     int i;
 313     tree234 *incomplete_edges;
 314     grid_edge *next_new_edge; /* Where new edge will go into g->edges */
 315
 316 #ifdef DEBUG_GRID
 317     grid_print_basic(g);
 318 #endif
 319
 320     /* ====== Stage 1 ======
 321      * Generate edges
 322      */
 323
 324     /* We know how many dots and faces there are, so we can find the exact
 325      * number of edges from Euler's polyhedral formula: F + V = E + 2 .
 326      * We use "-1", not "-2" here, because Euler's formula includes the
 327      * infinite face, which we don't count. */
 328     g->num_edges = g->num_faces + g->num_dots - 1;
 329     g->edges = snewn(g->num_edges, grid_edge);
 330     next_new_edge = g->edges;
 331
 332     /* Iterate over faces, and over each face's dots, generating edges as we
 333      * go.  As we find each new edge, we can immediately fill in the edge's
 334      * dots, but only one of the edge's faces.  Later on in the iteration, we
 335      * will find the same edge again (unless it's on the border), but we will
 336      * know the other face.
 337      * For efficiency, maintain a list of the incomplete edges, sorted by
 338      * their dots. */
 339     incomplete_edges = newtree234(grid_edge_bydots_cmpfn);
 340     for (i = 0; i < g->num_faces; i++) {
 341         grid_face *f = g->faces + i;
 342         int j;
 343         for (j = 0; j < f->order; j++) {
 344             grid_edge e; /* fake edge for searching */
 345             grid_edge *edge_found;
 346             int j2 = j + 1;
 347             if (j2 == f->order)
 348                 j2 = 0;
 349             e.dot1 = f->dots[j];
 350             e.dot2 = f->dots[j2];
 351             /* Use del234 instead of find234, because we always want to
 352              * remove the edge if found */
 353             edge_found = del234(incomplete_edges, &e);
 354             if (edge_found) {
 355                 /* This edge already added, so fill out missing face.
 356                  * Edge is already removed from incomplete_edges. */
 357                 edge_found->face2 = f;
 358             } else {
 359                 assert(next_new_edge - g->edges < g->num_edges);
 360                 next_new_edge->dot1 = e.dot1;
 361                 next_new_edge->dot2 = e.dot2;
 362                 next_new_edge->face1 = f;
 363                 next_new_edge->face2 = NULL; /* potentially infinite face */
 364                 add234(incomplete_edges, next_new_edge);
 365                 ++next_new_edge;
 366             }
 367         }
 368     }
 369     freetree234(incomplete_edges);
 370
 371     /* ====== Stage 2 ======
 372      * For each face, build its edge list.
 373      */
 374
 375     /* Allocate space for each edge list.  Can do this, because each face's
 376      * edge-list is the same size as its dot-list. */
 377     for (i = 0; i < g->num_faces; i++) {
 378         grid_face *f = g->faces + i;
 379         int j;
 380         f->edges = snewn(f->order, grid_edge*);
 381         /* Preload with NULLs, to help detect potential bugs. */
 382         for (j = 0; j < f->order; j++)
 383             f->edges[j] = NULL;
 384     }
 385
 386     /* Iterate over each edge, and over both its faces.  Add this edge to
 387      * the face's edge-list, after finding where it should go in the
 388      * sequence. */
 389     for (i = 0; i < g->num_edges; i++) {
 390         grid_edge *e = g->edges + i;
 391         int j;
 392         for (j = 0; j < 2; j++) {
 393             grid_face *f = j ? e->face2 : e->face1;
 394             int k, k2;
 395             if (f == NULL) continue;
 396             /* Find one of the dots around the face */
 397             for (k = 0; k < f->order; k++) {
 398                 if (f->dots[k] == e->dot1)
 399                     break; /* found dot1 */
 400             }
 401             assert(k != f->order); /* Must find the dot around this face */
 402
 403             /* Labelling scheme: as we walk clockwise around the face,
 404              * starting at dot0 (f->dots[0]), we hit:
 405              * (dot0), edge0, dot1, edge1, dot2,...
 406              *
 407              *     0
 408              *  0-----1
 409              *        |
 410              *        |1
 411              *        |
 412              *  3-----2
 413              *     2
 414              *
 415              * Therefore, edgeK joins dotK and dot{K+1}
 416              */
 417
 418             /* Around this face, either the next dot or the previous dot
 419              * must be e->dot2.  Otherwise the edge is wrong. */
 420             k2 = k + 1;
 421             if (k2 == f->order)
 422                 k2 = 0;
 423             if (f->dots[k2] == e->dot2) {
 424                 /* dot1(k) and dot2(k2) go clockwise around this face, so add
 425                  * this edge at position k (see diagram). */
 426                 assert(f->edges[k] == NULL);
 427                 f->edges[k] = e;
 428                 continue;
 429             }
 430             /* Try previous dot */
 431             k2 = k - 1;
 432             if (k2 == -1)
 433                 k2 = f->order - 1;
 434             if (f->dots[k2] == e->dot2) {
 435                 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
 436                 assert(f->edges[k2] == NULL);
 437                 f->edges[k2] = e;
 438                 continue;
 439             }
 440             assert(!"Grid broken: bad edge-face relationship");
 441         }
 442     }
 443
 444     /* ====== Stage 3 ======
 445      * For each dot, build its edge-list and face-list.
 446      */
 447
 448     /* We don't know how many edges/faces go around each dot, so we can't
 449      * allocate the right space for these lists.  Pre-compute the sizes by
 450      * iterating over each edge and recording a tally against each dot. */
 451     for (i = 0; i < g->num_dots; i++) {
 452         g->dots[i].order = 0;
 453     }
 454     for (i = 0; i < g->num_edges; i++) {
 455         grid_edge *e = g->edges + i;
 456         ++(e->dot1->order);
 457         ++(e->dot2->order);
 458     }
 459     /* Now we have the sizes, pre-allocate the edge and face lists. */
 460     for (i = 0; i < g->num_dots; i++) {
 461         grid_dot *d = g->dots + i;
 462         int j;
 463         assert(d->order >= 2); /* sanity check */
 464         d->edges = snewn(d->order, grid_edge*);
 465         d->faces = snewn(d->order, grid_face*);
 466         for (j = 0; j < d->order; j++) {
 467             d->edges[j] = NULL;
 468             d->faces[j] = NULL;
 469         }
 470     }
 471     /* For each dot, need to find a face that touches it, so we can seed
 472      * the edge-face-edge-face process around each dot. */
 473     for (i = 0; i < g->num_faces; i++) {
 474         grid_face *f = g->faces + i;
 475         int j;
 476         for (j = 0; j < f->order; j++) {
 477             grid_dot *d = f->dots[j];
 478             d->faces[0] = f;
 479         }
 480     }
 481     /* Each dot now has a face in its first slot.  Generate the remaining
 482      * faces and edges around the dot, by searching both clockwise and
 483      * anticlockwise from the first face.  Need to do both directions,
 484      * because of the possibility of hitting the infinite face, which
 485      * blocks progress.  But there's only one such face, so we will
 486      * succeed in finding every edge and face this way. */
 487     for (i = 0; i < g->num_dots; i++) {
 488         grid_dot *d = g->dots + i;
 489         int current_face1 = 0; /* ascends clockwise */
 490         int current_face2 = 0; /* descends anticlockwise */
 491
 492         /* Labelling scheme: as we walk clockwise around the dot, starting
 493          * at face0 (d->faces[0]), we hit:
 494          * (face0), edge0, face1, edge1, face2,...
 495          *
 496          *       0
 497          *       |
 498          *    0  |  1
 499          *       |
 500          *  -----d-----1
 501          *       |
 502          *       |  2
 503          *       |
 504          *       2
 505          *
 506          * So, for example, face1 should be joined to edge0 and edge1,
 507          * and those edges should appear in an anticlockwise sense around
 508          * that face (see diagram). */
 509
 510         /* clockwise search */
 511         while (TRUE) {
 512             grid_face *f = d->faces[current_face1];
 513             grid_edge *e;
 514             int j;
 515             assert(f != NULL);
 516             /* find dot around this face */
 517             for (j = 0; j < f->order; j++) {
 518                 if (f->dots[j] == d)
 519                     break;
 520             }
 521             assert(j != f->order); /* must find dot */
 522
 523             /* Around f, required edge is anticlockwise from the dot.  See
 524              * the other labelling scheme higher up, for why we subtract 1
 525              * from j. */
 526             j--;
 527             if (j == -1)
 528                 j = f->order - 1;
 529             e = f->edges[j];
 530             d->edges[current_face1] = e; /* set edge */
 531             current_face1++;
 532             if (current_face1 == d->order)
 533                 break;
 534             else {
 535                 /* set face */
 536                 d->faces[current_face1] =
 537                     (e->face1 == f) ? e->face2 : e->face1;
 538                 if (d->faces[current_face1] == NULL)
 539                     break; /* cannot progress beyond infinite face */
 540             }
 541         }
 542         /* If the clockwise search made it all the way round, don't need to
 543          * bother with the anticlockwise search. */
 544         if (current_face1 == d->order)
 545             continue; /* this dot is complete, move on to next dot */
 546
 547         /* anticlockwise search */
 548         while (TRUE) {
 549             grid_face *f = d->faces[current_face2];
 550             grid_edge *e;
 551             int j;
 552             assert(f != NULL);
 553             /* find dot around this face */
 554             for (j = 0; j < f->order; j++) {
 555                 if (f->dots[j] == d)
 556                     break;
 557             }
 558             assert(j != f->order); /* must find dot */
 559
 560             /* Around f, required edge is clockwise from the dot. */
 561             e = f->edges[j];
 562
 563             current_face2--;
 564             if (current_face2 == -1)
 565                 current_face2 = d->order - 1;
 566             d->edges[current_face2] = e; /* set edge */
 567
 568             /* set face */
 569             if (current_face2 == current_face1)
 570                 break;
 571             d->faces[current_face2] =
 572                     (e->face1 == f) ? e->face2 : e->face1;
 573             /* There's only 1 infinite face, so we must get all the way
 574              * to current_face1 before we hit it. */
 575             assert(d->faces[current_face2]);
 576         }
 577     }
 578
 579     /* ====== Stage 4 ======
 580      * Compute other grid settings
 581      */
 582
 583     /* Bounding rectangle */
 584     for (i = 0; i < g->num_dots; i++) {
 585         grid_dot *d = g->dots + i;
 586         if (i == 0) {
 587             g->lowest_x = g->highest_x = d->x;
 588             g->lowest_y = g->highest_y = d->y;
 589         } else {
 590             g->lowest_x = min(g->lowest_x, d->x);
 591             g->highest_x = max(g->highest_x, d->x);
 592             g->lowest_y = min(g->lowest_y, d->y);
 593             g->highest_y = max(g->highest_y, d->y);
 594         }
 595     }
 596
 597 #ifdef DEBUG_GRID
 598     grid_print_derived(g);
 599 #endif
 600 }
 601
 602 /* Helpers for making grid-generation easier.  These functions are only
 603  * intended for use during grid generation. */
 604
 605 /* Comparison function for the (tree234) sorted dot list */
 606 static int grid_point_cmp_fn(void *v1, void *v2)
 607 {
 608     grid_dot *p1 = v1;
 609     grid_dot *p2 = v2;
 610     if (p1->y != p2->y)
 611         return p2->y - p1->y;
 612     else
 613         return p2->x - p1->x;
 614 }
 615 /* Add a new face to the grid, with its dot list allocated.
 616  * Assumes there's enough space allocated for the new face in grid->faces */
 617 static void grid_face_add_new(grid *g, int face_size)
 618 {
 619     int i;
 620     grid_face *new_face = g->faces + g->num_faces;
 621     new_face->order = face_size;
 622     new_face->dots = snewn(face_size, grid_dot*);
 623     for (i = 0; i < face_size; i++)
 624         new_face->dots[i] = NULL;
 625     new_face->edges = NULL;
 626     g->num_faces++;
 627 }
 628 /* Assumes dot list has enough space */
 629 static grid_dot *grid_dot_add_new(grid *g, int x, int y)
 630 {
 631     grid_dot *new_dot = g->dots + g->num_dots;
 632     new_dot->order = 0;
 633     new_dot->edges = NULL;
 634     new_dot->faces = NULL;
 635     new_dot->x = x;
 636     new_dot->y = y;
 637     g->num_dots++;
 638     return new_dot;
 639 }
 640 /* Retrieve a dot with these (x,y) coordinates.  Either return an existing dot
 641  * in the dot_list, or add a new dot to the grid (and the dot_list) and
 642  * return that.
 643  * Assumes g->dots has enough capacity allocated */
 644 static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y)
 645 {
 646     grid_dot test, *ret;
 647
 648     test.order = 0;
 649     test.edges = NULL;
 650     test.faces = NULL;
 651     test.x = x;
 652     test.y = y;
 653     ret = find234(dot_list, &test, NULL);
 654     if (ret)
 655         return ret;
 656
 657     ret = grid_dot_add_new(g, x, y);
 658     add234(dot_list, ret);
 659     return ret;
 660 }
 661
 662 /* Sets the last face of the grid to include this dot, at this position
 663  * around the face. Assumes num_faces is at least 1 (a new face has
 664  * previously been added, with the required number of dots allocated) */
 665 static void grid_face_set_dot(grid *g, grid_dot *d, int position)
 666 {
 667     grid_face *last_face = g->faces + g->num_faces - 1;
 668     last_face->dots[position] = d;
 669 }
 670
 671 /* ------ Generate various types of grid ------ */
 672
 673 /* General method is to generate faces, by calculating their dot coordinates.
 674  * As new faces are added, we keep track of all the dots so we can tell when
 675  * a new face reuses an existing dot.  For example, two squares touching at an
 676  * edge would generate six unique dots: four dots from the first face, then
 677  * two additional dots for the second face, because we detect the other two
 678  * dots have already been taken up.  This list is stored in a tree234
 679  * called "points".  No extra memory-allocation needed here - we store the
 680  * actual grid_dot* pointers, which all point into the g->dots list.
 681  * For this reason, we have to calculate coordinates in such a way as to
 682  * eliminate any rounding errors, so we can detect when a dot on one
 683  * face precisely lands on a dot of a different face.  No floating-point
 684  * arithmetic here!
 685  */
 686
 687 grid *grid_new_square(int width, int height)
 688 {
 689     int x, y;
 690     /* Side length */
 691     int a = 20;
 692
 693     /* Upper bounds - don't have to be exact */
 694     int max_faces = width * height;
 695     int max_dots = (width + 1) * (height + 1);
 696
 697     tree234 *points;
 698
 699     grid *g = grid_new();
 700     g->tilesize = a;
 701     g->faces = snewn(max_faces, grid_face);
 702     g->dots = snewn(max_dots, grid_dot);
 703
 704     points = newtree234(grid_point_cmp_fn);
 705
 706     /* generate square faces */
 707     for (y = 0; y < height; y++) {
 708         for (x = 0; x < width; x++) {
 709             grid_dot *d;
 710             /* face position */
 711             int px = a * x;
 712             int py = a * y;
 713
 714             grid_face_add_new(g, 4);
 715             d = grid_get_dot(g, points, px, py);
 716             grid_face_set_dot(g, d, 0);
 717             d = grid_get_dot(g, points, px + a, py);
 718             grid_face_set_dot(g, d, 1);
 719             d = grid_get_dot(g, points, px + a, py + a);
 720             grid_face_set_dot(g, d, 2);
 721             d = grid_get_dot(g, points, px, py + a);
 722             grid_face_set_dot(g, d, 3);
 723         }
 724     }
 725
 726     freetree234(points);
 727     assert(g->num_faces <= max_faces);
 728     assert(g->num_dots <= max_dots);
 729     g->middle_face = g->faces + (height/2) * width + (width/2);
 730
 731     grid_make_consistent(g);
 732     return g;
 733 }
 734
 735 grid *grid_new_honeycomb(int width, int height)
 736 {
 737     int x, y;
 738     /* Vector for side of hexagon - ratio is close to sqrt(3) */
 739     int a = 15;
 740     int b = 26;
 741
 742     /* Upper bounds - don't have to be exact */
 743     int max_faces = width * height;
 744     int max_dots = 2 * (width + 1) * (height + 1);
 745
 746     tree234 *points;
 747
 748     grid *g = grid_new();
 749     g->tilesize = 3 * a;
 750     g->faces = snewn(max_faces, grid_face);
 751     g->dots = snewn(max_dots, grid_dot);
 752
 753     points = newtree234(grid_point_cmp_fn);
 754
 755     /* generate hexagonal faces */
 756     for (y = 0; y < height; y++) {
 757         for (x = 0; x < width; x++) {
 758             grid_dot *d;
 759             /* face centre */
 760             int cx = 3 * a * x;
 761             int cy = 2 * b * y;
 762             if (x % 2)
 763                 cy += b;
 764             grid_face_add_new(g, 6);
 765
 766             d = grid_get_dot(g, points, cx - a, cy - b);
 767             grid_face_set_dot(g, d, 0);
 768             d = grid_get_dot(g, points, cx + a, cy - b);
 769             grid_face_set_dot(g, d, 1);
 770             d = grid_get_dot(g, points, cx + 2*a, cy);
 771             grid_face_set_dot(g, d, 2);
 772             d = grid_get_dot(g, points, cx + a, cy + b);
 773             grid_face_set_dot(g, d, 3);
 774             d = grid_get_dot(g, points, cx - a, cy + b);
 775             grid_face_set_dot(g, d, 4);
 776             d = grid_get_dot(g, points, cx - 2*a, cy);
 777             grid_face_set_dot(g, d, 5);
 778         }
 779     }
 780
 781     freetree234(points);
 782     assert(g->num_faces <= max_faces);
 783     assert(g->num_dots <= max_dots);
 784     g->middle_face = g->faces + (height/2) * width + (width/2);
 785
 786     grid_make_consistent(g);
 787     return g;
 788 }
 789
 790 /* Doesn't use the previous method of generation, it pre-dates it!
 791  * A triangular grid is just about simple enough to do by "brute force" */
 792 grid *grid_new_triangular(int width, int height)
 793 {
 794     int x,y;
 795
 796     /* Vector for side of triangle - ratio is close to sqrt(3) */
 797     int vec_x = 15;
 798     int vec_y = 26;
 799
 800     int index;
 801
 802     /* convenient alias */
 803     int w = width + 1;
 804
 805     grid *g = grid_new();
 806     g->tilesize = 18; /* adjust to your taste */
 807
 808     g->num_faces = width * height * 2;
 809     g->num_dots = (width + 1) * (height + 1);
 810     g->faces = snewn(g->num_faces, grid_face);
 811     g->dots = snewn(g->num_dots, grid_dot);
 812
 813     /* generate dots */
 814     index = 0;
 815     for (y = 0; y <= height; y++) {
 816         for (x = 0; x <= width; x++) {
 817             grid_dot *d = g->dots + index;
 818             /* odd rows are offset to the right */
 819             d->order = 0;
 820             d->edges = NULL;
 821             d->faces = NULL;
 822             d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0);
 823             d->y = y * vec_y;
 824             index++;
 825         }
 826     }
 827
 828     /* generate faces */
 829     index = 0;
 830     for (y = 0; y < height; y++) {
 831         for (x = 0; x < width; x++) {
 832             /* initialise two faces for this (x,y) */
 833             grid_face *f1 = g->faces + index;
 834             grid_face *f2 = f1 + 1;
 835             f1->edges = NULL;
 836             f1->order = 3;
 837             f1->dots = snewn(f1->order, grid_dot*);
 838             f2->edges = NULL;
 839             f2->order = 3;
 840             f2->dots = snewn(f2->order, grid_dot*);
 841
 842             /* face descriptions depend on whether the row-number is
 843              * odd or even */
 844             if (y % 2) {
 845                 f1->dots[0] = g->dots + y       * w + x;
 846                 f1->dots[1] = g->dots + (y + 1) * w + x + 1;
 847                 f1->dots[2] = g->dots + (y + 1) * w + x;
 848                 f2->dots[0] = g->dots + y       * w + x;
 849                 f2->dots[1] = g->dots + y       * w + x + 1;
 850                 f2->dots[2] = g->dots + (y + 1) * w + x + 1;
 851             } else {
 852                 f1->dots[0] = g->dots + y       * w + x;
 853                 f1->dots[1] = g->dots + y       * w + x + 1;
 854                 f1->dots[2] = g->dots + (y + 1) * w + x;
 855                 f2->dots[0] = g->dots + y       * w + x + 1;
 856                 f2->dots[1] = g->dots + (y + 1) * w + x + 1;
 857                 f2->dots[2] = g->dots + (y + 1) * w + x;
 858             }
 859             index += 2;
 860         }
 861     }
 862
 863     /* "+ width" takes us to the middle of the row, because each row has
 864      * (2*width) faces. */
 865     g->middle_face = g->faces + (height / 2) * 2 * width + width;
 866
 867     grid_make_consistent(g);
 868     return g;
 869 }
 870
 871 grid *grid_new_snubsquare(int width, int height)
 872 {
 873     int x, y;
 874     /* Vector for side of triangle - ratio is close to sqrt(3) */
 875     int a = 15;
 876     int b = 26;
 877
 878     /* Upper bounds - don't have to be exact */
 879     int max_faces = 3 * width * height;
 880     int max_dots = 2 * (width + 1) * (height + 1);
 881
 882     tree234 *points;
 883
 884     grid *g = grid_new();
 885     g->tilesize = 18;
 886     g->faces = snewn(max_faces, grid_face);
 887     g->dots = snewn(max_dots, grid_dot);
 888
 889     points = newtree234(grid_point_cmp_fn);
 890
 891     for (y = 0; y < height; y++) {
 892         for (x = 0; x < width; x++) {
 893             grid_dot *d;
 894             /* face position */
 895             int px = (a + b) * x;
 896             int py = (a + b) * y;
 897
 898             /* generate square faces */
 899             grid_face_add_new(g, 4);
 900             if ((x + y) % 2) {
 901                 d = grid_get_dot(g, points, px + a, py);
 902                 grid_face_set_dot(g, d, 0);
 903                 d = grid_get_dot(g, points, px + a + b, py + a);
 904                 grid_face_set_dot(g, d, 1);
 905                 d = grid_get_dot(g, points, px + b, py + a + b);
 906                 grid_face_set_dot(g, d, 2);
 907                 d = grid_get_dot(g, points, px, py + b);
 908                 grid_face_set_dot(g, d, 3);
 909             } else {
 910                 d = grid_get_dot(g, points, px + b, py);
 911                 grid_face_set_dot(g, d, 0);
 912                 d = grid_get_dot(g, points, px + a + b, py + b);
 913                 grid_face_set_dot(g, d, 1);
 914                 d = grid_get_dot(g, points, px + a, py + a + b);
 915                 grid_face_set_dot(g, d, 2);
 916                 d = grid_get_dot(g, points, px, py + a);
 917                 grid_face_set_dot(g, d, 3);
 918             }
 919
 920             /* generate up/down triangles */
 921             if (x > 0) {
 922                 grid_face_add_new(g, 3);
 923                 if ((x + y) % 2) {
 924                     d = grid_get_dot(g, points, px + a, py);
 925                     grid_face_set_dot(g, d, 0);
 926                     d = grid_get_dot(g, points, px, py + b);
 927                     grid_face_set_dot(g, d, 1);
 928                     d = grid_get_dot(g, points, px - a, py);
 929                     grid_face_set_dot(g, d, 2);
 930                 } else {
 931                     d = grid_get_dot(g, points, px, py + a);
 932                     grid_face_set_dot(g, d, 0);
 933                     d = grid_get_dot(g, points, px + a, py + a + b);
 934                     grid_face_set_dot(g, d, 1);
 935                     d = grid_get_dot(g, points, px - a, py + a + b);
 936                     grid_face_set_dot(g, d, 2);
 937                 }
 938             }
 939
 940             /* generate left/right triangles */
 941             if (y > 0) {
 942                 grid_face_add_new(g, 3);
 943                 if ((x + y) % 2) {
 944                     d = grid_get_dot(g, points, px + a, py);
 945                     grid_face_set_dot(g, d, 0);
 946                     d = grid_get_dot(g, points, px + a + b, py - a);
 947                     grid_face_set_dot(g, d, 1);
 948                     d = grid_get_dot(g, points, px + a + b, py + a);
 949                     grid_face_set_dot(g, d, 2);
 950                 } else {
 951                     d = grid_get_dot(g, points, px, py - a);
 952                     grid_face_set_dot(g, d, 0);
 953                     d = grid_get_dot(g, points, px + b, py);
 954                     grid_face_set_dot(g, d, 1);
 955                     d = grid_get_dot(g, points, px, py + a);
 956                     grid_face_set_dot(g, d, 2);
 957                 }
 958             }
 959         }
 960     }
 961
 962     freetree234(points);
 963     assert(g->num_faces <= max_faces);
 964     assert(g->num_dots <= max_dots);
 965     g->middle_face = g->faces + (height/2) * width + (width/2);
 966
 967     grid_make_consistent(g);
 968     return g;
 969 }
 970
 971 grid *grid_new_cairo(int width, int height)
 972 {
 973     int x, y;
 974     /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
 975     int a = 14;
 976     int b = 31;
 977
 978     /* Upper bounds - don't have to be exact */
 979     int max_faces = 2 * width * height;
 980     int max_dots = 3 * (width + 1) * (height + 1);
 981
 982     tree234 *points;
 983
 984     grid *g = grid_new();
 985     g->tilesize = 40;
 986     g->faces = snewn(max_faces, grid_face);
 987     g->dots = snewn(max_dots, grid_dot);
 988
 989     points = newtree234(grid_point_cmp_fn);
 990
 991     for (y = 0; y < height; y++) {
 992         for (x = 0; x < width; x++) {
 993             grid_dot *d;
 994             /* cell position */
 995             int px = 2 * b * x;
 996             int py = 2 * b * y;
 997
 998             /* horizontal pentagons */
 999             if (y > 0) {
1000                 grid_face_add_new(g, 5);
1001                 if ((x + y) % 2) {
1002                     d = grid_get_dot(g, points, px + a, py - b);
1003                     grid_face_set_dot(g, d, 0);
1004                     d = grid_get_dot(g, points, px + 2*b - a, py - b);
1005                     grid_face_set_dot(g, d, 1);
1006                     d = grid_get_dot(g, points, px + 2*b, py);
1007                     grid_face_set_dot(g, d, 2);
1008                     d = grid_get_dot(g, points, px + b, py + a);
1009                     grid_face_set_dot(g, d, 3);
1010                     d = grid_get_dot(g, points, px, py);
1011                     grid_face_set_dot(g, d, 4);
1012                 } else {
1013                     d = grid_get_dot(g, points, px, py);
1014                     grid_face_set_dot(g, d, 0);
1015                     d = grid_get_dot(g, points, px + b, py - a);
1016                     grid_face_set_dot(g, d, 1);
1017                     d = grid_get_dot(g, points, px + 2*b, py);
1018                     grid_face_set_dot(g, d, 2);
1019                     d = grid_get_dot(g, points, px + 2*b - a, py + b);
1020                     grid_face_set_dot(g, d, 3);
1021                     d = grid_get_dot(g, points, px + a, py + b);
1022                     grid_face_set_dot(g, d, 4);
1023                 }
1024             }
1025             /* vertical pentagons */
1026             if (x > 0) {
1027                 grid_face_add_new(g, 5);
1028                 if ((x + y) % 2) {
1029                     d = grid_get_dot(g, points, px, py);
1030                     grid_face_set_dot(g, d, 0);
1031                     d = grid_get_dot(g, points, px + b, py + a);
1032                     grid_face_set_dot(g, d, 1);
1033                     d = grid_get_dot(g, points, px + b, py + 2*b - a);
1034                     grid_face_set_dot(g, d, 2);
1035                     d = grid_get_dot(g, points, px, py + 2*b);
1036                     grid_face_set_dot(g, d, 3);
1037                     d = grid_get_dot(g, points, px - a, py + b);
1038                     grid_face_set_dot(g, d, 4);
1039                 } else {
1040                     d = grid_get_dot(g, points, px, py);
1041                     grid_face_set_dot(g, d, 0);
1042                     d = grid_get_dot(g, points, px + a, py + b);
1043                     grid_face_set_dot(g, d, 1);
1044                     d = grid_get_dot(g, points, px, py + 2*b);
1045                     grid_face_set_dot(g, d, 2);
1046                     d = grid_get_dot(g, points, px - b, py + 2*b - a);
1047                     grid_face_set_dot(g, d, 3);
1048                     d = grid_get_dot(g, points, px - b, py + a);
1049                     grid_face_set_dot(g, d, 4);
1050                 }
1051             }
1052         }
1053     }
1054
1055     freetree234(points);
1056     assert(g->num_faces <= max_faces);
1057     assert(g->num_dots <= max_dots);
1058     g->middle_face = g->faces + (height/2) * width + (width/2);
1059
1060     grid_make_consistent(g);
1061     return g;
1062 }
1063
1064 grid *grid_new_greathexagonal(int width, int height)
1065 {
1066     int x, y;
1067     /* Vector for side of triangle - ratio is close to sqrt(3) */
1068     int a = 15;
1069     int b = 26;
1070
1071     /* Upper bounds - don't have to be exact */
1072     int max_faces = 6 * (width + 1) * (height + 1);
1073     int max_dots = 6 * width * height;
1074
1075     tree234 *points;
1076
1077     grid *g = grid_new();
1078     g->tilesize = 18;
1079     g->faces = snewn(max_faces, grid_face);
1080     g->dots = snewn(max_dots, grid_dot);
1081
1082     points = newtree234(grid_point_cmp_fn);
1083
1084     for (y = 0; y < height; y++) {
1085         for (x = 0; x < width; x++) {
1086             grid_dot *d;
1087             /* centre of hexagon */
1088             int px = (3*a + b) * x;
1089             int py = (2*a + 2*b) * y;
1090             if (x % 2)
1091                 py += a + b;
1092
1093             /* hexagon */
1094             grid_face_add_new(g, 6);
1095             d = grid_get_dot(g, points, px - a, py - b);
1096             grid_face_set_dot(g, d, 0);
1097             d = grid_get_dot(g, points, px + a, py - b);
1098             grid_face_set_dot(g, d, 1);
1099             d = grid_get_dot(g, points, px + 2*a, py);
1100             grid_face_set_dot(g, d, 2);
1101             d = grid_get_dot(g, points, px + a, py + b);
1102             grid_face_set_dot(g, d, 3);
1103             d = grid_get_dot(g, points, px - a, py + b);
1104             grid_face_set_dot(g, d, 4);
1105             d = grid_get_dot(g, points, px - 2*a, py);
1106             grid_face_set_dot(g, d, 5);
1107
1108             /* square below hexagon */
1109             if (y < height - 1) {
1110                 grid_face_add_new(g, 4);
1111                 d = grid_get_dot(g, points, px - a, py + b);
1112                 grid_face_set_dot(g, d, 0);
1113                 d = grid_get_dot(g, points, px + a, py + b);
1114                 grid_face_set_dot(g, d, 1);
1115                 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1116                 grid_face_set_dot(g, d, 2);
1117                 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1118                 grid_face_set_dot(g, d, 3);
1119             }
1120
1121             /* square below right */
1122             if ((x < width - 1) && (((x % 2) == 0) || (y < height - 1))) {
1123                 grid_face_add_new(g, 4);
1124                 d = grid_get_dot(g, points, px + 2*a, py);
1125                 grid_face_set_dot(g, d, 0);
1126                 d = grid_get_dot(g, points, px + 2*a + b, py + a);
1127                 grid_face_set_dot(g, d, 1);
1128                 d = grid_get_dot(g, points, px + a + b, py + a + b);
1129                 grid_face_set_dot(g, d, 2);
1130                 d = grid_get_dot(g, points, px + a, py + b);
1131                 grid_face_set_dot(g, d, 3);
1132             }
1133
1134             /* square below left */
1135             if ((x > 0) && (((x % 2) == 0) || (y < height - 1))) {
1136                 grid_face_add_new(g, 4);
1137                 d = grid_get_dot(g, points, px - 2*a, py);
1138                 grid_face_set_dot(g, d, 0);
1139                 d = grid_get_dot(g, points, px - a, py + b);
1140                 grid_face_set_dot(g, d, 1);
1141                 d = grid_get_dot(g, points, px - a - b, py + a + b);
1142                 grid_face_set_dot(g, d, 2);
1143                 d = grid_get_dot(g, points, px - 2*a - b, py + a);
1144                 grid_face_set_dot(g, d, 3);
1145             }
1146
1147             /* Triangle below right */
1148             if ((x < width - 1) && (y < height - 1)) {
1149                 grid_face_add_new(g, 3);
1150                 d = grid_get_dot(g, points, px + a, py + b);
1151                 grid_face_set_dot(g, d, 0);
1152                 d = grid_get_dot(g, points, px + a + b, py + a + b);
1153                 grid_face_set_dot(g, d, 1);
1154                 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1155                 grid_face_set_dot(g, d, 2);
1156             }
1157
1158             /* Triangle below left */
1159             if ((x > 0) && (y < height - 1)) {
1160                 grid_face_add_new(g, 3);
1161                 d = grid_get_dot(g, points, px - a, py + b);
1162                 grid_face_set_dot(g, d, 0);
1163                 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1164                 grid_face_set_dot(g, d, 1);
1165                 d = grid_get_dot(g, points, px - a - b, py + a + b);
1166                 grid_face_set_dot(g, d, 2);
1167             }
1168         }
1169     }
1170
1171     freetree234(points);
1172     assert(g->num_faces <= max_faces);
1173     assert(g->num_dots <= max_dots);
1174     g->middle_face = g->faces + (height/2) * width + (width/2);
1175
1176     grid_make_consistent(g);
1177     return g;
1178 }
1179
1180 grid *grid_new_octagonal(int width, int height)
1181 {
1182     int x, y;
1183     /* b/a approx sqrt(2) */
1184     int a = 29;
1185     int b = 41;
1186
1187     /* Upper bounds - don't have to be exact */
1188     int max_faces = 2 * width * height;
1189     int max_dots = 4 * (width + 1) * (height + 1);
1190
1191     tree234 *points;
1192
1193     grid *g = grid_new();
1194     g->tilesize = 40;
1195     g->faces = snewn(max_faces, grid_face);
1196     g->dots = snewn(max_dots, grid_dot);
1197
1198     points = newtree234(grid_point_cmp_fn);
1199
1200     for (y = 0; y < height; y++) {
1201         for (x = 0; x < width; x++) {
1202             grid_dot *d;
1203             /* cell position */
1204             int px = (2*a + b) * x;
1205             int py = (2*a + b) * y;
1206             /* octagon */
1207             grid_face_add_new(g, 8);
1208             d = grid_get_dot(g, points, px + a, py);
1209             grid_face_set_dot(g, d, 0);
1210             d = grid_get_dot(g, points, px + a + b, py);
1211             grid_face_set_dot(g, d, 1);
1212             d = grid_get_dot(g, points, px + 2*a + b, py + a);
1213             grid_face_set_dot(g, d, 2);
1214             d = grid_get_dot(g, points, px + 2*a + b, py + a + b);
1215             grid_face_set_dot(g, d, 3);
1216             d = grid_get_dot(g, points, px + a + b, py + 2*a + b);
1217             grid_face_set_dot(g, d, 4);
1218             d = grid_get_dot(g, points, px + a, py + 2*a + b);
1219             grid_face_set_dot(g, d, 5);
1220             d = grid_get_dot(g, points, px, py + a + b);
1221             grid_face_set_dot(g, d, 6);
1222             d = grid_get_dot(g, points, px, py + a);
1223             grid_face_set_dot(g, d, 7);
1224
1225             /* diamond */
1226             if ((x > 0) && (y > 0)) {
1227                 grid_face_add_new(g, 4);
1228                 d = grid_get_dot(g, points, px, py - a);
1229                 grid_face_set_dot(g, d, 0);
1230                 d = grid_get_dot(g, points, px + a, py);
1231                 grid_face_set_dot(g, d, 1);
1232                 d = grid_get_dot(g, points, px, py + a);
1233                 grid_face_set_dot(g, d, 2);
1234                 d = grid_get_dot(g, points, px - a, py);
1235                 grid_face_set_dot(g, d, 3);
1236             }
1237         }
1238     }
1239
1240     freetree234(points);
1241     assert(g->num_faces <= max_faces);
1242     assert(g->num_dots <= max_dots);
1243     g->middle_face = g->faces + (height/2) * width + (width/2);
1244
1245     grid_make_consistent(g);
1246     return g;
1247 }
1248
1249 grid *grid_new_kites(int width, int height)
1250 {
1251     int x, y;
1252     /* b/a approx sqrt(3) */
1253     int a = 15;
1254     int b = 26;
1255
1256     /* Upper bounds - don't have to be exact */
1257     int max_faces = 6 * width * height;
1258     int max_dots = 6 * (width + 1) * (height + 1);
1259
1260     tree234 *points;
1261
1262     grid *g = grid_new();
1263     g->tilesize = 40;
1264     g->faces = snewn(max_faces, grid_face);
1265     g->dots = snewn(max_dots, grid_dot);
1266
1267     points = newtree234(grid_point_cmp_fn);
1268
1269     for (y = 0; y < height; y++) {
1270         for (x = 0; x < width; x++) {
1271             grid_dot *d;
1272             /* position of order-6 dot */
1273             int px = 4*b * x;
1274             int py = 6*a * y;
1275             if (y % 2)
1276                 px += 2*b;
1277
1278             /* kite pointing up-left */
1279             grid_face_add_new(g, 4);
1280             d = grid_get_dot(g, points, px, py);
1281             grid_face_set_dot(g, d, 0);
1282             d = grid_get_dot(g, points, px + 2*b, py);
1283             grid_face_set_dot(g, d, 1);
1284             d = grid_get_dot(g, points, px + 2*b, py + 2*a);
1285             grid_face_set_dot(g, d, 2);
1286             d = grid_get_dot(g, points, px + b, py + 3*a);
1287             grid_face_set_dot(g, d, 3);
1288
1289             /* kite pointing up */
1290             grid_face_add_new(g, 4);
1291             d = grid_get_dot(g, points, px, py);
1292             grid_face_set_dot(g, d, 0);
1293             d = grid_get_dot(g, points, px + b, py + 3*a);
1294             grid_face_set_dot(g, d, 1);
1295             d = grid_get_dot(g, points, px, py + 4*a);
1296             grid_face_set_dot(g, d, 2);
1297             d = grid_get_dot(g, points, px - b, py + 3*a);
1298             grid_face_set_dot(g, d, 3);
1299
1300             /* kite pointing up-right */
1301             grid_face_add_new(g, 4);
1302             d = grid_get_dot(g, points, px, py);
1303             grid_face_set_dot(g, d, 0);
1304             d = grid_get_dot(g, points, px - b, py + 3*a);
1305             grid_face_set_dot(g, d, 1);
1306             d = grid_get_dot(g, points, px - 2*b, py + 2*a);
1307             grid_face_set_dot(g, d, 2);
1308             d = grid_get_dot(g, points, px - 2*b, py);
1309             grid_face_set_dot(g, d, 3);
1310
1311             /* kite pointing down-right */
1312             grid_face_add_new(g, 4);
1313             d = grid_get_dot(g, points, px, py);
1314             grid_face_set_dot(g, d, 0);
1315             d = grid_get_dot(g, points, px - 2*b, py);
1316             grid_face_set_dot(g, d, 1);
1317             d = grid_get_dot(g, points, px - 2*b, py - 2*a);
1318             grid_face_set_dot(g, d, 2);
1319             d = grid_get_dot(g, points, px - b, py - 3*a);
1320             grid_face_set_dot(g, d, 3);
1321
1322             /* kite pointing down */
1323             grid_face_add_new(g, 4);
1324             d = grid_get_dot(g, points, px, py);
1325             grid_face_set_dot(g, d, 0);
1326             d = grid_get_dot(g, points, px - b, py - 3*a);
1327             grid_face_set_dot(g, d, 1);
1328             d = grid_get_dot(g, points, px, py - 4*a);
1329             grid_face_set_dot(g, d, 2);
1330             d = grid_get_dot(g, points, px + b, py - 3*a);
1331             grid_face_set_dot(g, d, 3);
1332
1333             /* kite pointing down-left */
1334             grid_face_add_new(g, 4);
1335             d = grid_get_dot(g, points, px, py);
1336             grid_face_set_dot(g, d, 0);
1337             d = grid_get_dot(g, points, px + b, py - 3*a);
1338             grid_face_set_dot(g, d, 1);
1339             d = grid_get_dot(g, points, px + 2*b, py - 2*a);
1340             grid_face_set_dot(g, d, 2);
1341             d = grid_get_dot(g, points, px + 2*b, py);
1342             grid_face_set_dot(g, d, 3);
1343         }
1344     }
1345
1346     freetree234(points);
1347     assert(g->num_faces <= max_faces);
1348     assert(g->num_dots <= max_dots);
1349     g->middle_face = g->faces + 6 * ((height/2) * width + (width/2));
1350
1351     grid_make_consistent(g);
1352     return g;
1353 }
1354
1355 /* ----------- End of grid generators ------------- */