From 881746789a489fad85aae8317555f73dbe261556 Mon Sep 17 00:00:00 2001 From: Franklin Wei Date: Sat, 29 Apr 2017 18:21:56 -0400 Subject: puzzles: refactor and resync with upstream This brings puzzles up-to-date with upstream revision 2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made by me, including cursor-only Untangle and some compilation fixes remain. Upstream code has been moved to its separate subdirectory and future syncs can be done by simply copying over the new sources. Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804 --- apps/plugins/puzzles/src/grid.c | 3065 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 3065 insertions(+) create mode 100644 apps/plugins/puzzles/src/grid.c (limited to 'apps/plugins/puzzles/src/grid.c') diff --git a/apps/plugins/puzzles/src/grid.c b/apps/plugins/puzzles/src/grid.c new file mode 100644 index 0000000000..4929b5c7d3 --- /dev/null +++ b/apps/plugins/puzzles/src/grid.c @@ -0,0 +1,3065 @@ +/* + * (c) Lambros Lambrou 2008 + * + * Code for working with general grids, which can be any planar graph + * with faces, edges and vertices (dots). Includes generators for a few + * types of grid, including square, hexagonal, triangular and others. + */ + +#include +#include +#include +#include +#include +#include +#include + +#include "puzzles.h" +#include "tree234.h" +#include "grid.h" +#include "penrose.h" + +/* Debugging options */ + +/* +#define DEBUG_GRID +*/ + +/* ---------------------------------------------------------------------- + * Deallocate or dereference a grid + */ +void grid_free(grid *g) +{ + assert(g->refcount); + + g->refcount--; + if (g->refcount == 0) { + int i; + for (i = 0; i < g->num_faces; i++) { + sfree(g->faces[i].dots); + sfree(g->faces[i].edges); + } + for (i = 0; i < g->num_dots; i++) { + sfree(g->dots[i].faces); + sfree(g->dots[i].edges); + } + sfree(g->faces); + sfree(g->edges); + sfree(g->dots); + sfree(g); + } +} + +/* Used by the other grid generators. Create a brand new grid with nothing + * initialised (all lists are NULL) */ +static grid *grid_empty(void) +{ + grid *g = snew(grid); + g->faces = NULL; + g->edges = NULL; + g->dots = NULL; + g->num_faces = g->num_edges = g->num_dots = 0; + g->refcount = 1; + g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0; + return g; +} + +/* Helper function to calculate perpendicular distance from + * a point P to a line AB. A and B mustn't be equal here. + * + * Well-known formula for area A of a triangle: + * / 1 1 1 \ + * 2A = determinant of matrix | px ax bx | + * \ py ay by / + * + * Also well-known: 2A = base * height + * = perpendicular distance * line-length. + * + * Combining gives: distance = determinant / line-length(a,b) + */ +static double point_line_distance(long px, long py, + long ax, long ay, + long bx, long by) +{ + long det = ax*by - bx*ay + bx*py - px*by + px*ay - ax*py; + double len; + det = max(det, -det); + len = sqrt(SQ(ax - bx) + SQ(ay - by)); + return det / len; +} + +/* Determine nearest edge to where the user clicked. + * (x, y) is the clicked location, converted to grid coordinates. + * Returns the nearest edge, or NULL if no edge is reasonably + * near the position. + * + * Just judging edges by perpendicular distance is not quite right - + * the edge might be "off to one side". So we insist that the triangle + * with (x,y) has acute angles at the edge's dots. + * + * edge1 + * *---------*------ + * | + * | *(x,y) + * edge2 | + * | edge2 is OK, but edge1 is not, even though + * | edge1 is perpendicularly closer to (x,y) + * * + * + */ +grid_edge *grid_nearest_edge(grid *g, int x, int y) +{ + grid_edge *best_edge; + double best_distance = 0; + int i; + + best_edge = NULL; + + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = &g->edges[i]; + long e2; /* squared length of edge */ + long a2, b2; /* squared lengths of other sides */ + double dist; + + /* See if edge e is eligible - the triangle must have acute angles + * at the edge's dots. + * Pythagoras formula h^2 = a^2 + b^2 detects right-angles, + * so detect acute angles by testing for h^2 < a^2 + b^2 */ + e2 = SQ((long)e->dot1->x - (long)e->dot2->x) + SQ((long)e->dot1->y - (long)e->dot2->y); + a2 = SQ((long)e->dot1->x - (long)x) + SQ((long)e->dot1->y - (long)y); + b2 = SQ((long)e->dot2->x - (long)x) + SQ((long)e->dot2->y - (long)y); + if (a2 >= e2 + b2) continue; + if (b2 >= e2 + a2) continue; + + /* e is eligible so far. Now check the edge is reasonably close + * to where the user clicked. Don't want to toggle an edge if the + * click was way off the grid. + * There is room for experimentation here. We could check the + * perpendicular distance is within a certain fraction of the length + * of the edge. That amounts to testing a rectangular region around + * the edge. + * Alternatively, we could check that the angle at the point is obtuse. + * That would amount to testing a circular region with the edge as + * diameter. */ + dist = point_line_distance((long)x, (long)y, + (long)e->dot1->x, (long)e->dot1->y, + (long)e->dot2->x, (long)e->dot2->y); + /* Is dist more than half edge length ? */ + if (4 * SQ(dist) > e2) + continue; + + if (best_edge == NULL || dist < best_distance) { + best_edge = e; + best_distance = dist; + } + } + return best_edge; +} + +/* ---------------------------------------------------------------------- + * Grid generation + */ + +#ifdef SVG_GRID + +#define SVG_DOTS 1 +#define SVG_EDGES 2 +#define SVG_FACES 4 + +#define FACE_COLOUR "red" +#define EDGE_COLOUR "blue" +#define DOT_COLOUR "black" + +static void grid_output_svg(FILE *fp, grid *g, int which) +{ + int i, j; + + fprintf(fp,"\ +\n\ +\n\ +\n\ +\n\n"); + + if (which & SVG_FACES) { + fprintf(fp, "\n"); + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + fprintf(fp, "order; j++) { + grid_dot *d = f->dots[j]; + fprintf(fp, "%s%d,%d", (j == 0) ? "" : " ", + d->x, d->y); + } + fprintf(fp, "\" style=\"fill: %s; fill-opacity: 0.2; stroke: %s\" />\n", + FACE_COLOUR, FACE_COLOUR); + } + fprintf(fp, "\n"); + } + if (which & SVG_EDGES) { + fprintf(fp, "\n"); + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + grid_dot *d1 = e->dot1, *d2 = e->dot2; + + fprintf(fp, "\n", + d1->x, d1->y, d2->x, d2->y, EDGE_COLOUR); + } + fprintf(fp, "\n"); + } + + if (which & SVG_DOTS) { + fprintf(fp, "\n"); + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + fprintf(fp, "", + d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR); + } + fprintf(fp, "\n"); + } + + fprintf(fp, "\n"); +} +#endif + +#ifdef SVG_GRID +#include + +static void grid_try_svg(grid *g, int which) +{ + char *svg = getenv("PUZZLES_SVG_GRID"); + if (svg) { + FILE *svgf = fopen(svg, "w"); + if (svgf) { + grid_output_svg(svgf, g, which); + fclose(svgf); + } else { + fprintf(stderr, "Unable to open file `%s': %s", svg, strerror(errno)); + } + } +} +#endif + +/* Show the basic grid information, before doing grid_make_consistent */ +static void grid_debug_basic(grid *g) +{ + /* TODO: Maybe we should generate an SVG image of the dots and lines + * of the grid here, before grid_make_consistent. + * Would help with debugging grid generation. */ +#ifdef DEBUG_GRID + int i; + printf("--- Basic Grid Data ---\n"); + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + printf("Face %d: dots[", i); + int j; + for (j = 0; j < f->order; j++) { + grid_dot *d = f->dots[j]; + printf("%s%d", j ? "," : "", (int)(d - g->dots)); + } + printf("]\n"); + } +#endif +#ifdef SVG_GRID + grid_try_svg(g, SVG_FACES); +#endif +} + +/* Show the derived grid information, computed by grid_make_consistent */ +static void grid_debug_derived(grid *g) +{ +#ifdef DEBUG_GRID + /* edges */ + int i; + printf("--- Derived Grid Data ---\n"); + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + printf("Edge %d: dots[%d,%d] faces[%d,%d]\n", + i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots), + e->face1 ? (int)(e->face1 - g->faces) : -1, + e->face2 ? (int)(e->face2 - g->faces) : -1); + } + /* faces */ + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int j; + printf("Face %d: faces[", i); + for (j = 0; j < f->order; j++) { + grid_edge *e = f->edges[j]; + grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1; + printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1); + } + printf("]\n"); + } + /* dots */ + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + int j; + printf("Dot %d: dots[", i); + for (j = 0; j < d->order; j++) { + grid_edge *e = d->edges[j]; + grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1; + printf("%s%d", j ? "," : "", (int)(d2 - g->dots)); + } + printf("] faces["); + for (j = 0; j < d->order; j++) { + grid_face *f = d->faces[j]; + printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1); + } + printf("]\n"); + } +#endif +#ifdef SVG_GRID + grid_try_svg(g, SVG_DOTS | SVG_EDGES | SVG_FACES); +#endif +} + +/* Helper function for building incomplete-edges list in + * grid_make_consistent() */ +static int grid_edge_bydots_cmpfn(void *v1, void *v2) +{ + grid_edge *a = v1; + grid_edge *b = v2; + grid_dot *da, *db; + + /* Pointer subtraction is valid here, because all dots point into the + * same dot-list (g->dots). + * Edges are not "normalised" - the 2 dots could be stored in any order, + * so we need to take this into account when comparing edges. */ + + /* Compare first dots */ + da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2; + db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2; + if (da != db) + return db - da; + /* Compare last dots */ + da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1; + db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1; + if (da != db) + return db - da; + + return 0; +} + +/* + * 'Vigorously trim' a grid, by which I mean deleting any isolated or + * uninteresting faces. By which, in turn, I mean: ensure that the + * grid is composed solely of faces adjacent to at least one + * 'landlocked' dot (i.e. one not in contact with the infinite + * exterior face), and that all those dots are in a single connected + * component. + * + * This function operates on, and returns, a grid satisfying the + * preconditions to grid_make_consistent() rather than the + * postconditions. (So call it first.) + */ +static void grid_trim_vigorously(grid *g) +{ + int *dotpairs, *faces, *dots; + int *dsf; + int i, j, k, size, newfaces, newdots; + + /* + * First construct a matrix in which each ordered pair of dots is + * mapped to the index of the face in which those dots occur in + * that order. + */ + dotpairs = snewn(g->num_dots * g->num_dots, int); + for (i = 0; i < g->num_dots; i++) + for (j = 0; j < g->num_dots; j++) + dotpairs[i*g->num_dots+j] = -1; + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int dot0 = f->dots[f->order-1] - g->dots; + for (j = 0; j < f->order; j++) { + int dot1 = f->dots[j] - g->dots; + dotpairs[dot0 * g->num_dots + dot1] = i; + dot0 = dot1; + } + } + + /* + * Now we can identify landlocked dots: they're the ones all of + * whose edges have a mirror-image counterpart in this matrix. + */ + dots = snewn(g->num_dots, int); + for (i = 0; i < g->num_dots; i++) { + dots[i] = TRUE; + for (j = 0; j < g->num_dots; j++) { + if ((dotpairs[i*g->num_dots+j] >= 0) ^ + (dotpairs[j*g->num_dots+i] >= 0)) + dots[i] = FALSE; /* non-duplicated edge: coastal dot */ + } + } + + /* + * Now identify connected pairs of landlocked dots, and form a dsf + * unifying them. + */ + dsf = snew_dsf(g->num_dots); + for (i = 0; i < g->num_dots; i++) + for (j = 0; j < i; j++) + if (dots[i] && dots[j] && + dotpairs[i*g->num_dots+j] >= 0 && + dotpairs[j*g->num_dots+i] >= 0) + dsf_merge(dsf, i, j); + + /* + * Now look for the largest component. + */ + size = 0; + j = -1; + for (i = 0; i < g->num_dots; i++) { + int newsize; + if (dots[i] && dsf_canonify(dsf, i) == i && + (newsize = dsf_size(dsf, i)) > size) { + j = i; + size = newsize; + } + } + + /* + * Work out which faces we're going to keep (precisely those with + * at least one dot in the same connected component as j) and + * which dots (those required by any face we're keeping). + * + * At this point we reuse the 'dots' array to indicate the dots + * we're keeping, rather than the ones that are landlocked. + */ + faces = snewn(g->num_faces, int); + for (i = 0; i < g->num_faces; i++) + faces[i] = 0; + for (i = 0; i < g->num_dots; i++) + dots[i] = 0; + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int keep = FALSE; + for (k = 0; k < f->order; k++) + if (dsf_canonify(dsf, f->dots[k] - g->dots) == j) + keep = TRUE; + if (keep) { + faces[i] = TRUE; + for (k = 0; k < f->order; k++) + dots[f->dots[k]-g->dots] = TRUE; + } + } + + /* + * Work out the new indices of those faces and dots, when we + * compact the arrays containing them. + */ + for (i = newfaces = 0; i < g->num_faces; i++) + faces[i] = (faces[i] ? newfaces++ : -1); + for (i = newdots = 0; i < g->num_dots; i++) + dots[i] = (dots[i] ? newdots++ : -1); + + /* + * Free the dynamically allocated 'dots' pointer lists in faces + * we're going to discard. + */ + for (i = 0; i < g->num_faces; i++) + if (faces[i] < 0) + sfree(g->faces[i].dots); + + /* + * Go through and compact the arrays. + */ + for (i = 0; i < g->num_dots; i++) + if (dots[i] >= 0) { + grid_dot *dnew = g->dots + dots[i], *dold = g->dots + i; + *dnew = *dold; /* structure copy */ + } + for (i = 0; i < g->num_faces; i++) + if (faces[i] >= 0) { + grid_face *fnew = g->faces + faces[i], *fold = g->faces + i; + *fnew = *fold; /* structure copy */ + for (j = 0; j < fnew->order; j++) { + /* + * Reindex the dots in this face. + */ + k = fnew->dots[j] - g->dots; + fnew->dots[j] = g->dots + dots[k]; + } + } + g->num_faces = newfaces; + g->num_dots = newdots; + + sfree(dotpairs); + sfree(dsf); + sfree(dots); + sfree(faces); +} + +/* Input: grid has its dots and faces initialised: + * - dots have (optionally) x and y coordinates, but no edges or faces + * (pointers are NULL). + * - edges not initialised at all + * - faces initialised and know which dots they have (but no edges yet). The + * dots around each face are assumed to be clockwise. + * + * Output: grid is complete and valid with all relationships defined. + */ +static void grid_make_consistent(grid *g) +{ + int i; + tree234 *incomplete_edges; + grid_edge *next_new_edge; /* Where new edge will go into g->edges */ + + grid_debug_basic(g); + + /* ====== Stage 1 ====== + * Generate edges + */ + + /* We know how many dots and faces there are, so we can find the exact + * number of edges from Euler's polyhedral formula: F + V = E + 2 . + * We use "-1", not "-2" here, because Euler's formula includes the + * infinite face, which we don't count. */ + g->num_edges = g->num_faces + g->num_dots - 1; + g->edges = snewn(g->num_edges, grid_edge); + next_new_edge = g->edges; + + /* Iterate over faces, and over each face's dots, generating edges as we + * go. As we find each new edge, we can immediately fill in the edge's + * dots, but only one of the edge's faces. Later on in the iteration, we + * will find the same edge again (unless it's on the border), but we will + * know the other face. + * For efficiency, maintain a list of the incomplete edges, sorted by + * their dots. */ + incomplete_edges = newtree234(grid_edge_bydots_cmpfn); + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int j; + for (j = 0; j < f->order; j++) { + grid_edge e; /* fake edge for searching */ + grid_edge *edge_found; + int j2 = j + 1; + if (j2 == f->order) + j2 = 0; + e.dot1 = f->dots[j]; + e.dot2 = f->dots[j2]; + /* Use del234 instead of find234, because we always want to + * remove the edge if found */ + edge_found = del234(incomplete_edges, &e); + if (edge_found) { + /* This edge already added, so fill out missing face. + * Edge is already removed from incomplete_edges. */ + edge_found->face2 = f; + } else { + assert(next_new_edge - g->edges < g->num_edges); + next_new_edge->dot1 = e.dot1; + next_new_edge->dot2 = e.dot2; + next_new_edge->face1 = f; + next_new_edge->face2 = NULL; /* potentially infinite face */ + add234(incomplete_edges, next_new_edge); + ++next_new_edge; + } + } + } + freetree234(incomplete_edges); + + /* ====== Stage 2 ====== + * For each face, build its edge list. + */ + + /* Allocate space for each edge list. Can do this, because each face's + * edge-list is the same size as its dot-list. */ + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int j; + f->edges = snewn(f->order, grid_edge*); + /* Preload with NULLs, to help detect potential bugs. */ + for (j = 0; j < f->order; j++) + f->edges[j] = NULL; + } + + /* Iterate over each edge, and over both its faces. Add this edge to + * the face's edge-list, after finding where it should go in the + * sequence. */ + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + int j; + for (j = 0; j < 2; j++) { + grid_face *f = j ? e->face2 : e->face1; + int k, k2; + if (f == NULL) continue; + /* Find one of the dots around the face */ + for (k = 0; k < f->order; k++) { + if (f->dots[k] == e->dot1) + break; /* found dot1 */ + } + assert(k != f->order); /* Must find the dot around this face */ + + /* Labelling scheme: as we walk clockwise around the face, + * starting at dot0 (f->dots[0]), we hit: + * (dot0), edge0, dot1, edge1, dot2,... + * + * 0 + * 0-----1 + * | + * |1 + * | + * 3-----2 + * 2 + * + * Therefore, edgeK joins dotK and dot{K+1} + */ + + /* Around this face, either the next dot or the previous dot + * must be e->dot2. Otherwise the edge is wrong. */ + k2 = k + 1; + if (k2 == f->order) + k2 = 0; + if (f->dots[k2] == e->dot2) { + /* dot1(k) and dot2(k2) go clockwise around this face, so add + * this edge at position k (see diagram). */ + assert(f->edges[k] == NULL); + f->edges[k] = e; + continue; + } + /* Try previous dot */ + k2 = k - 1; + if (k2 == -1) + k2 = f->order - 1; + if (f->dots[k2] == e->dot2) { + /* dot1(k) and dot2(k2) go anticlockwise around this face. */ + assert(f->edges[k2] == NULL); + f->edges[k2] = e; + continue; + } + assert(!"Grid broken: bad edge-face relationship"); + } + } + + /* ====== Stage 3 ====== + * For each dot, build its edge-list and face-list. + */ + + /* We don't know how many edges/faces go around each dot, so we can't + * allocate the right space for these lists. Pre-compute the sizes by + * iterating over each edge and recording a tally against each dot. */ + for (i = 0; i < g->num_dots; i++) { + g->dots[i].order = 0; + } + for (i = 0; i < g->num_edges; i++) { + grid_edge *e = g->edges + i; + ++(e->dot1->order); + ++(e->dot2->order); + } + /* Now we have the sizes, pre-allocate the edge and face lists. */ + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + int j; + assert(d->order >= 2); /* sanity check */ + d->edges = snewn(d->order, grid_edge*); + d->faces = snewn(d->order, grid_face*); + for (j = 0; j < d->order; j++) { + d->edges[j] = NULL; + d->faces[j] = NULL; + } + } + /* For each dot, need to find a face that touches it, so we can seed + * the edge-face-edge-face process around each dot. */ + for (i = 0; i < g->num_faces; i++) { + grid_face *f = g->faces + i; + int j; + for (j = 0; j < f->order; j++) { + grid_dot *d = f->dots[j]; + d->faces[0] = f; + } + } + /* Each dot now has a face in its first slot. Generate the remaining + * faces and edges around the dot, by searching both clockwise and + * anticlockwise from the first face. Need to do both directions, + * because of the possibility of hitting the infinite face, which + * blocks progress. But there's only one such face, so we will + * succeed in finding every edge and face this way. */ + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + int current_face1 = 0; /* ascends clockwise */ + int current_face2 = 0; /* descends anticlockwise */ + + /* Labelling scheme: as we walk clockwise around the dot, starting + * at face0 (d->faces[0]), we hit: + * (face0), edge0, face1, edge1, face2,... + * + * 0 + * | + * 0 | 1 + * | + * -----d-----1 + * | + * | 2 + * | + * 2 + * + * So, for example, face1 should be joined to edge0 and edge1, + * and those edges should appear in an anticlockwise sense around + * that face (see diagram). */ + + /* clockwise search */ + while (TRUE) { + grid_face *f = d->faces[current_face1]; + grid_edge *e; + int j; + assert(f != NULL); + /* find dot around this face */ + for (j = 0; j < f->order; j++) { + if (f->dots[j] == d) + break; + } + assert(j != f->order); /* must find dot */ + + /* Around f, required edge is anticlockwise from the dot. See + * the other labelling scheme higher up, for why we subtract 1 + * from j. */ + j--; + if (j == -1) + j = f->order - 1; + e = f->edges[j]; + d->edges[current_face1] = e; /* set edge */ + current_face1++; + if (current_face1 == d->order) + break; + else { + /* set face */ + d->faces[current_face1] = + (e->face1 == f) ? e->face2 : e->face1; + if (d->faces[current_face1] == NULL) + break; /* cannot progress beyond infinite face */ + } + } + /* If the clockwise search made it all the way round, don't need to + * bother with the anticlockwise search. */ + if (current_face1 == d->order) + continue; /* this dot is complete, move on to next dot */ + + /* anticlockwise search */ + while (TRUE) { + grid_face *f = d->faces[current_face2]; + grid_edge *e; + int j; + assert(f != NULL); + /* find dot around this face */ + for (j = 0; j < f->order; j++) { + if (f->dots[j] == d) + break; + } + assert(j != f->order); /* must find dot */ + + /* Around f, required edge is clockwise from the dot. */ + e = f->edges[j]; + + current_face2--; + if (current_face2 == -1) + current_face2 = d->order - 1; + d->edges[current_face2] = e; /* set edge */ + + /* set face */ + if (current_face2 == current_face1) + break; + d->faces[current_face2] = + (e->face1 == f) ? e->face2 : e->face1; + /* There's only 1 infinite face, so we must get all the way + * to current_face1 before we hit it. */ + assert(d->faces[current_face2]); + } + } + + /* ====== Stage 4 ====== + * Compute other grid settings + */ + + /* Bounding rectangle */ + for (i = 0; i < g->num_dots; i++) { + grid_dot *d = g->dots + i; + if (i == 0) { + g->lowest_x = g->highest_x = d->x; + g->lowest_y = g->highest_y = d->y; + } else { + g->lowest_x = min(g->lowest_x, d->x); + g->highest_x = max(g->highest_x, d->x); + g->lowest_y = min(g->lowest_y, d->y); + g->highest_y = max(g->highest_y, d->y); + } + } + + grid_debug_derived(g); +} + +/* Helpers for making grid-generation easier. These functions are only + * intended for use during grid generation. */ + +/* Comparison function for the (tree234) sorted dot list */ +static int grid_point_cmp_fn(void *v1, void *v2) +{ + grid_dot *p1 = v1; + grid_dot *p2 = v2; + if (p1->y != p2->y) + return p2->y - p1->y; + else + return p2->x - p1->x; +} +/* Add a new face to the grid, with its dot list allocated. + * Assumes there's enough space allocated for the new face in grid->faces */ +static void grid_face_add_new(grid *g, int face_size) +{ + int i; + grid_face *new_face = g->faces + g->num_faces; + new_face->order = face_size; + new_face->dots = snewn(face_size, grid_dot*); + for (i = 0; i < face_size; i++) + new_face->dots[i] = NULL; + new_face->edges = NULL; + new_face->has_incentre = FALSE; + g->num_faces++; +} +/* Assumes dot list has enough space */ +static grid_dot *grid_dot_add_new(grid *g, int x, int y) +{ + grid_dot *new_dot = g->dots + g->num_dots; + new_dot->order = 0; + new_dot->edges = NULL; + new_dot->faces = NULL; + new_dot->x = x; + new_dot->y = y; + g->num_dots++; + return new_dot; +} +/* Retrieve a dot with these (x,y) coordinates. Either return an existing dot + * in the dot_list, or add a new dot to the grid (and the dot_list) and + * return that. + * Assumes g->dots has enough capacity allocated */ +static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y) +{ + grid_dot test, *ret; + + test.order = 0; + test.edges = NULL; + test.faces = NULL; + test.x = x; + test.y = y; + ret = find234(dot_list, &test, NULL); + if (ret) + return ret; + + ret = grid_dot_add_new(g, x, y); + add234(dot_list, ret); + return ret; +} + +/* Sets the last face of the grid to include this dot, at this position + * around the face. Assumes num_faces is at least 1 (a new face has + * previously been added, with the required number of dots allocated) */ +static void grid_face_set_dot(grid *g, grid_dot *d, int position) +{ + grid_face *last_face = g->faces + g->num_faces - 1; + last_face->dots[position] = d; +} + +/* + * Helper routines for grid_find_incentre. + */ +static int solve_2x2_matrix(double mx[4], double vin[2], double vout[2]) +{ + double inv[4]; + double det; + det = (mx[0]*mx[3] - mx[1]*mx[2]); + if (det == 0) + return FALSE; + + inv[0] = mx[3] / det; + inv[1] = -mx[1] / det; + inv[2] = -mx[2] / det; + inv[3] = mx[0] / det; + + vout[0] = inv[0]*vin[0] + inv[1]*vin[1]; + vout[1] = inv[2]*vin[0] + inv[3]*vin[1]; + + return TRUE; +} +static int solve_3x3_matrix(double mx[9], double vin[3], double vout[3]) +{ + double inv[9]; + double det; + + det = (mx[0]*mx[4]*mx[8] + mx[1]*mx[5]*mx[6] + mx[2]*mx[3]*mx[7] - + mx[0]*mx[5]*mx[7] - mx[1]*mx[3]*mx[8] - mx[2]*mx[4]*mx[6]); + if (det == 0) + return FALSE; + + inv[0] = (mx[4]*mx[8] - mx[5]*mx[7]) / det; + inv[1] = (mx[2]*mx[7] - mx[1]*mx[8]) / det; + inv[2] = (mx[1]*mx[5] - mx[2]*mx[4]) / det; + inv[3] = (mx[5]*mx[6] - mx[3]*mx[8]) / det; + inv[4] = (mx[0]*mx[8] - mx[2]*mx[6]) / det; + inv[5] = (mx[2]*mx[3] - mx[0]*mx[5]) / det; + inv[6] = (mx[3]*mx[7] - mx[4]*mx[6]) / det; + inv[7] = (mx[1]*mx[6] - mx[0]*mx[7]) / det; + inv[8] = (mx[0]*mx[4] - mx[1]*mx[3]) / det; + + vout[0] = inv[0]*vin[0] + inv[1]*vin[1] + inv[2]*vin[2]; + vout[1] = inv[3]*vin[0] + inv[4]*vin[1] + inv[5]*vin[2]; + vout[2] = inv[6]*vin[0] + inv[7]*vin[1] + inv[8]*vin[2]; + + return TRUE; +} + +void grid_find_incentre(grid_face *f) +{ + double xbest, ybest, bestdist; + int i, j, k, m; + grid_dot *edgedot1[3], *edgedot2[3]; + grid_dot *dots[3]; + int nedges, ndots; + + if (f->has_incentre) + return; + + /* + * Find the point in the polygon with the maximum distance to any + * edge or corner. + * + * Such a point must exist which is in contact with at least three + * edges and/or vertices. (Proof: if it's only in contact with two + * edges and/or vertices, it can't even be at a _local_ maximum - + * any such circle can always be expanded in some direction.) So + * we iterate through all 3-subsets of the combined set of edges + * and vertices; for each subset we generate one or two candidate + * points that might be the incentre, and then we vet each one to + * see if it's inside the polygon and what its maximum radius is. + * + * (There's one case which this algorithm will get noticeably + * wrong, and that's when a continuum of equally good answers + * exists due to parallel edges. Consider a long thin rectangle, + * for instance, or a parallelogram. This algorithm will pick a + * point near one end, and choose the end arbitrarily; obviously a + * nicer point to choose would be in the centre. To fix this I + * would have to introduce a special-case system which detected + * parallel edges in advance, set aside all candidate points + * generated using both edges in a parallel pair, and generated + * some additional candidate points half way between them. Also, + * of course, I'd have to cope with rounding error making such a + * point look worse than one of its endpoints. So I haven't done + * this for the moment, and will cross it if necessary when I come + * to it.) + * + * We don't actually iterate literally over _edges_, in the sense + * of grid_edge structures. Instead, we fill in edgedot1[] and + * edgedot2[] with a pair of dots adjacent in the face's list of + * vertices. This ensures that we get the edges in consistent + * orientation, which we could not do from the grid structure + * alone. (A moment's consideration of an order-3 vertex should + * make it clear that if a notional arrow was written on each + * edge, _at least one_ of the three faces bordering that vertex + * would have to have the two arrows tip-to-tip or tail-to-tail + * rather than tip-to-tail.) + */ + nedges = ndots = 0; + bestdist = 0; + xbest = ybest = 0; + + for (i = 0; i+2 < 2*f->order; i++) { + if (i < f->order) { + edgedot1[nedges] = f->dots[i]; + edgedot2[nedges++] = f->dots[(i+1)%f->order]; + } else + dots[ndots++] = f->dots[i - f->order]; + + for (j = i+1; j+1 < 2*f->order; j++) { + if (j < f->order) { + edgedot1[nedges] = f->dots[j]; + edgedot2[nedges++] = f->dots[(j+1)%f->order]; + } else + dots[ndots++] = f->dots[j - f->order]; + + for (k = j+1; k < 2*f->order; k++) { + double cx[2], cy[2]; /* candidate positions */ + int cn = 0; /* number of candidates */ + + if (k < f->order) { + edgedot1[nedges] = f->dots[k]; + edgedot2[nedges++] = f->dots[(k+1)%f->order]; + } else + dots[ndots++] = f->dots[k - f->order]; + + /* + * Find a point, or pair of points, equidistant from + * all the specified edges and/or vertices. + */ + if (nedges == 3) { + /* + * Three edges. This is a linear matrix equation: + * each row of the matrix represents the fact that + * the point (x,y) we seek is at distance r from + * that edge, and we solve three of those + * simultaneously to obtain x,y,r. (We ignore r.) + */ + double matrix[9], vector[3], vector2[3]; + int m; + + for (m = 0; m < 3; m++) { + int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x; + int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y; + int dx = x2-x1, dy = y2-y1; + + /* + * ((x,y) - (x1,y1)) . (dy,-dx) = r |(dx,dy)| + * + * => x dy - y dx - r |(dx,dy)| = (x1 dy - y1 dx) + */ + matrix[3*m+0] = dy; + matrix[3*m+1] = -dx; + matrix[3*m+2] = -sqrt((double)dx*dx+(double)dy*dy); + vector[m] = (double)x1*dy - (double)y1*dx; + } + + if (solve_3x3_matrix(matrix, vector, vector2)) { + cx[cn] = vector2[0]; + cy[cn] = vector2[1]; + cn++; + } + } else if (nedges == 2) { + /* + * Two edges and a dot. This will end up in a + * quadratic equation. + * + * First, look at the two edges. Having our point + * be some distance r from both of them gives rise + * to a pair of linear equations in x,y,r of the + * form + * + * (x-x1) dy - (y-y1) dx = r sqrt(dx^2+dy^2) + * + * We eliminate r between those equations to give + * us a single linear equation in x,y describing + * the locus of points equidistant from both lines + * - i.e. the angle bisector. + * + * We then choose one of x,y to be a parameter t, + * and derive linear formulae for x,y,r in terms + * of t. This enables us to write down the + * circular equation (x-xd)^2+(y-yd)^2=r^2 as a + * quadratic in t; solving that and substituting + * in for x,y gives us two candidate points. + */ + double eqs[2][4]; /* a,b,c,d : ax+by+cr=d */ + double eq[3]; /* a,b,c: ax+by=c */ + double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */ + double q[3]; /* a,b,c: at^2+bt+c=0 */ + double disc; + + /* Find equations of the two input lines. */ + for (m = 0; m < 2; m++) { + int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x; + int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y; + int dx = x2-x1, dy = y2-y1; + + eqs[m][0] = dy; + eqs[m][1] = -dx; + eqs[m][2] = -sqrt(dx*dx+dy*dy); + eqs[m][3] = x1*dy - y1*dx; + } + + /* Derive the angle bisector by eliminating r. */ + eq[0] = eqs[0][0]*eqs[1][2] - eqs[1][0]*eqs[0][2]; + eq[1] = eqs[0][1]*eqs[1][2] - eqs[1][1]*eqs[0][2]; + eq[2] = eqs[0][3]*eqs[1][2] - eqs[1][3]*eqs[0][2]; + + /* Parametrise x and y in terms of some t. */ + if (fabs(eq[0]) < fabs(eq[1])) { + /* Parameter is x. */ + xt[0] = 1; xt[1] = 0; + yt[0] = -eq[0]/eq[1]; yt[1] = eq[2]/eq[1]; + } else { + /* Parameter is y. */ + yt[0] = 1; yt[1] = 0; + xt[0] = -eq[1]/eq[0]; xt[1] = eq[2]/eq[0]; + } + + /* Find a linear representation of r using eqs[0]. */ + rt[0] = -(eqs[0][0]*xt[0] + eqs[0][1]*yt[0])/eqs[0][2]; + rt[1] = (eqs[0][3] - eqs[0][0]*xt[1] - + eqs[0][1]*yt[1])/eqs[0][2]; + + /* Construct the quadratic equation. */ + q[0] = -rt[0]*rt[0]; + q[1] = -2*rt[0]*rt[1]; + q[2] = -rt[1]*rt[1]; + q[0] += xt[0]*xt[0]; + q[1] += 2*xt[0]*(xt[1]-dots[0]->x); + q[2] += (xt[1]-dots[0]->x)*(xt[1]-dots[0]->x); + q[0] += yt[0]*yt[0]; + q[1] += 2*yt[0]*(yt[1]-dots[0]->y); + q[2] += (yt[1]-dots[0]->y)*(yt[1]-dots[0]->y); + + /* And solve it. */ + disc = q[1]*q[1] - 4*q[0]*q[2]; + if (disc >= 0) { + double t; + + disc = sqrt(disc); + + t = (-q[1] + disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + + t = (-q[1] - disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + } + } else if (nedges == 1) { + /* + * Two dots and an edge. This one's another + * quadratic equation. + * + * The point we want must lie on the perpendicular + * bisector of the two dots; that much is obvious. + * So we can construct a parametrisation of that + * bisecting line, giving linear formulae for x,y + * in terms of t. We can also express the distance + * from the edge as such a linear formula. + * + * Then we set that equal to the radius of the + * circle passing through the two points, which is + * a Pythagoras exercise; that gives rise to a + * quadratic in t, which we solve. + */ + double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */ + double q[3]; /* a,b,c: at^2+bt+c=0 */ + double disc; + double halfsep; + + /* Find parametric formulae for x,y. */ + { + int x1 = dots[0]->x, x2 = dots[1]->x; + int y1 = dots[0]->y, y2 = dots[1]->y; + int dx = x2-x1, dy = y2-y1; + double d = sqrt((double)dx*dx + (double)dy*dy); + + xt[1] = (x1+x2)/2.0; + yt[1] = (y1+y2)/2.0; + /* It's convenient if we have t at standard scale. */ + xt[0] = -dy/d; + yt[0] = dx/d; + + /* Also note down half the separation between + * the dots, for use in computing the circle radius. */ + halfsep = 0.5*d; + } + + /* Find a parametric formula for r. */ + { + int x1 = edgedot1[0]->x, x2 = edgedot2[0]->x; + int y1 = edgedot1[0]->y, y2 = edgedot2[0]->y; + int dx = x2-x1, dy = y2-y1; + double d = sqrt((double)dx*dx + (double)dy*dy); + rt[0] = (xt[0]*dy - yt[0]*dx) / d; + rt[1] = ((xt[1]-x1)*dy - (yt[1]-y1)*dx) / d; + } + + /* Construct the quadratic equation. */ + q[0] = rt[0]*rt[0]; + q[1] = 2*rt[0]*rt[1]; + q[2] = rt[1]*rt[1]; + q[0] -= 1; + q[2] -= halfsep*halfsep; + + /* And solve it. */ + disc = q[1]*q[1] - 4*q[0]*q[2]; + if (disc >= 0) { + double t; + + disc = sqrt(disc); + + t = (-q[1] + disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + + t = (-q[1] - disc) / (2*q[0]); + cx[cn] = xt[0]*t + xt[1]; + cy[cn] = yt[0]*t + yt[1]; + cn++; + } + } else if (nedges == 0) { + /* + * Three dots. This is another linear matrix + * equation, this time with each row of the matrix + * representing the perpendicular bisector between + * two of the points. Of course we only need two + * such lines to find their intersection, so we + * need only solve a 2x2 matrix equation. + */ + + double matrix[4], vector[2], vector2[2]; + int m; + + for (m = 0; m < 2; m++) { + int x1 = dots[m]->x, x2 = dots[m+1]->x; + int y1 = dots[m]->y, y2 = dots[m+1]->y; + int dx = x2-x1, dy = y2-y1; + + /* + * ((x,y) - (x1,y1)) . (dx,dy) = 1/2 |(dx,dy)|^2 + * + * => 2x dx + 2y dy = dx^2+dy^2 + (2 x1 dx + 2 y1 dy) + */ + matrix[2*m+0] = 2*dx; + matrix[2*m+1] = 2*dy; + vector[m] = ((double)dx*dx + (double)dy*dy + + 2.0*x1*dx + 2.0*y1*dy); + } + + if (solve_2x2_matrix(matrix, vector, vector2)) { + cx[cn] = vector2[0]; + cy[cn] = vector2[1]; + cn++; + } + } + + /* + * Now go through our candidate points and see if any + * of them are better than what we've got so far. + */ + for (m = 0; m < cn; m++) { + double x = cx[m], y = cy[m]; + + /* + * First, disqualify the point if it's not inside + * the polygon, which we work out by counting the + * edges to the right of the point. (For + * tiebreaking purposes when edges start or end on + * our y-coordinate or go right through it, we + * consider our point to be offset by a small + * _positive_ epsilon in both the x- and + * y-direction.) + */ + int e, in = 0; + for (e = 0; e < f->order; e++) { + int xs = f->edges[e]->dot1->x; + int xe = f->edges[e]->dot2->x; + int ys = f->edges[e]->dot1->y; + int ye = f->edges[e]->dot2->y; + if ((y >= ys && y < ye) || (y >= ye && y < ys)) { + /* + * The line goes past our y-position. Now we need + * to know if its x-coordinate when it does so is + * to our right. + * + * The x-coordinate in question is mathematically + * (y - ys) * (xe - xs) / (ye - ys), and we want + * to know whether (x - xs) >= that. Of course we + * avoid the division, so we can work in integers; + * to do this we must multiply both sides of the + * inequality by ye - ys, which means we must + * first check that's not negative. + */ + int num = xe - xs, denom = ye - ys; + if (denom < 0) { + num = -num; + denom = -denom; + } + if ((x - xs) * denom >= (y - ys) * num) + in ^= 1; + } + } + + if (in) { +#ifdef HUGE_VAL + double mindist = HUGE_VAL; +#else +#ifdef DBL_MAX + double mindist = DBL_MAX; +#else +#error No way to get maximum floating-point number. +#endif +#endif + int e, d; + + /* + * This point is inside the polygon, so now we check + * its minimum distance to every edge and corner. + * First the corners ... + */ + for (d = 0; d < f->order; d++) { + int xp = f->dots[d]->x; + int yp = f->dots[d]->y; + double dx = x - xp, dy = y - yp; + double dist = dx*dx + dy*dy; + if (mindist > dist) + mindist = dist; + } + + /* + * ... and now also check the perpendicular distance + * to every edge, if the perpendicular lies between + * the edge's endpoints. + */ + for (e = 0; e < f->order; e++) { + int xs = f->edges[e]->dot1->x; + int xe = f->edges[e]->dot2->x; + int ys = f->edges[e]->dot1->y; + int ye = f->edges[e]->dot2->y; + + /* + * If s and e are our endpoints, and p our + * candidate circle centre, the foot of a + * perpendicular from p to the line se lies + * between s and e if and only if (p-s).(e-s) lies + * strictly between 0 and (e-s).(e-s). + */ + int edx = xe - xs, edy = ye - ys; + double pdx = x - xs, pdy = y - ys; + double pde = pdx * edx + pdy * edy; + long ede = (long)edx * edx + (long)edy * edy; + if (0 < pde && pde < ede) { + /* + * Yes, the nearest point on this edge is + * closer than either endpoint, so we must + * take it into account by measuring the + * perpendicular distance to the edge and + * checking its square against mindist. + */ + + double pdre = pdx * edy - pdy * edx; + double sqlen = pdre * pdre / ede; + + if (mindist > sqlen) + mindist = sqlen; + } + } + + /* + * Right. Now we know the biggest circle around this + * point, so we can check it against bestdist. + */ + if (bestdist < mindist) { + bestdist = mindist; + xbest = x; + ybest = y; + } + } + } + + if (k < f->order) + nedges--; + else + ndots--; + } + if (j < f->order) + nedges--; + else + ndots--; + } + if (i < f->order) + nedges--; + else + ndots--; + } + + assert(bestdist > 0); + + f->has_incentre = TRUE; + f->ix = xbest + 0.5; /* round to nearest */ + f->iy = ybest + 0.5; +} + +/* ------ Generate various types of grid ------ */ + +/* General method is to generate faces, by calculating their dot coordinates. + * As new faces are added, we keep track of all the dots so we can tell when + * a new face reuses an existing dot. For example, two squares touching at an + * edge would generate six unique dots: four dots from the first face, then + * two additional dots for the second face, because we detect the other two + * dots have already been taken up. This list is stored in a tree234 + * called "points". No extra memory-allocation needed here - we store the + * actual grid_dot* pointers, which all point into the g->dots list. + * For this reason, we have to calculate coordinates in such a way as to + * eliminate any rounding errors, so we can detect when a dot on one + * face precisely lands on a dot of a different face. No floating-point + * arithmetic here! + */ + +#define SQUARE_TILESIZE 20 + +static void grid_size_square(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = SQUARE_TILESIZE; + + *tilesize = a; + *xextent = width * a; + *yextent = height * a; +} + +static grid *grid_new_square(int width, int height, const char *desc) +{ + int x, y; + /* Side length */ + int a = SQUARE_TILESIZE; + + /* Upper bounds - don't have to be exact */ + int max_faces = width * height; + int max_dots = (width + 1) * (height + 1); + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = a; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + /* generate square faces */ + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* face position */ + int px = a * x; + int py = a * y; + + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py + a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px, py + a); + grid_face_set_dot(g, d, 3); + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +#define HONEY_TILESIZE 45 +/* Vector for side of hexagon - ratio is close to sqrt(3) */ +#define HONEY_A 15 +#define HONEY_B 26 + +static void grid_size_honeycomb(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = HONEY_A; + int b = HONEY_B; + + *tilesize = HONEY_TILESIZE; + *xextent = (3 * a * (width-1)) + 4*a; + *yextent = (2 * b * (height-1)) + 3*b; +} + +static grid *grid_new_honeycomb(int width, int height, const char *desc) +{ + int x, y; + int a = HONEY_A; + int b = HONEY_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = width * height; + int max_dots = 2 * (width + 1) * (height + 1); + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = HONEY_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + /* generate hexagonal faces */ + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* face centre */ + int cx = 3 * a * x; + int cy = 2 * b * y; + if (x % 2) + cy += b; + grid_face_add_new(g, 6); + + d = grid_get_dot(g, points, cx - a, cy - b); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, cx + a, cy - b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, cx + 2*a, cy); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, cx + a, cy + b); + grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, cx - a, cy + b); + grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, cx - 2*a, cy); + grid_face_set_dot(g, d, 5); + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +#define TRIANGLE_TILESIZE 18 +/* Vector for side of triangle - ratio is close to sqrt(3) */ +#define TRIANGLE_VEC_X 15 +#define TRIANGLE_VEC_Y 26 + +static void grid_size_triangular(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int vec_x = TRIANGLE_VEC_X; + int vec_y = TRIANGLE_VEC_Y; + + *tilesize = TRIANGLE_TILESIZE; + *xextent = (width+1) * 2 * vec_x; + *yextent = height * vec_y; +} + +static char *grid_validate_desc_triangular(grid_type type, int width, + int height, const char *desc) +{ + /* + * Triangular grids: an absent description is valid (indicating + * the old-style approach which had 'ears', i.e. triangles + * connected to only one other face, at some grid corners), and so + * is a description reading just "0" (indicating the new-style + * approach in which those ears are trimmed off). Anything else is + * illegal. + */ + + if (!desc || !strcmp(desc, "0")) + return NULL; + + return "Unrecognised grid description."; +} + +/* Doesn't use the previous method of generation, it pre-dates it! + * A triangular grid is just about simple enough to do by "brute force" */ +static grid *grid_new_triangular(int width, int height, const char *desc) +{ + int x,y; + int version = (desc == NULL ? -1 : atoi(desc)); + + /* Vector for side of triangle - ratio is close to sqrt(3) */ + int vec_x = TRIANGLE_VEC_X; + int vec_y = TRIANGLE_VEC_Y; + + int index; + + /* convenient alias */ + int w = width + 1; + + grid *g = grid_empty(); + g->tilesize = TRIANGLE_TILESIZE; + + if (version == -1) { + /* + * Old-style triangular grid generation, preserved as-is for + * backwards compatibility with old game ids, in which it's + * just a little asymmetric and there are 'ears' (faces linked + * to only one other face) at two grid corners. + * + * Example old-style game ids, which should still work, and in + * which you should see the ears in the TL/BR corners on the + * first one and in the TL/BL corners on the second: + * + * 5x5t1:2c2a1a2a201a1a1a1112a1a2b1211f0b21a2a2a0a + * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e + */ + + g->num_faces = width * height * 2; + g->num_dots = (width + 1) * (height + 1); + g->faces = snewn(g->num_faces, grid_face); + g->dots = snewn(g->num_dots, grid_dot); + + /* generate dots */ + index = 0; + for (y = 0; y <= height; y++) { + for (x = 0; x <= width; x++) { + grid_dot *d = g->dots + index; + /* odd rows are offset to the right */ + d->order = 0; + d->edges = NULL; + d->faces = NULL; + d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0); + d->y = y * vec_y; + index++; + } + } + + /* generate faces */ + index = 0; + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + /* initialise two faces for this (x,y) */ + grid_face *f1 = g->faces + index; + grid_face *f2 = f1 + 1; + f1->edges = NULL; + f1->order = 3; + f1->dots = snewn(f1->order, grid_dot*); + f1->has_incentre = FALSE; + f2->edges = NULL; + f2->order = 3; + f2->dots = snewn(f2->order, grid_dot*); + f2->has_incentre = FALSE; + + /* face descriptions depend on whether the row-number is + * odd or even */ + if (y % 2) { + f1->dots[0] = g->dots + y * w + x; + f1->dots[1] = g->dots + (y + 1) * w + x + 1; + f1->dots[2] = g->dots + (y + 1) * w + x; + f2->dots[0] = g->dots + y * w + x; + f2->dots[1] = g->dots + y * w + x + 1; + f2->dots[2] = g->dots + (y + 1) * w + x + 1; + } else { + f1->dots[0] = g->dots + y * w + x; + f1->dots[1] = g->dots + y * w + x + 1; + f1->dots[2] = g->dots + (y + 1) * w + x; + f2->dots[0] = g->dots + y * w + x + 1; + f2->dots[1] = g->dots + (y + 1) * w + x + 1; + f2->dots[2] = g->dots + (y + 1) * w + x; + } + index += 2; + } + } + } else { + /* + * New-style approach, in which there are never any 'ears', + * and if height is even then the grid is nicely 4-way + * symmetric. + * + * Example new-style grids: + * + * 5x5t1:0_21120b11a1a01a1a00c1a0b211021c1h1a2a1a0a + * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1 + */ + tree234 *points = newtree234(grid_point_cmp_fn); + /* Upper bounds - don't have to be exact */ + int max_faces = height * (2*width+1); + int max_dots = (height+1) * (width+1) * 4; + + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + for (y = 0; y < height; y++) { + /* + * Each row contains (width+1) triangles one way up, and + * (width) triangles the other way up. Which way up is + * which varies with parity of y. Also, the dots around + * each face will flip direction with parity of y, so we + * set up n1 and n2 to cope with that easily. + */ + int y0, y1, n1, n2; + y0 = y1 = y * vec_y; + if (y % 2) { + y1 += vec_y; + n1 = 2; n2 = 1; + } else { + y0 += vec_y; + n1 = 1; n2 = 2; + } + + for (x = 0; x <= width; x++) { + int x0 = 2*x * vec_x, x1 = x0 + vec_x, x2 = x1 + vec_x; + + /* + * If the grid has odd height, then we skip the first + * and last triangles on this row, otherwise they'll + * end up as ears. + */ + if (height % 2 == 1 && y == height-1 && (x == 0 || x == width)) + continue; + + grid_face_add_new(g, 3); + grid_face_set_dot(g, grid_get_dot(g, points, x0, y0), 0); + grid_face_set_dot(g, grid_get_dot(g, points, x1, y1), n1); + grid_face_set_dot(g, grid_get_dot(g, points, x2, y0), n2); + } + + for (x = 0; x < width; x++) { + int x0 = (2*x+1) * vec_x, x1 = x0 + vec_x, x2 = x1 + vec_x; + + grid_face_add_new(g, 3); + grid_face_set_dot(g, grid_get_dot(g, points, x0, y1), 0); + grid_face_set_dot(g, grid_get_dot(g, points, x1, y0), n2); + grid_face_set_dot(g, grid_get_dot(g, points, x2, y1), n1); + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + } + + grid_make_consistent(g); + return g; +} + +#define SNUBSQUARE_TILESIZE 18 +/* Vector for side of triangle - ratio is close to sqrt(3) */ +#define SNUBSQUARE_A 15 +#define SNUBSQUARE_B 26 + +static void grid_size_snubsquare(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = SNUBSQUARE_A; + int b = SNUBSQUARE_B; + + *tilesize = SNUBSQUARE_TILESIZE; + *xextent = (a+b) * (width-1) + a + b; + *yextent = (a+b) * (height-1) + a + b; +} + +static grid *grid_new_snubsquare(int width, int height, const char *desc) +{ + int x, y; + int a = SNUBSQUARE_A; + int b = SNUBSQUARE_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 3 * width * height; + int max_dots = 2 * (width + 1) * (height + 1); + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = SNUBSQUARE_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* face position */ + int px = (a + b) * x; + int py = (a + b) * y; + + /* generate square faces */ + grid_face_add_new(g, 4); + if ((x + y) % 2) { + d = grid_get_dot(g, points, px + a, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a + b, py + a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + b, py + a + b); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px, py + b); + grid_face_set_dot(g, d, 3); + } else { + d = grid_get_dot(g, points, px + b, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a + b, py + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py + a + b); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px, py + a); + grid_face_set_dot(g, d, 3); + } + + /* generate up/down triangles */ + if (x > 0) { + grid_face_add_new(g, 3); + if ((x + y) % 2) { + d = grid_get_dot(g, points, px + a, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px, py + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py); + grid_face_set_dot(g, d, 2); + } else { + d = grid_get_dot(g, points, px, py + a); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py + a + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py + a + b); + grid_face_set_dot(g, d, 2); + } + } + + /* generate left/right triangles */ + if (y > 0) { + grid_face_add_new(g, 3); + if ((x + y) % 2) { + d = grid_get_dot(g, points, px + a, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a + b, py - a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a + b, py + a); + grid_face_set_dot(g, d, 2); + } else { + d = grid_get_dot(g, points, px, py - a); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + b, py); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px, py + a); + grid_face_set_dot(g, d, 2); + } + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +#define CAIRO_TILESIZE 40 +/* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */ +#define CAIRO_A 14 +#define CAIRO_B 31 + +static void grid_size_cairo(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int b = CAIRO_B; /* a unused in determining grid size. */ + + *tilesize = CAIRO_TILESIZE; + *xextent = 2*b*(width-1) + 2*b; + *yextent = 2*b*(height-1) + 2*b; +} + +static grid *grid_new_cairo(int width, int height, const char *desc) +{ + int x, y; + int a = CAIRO_A; + int b = CAIRO_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 2 * width * height; + int max_dots = 3 * (width + 1) * (height + 1); + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = CAIRO_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* cell position */ + int px = 2 * b * x; + int py = 2 * b * y; + + /* horizontal pentagons */ + if (y > 0) { + grid_face_add_new(g, 5); + if ((x + y) % 2) { + d = grid_get_dot(g, points, px + a, py - b); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + 2*b - a, py - b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 2*b, py); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + b, py + a); + grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 4); + } else { + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + b, py - a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 2*b, py); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + 2*b - a, py + b); + grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + a, py + b); + grid_face_set_dot(g, d, 4); + } + } + /* vertical pentagons */ + if (x > 0) { + grid_face_add_new(g, 5); + if ((x + y) % 2) { + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + b, py + a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + b, py + 2*b - a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px, py + 2*b); + grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px - a, py + b); + grid_face_set_dot(g, d, 4); + } else { + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px, py + 2*b); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - b, py + 2*b - a); + grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px - b, py + a); + grid_face_set_dot(g, d, 4); + } + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +#define GREATHEX_TILESIZE 18 +/* Vector for side of triangle - ratio is close to sqrt(3) */ +#define GREATHEX_A 15 +#define GREATHEX_B 26 + +static void grid_size_greathexagonal(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = GREATHEX_A; + int b = GREATHEX_B; + + *tilesize = GREATHEX_TILESIZE; + *xextent = (3*a + b) * (width-1) + 4*a; + *yextent = (2*a + 2*b) * (height-1) + 3*b + a; +} + +static grid *grid_new_greathexagonal(int width, int height, const char *desc) +{ + int x, y; + int a = GREATHEX_A; + int b = GREATHEX_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 6 * (width + 1) * (height + 1); + int max_dots = 6 * width * height; + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = GREATHEX_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* centre of hexagon */ + int px = (3*a + b) * x; + int py = (2*a + 2*b) * y; + if (x % 2) + py += a + b; + + /* hexagon */ + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px - a, py - b); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py - b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 2*a, py); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + a, py + b); + grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px - a, py + b); + grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px - 2*a, py); + grid_face_set_dot(g, d, 5); + + /* square below hexagon */ + if (y < height - 1) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px - a, py + b); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py + 2*a + b); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - a, py + 2*a + b); + grid_face_set_dot(g, d, 3); + } + + /* square below right */ + if ((x < width - 1) && (((x % 2) == 0) || (y < height - 1))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + 2*a, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + 2*a + b, py + a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a + b, py + a + b); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + a, py + b); + grid_face_set_dot(g, d, 3); + } + + /* square below left */ + if ((x > 0) && (((x % 2) == 0) || (y < height - 1))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px - 2*a, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - a, py + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a - b, py + a + b); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - 2*a - b, py + a); + grid_face_set_dot(g, d, 3); + } + + /* Triangle below right */ + if ((x < width - 1) && (y < height - 1)) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px + a, py + b); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a + b, py + a + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py + 2*a + b); + grid_face_set_dot(g, d, 2); + } + + /* Triangle below left */ + if ((x > 0) && (y < height - 1)) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px - a, py + b); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - a, py + 2*a + b); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a - b, py + a + b); + grid_face_set_dot(g, d, 2); + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +#define OCTAGONAL_TILESIZE 40 +/* b/a approx sqrt(2) */ +#define OCTAGONAL_A 29 +#define OCTAGONAL_B 41 + +static void grid_size_octagonal(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = OCTAGONAL_A; + int b = OCTAGONAL_B; + + *tilesize = OCTAGONAL_TILESIZE; + *xextent = (2*a + b) * width; + *yextent = (2*a + b) * height; +} + +static grid *grid_new_octagonal(int width, int height, const char *desc) +{ + int x, y; + int a = OCTAGONAL_A; + int b = OCTAGONAL_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 2 * width * height; + int max_dots = 4 * (width + 1) * (height + 1); + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = OCTAGONAL_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* cell position */ + int px = (2*a + b) * x; + int py = (2*a + b) * y; + /* octagon */ + grid_face_add_new(g, 8); + d = grid_get_dot(g, points, px + a, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a + b, py); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 2*a + b, py + a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + 2*a + b, py + a + b); + grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + a + b, py + 2*a + b); + grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + a, py + 2*a + b); + grid_face_set_dot(g, d, 5); + d = grid_get_dot(g, points, px, py + a + b); + grid_face_set_dot(g, d, 6); + d = grid_get_dot(g, points, px, py + a); + grid_face_set_dot(g, d, 7); + + /* diamond */ + if ((x > 0) && (y > 0)) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py - a); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px, py + a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - a, py); + grid_face_set_dot(g, d, 3); + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +#define KITE_TILESIZE 40 +/* b/a approx sqrt(3) */ +#define KITE_A 15 +#define KITE_B 26 + +static void grid_size_kites(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = KITE_A; + int b = KITE_B; + + *tilesize = KITE_TILESIZE; + *xextent = 4*b * width + 2*b; + *yextent = 6*a * (height-1) + 8*a; +} + +static grid *grid_new_kites(int width, int height, const char *desc) +{ + int x, y; + int a = KITE_A; + int b = KITE_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 6 * width * height; + int max_dots = 6 * (width + 1) * (height + 1); + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = KITE_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* position of order-6 dot */ + int px = 4*b * x; + int py = 6*a * y; + if (y % 2) + px += 2*b; + + /* kite pointing up-left */ + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + 2*b, py); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 2*b, py + 2*a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + b, py + 3*a); + grid_face_set_dot(g, d, 3); + + /* kite pointing up */ + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + b, py + 3*a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px, py + 4*a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - b, py + 3*a); + grid_face_set_dot(g, d, 3); + + /* kite pointing up-right */ + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - b, py + 3*a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - 2*b, py + 2*a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - 2*b, py); + grid_face_set_dot(g, d, 3); + + /* kite pointing down-right */ + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - 2*b, py); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - 2*b, py - 2*a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - b, py - 3*a); + grid_face_set_dot(g, d, 3); + + /* kite pointing down */ + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - b, py - 3*a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px, py - 4*a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + b, py - 3*a); + grid_face_set_dot(g, d, 3); + + /* kite pointing down-left */ + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px, py); + grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + b, py - 3*a); + grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 2*b, py - 2*a); + grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + 2*b, py); + grid_face_set_dot(g, d, 3); + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +#define FLORET_TILESIZE 150 +/* -py/px is close to tan(30 - atan(sqrt(3)/9)) + * using py=26 makes everything lean to the left, rather than right + */ +#define FLORET_PX 75 +#define FLORET_PY -26 + +static void grid_size_floret(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */ + int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */ + int ry = qy-py; + /* rx unused in determining grid size. */ + + *tilesize = FLORET_TILESIZE; + *xextent = (6*px+3*qx)/2 * (width-1) + 4*qx + 2*px; + *yextent = (5*qy-4*py) * (height-1) + 4*qy + 2*ry; +} + +static grid *grid_new_floret(int width, int height, const char *desc) +{ + int x, y; + /* Vectors for sides; weird numbers needed to keep puzzle aligned with window + * -py/px is close to tan(30 - atan(sqrt(3)/9)) + * using py=26 makes everything lean to the left, rather than right + */ + int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */ + int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */ + int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */ + + /* Upper bounds - don't have to be exact */ + int max_faces = 6 * width * height; + int max_dots = 9 * (width + 1) * (height + 1); + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = FLORET_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + /* generate pentagonal faces */ + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* face centre */ + int cx = (6*px+3*qx)/2 * x; + int cy = (4*py-5*qy) * y; + if (x % 2) + cy -= (4*py-5*qy)/2; + else if (y && y == height-1) + continue; /* make better looking grids? try 3x3 for instance */ + + grid_face_add_new(g, 5); + d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, cx+2*rx , cy+2*ry ); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, cx+2*rx+qx, cy+2*ry+qy); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, cx+2*qx+rx, cy+2*qy+ry); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, cx+2*qx , cy+2*qy ); grid_face_set_dot(g, d, 4); + + grid_face_add_new(g, 5); + d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, cx+2*qx , cy+2*qy ); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, cx+2*qx+px, cy+2*qy+py); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, cx+2*px+qx, cy+2*py+qy); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, cx+2*px , cy+2*py ); grid_face_set_dot(g, d, 4); + + grid_face_add_new(g, 5); + d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, cx+2*px , cy+2*py ); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, cx+2*px-rx, cy+2*py-ry); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, cx-2*rx+px, cy-2*ry+py); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, cx-2*rx , cy-2*ry ); grid_face_set_dot(g, d, 4); + + grid_face_add_new(g, 5); + d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, cx-2*rx , cy-2*ry ); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, cx-2*rx-qx, cy-2*ry-qy); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, cx-2*qx-rx, cy-2*qy-ry); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, cx-2*qx , cy-2*qy ); grid_face_set_dot(g, d, 4); + + grid_face_add_new(g, 5); + d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, cx-2*qx , cy-2*qy ); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, cx-2*qx-px, cy-2*qy-py); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, cx-2*px-qx, cy-2*py-qy); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, cx-2*px , cy-2*py ); grid_face_set_dot(g, d, 4); + + grid_face_add_new(g, 5); + d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, cx-2*px , cy-2*py ); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, cx-2*px+rx, cy-2*py+ry); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, cx+2*rx-px, cy+2*ry-py); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, cx+2*rx , cy+2*ry ); grid_face_set_dot(g, d, 4); + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +/* DODEC_* are used for dodecagonal and great-dodecagonal grids. */ +#define DODEC_TILESIZE 26 +/* Vector for side of triangle - ratio is close to sqrt(3) */ +#define DODEC_A 15 +#define DODEC_B 26 + +static void grid_size_dodecagonal(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = DODEC_A; + int b = DODEC_B; + + *tilesize = DODEC_TILESIZE; + *xextent = (4*a + 2*b) * (width-1) + 3*(2*a + b); + *yextent = (3*a + 2*b) * (height-1) + 2*(2*a + b); +} + +static grid *grid_new_dodecagonal(int width, int height, const char *desc) +{ + int x, y; + int a = DODEC_A; + int b = DODEC_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 3 * width * height; + int max_dots = 14 * width * height; + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = DODEC_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* centre of dodecagon */ + int px = (4*a + 2*b) * x; + int py = (3*a + 2*b) * y; + if (y % 2) + px += 2*a + b; + + /* dodecagon */ + grid_face_add_new(g, 12); + d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5); + d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6); + d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7); + d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10); + d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11); + + /* triangle below dodecagon */ + if ((y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px , py + (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 2); + } + + /* triangle above dodecagon */ + if ((y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px , py - (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 2); + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +static void grid_size_greatdodecagonal(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = DODEC_A; + int b = DODEC_B; + + *tilesize = DODEC_TILESIZE; + *xextent = (6*a + 2*b) * (width-1) + 2*(2*a + b) + 3*a + b; + *yextent = (3*a + 3*b) * (height-1) + 2*(2*a + b); +} + +static grid *grid_new_greatdodecagonal(int width, int height, const char *desc) +{ + int x, y; + /* Vector for side of triangle - ratio is close to sqrt(3) */ + int a = DODEC_A; + int b = DODEC_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 30 * width * height; + int max_dots = 200 * width * height; + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = DODEC_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* centre of dodecagon */ + int px = (6*a + 2*b) * x; + int py = (3*a + 3*b) * y; + if (y % 2) + px += 3*a + b; + + /* dodecagon */ + grid_face_add_new(g, 12); + d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5); + d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6); + d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7); + d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10); + d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11); + + /* hexagon below dodecagon */ + if (y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) { + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px - 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 5); + } + + /* hexagon above dodecagon */ + if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) { + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 5); + } + + /* square on right of dodecagon */ + if (x < width - 1) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + 2*a + b, py - a); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + 4*a + b, py - a); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + 4*a + b, py + a); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + 2*a + b, py + a); grid_face_set_dot(g, d, 3); + } + + /* square on top right of dodecagon */ + if (y && (x < width - 1 || !(y % 2))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 3); + } + + /* square on top left of dodecagon */ + if (y && (x || (y % 2))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 3); + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +static void grid_size_greatgreatdodecagonal(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int a = DODEC_A; + int b = DODEC_B; + + *tilesize = DODEC_TILESIZE; + *xextent = (4*a + 4*b) * (width-1) + 2*(2*a + b) + 2*a + 2*b; + *yextent = (6*a + 2*b) * (height-1) + 2*(2*a + b); +} + +static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *desc) +{ + int x, y; + /* Vector for side of triangle - ratio is close to sqrt(3) */ + int a = DODEC_A; + int b = DODEC_B; + + /* Upper bounds - don't have to be exact */ + int max_faces = 50 * width * height; + int max_dots = 300 * width * height; + + tree234 *points; + + grid *g = grid_empty(); + g->tilesize = DODEC_TILESIZE; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + for (y = 0; y < height; y++) { + for (x = 0; x < width; x++) { + grid_dot *d; + /* centre of dodecagon */ + int px = (4*a + 4*b) * x; + int py = (6*a + 2*b) * y; + if (y % 2) + px += 2*a + 2*b; + + /* dodecagon */ + grid_face_add_new(g, 12); + d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5); + d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6); + d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7); + d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10); + d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11); + + /* hexagon on top right of dodecagon */ + if (y && (x < width - 1 || !(y % 2))) { + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px + (a + 2*b), py - (4*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + (a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (a + b), py - ( a + b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (a ), py - (2*a + b)); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + (a ), py - (4*a + b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + (a + b), py - (5*a + b)); grid_face_set_dot(g, d, 5); + } + + /* hexagon on right of dodecagon*/ + if (x < width - 1) { + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px + (2*a + 3*b), py - a); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + (2*a + 3*b), py + a); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + 2*b), py + 2*a); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (2*a + b), py + a); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + (2*a + b), py - a); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + (2*a + 2*b), py - 2*a); grid_face_set_dot(g, d, 5); + } + + /* hexagon on bottom right of dodecagon */ + if ((y < height - 1) && (x < width - 1 || !(y % 2))) { + grid_face_add_new(g, 6); + d = grid_get_dot(g, points, px + (a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + (a + 2*b), py + (4*a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (a + b), py + (5*a + b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (a ), py + (4*a + b)); grid_face_set_dot(g, d, 3); + d = grid_get_dot(g, points, px + (a ), py + (2*a + b)); grid_face_set_dot(g, d, 4); + d = grid_get_dot(g, points, px + (a + b), py + ( a + b)); grid_face_set_dot(g, d, 5); + } + + /* square on top right of dodecagon */ + if (y && (x < width - 1 )) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 3); + } + + /* square on bottom right of dodecagon */ + if ((y < height - 1) && (x < width - 1 )) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3); + } + + /* square below dodecagon */ + if ((y < height - 1) && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py + (4*a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py + (4*a + b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 3); + } + + /* square on bottom left of dodecagon */ + if (x && (y < height - 1)) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 3); + } + + /* square on top left of dodecagon */ + if (x && y) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 3); + + } + + /* square above dodecagon */ + if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) { + grid_face_add_new(g, 4); + d = grid_get_dot(g, points, px + a, py - (4*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 2); + d = grid_get_dot(g, points, px - a, py - (4*a + b)); grid_face_set_dot(g, d, 3); + } + + /* upper triangle (v) */ + if (y && (x < width - 1)) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px + (3*a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 2); + } + + /* lower triangle (^) */ + if ((y < height - 1) && (x < width - 1)) { + grid_face_add_new(g, 3); + d = grid_get_dot(g, points, px + (3*a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0); + d = grid_get_dot(g, points, px + ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 1); + d = grid_get_dot(g, points, px + (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 2); + } + } + } + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + grid_make_consistent(g); + return g; +} + +typedef struct setface_ctx +{ + int xmin, xmax, ymin, ymax; + + grid *g; + tree234 *points; +} setface_ctx; + +static double round_int_nearest_away(double r) +{ + return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); +} + +static int set_faces(penrose_state *state, vector *vs, int n, int depth) +{ + setface_ctx *sf_ctx = (setface_ctx *)state->ctx; + int i; + int xs[4], ys[4]; + + if (depth < state->max_depth) return 0; +#ifdef DEBUG_PENROSE + if (n != 4) return 0; /* triangles are sent as debugging. */ +#endif + + for (i = 0; i < n; i++) { + double tx = v_x(vs, i), ty = v_y(vs, i); + + xs[i] = (int)round_int_nearest_away(tx); + ys[i] = (int)round_int_nearest_away(ty); + + if (xs[i] < sf_ctx->xmin || xs[i] > sf_ctx->xmax) return 0; + if (ys[i] < sf_ctx->ymin || ys[i] > sf_ctx->ymax) return 0; + } + + grid_face_add_new(sf_ctx->g, n); + debug(("penrose: new face l=%f gen=%d...", + penrose_side_length(state->start_size, depth), depth)); + for (i = 0; i < n; i++) { + grid_dot *d = grid_get_dot(sf_ctx->g, sf_ctx->points, + xs[i], ys[i]); + grid_face_set_dot(sf_ctx->g, d, i); + debug((" ... dot 0x%x (%d,%d) (was %2.2f,%2.2f)", + d, d->x, d->y, v_x(vs, i), v_y(vs, i))); + } + + return 0; +} + +#define PENROSE_TILESIZE 100 + +static void grid_size_penrose(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + int l = PENROSE_TILESIZE; + + *tilesize = l; + *xextent = l * width; + *yextent = l * height; +} + +static grid *grid_new_penrose(int width, int height, int which, const char *desc); /* forward reference */ + +static char *grid_new_desc_penrose(grid_type type, int width, int height, random_state *rs) +{ + int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff; + double outer_radius; + int inner_radius; + char gd[255]; + int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3); + grid *g; + + while (1) { + /* We want to produce a random bit of penrose tiling, so we + * calculate a random offset (within the patch that penrose.c + * calculates for us) and an angle (multiple of 36) to rotate + * the patch. */ + + penrose_calculate_size(which, tilesize, width, height, + &outer_radius, &startsz, &depth); + + /* Calculate radius of (circumcircle of) patch, subtract from + * radius calculated. */ + inner_radius = (int)(outer_radius - sqrt(width*width + height*height)); + + /* Pick a random offset (the easy way: choose within outer + * square, discarding while it's outside the circle) */ + do { + xoff = random_upto(rs, 2*inner_radius) - inner_radius; + yoff = random_upto(rs, 2*inner_radius) - inner_radius; + } while (sqrt(xoff*xoff+yoff*yoff) > inner_radius); + + aoff = random_upto(rs, 360/36) * 36; + + debug(("grid_desc: ts %d, %dx%d patch, orad %2.2f irad %d", + tilesize, width, height, outer_radius, inner_radius)); + debug((" -> xoff %d yoff %d aoff %d", xoff, yoff, aoff)); + + sprintf(gd, "G%d,%d,%d", xoff, yoff, aoff); + + /* + * Now test-generate our grid, to make sure it actually + * produces something. + */ + g = grid_new_penrose(width, height, which, gd); + if (g) { + grid_free(g); + break; + } + /* If not, go back to the top of this while loop and try again + * with a different random offset. */ + } + + return dupstr(gd); +} + +static char *grid_validate_desc_penrose(grid_type type, int width, int height, + const char *desc) +{ + int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff, inner_radius; + double outer_radius; + int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3); + grid *g; + + if (!desc) + return "Missing grid description string."; + + penrose_calculate_size(which, tilesize, width, height, + &outer_radius, &startsz, &depth); + inner_radius = (int)(outer_radius - sqrt(width*width + height*height)); + + if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3) + return "Invalid format grid description string."; + + if (sqrt(xoff*xoff + yoff*yoff) > inner_radius) + return "Patch offset out of bounds."; + if ((aoff % 36) != 0 || aoff < 0 || aoff >= 360) + return "Angle offset out of bounds."; + + /* + * Test-generate to ensure these parameters don't end us up with + * no grid at all. + */ + g = grid_new_penrose(width, height, which, desc); + if (!g) + return "Patch coordinates do not identify a usable grid fragment"; + grid_free(g); + + return NULL; +} + +/* + * We're asked for a grid of a particular size, and we generate enough + * of the tiling so we can be sure to have enough random grid from which + * to pick. + */ + +static grid *grid_new_penrose(int width, int height, int which, const char *desc) +{ + int max_faces, max_dots, tilesize = PENROSE_TILESIZE; + int xsz, ysz, xoff, yoff, aoff; + double rradius; + + tree234 *points; + grid *g; + + penrose_state ps; + setface_ctx sf_ctx; + + penrose_calculate_size(which, tilesize, width, height, + &rradius, &ps.start_size, &ps.max_depth); + + debug(("penrose: w%d h%d, tile size %d, start size %d, depth %d", + width, height, tilesize, ps.start_size, ps.max_depth)); + + ps.new_tile = set_faces; + ps.ctx = &sf_ctx; + + max_faces = (width*3) * (height*3); /* somewhat paranoid... */ + max_dots = max_faces * 4; /* ditto... */ + + g = grid_empty(); + g->tilesize = tilesize; + g->faces = snewn(max_faces, grid_face); + g->dots = snewn(max_dots, grid_dot); + + points = newtree234(grid_point_cmp_fn); + + memset(&sf_ctx, 0, sizeof(sf_ctx)); + sf_ctx.g = g; + sf_ctx.points = points; + + if (desc != NULL) { + if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3) + assert(!"Invalid grid description."); + } else { + xoff = yoff = aoff = 0; + } + + xsz = width * tilesize; + ysz = height * tilesize; + + sf_ctx.xmin = xoff - xsz/2; + sf_ctx.xmax = xoff + xsz/2; + sf_ctx.ymin = yoff - ysz/2; + sf_ctx.ymax = yoff + ysz/2; + + debug(("penrose: centre (%f, %f) xsz %f ysz %f", + 0.0, 0.0, xsz, ysz)); + debug(("penrose: x range (%f --> %f), y range (%f --> %f)", + sf_ctx.xmin, sf_ctx.xmax, sf_ctx.ymin, sf_ctx.ymax)); + + penrose(&ps, which, aoff); + + freetree234(points); + assert(g->num_faces <= max_faces); + assert(g->num_dots <= max_dots); + + debug(("penrose: %d faces total (equivalent to %d wide by %d high)", + g->num_faces, g->num_faces/height, g->num_faces/width)); + + /* + * Return NULL if we ended up with an empty grid, either because + * the initial generation was over too small a rectangle to + * encompass any face or because grid_trim_vigorously ended up + * removing absolutely everything. + */ + if (g->num_faces == 0 || g->num_dots == 0) { + grid_free(g); + return NULL; + } + grid_trim_vigorously(g); + if (g->num_faces == 0 || g->num_dots == 0) { + grid_free(g); + return NULL; + } + + grid_make_consistent(g); + + /* + * Centre the grid in its originally promised rectangle. + */ + g->lowest_x -= ((sf_ctx.xmax - sf_ctx.xmin) - + (g->highest_x - g->lowest_x)) / 2; + g->highest_x = g->lowest_x + (sf_ctx.xmax - sf_ctx.xmin); + g->lowest_y -= ((sf_ctx.ymax - sf_ctx.ymin) - + (g->highest_y - g->lowest_y)) / 2; + g->highest_y = g->lowest_y + (sf_ctx.ymax - sf_ctx.ymin); + + return g; +} + +static void grid_size_penrose_p2_kite(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + grid_size_penrose(width, height, tilesize, xextent, yextent); +} + +static void grid_size_penrose_p3_thick(int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + grid_size_penrose(width, height, tilesize, xextent, yextent); +} + +static grid *grid_new_penrose_p2_kite(int width, int height, const char *desc) +{ + return grid_new_penrose(width, height, PENROSE_P2, desc); +} + +static grid *grid_new_penrose_p3_thick(int width, int height, const char *desc) +{ + return grid_new_penrose(width, height, PENROSE_P3, desc); +} + +/* ----------- End of grid generators ------------- */ + +#define FNNEW(upper,lower) &grid_new_ ## lower, +#define FNSZ(upper,lower) &grid_size_ ## lower, + +static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) }; +static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) }; + +char *grid_new_desc(grid_type type, int width, int height, random_state *rs) +{ + if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { + return grid_new_desc_penrose(type, width, height, rs); + } else if (type == GRID_TRIANGULAR) { + return dupstr("0"); /* up-to-date version of triangular grid */ + } else { + return NULL; + } +} + +char *grid_validate_desc(grid_type type, int width, int height, + const char *desc) +{ + if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { + return grid_validate_desc_penrose(type, width, height, desc); + } else if (type == GRID_TRIANGULAR) { + return grid_validate_desc_triangular(type, width, height, desc); + } else { + if (desc != NULL) + return "Grid description strings not used with this grid type"; + return NULL; + } +} + +grid *grid_new(grid_type type, int width, int height, const char *desc) +{ + char *err = grid_validate_desc(type, width, height, desc); + if (err) assert(!"Invalid grid description."); + + return grid_news[type](width, height, desc); +} + +void grid_compute_size(grid_type type, int width, int height, + int *tilesize, int *xextent, int *yextent) +{ + grid_sizes[type](width, height, tilesize, xextent, yextent); +} + +/* ----------- End of grid helpers ------------- */ + +/* vim: set shiftwidth=4 tabstop=8: */ -- cgit v1.2.3