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 = {0, NULL, NULL, x, y};
 647     grid_dot *ret = find234(dot_list, &test, NULL);
 648     if (ret)
 649         return ret;
 650
 651     ret = grid_dot_add_new(g, x, y);
 652     add234(dot_list, ret);
 653     return ret;
 654 }
 655
 656 /* Sets the last face of the grid to include this dot, at this position
 657  * around the face. Assumes num_faces is at least 1 (a new face has
 658  * previously been added, with the required number of dots allocated) */
 659 static void grid_face_set_dot(grid *g, grid_dot *d, int position)
 660 {
 661     grid_face *last_face = g->faces + g->num_faces - 1;
 662     last_face->dots[position] = d;
 663 }
 664
 665 /* ------ Generate various types of grid ------ */
 666
 667 /* General method is to generate faces, by calculating their dot coordinates.
 668  * As new faces are added, we keep track of all the dots so we can tell when
 669  * a new face reuses an existing dot.  For example, two squares touching at an
 670  * edge would generate six unique dots: four dots from the first face, then
 671  * two additional dots for the second face, because we detect the other two
 672  * dots have already been taken up.  This list is stored in a tree234
 673  * called "points".  No extra memory-allocation needed here - we store the
 674  * actual grid_dot* pointers, which all point into the g->dots list.
 675  * For this reason, we have to calculate coordinates in such a way as to
 676  * eliminate any rounding errors, so we can detect when a dot on one
 677  * face precisely lands on a dot of a different face.  No floating-point
 678  * arithmetic here!
 679  */
 680
 681 grid *grid_new_square(int width, int height)
 682 {
 683     int x, y;
 684     /* Side length */
 685     int a = 20;
 686
 687     /* Upper bounds - don't have to be exact */
 688     int max_faces = width * height;
 689     int max_dots = (width + 1) * (height + 1);
 690
 691     tree234 *points;
 692
 693     grid *g = grid_new();
 694     g->tilesize = a;
 695     g->faces = snewn(max_faces, grid_face);
 696     g->dots = snewn(max_dots, grid_dot);
 697
 698     points = newtree234(grid_point_cmp_fn);
 699
 700     /* generate square faces */
 701     for (y = 0; y < height; y++) {
 702         for (x = 0; x < width; x++) {
 703             grid_dot *d;
 704             /* face position */
 705             int px = a * x;
 706             int py = a * y;
 707
 708             grid_face_add_new(g, 4);
 709             d = grid_get_dot(g, points, px, py);
 710             grid_face_set_dot(g, d, 0);
 711             d = grid_get_dot(g, points, px + a, py);
 712             grid_face_set_dot(g, d, 1);
 713             d = grid_get_dot(g, points, px + a, py + a);
 714             grid_face_set_dot(g, d, 2);
 715             d = grid_get_dot(g, points, px, py + a);
 716             grid_face_set_dot(g, d, 3);
 717         }
 718     }
 719
 720     freetree234(points);
 721     assert(g->num_faces <= max_faces);
 722     assert(g->num_dots <= max_dots);
 723     g->middle_face = g->faces + (height/2) * width + (width/2);
 724
 725     grid_make_consistent(g);
 726     return g;
 727 }
 728
 729 grid *grid_new_honeycomb(int width, int height)
 730 {
 731     int x, y;
 732     /* Vector for side of hexagon - ratio is close to sqrt(3) */
 733     int a = 15;
 734     int b = 26;
 735
 736     /* Upper bounds - don't have to be exact */
 737     int max_faces = width * height;
 738     int max_dots = 2 * (width + 1) * (height + 1);
 739
 740     tree234 *points;
 741
 742     grid *g = grid_new();
 743     g->tilesize = 3 * a;
 744     g->faces = snewn(max_faces, grid_face);
 745     g->dots = snewn(max_dots, grid_dot);
 746
 747     points = newtree234(grid_point_cmp_fn);
 748
 749     /* generate hexagonal faces */
 750     for (y = 0; y < height; y++) {
 751         for (x = 0; x < width; x++) {
 752             grid_dot *d;
 753             /* face centre */
 754             int cx = 3 * a * x;
 755             int cy = 2 * b * y;
 756             if (x % 2)
 757                 cy += b;
 758             grid_face_add_new(g, 6);
 759
 760             d = grid_get_dot(g, points, cx - a, cy - b);
 761             grid_face_set_dot(g, d, 0);
 762             d = grid_get_dot(g, points, cx + a, cy - b);
 763             grid_face_set_dot(g, d, 1);
 764             d = grid_get_dot(g, points, cx + 2*a, cy);
 765             grid_face_set_dot(g, d, 2);
 766             d = grid_get_dot(g, points, cx + a, cy + b);
 767             grid_face_set_dot(g, d, 3);
 768             d = grid_get_dot(g, points, cx - a, cy + b);
 769             grid_face_set_dot(g, d, 4);
 770             d = grid_get_dot(g, points, cx - 2*a, cy);
 771             grid_face_set_dot(g, d, 5);
 772         }
 773     }
 774
 775     freetree234(points);
 776     assert(g->num_faces <= max_faces);
 777     assert(g->num_dots <= max_dots);
 778     g->middle_face = g->faces + (height/2) * width + (width/2);
 779
 780     grid_make_consistent(g);
 781     return g;
 782 }
 783
 784 /* Doesn't use the previous method of generation, it pre-dates it!
 785  * A triangular grid is just about simple enough to do by "brute force" */
 786 grid *grid_new_triangular(int width, int height)
 787 {
 788     int x,y;
 789
 790     /* Vector for side of triangle - ratio is close to sqrt(3) */
 791     int vec_x = 15;
 792     int vec_y = 26;
 793
 794     int index;
 795
 796     /* convenient alias */
 797     int w = width + 1;
 798
 799     grid *g = grid_new();
 800     g->tilesize = 18; /* adjust to your taste */
 801
 802     g->num_faces = width * height * 2;
 803     g->num_dots = (width + 1) * (height + 1);
 804     g->faces = snewn(g->num_faces, grid_face);
 805     g->dots = snewn(g->num_dots, grid_dot);
 806
 807     /* generate dots */
 808     index = 0;
 809     for (y = 0; y <= height; y++) {
 810         for (x = 0; x <= width; x++) {
 811             grid_dot *d = g->dots + index;
 812             /* odd rows are offset to the right */
 813             d->order = 0;
 814             d->edges = NULL;
 815             d->faces = NULL;
 816             d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0);
 817             d->y = y * vec_y;
 818             index++;
 819         }
 820     }
 821
 822     /* generate faces */
 823     index = 0;
 824     for (y = 0; y < height; y++) {
 825         for (x = 0; x < width; x++) {
 826             /* initialise two faces for this (x,y) */
 827             grid_face *f1 = g->faces + index;
 828             grid_face *f2 = f1 + 1;
 829             f1->edges = NULL;
 830             f1->order = 3;
 831             f1->dots = snewn(f1->order, grid_dot*);
 832             f2->edges = NULL;
 833             f2->order = 3;
 834             f2->dots = snewn(f2->order, grid_dot*);
 835
 836             /* face descriptions depend on whether the row-number is
 837              * odd or even */
 838             if (y % 2) {
 839                 f1->dots[0] = g->dots + y       * w + x;
 840                 f1->dots[1] = g->dots + (y + 1) * w + x + 1;
 841                 f1->dots[2] = g->dots + (y + 1) * w + x;
 842                 f2->dots[0] = g->dots + y       * w + x;
 843                 f2->dots[1] = g->dots + y       * w + x + 1;
 844                 f2->dots[2] = g->dots + (y + 1) * w + x + 1;
 845             } else {
 846                 f1->dots[0] = g->dots + y       * w + x;
 847                 f1->dots[1] = g->dots + y       * w + x + 1;
 848                 f1->dots[2] = g->dots + (y + 1) * w + x;
 849                 f2->dots[0] = g->dots + y       * w + x + 1;
 850                 f2->dots[1] = g->dots + (y + 1) * w + x + 1;
 851                 f2->dots[2] = g->dots + (y + 1) * w + x;
 852             }
 853             index += 2;
 854         }
 855     }
 856
 857     /* "+ width" takes us to the middle of the row, because each row has
 858      * (2*width) faces. */
 859     g->middle_face = g->faces + (height / 2) * 2 * width + width;
 860
 861     grid_make_consistent(g);
 862     return g;
 863 }
 864
 865 grid *grid_new_snubsquare(int width, int height)
 866 {
 867     int x, y;
 868     /* Vector for side of triangle - ratio is close to sqrt(3) */
 869     int a = 15;
 870     int b = 26;
 871
 872     /* Upper bounds - don't have to be exact */
 873     int max_faces = 3 * width * height;
 874     int max_dots = 2 * (width + 1) * (height + 1);
 875
 876     tree234 *points;
 877
 878     grid *g = grid_new();
 879     g->tilesize = 18;
 880     g->faces = snewn(max_faces, grid_face);
 881     g->dots = snewn(max_dots, grid_dot);
 882
 883     points = newtree234(grid_point_cmp_fn);
 884
 885     for (y = 0; y < height; y++) {
 886         for (x = 0; x < width; x++) {
 887             grid_dot *d;
 888             /* face position */
 889             int px = (a + b) * x;
 890             int py = (a + b) * y;
 891
 892             /* generate square faces */
 893             grid_face_add_new(g, 4);
 894             if ((x + y) % 2) {
 895                 d = grid_get_dot(g, points, px + a, py);
 896                 grid_face_set_dot(g, d, 0);
 897                 d = grid_get_dot(g, points, px + a + b, py + a);
 898                 grid_face_set_dot(g, d, 1);
 899                 d = grid_get_dot(g, points, px + b, py + a + b);
 900                 grid_face_set_dot(g, d, 2);
 901                 d = grid_get_dot(g, points, px, py + b);
 902                 grid_face_set_dot(g, d, 3);
 903             } else {
 904                 d = grid_get_dot(g, points, px + b, py);
 905                 grid_face_set_dot(g, d, 0);
 906                 d = grid_get_dot(g, points, px + a + b, py + b);
 907                 grid_face_set_dot(g, d, 1);
 908                 d = grid_get_dot(g, points, px + a, py + a + b);
 909                 grid_face_set_dot(g, d, 2);
 910                 d = grid_get_dot(g, points, px, py + a);
 911                 grid_face_set_dot(g, d, 3);
 912             }
 913
 914             /* generate up/down triangles */
 915             if (x > 0) {
 916                 grid_face_add_new(g, 3);
 917                 if ((x + y) % 2) {
 918                     d = grid_get_dot(g, points, px + a, py);
 919                     grid_face_set_dot(g, d, 0);
 920                     d = grid_get_dot(g, points, px, py + b);
 921                     grid_face_set_dot(g, d, 1);
 922                     d = grid_get_dot(g, points, px - a, py);
 923                     grid_face_set_dot(g, d, 2);
 924                 } else {
 925                     d = grid_get_dot(g, points, px, py + a);
 926                     grid_face_set_dot(g, d, 0);
 927                     d = grid_get_dot(g, points, px + a, py + a + b);
 928                     grid_face_set_dot(g, d, 1);
 929                     d = grid_get_dot(g, points, px - a, py + a + b);
 930                     grid_face_set_dot(g, d, 2);
 931                 }
 932             }
 933
 934             /* generate left/right triangles */
 935             if (y > 0) {
 936                 grid_face_add_new(g, 3);
 937                 if ((x + y) % 2) {
 938                     d = grid_get_dot(g, points, px + a, py);
 939                     grid_face_set_dot(g, d, 0);
 940                     d = grid_get_dot(g, points, px + a + b, py - a);
 941                     grid_face_set_dot(g, d, 1);
 942                     d = grid_get_dot(g, points, px + a + b, py + a);
 943                     grid_face_set_dot(g, d, 2);
 944                 } else {
 945                     d = grid_get_dot(g, points, px, py - a);
 946                     grid_face_set_dot(g, d, 0);
 947                     d = grid_get_dot(g, points, px + b, py);
 948                     grid_face_set_dot(g, d, 1);
 949                     d = grid_get_dot(g, points, px, py + a);
 950                     grid_face_set_dot(g, d, 2);
 951                 }
 952             }
 953         }
 954     }
 955
 956     freetree234(points);
 957     assert(g->num_faces <= max_faces);
 958     assert(g->num_dots <= max_dots);
 959     g->middle_face = g->faces + (height/2) * width + (width/2);
 960
 961     grid_make_consistent(g);
 962     return g;
 963 }
 964
 965 grid *grid_new_cairo(int width, int height)
 966 {
 967     int x, y;
 968     /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
 969     int a = 14;
 970     int b = 31;
 971
 972     /* Upper bounds - don't have to be exact */
 973     int max_faces = 2 * width * height;
 974     int max_dots = 3 * (width + 1) * (height + 1);
 975
 976     tree234 *points;
 977
 978     grid *g = grid_new();
 979     g->tilesize = 40;
 980     g->faces = snewn(max_faces, grid_face);
 981     g->dots = snewn(max_dots, grid_dot);
 982
 983     points = newtree234(grid_point_cmp_fn);
 984
 985     for (y = 0; y < height; y++) {
 986         for (x = 0; x < width; x++) {
 987             grid_dot *d;
 988             /* cell position */
 989             int px = 2 * b * x;
 990             int py = 2 * b * y;
 991
 992             /* horizontal pentagons */
 993             if (y > 0) {
 994                 grid_face_add_new(g, 5);
 995                 if ((x + y) % 2) {
 996                     d = grid_get_dot(g, points, px + a, py - b);
 997                     grid_face_set_dot(g, d, 0);
 998                     d = grid_get_dot(g, points, px + 2*b - a, py - b);
 999                     grid_face_set_dot(g, d, 1);
1000                     d = grid_get_dot(g, points, px + 2*b, py);
1001                     grid_face_set_dot(g, d, 2);
1002                     d = grid_get_dot(g, points, px + b, py + a);
1003                     grid_face_set_dot(g, d, 3);
1004                     d = grid_get_dot(g, points, px, py);
1005                     grid_face_set_dot(g, d, 4);
1006                 } else {
1007                     d = grid_get_dot(g, points, px, py);
1008                     grid_face_set_dot(g, d, 0);
1009                     d = grid_get_dot(g, points, px + b, py - a);
1010                     grid_face_set_dot(g, d, 1);
1011                     d = grid_get_dot(g, points, px + 2*b, py);
1012                     grid_face_set_dot(g, d, 2);
1013                     d = grid_get_dot(g, points, px + 2*b - a, py + b);
1014                     grid_face_set_dot(g, d, 3);
1015                     d = grid_get_dot(g, points, px + a, py + b);
1016                     grid_face_set_dot(g, d, 4);
1017                 }
1018             }
1019             /* vertical pentagons */
1020             if (x > 0) {
1021                 grid_face_add_new(g, 5);
1022                 if ((x + y) % 2) {
1023                     d = grid_get_dot(g, points, px, py);
1024                     grid_face_set_dot(g, d, 0);
1025                     d = grid_get_dot(g, points, px + b, py + a);
1026                     grid_face_set_dot(g, d, 1);
1027                     d = grid_get_dot(g, points, px + b, py + 2*b - a);
1028                     grid_face_set_dot(g, d, 2);
1029                     d = grid_get_dot(g, points, px, py + 2*b);
1030                     grid_face_set_dot(g, d, 3);
1031                     d = grid_get_dot(g, points, px - a, py + b);
1032                     grid_face_set_dot(g, d, 4);
1033                 } else {
1034                     d = grid_get_dot(g, points, px, py);
1035                     grid_face_set_dot(g, d, 0);
1036                     d = grid_get_dot(g, points, px + a, py + b);
1037                     grid_face_set_dot(g, d, 1);
1038                     d = grid_get_dot(g, points, px, py + 2*b);
1039                     grid_face_set_dot(g, d, 2);
1040                     d = grid_get_dot(g, points, px - b, py + 2*b - a);
1041                     grid_face_set_dot(g, d, 3);
1042                     d = grid_get_dot(g, points, px - b, py + a);
1043                     grid_face_set_dot(g, d, 4);
1044                 }
1045             }
1046         }
1047     }
1048
1049     freetree234(points);
1050     assert(g->num_faces <= max_faces);
1051     assert(g->num_dots <= max_dots);
1052     g->middle_face = g->faces + (height/2) * width + (width/2);
1053
1054     grid_make_consistent(g);
1055     return g;
1056 }
1057
1058 grid *grid_new_greathexagonal(int width, int height)
1059 {
1060     int x, y;
1061     /* Vector for side of triangle - ratio is close to sqrt(3) */
1062     int a = 15;
1063     int b = 26;
1064
1065     /* Upper bounds - don't have to be exact */
1066     int max_faces = 6 * (width + 1) * (height + 1);
1067     int max_dots = 6 * width * height;
1068
1069     tree234 *points;
1070
1071     grid *g = grid_new();
1072     g->tilesize = 18;
1073     g->faces = snewn(max_faces, grid_face);
1074     g->dots = snewn(max_dots, grid_dot);
1075
1076     points = newtree234(grid_point_cmp_fn);
1077
1078     for (y = 0; y < height; y++) {
1079         for (x = 0; x < width; x++) {
1080             grid_dot *d;
1081             /* centre of hexagon */
1082             int px = (3*a + b) * x;
1083             int py = (2*a + 2*b) * y;
1084             if (x % 2)
1085                 py += a + b;
1086
1087             /* hexagon */
1088             grid_face_add_new(g, 6);
1089             d = grid_get_dot(g, points, px - a, py - b);
1090             grid_face_set_dot(g, d, 0);
1091             d = grid_get_dot(g, points, px + a, py - b);
1092             grid_face_set_dot(g, d, 1);
1093             d = grid_get_dot(g, points, px + 2*a, py);
1094             grid_face_set_dot(g, d, 2);
1095             d = grid_get_dot(g, points, px + a, py + b);
1096             grid_face_set_dot(g, d, 3);
1097             d = grid_get_dot(g, points, px - a, py + b);
1098             grid_face_set_dot(g, d, 4);
1099             d = grid_get_dot(g, points, px - 2*a, py);
1100             grid_face_set_dot(g, d, 5);
1101
1102             /* square below hexagon */
1103             if (y < height - 1) {
1104                 grid_face_add_new(g, 4);
1105                 d = grid_get_dot(g, points, px - a, py + b);
1106                 grid_face_set_dot(g, d, 0);
1107                 d = grid_get_dot(g, points, px + a, py + b);
1108                 grid_face_set_dot(g, d, 1);
1109                 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1110                 grid_face_set_dot(g, d, 2);
1111                 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1112                 grid_face_set_dot(g, d, 3);
1113             }
1114
1115             /* square below right */
1116             if ((x < width - 1) && (((x % 2) == 0) || (y < height - 1))) {
1117                 grid_face_add_new(g, 4);
1118                 d = grid_get_dot(g, points, px + 2*a, py);
1119                 grid_face_set_dot(g, d, 0);
1120                 d = grid_get_dot(g, points, px + 2*a + b, py + a);
1121                 grid_face_set_dot(g, d, 1);
1122                 d = grid_get_dot(g, points, px + a + b, py + a + b);
1123                 grid_face_set_dot(g, d, 2);
1124                 d = grid_get_dot(g, points, px + a, py + b);
1125                 grid_face_set_dot(g, d, 3);
1126             }
1127
1128             /* square below left */
1129             if ((x > 0) && (((x % 2) == 0) || (y < height - 1))) {
1130                 grid_face_add_new(g, 4);
1131                 d = grid_get_dot(g, points, px - 2*a, py);
1132                 grid_face_set_dot(g, d, 0);
1133                 d = grid_get_dot(g, points, px - a, py + b);
1134                 grid_face_set_dot(g, d, 1);
1135                 d = grid_get_dot(g, points, px - a - b, py + a + b);
1136                 grid_face_set_dot(g, d, 2);
1137                 d = grid_get_dot(g, points, px - 2*a - b, py + a);
1138                 grid_face_set_dot(g, d, 3);
1139             }
1140
1141             /* Triangle below right */
1142             if ((x < width - 1) && (y < height - 1)) {
1143                 grid_face_add_new(g, 3);
1144                 d = grid_get_dot(g, points, px + a, py + b);
1145                 grid_face_set_dot(g, d, 0);
1146                 d = grid_get_dot(g, points, px + a + b, py + a + b);
1147                 grid_face_set_dot(g, d, 1);
1148                 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1149                 grid_face_set_dot(g, d, 2);
1150             }
1151
1152             /* Triangle below left */
1153             if ((x > 0) && (y < height - 1)) {
1154                 grid_face_add_new(g, 3);
1155                 d = grid_get_dot(g, points, px - a, py + b);
1156                 grid_face_set_dot(g, d, 0);
1157                 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1158                 grid_face_set_dot(g, d, 1);
1159                 d = grid_get_dot(g, points, px - a - b, py + a + b);
1160                 grid_face_set_dot(g, d, 2);
1161             }
1162         }
1163     }
1164
1165     freetree234(points);
1166     assert(g->num_faces <= max_faces);
1167     assert(g->num_dots <= max_dots);
1168     g->middle_face = g->faces + (height/2) * width + (width/2);
1169
1170     grid_make_consistent(g);
1171     return g;
1172 }
1173
1174 grid *grid_new_octagonal(int width, int height)
1175 {
1176     int x, y;
1177     /* b/a approx sqrt(2) */
1178     int a = 29;
1179     int b = 41;
1180
1181     /* Upper bounds - don't have to be exact */
1182     int max_faces = 2 * width * height;
1183     int max_dots = 4 * (width + 1) * (height + 1);
1184
1185     tree234 *points;
1186
1187     grid *g = grid_new();
1188     g->tilesize = 40;
1189     g->faces = snewn(max_faces, grid_face);
1190     g->dots = snewn(max_dots, grid_dot);
1191
1192     points = newtree234(grid_point_cmp_fn);
1193
1194     for (y = 0; y < height; y++) {
1195         for (x = 0; x < width; x++) {
1196             grid_dot *d;
1197             /* cell position */
1198             int px = (2*a + b) * x;
1199             int py = (2*a + b) * y;
1200             /* octagon */
1201             grid_face_add_new(g, 8);
1202             d = grid_get_dot(g, points, px + a, py);
1203             grid_face_set_dot(g, d, 0);
1204             d = grid_get_dot(g, points, px + a + b, py);
1205             grid_face_set_dot(g, d, 1);
1206             d = grid_get_dot(g, points, px + 2*a + b, py + a);
1207             grid_face_set_dot(g, d, 2);
1208             d = grid_get_dot(g, points, px + 2*a + b, py + a + b);
1209             grid_face_set_dot(g, d, 3);
1210             d = grid_get_dot(g, points, px + a + b, py + 2*a + b);
1211             grid_face_set_dot(g, d, 4);
1212             d = grid_get_dot(g, points, px + a, py + 2*a + b);
1213             grid_face_set_dot(g, d, 5);
1214             d = grid_get_dot(g, points, px, py + a + b);
1215             grid_face_set_dot(g, d, 6);
1216             d = grid_get_dot(g, points, px, py + a);
1217             grid_face_set_dot(g, d, 7);
1218
1219             /* diamond */
1220             if ((x > 0) && (y > 0)) {
1221                 grid_face_add_new(g, 4);
1222                 d = grid_get_dot(g, points, px, py - a);
1223                 grid_face_set_dot(g, d, 0);
1224                 d = grid_get_dot(g, points, px + a, py);
1225                 grid_face_set_dot(g, d, 1);
1226                 d = grid_get_dot(g, points, px, py + a);
1227                 grid_face_set_dot(g, d, 2);
1228                 d = grid_get_dot(g, points, px - a, py);
1229                 grid_face_set_dot(g, d, 3);
1230             }
1231         }
1232     }
1233
1234     freetree234(points);
1235     assert(g->num_faces <= max_faces);
1236     assert(g->num_dots <= max_dots);
1237     g->middle_face = g->faces + (height/2) * width + (width/2);
1238
1239     grid_make_consistent(g);
1240     return g;
1241 }
1242
1243 grid *grid_new_kites(int width, int height)
1244 {
1245     int x, y;
1246     /* b/a approx sqrt(3) */
1247     int a = 15;
1248     int b = 26;
1249
1250     /* Upper bounds - don't have to be exact */
1251     int max_faces = 6 * width * height;
1252     int max_dots = 6 * (width + 1) * (height + 1);
1253
1254     tree234 *points;
1255
1256     grid *g = grid_new();
1257     g->tilesize = 40;
1258     g->faces = snewn(max_faces, grid_face);
1259     g->dots = snewn(max_dots, grid_dot);
1260
1261     points = newtree234(grid_point_cmp_fn);
1262
1263     for (y = 0; y < height; y++) {
1264         for (x = 0; x < width; x++) {
1265             grid_dot *d;
1266             /* position of order-6 dot */
1267             int px = 4*b * x;
1268             int py = 6*a * y;
1269             if (y % 2)
1270                 px += 2*b;
1271
1272             /* kite pointing up-left */
1273             grid_face_add_new(g, 4);
1274             d = grid_get_dot(g, points, px, py);
1275             grid_face_set_dot(g, d, 0);
1276             d = grid_get_dot(g, points, px + 2*b, py);
1277             grid_face_set_dot(g, d, 1);
1278             d = grid_get_dot(g, points, px + 2*b, py + 2*a);
1279             grid_face_set_dot(g, d, 2);
1280             d = grid_get_dot(g, points, px + b, py + 3*a);
1281             grid_face_set_dot(g, d, 3);
1282
1283             /* kite pointing up */
1284             grid_face_add_new(g, 4);
1285             d = grid_get_dot(g, points, px, py);
1286             grid_face_set_dot(g, d, 0);
1287             d = grid_get_dot(g, points, px + b, py + 3*a);
1288             grid_face_set_dot(g, d, 1);
1289             d = grid_get_dot(g, points, px, py + 4*a);
1290             grid_face_set_dot(g, d, 2);
1291             d = grid_get_dot(g, points, px - b, py + 3*a);
1292             grid_face_set_dot(g, d, 3);
1293
1294             /* kite pointing up-right */
1295             grid_face_add_new(g, 4);
1296             d = grid_get_dot(g, points, px, py);
1297             grid_face_set_dot(g, d, 0);
1298             d = grid_get_dot(g, points, px - b, py + 3*a);
1299             grid_face_set_dot(g, d, 1);
1300             d = grid_get_dot(g, points, px - 2*b, py + 2*a);
1301             grid_face_set_dot(g, d, 2);
1302             d = grid_get_dot(g, points, px - 2*b, py);
1303             grid_face_set_dot(g, d, 3);
1304
1305             /* kite pointing down-right */
1306             grid_face_add_new(g, 4);
1307             d = grid_get_dot(g, points, px, py);
1308             grid_face_set_dot(g, d, 0);
1309             d = grid_get_dot(g, points, px - 2*b, py);
1310             grid_face_set_dot(g, d, 1);
1311             d = grid_get_dot(g, points, px - 2*b, py - 2*a);
1312             grid_face_set_dot(g, d, 2);
1313             d = grid_get_dot(g, points, px - b, py - 3*a);
1314             grid_face_set_dot(g, d, 3);
1315
1316             /* kite pointing down */
1317             grid_face_add_new(g, 4);
1318             d = grid_get_dot(g, points, px, py);
1319             grid_face_set_dot(g, d, 0);
1320             d = grid_get_dot(g, points, px - b, py - 3*a);
1321             grid_face_set_dot(g, d, 1);
1322             d = grid_get_dot(g, points, px, py - 4*a);
1323             grid_face_set_dot(g, d, 2);
1324             d = grid_get_dot(g, points, px + b, py - 3*a);
1325             grid_face_set_dot(g, d, 3);
1326
1327             /* kite pointing down-left */
1328             grid_face_add_new(g, 4);
1329             d = grid_get_dot(g, points, px, py);
1330             grid_face_set_dot(g, d, 0);
1331             d = grid_get_dot(g, points, px + b, py - 3*a);
1332             grid_face_set_dot(g, d, 1);
1333             d = grid_get_dot(g, points, px + 2*b, py - 2*a);
1334             grid_face_set_dot(g, d, 2);
1335             d = grid_get_dot(g, points, px + 2*b, py);
1336             grid_face_set_dot(g, d, 3);
1337         }
1338     }
1339
1340     freetree234(points);
1341     assert(g->num_faces <= max_faces);
1342     assert(g->num_dots <= max_dots);
1343     g->middle_face = g->faces + 6 * ((height/2) * width + (width/2));
1344
1345     grid_make_consistent(g);
1346     return g;
1347 }
1348
1349 /* ----------- End of grid generators ------------- */