X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/e30d39f6f3df08ea9c8a91df5db31d0346d1c5ad..a2f35d71b745ec2a03de58976c6434437c5f303e:/grid.c

diff --git a/grid.c b/grid.c
index 6e09c40..1e5fe6f 100644
--- a/grid.c
+++ b/grid.c
@@ -57,7 +57,6 @@ static grid *grid_new(void)
     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;
@@ -92,17 +91,9 @@ static double point_line_distance(long px, long py,
  * 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
  *  *---------*------
@@ -116,50 +107,14 @@ static double point_line_distance(long px, long py,
  */
 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 */
-        long dist = SQ((long)cur->x - (long)x) + SQ((long)cur->y - (long)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++) {
-		long new_dist;
-                grid_dot *d = f->dots[j];
-                if (d == cur) continue;
-                new_dist = SQ((long)d->x - (long)x) + SQ((long)d->y - (long)y);
-                if (new_dist < dist) { /* found closer dot */
-                    new = d;
-                    dist = new_dist;
-                }
-            }
-        }
-
-        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];
+    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;
@@ -222,7 +177,6 @@ static void grid_print_basic(grid *g)
         }
         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)
@@ -724,7 +678,6 @@ grid *grid_new_square(int width, int height)
     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;
@@ -779,7 +732,6 @@ grid *grid_new_honeycomb(int width, int height)
     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;
@@ -858,10 +810,6 @@ grid *grid_new_triangular(int width, int height)
         }
     }
 
-    /* "+ 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;
 }
@@ -960,7 +908,6 @@ grid *grid_new_snubsquare(int width, int height)
     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;
@@ -1053,7 +1000,6 @@ grid *grid_new_cairo(int width, int height)
     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;
@@ -1169,7 +1115,6 @@ grid *grid_new_greathexagonal(int width, int height)
     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;
@@ -1238,7 +1183,6 @@ grid *grid_new_octagonal(int width, int height)
     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;
@@ -1344,7 +1288,6 @@ grid *grid_new_kites(int width, int height)
     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;
@@ -1433,7 +1376,179 @@ grid *grid_new_floret(int width, int height)
     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_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;