X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/18eb897ff68aef4a40e0c966dbcfb7148a12759e..1a960a48298c0eb3832704bbd5bb72023d2873a0:/grid.c diff --git a/grid.c b/grid.c index d73e521..24380d9 100644 --- a/grid.c +++ b/grid.c @@ -12,7 +12,7 @@ #include #include #include -#include +#include #include "puzzles.h" #include "tree234.h" @@ -52,7 +52,7 @@ void grid_free(grid *g) /* Used by the other grid generators. Create a brand new grid with nothing * initialised (all lists are NULL) */ -static grid *grid_empty() +static grid *grid_empty(void) { grid *g = snew(grid); g->faces = NULL; @@ -225,6 +225,8 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); #endif #ifdef SVG_GRID +#include + static void grid_try_svg(grid *g, int which) { char *svg = getenv("PUZZLES_SVG_GRID"); @@ -454,6 +456,14 @@ static void grid_trim_vigorously(grid *g) 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++) @@ -508,6 +518,7 @@ static void grid_make_consistent(grid *g) * 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; + debug(("allocating room for %d edges\n", g->num_edges)); g->edges = snewn(g->num_edges, grid_edge); next_new_edge = g->edges; @@ -522,6 +533,7 @@ static void grid_make_consistent(grid *g) for (i = 0; i < g->num_faces; i++) { grid_face *f = g->faces + i; int j; + assert(f->order > 2); for (j = 0; j < f->order; j++) { grid_edge e; /* fake edge for searching */ grid_edge *edge_found; @@ -1260,7 +1272,15 @@ void grid_find_incentre(grid_face *f) } 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; /* @@ -1351,6 +1371,70 @@ void grid_find_incentre(grid_face *f) f->iy = ybest + 0.5; } +/* Generate the dual to a grid + * Returns a new dynamically-allocated grid whose dots are the + * faces of the input, and whose faces are the dots of the input. + * A few modifications are made: dots on input that have only two + * edges are deleted, and the infinite exterior face is also removed + * before conversion. + */ +static grid *grid_dual(grid *g) +{ + grid *new_g; + int i, j, k; + tree234* points; + + new_g = grid_empty(); + new_g->tilesize = g->tilesize; + new_g->faces = snewn(g->num_dots, grid_face); + new_g->dots = snewn(g->num_faces, grid_dot); + debug(("taking the dual of a grid with %d faces and %d dots\n", + g->num_faces,g->num_dots)); + + points = newtree234(grid_point_cmp_fn); + + for (i=0;inum_faces;i++) + { + grid_find_incentre(&(g->faces[i])); + } + for (i=0;inum_dots;i++) + { + int order; + grid_dot *d; + + d = &(g->dots[i]); + + order = d->order; + for (j=0;jorder;j++) + { + if (!d->faces[j]) order--; + } + if (order>2) + { + grid_face_add_new(new_g, order); + for (j=0,k=0;jorder;j++) + { + grid_dot *new_d; + if (d->faces[j]) + { + new_d = grid_get_dot(new_g, points, + d->faces[j]->ix, d->faces[j]->iy); + grid_face_set_dot(new_g, new_d, k++); + } + } + assert(k==order); + } + } + + freetree234(points); + assert(new_g->num_faces <= g->num_dots); + assert(new_g->num_dots <= g->num_faces); + + debug(("dual has %d faces and %d dots\n", + new_g->num_faces,new_g->num_dots)); + grid_make_consistent(new_g); + return new_g; +} /* ------ Generate various types of grid ------ */ /* General method is to generate faces, by calculating their dot coordinates. @@ -1369,7 +1453,7 @@ void grid_find_incentre(grid_face *f) #define SQUARE_TILESIZE 20 -void grid_size_square(int width, int height, +static void grid_size_square(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = SQUARE_TILESIZE; @@ -1379,7 +1463,7 @@ void grid_size_square(int width, int height, *yextent = height * a; } -grid *grid_new_square(int width, int height, char *desc) +static grid *grid_new_square(int width, int height, char *desc) { int x, y; /* Side length */ @@ -1431,7 +1515,7 @@ grid *grid_new_square(int width, int height, char *desc) #define HONEY_A 15 #define HONEY_B 26 -void grid_size_honeycomb(int width, int height, +static void grid_size_honeycomb(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = HONEY_A; @@ -1442,7 +1526,7 @@ void grid_size_honeycomb(int width, int height, *yextent = (2 * b * (height-1)) + 3*b; } -grid *grid_new_honeycomb(int width, int height, char *desc) +static grid *grid_new_honeycomb(int width, int height, char *desc) { int x, y; int a = HONEY_A; @@ -1500,7 +1584,7 @@ grid *grid_new_honeycomb(int width, int height, char *desc) #define TRIANGLE_VEC_X 15 #define TRIANGLE_VEC_Y 26 -void grid_size_triangular(int width, int height, +static void grid_size_triangular(int width, int height, int *tilesize, int *xextent, int *yextent) { int vec_x = TRIANGLE_VEC_X; @@ -1513,7 +1597,7 @@ void grid_size_triangular(int width, int height, /* 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" */ -grid *grid_new_triangular(int width, int height, char *desc) +static grid *grid_new_triangular(int width, int height, char *desc) { int x,y; @@ -1595,7 +1679,7 @@ grid *grid_new_triangular(int width, int height, char *desc) #define SNUBSQUARE_A 15 #define SNUBSQUARE_B 26 -void grid_size_snubsquare(int width, int height, +static void grid_size_snubsquare(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = SNUBSQUARE_A; @@ -1606,7 +1690,7 @@ void grid_size_snubsquare(int width, int height, *yextent = (a+b) * (height-1) + a + b; } -grid *grid_new_snubsquare(int width, int height, char *desc) +static grid *grid_new_snubsquare(int width, int height, char *desc) { int x, y; int a = SNUBSQUARE_A; @@ -1709,7 +1793,7 @@ grid *grid_new_snubsquare(int width, int height, char *desc) #define CAIRO_A 14 #define CAIRO_B 31 -void grid_size_cairo(int width, int height, +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. */ @@ -1719,7 +1803,7 @@ void grid_size_cairo(int width, int height, *yextent = 2*b*(height-1) + 2*b; } -grid *grid_new_cairo(int width, int height, char *desc) +static grid *grid_new_cairo(int width, int height, char *desc) { int x, y; int a = CAIRO_A; @@ -1815,7 +1899,7 @@ grid *grid_new_cairo(int width, int height, char *desc) #define GREATHEX_A 15 #define GREATHEX_B 26 -void grid_size_greathexagonal(int width, int height, +static void grid_size_greathexagonal(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = GREATHEX_A; @@ -1826,7 +1910,7 @@ void grid_size_greathexagonal(int width, int height, *yextent = (2*a + 2*b) * (height-1) + 3*b + a; } -grid *grid_new_greathexagonal(int width, int height, char *desc) +static grid *grid_new_greathexagonal(int width, int height, char *desc) { int x, y; int a = GREATHEX_A; @@ -1939,13 +2023,12 @@ grid *grid_new_greathexagonal(int width, int height, char *desc) grid_make_consistent(g); return g; } - #define OCTAGONAL_TILESIZE 40 /* b/a approx sqrt(2) */ #define OCTAGONAL_A 29 #define OCTAGONAL_B 41 -void grid_size_octagonal(int width, int height, +static void grid_size_octagonal(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = OCTAGONAL_A; @@ -1956,7 +2039,7 @@ void grid_size_octagonal(int width, int height, *yextent = (2*a + b) * height; } -grid *grid_new_octagonal(int width, int height, char *desc) +static grid *grid_new_octagonal(int width, int height, char *desc) { int x, y; int a = OCTAGONAL_A; @@ -2028,7 +2111,7 @@ grid *grid_new_octagonal(int width, int height, char *desc) #define KITE_A 15 #define KITE_B 26 -void grid_size_kites(int width, int height, +static void grid_size_kites(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = KITE_A; @@ -2039,7 +2122,7 @@ void grid_size_kites(int width, int height, *yextent = 6*a * (height-1) + 8*a; } -grid *grid_new_kites(int width, int height, char *desc) +static grid *grid_new_kites(int width, int height, char *desc) { int x, y; int a = KITE_A; @@ -2150,7 +2233,7 @@ grid *grid_new_kites(int width, int height, char *desc) #define FLORET_PX 75 #define FLORET_PY -26 -void grid_size_floret(int width, int height, +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 */ @@ -2163,7 +2246,7 @@ void grid_size_floret(int width, int height, *yextent = (5*qy-4*py) * (height-1) + 4*qy + 2*ry; } -grid *grid_new_floret(int width, int height, char *desc) +static grid *grid_new_floret(int width, int height, char *desc) { int x, y; /* Vectors for sides; weird numbers needed to keep puzzle aligned with window @@ -2257,7 +2340,7 @@ grid *grid_new_floret(int width, int height, char *desc) #define DODEC_A 15 #define DODEC_B 26 -void grid_size_dodecagonal(int width, int height, +static void grid_size_dodecagonal(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = DODEC_A; @@ -2268,7 +2351,7 @@ void grid_size_dodecagonal(int width, int height, *yextent = (3*a + 2*b) * (height-1) + 2*(2*a + b); } -grid *grid_new_dodecagonal(int width, int height, char *desc) +static grid *grid_new_dodecagonal(int width, int height, char *desc) { int x, y; int a = DODEC_A; @@ -2337,7 +2420,7 @@ grid *grid_new_dodecagonal(int width, int height, char *desc) return g; } -void grid_size_greatdodecagonal(int width, int height, +static void grid_size_greatdodecagonal(int width, int height, int *tilesize, int *xextent, int *yextent) { int a = DODEC_A; @@ -2348,7 +2431,7 @@ void grid_size_greatdodecagonal(int width, int height, *yextent = (3*a + 3*b) * (height-1) + 2*(2*a + b); } -grid *grid_new_greatdodecagonal(int width, int height, char *desc) +static grid *grid_new_greatdodecagonal(int width, int height, char *desc) { int x, y; /* Vector for side of triangle - ratio is close to sqrt(3) */ @@ -2454,24 +2537,21 @@ grid *grid_new_greatdodecagonal(int width, int height, char *desc) typedef struct setface_ctx { int xmin, xmax, ymin, ymax; - int aoff; grid *g; tree234 *points; } setface_ctx; -double round(double r) +static double round_int_nearest_away(double r) { return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); } -int set_faces(penrose_state *state, vector *vs, int n, int depth) +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]; - double cosa = cos(sf_ctx->aoff * PI / 180.0); - double sina = sin(sf_ctx->aoff * PI / 180.0); if (depth < state->max_depth) return 0; #ifdef DEBUG_PENROSE @@ -2481,8 +2561,8 @@ int set_faces(penrose_state *state, vector *vs, int n, int depth) for (i = 0; i < n; i++) { double tx = v_x(vs, i), ty = v_y(vs, i); - xs[i] = (int)round( tx*cosa + ty*sina); - ys[i] = (int)round(-tx*sina + ty*cosa); + 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; @@ -2504,7 +2584,7 @@ int set_faces(penrose_state *state, vector *vs, int n, int depth) #define PENROSE_TILESIZE 100 -void grid_size_penrose(int width, int height, +static void grid_size_penrose(int width, int height, int *tilesize, int *xextent, int *yextent) { int l = PENROSE_TILESIZE; @@ -2584,7 +2664,7 @@ static char *grid_validate_desc_penrose(grid_type type, int width, int height, c static grid *grid_new_penrose(int width, int height, int which, char *desc) { int max_faces, max_dots, tilesize = PENROSE_TILESIZE; - int xsz, ysz, xoff, yoff; + int xsz, ysz, xoff, yoff, aoff; double rradius; tree234 *points; @@ -2617,7 +2697,7 @@ static grid *grid_new_penrose(int width, int height, int which, char *desc) sf_ctx.points = points; if (desc != NULL) { - if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &sf_ctx.aoff) != 3) + if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3) assert(!"Invalid grid description."); } else { xoff = yoff = 0; @@ -2636,7 +2716,7 @@ static grid *grid_new_penrose(int width, int height, int which, char *desc) 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); + penrose(&ps, which, aoff); freetree234(points); assert(g->num_faces <= max_faces); @@ -2661,24 +2741,24 @@ static grid *grid_new_penrose(int width, int height, int which, char *desc) return g; } -void grid_size_penrose_p2_kite(int width, int height, +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); } -void grid_size_penrose_p3_thick(int width, int height, +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); } -grid *grid_new_penrose_p2_kite(int width, int height, char *desc) +static grid *grid_new_penrose_p2_kite(int width, int height, char *desc) { return grid_new_penrose(width, height, PENROSE_P2, desc); } -grid *grid_new_penrose_p3_thick(int width, int height, char *desc) +static grid *grid_new_penrose_p3_thick(int width, int height, char *desc) { return grid_new_penrose(width, height, PENROSE_P3, desc); } @@ -2691,7 +2771,7 @@ grid *grid_new_penrose_p3_thick(int width, int height, char *desc) static grid *(*(grid_news[]))(int, int, 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) +char *grid_new_desc(grid_type type, int width, int height, int dual, random_state *rs) { if (type != GRID_PENROSE_P2 && type != GRID_PENROSE_P3) return NULL; @@ -2699,7 +2779,7 @@ char *grid_new_desc(grid_type type, int width, int height, random_state *rs) return grid_new_desc_penrose(type, width, height, rs); } -char *grid_validate_desc(grid_type type, int width, int height, char *desc) +char *grid_validate_desc(grid_type type, int width, int height, int dual, char *desc) { if (type != GRID_PENROSE_P2 && type != GRID_PENROSE_P3) { if (desc != NULL) @@ -2710,12 +2790,25 @@ char *grid_validate_desc(grid_type type, int width, int height, char *desc) return grid_validate_desc_penrose(type, width, height, desc); } -grid *grid_new(grid_type type, int width, int height, char *desc) +grid *grid_new(grid_type type, int width, int height, int dual, char *desc) { - char *err = grid_validate_desc(type, width, height, desc); + char *err = grid_validate_desc(type, width, height, dual, desc); if (err) assert(!"Invalid grid description."); - return grid_news[type](width, height, desc); + if (!dual) + { + return grid_news[type](width, height, desc); + } + else + { + grid *temp; + grid *g; + + temp = grid_news[type](width, height, desc); + g = grid_dual(temp); + grid_free(temp); + return g; + } } void grid_compute_size(grid_type type, int width, int height,