#include <assert.h>
#include <ctype.h>
#include <math.h>
-#include <errno.h>
+#include <float.h>
#include "puzzles.h"
#include "tree234.h"
/* 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;
#endif
#ifdef SVG_GRID
+#include <errno.h>
+
static void grid_try_svg(grid *g, int which)
{
char *svg = getenv("PUZZLES_SVG_GRID");
* 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;
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;
}
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;
/*
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;i<g->num_faces;i++)
+ {
+ grid_find_incentre(&(g->faces[i]));
+ }
+ for (i=0;i<g->num_dots;i++)
+ {
+ int order;
+ grid_dot *d;
+
+ d = &(g->dots[i]);
+
+ order = d->order;
+ for (j=0;j<d->order;j++)
+ {
+ if (!d->faces[j]) order--;
+ }
+ if (order>2)
+ {
+ grid_face_add_new(new_g, order);
+ for (j=0,k=0;j<d->order;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.
#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;
*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 */
#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;
*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;
#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;
/* 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;
#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;
*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;
#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. */
*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;
#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;
*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;
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;
*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;
#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;
*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;
#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 */
*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
#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;
*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;
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;
*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) */
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
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;
#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;
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;
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;
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);
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);
}
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;
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)
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,
~mdw / sgt / puzzles / blobdiff