X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=grid.c;h=4929b5c7d3c99547183543560a9180f815c555df;hb=db313b3948d27244dd7c34c2609c66d6204d8931;hp=aba11570742e45e123631dd4f80311cc18ae8fbc;hpb=251b21c41813055d9c416378508b1ee038bc3dac;p=sgt-puzzles.git diff --git a/grid.c b/grid.c index aba1157..4929b5c 100644 --- a/grid.c +++ b/grid.c @@ -1069,7 +1069,7 @@ void grid_find_incentre(grid_face *f) eq[2] = eqs[0][3]*eqs[1][2] - eqs[1][3]*eqs[0][2]; /* Parametrise x and y in terms of some t. */ - if (abs(eq[0]) < abs(eq[1])) { + 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]; @@ -2571,6 +2571,175 @@ static grid *grid_new_greatdodecagonal(int width, int height, const char *desc) 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; @@ -2631,6 +2800,8 @@ static void grid_size_penrose(int width, int height, *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; @@ -2638,32 +2809,48 @@ static char *grid_new_desc_penrose(grid_type type, int width, int height, random int inner_radius; char gd[255]; int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3); + grid *g; - /* 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. */ + 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); + 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)); + /* 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); + /* 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; + 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)); + 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); + 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); } @@ -2674,6 +2861,7 @@ static char *grid_validate_desc_penrose(grid_type type, int width, int height, 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."; @@ -2690,6 +2878,15 @@ static char *grid_validate_desc_penrose(grid_type type, int width, int height, 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; } @@ -2763,7 +2960,22 @@ static grid *grid_new_penrose(int width, int height, int which, const char *desc 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); /*