/* Used by the other grid generators. Create a brand new grid with nothing
* initialised (all lists are NULL) */
-static grid *grid_new()
+static grid *grid_new(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->middle_face = NULL;
g->refcount = 1;
g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
return g;
*
* Combining gives: distance = determinant / line-length(a,b)
*/
-static double point_line_distance(int px, int py,
- int ax, int ay,
- int bx, int by)
+static double point_line_distance(long px, long py,
+ long ax, long ay,
+ long bx, long by)
{
- int det = ax*by - bx*ay + bx*py - px*by + px*ay - ax*py;
+ 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));
* Returns the nearest edge, or NULL if no edge is reasonably
* near the position.
*
- * This algorithm is nice and generic, and doesn't depend on any particular
- * geometric layout of the grid:
- * Start at any dot (pick one next to middle_face).
- * Walk along a path by choosing, from all nearby dots, the one that is
- * nearest the target (x,y). Hopefully end up at the dot which is closest
- * to (x,y). Should work, as long as faces aren't too badly shaped.
- * Then examine each edge around this dot, and pick whichever one is
- * closest (perpendicular distance) to (x,y).
- * Using 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.
+ * 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
* *---------*------
*/
grid_edge *grid_nearest_edge(grid *g, int x, int y)
{
- grid_dot *cur;
grid_edge *best_edge;
double best_distance = 0;
int i;
- cur = g->middle_face->dots[0];
-
- for (;;) {
- /* Target to beat */
- int dist = SQ(cur->x - x) + SQ(cur->y - y);
- /* Look for nearer dot - if found, store in 'new'. */
- grid_dot *new = cur;
- int i;
- /* Search all dots in all faces touching this dot. Some shapes
- * (such as in Cairo) don't quite work properly if we only search
- * the dot's immediate neighbours. */
- for (i = 0; i < cur->order; i++) {
- grid_face *f = cur->faces[i];
- int j;
- if (!f) continue;
- for (j = 0; j < f->order; j++) {
- int new_dist;
- grid_dot *d = f->dots[j];
- if (d == cur) continue;
- new_dist = SQ(d->x - x) + SQ(d->y - y);
- if (new_dist < dist) {
- new = d;
- break; /* found closer dot */
- }
- }
- if (new != cur)
- break; /* found closer dot */
- }
-
- if (new == cur) {
- /* Didn't find a closer dot among the neighbours of 'cur' */
- break;
- } else {
- cur = new;
- }
- }
-
- /* 'cur' is nearest dot, so find which of the dot's edges is closest. */
best_edge = NULL;
- for (i = 0; i < cur->order; i++) {
- grid_edge *e = cur->edges[i];
- int e2; /* squared length of edge */
- int a2, b2; /* squared lengths of other sides */
+ 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(e->dot1->x - e->dot2->x) + SQ(e->dot1->y - e->dot2->y);
- a2 = SQ(e->dot1->x - x) + SQ(e->dot1->y - y);
- b2 = SQ(e->dot2->x - x) + SQ(e->dot2->y - y);
+ 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;
* 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(x, y,
- e->dot1->x, e->dot1->y,
- e->dot2->x, e->dot2->y);
+ 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;
}
printf("]\n");
}
- printf("Middle face: %d\n", (int)(g->middle_face - g->faces));
}
/* Show the derived grid information, computed by grid_make_consistent */
static void grid_print_derived(grid *g)
* 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 = {0, NULL, NULL, x, y};
- grid_dot *ret = find234(dot_list, &test, NULL);
+ 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;
freetree234(points);
assert(g->num_faces <= max_faces);
assert(g->num_dots <= max_dots);
- g->middle_face = g->faces + (height/2) * width + (width/2);
grid_make_consistent(g);
return g;
freetree234(points);
assert(g->num_faces <= max_faces);
assert(g->num_dots <= max_dots);
- g->middle_face = g->faces + (height/2) * width + (width/2);
grid_make_consistent(g);
return g;
}
}
- /* "+ width" takes us to the middle of the row, because each row has
- * (2*width) faces. */
- g->middle_face = g->faces + (height / 2) * 2 * width + width;
-
grid_make_consistent(g);
return g;
}
freetree234(points);
assert(g->num_faces <= max_faces);
assert(g->num_dots <= max_dots);
- g->middle_face = g->faces + (height/2) * width + (width/2);
grid_make_consistent(g);
return g;
freetree234(points);
assert(g->num_faces <= max_faces);
assert(g->num_dots <= max_dots);
- g->middle_face = g->faces + (height/2) * width + (width/2);
grid_make_consistent(g);
return g;
freetree234(points);
assert(g->num_faces <= max_faces);
assert(g->num_dots <= max_dots);
- g->middle_face = g->faces + (height/2) * width + (width/2);
grid_make_consistent(g);
return g;
freetree234(points);
assert(g->num_faces <= max_faces);
assert(g->num_dots <= max_dots);
- g->middle_face = g->faces + (height/2) * width + (width/2);
grid_make_consistent(g);
return g;
freetree234(points);
assert(g->num_faces <= max_faces);
assert(g->num_dots <= max_dots);
- g->middle_face = g->faces + 6 * ((height/2) * width + (width/2));
+
+ grid_make_consistent(g);
+ return g;
+}
+
+grid *grid_new_floret(int width, int height)
+{
+ 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 = 75, py = -26; /* |( 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_new();
+ g->tilesize = 2 * px;
+ 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;
+}
+
+grid *grid_new_dodecagonal(int width, int height)
+{
+ int x, y;
+ /* Vector for side of triangle - ratio is close to sqrt(3) */
+ int a = 15;
+ int b = 26;
+
+ /* 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_new();
+ g->tilesize = b;
+ 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;
+}
+
+grid *grid_new_greatdodecagonal(int width, int height)
+{
+ int x, y;
+ /* Vector for side of triangle - ratio is close to sqrt(3) */
+ int a = 15;
+ int b = 26;
+
+ /* 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_new();
+ g->tilesize = b;
+ 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;
~mdw / sgt / puzzles / blobdiff