ref: 621649491dbc36285c3cfc0cd577ab04a2cbf5dc
parent: 53f6e4c6cb0b342f37e75c2686c1b542212c5f3e
author: Simon Tatham <anakin@pobox.com>
date: Thu Feb 24 14:06:48 EST 2011
Retire the 'middle_face' field in 'struct grid', together with the overly complicated algorithm that uses it to home in on the grid edge closest to a mouse click. That algorithm is being stressed beyond its limit by the new grid type, and it's unnecessary anyway given that no sensibly sized puzzle grid is going to be big enough to make it prohibitively expensive just to do the trivial approach of iterating over all edges and finding the closest of the eligible ones. [originally from svn r9108]
--- a/grid.c
+++ b/grid.c
@@ -57,7 +57,6 @@
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 @@
* 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 @@
*/
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 @@
}
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 @@
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 @@
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 @@
}
}
- /* "+ 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 @@
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 @@
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 @@
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 @@
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 @@
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,6 @@
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;
--- a/grid.h
+++ b/grid.h
@@ -57,11 +57,6 @@
int num_edges; grid_edge *edges;
int num_dots; grid_dot *dots;
- /* Should be a face roughly near the middle of the grid.
- * Used to seed path-generation, and also for nearest-edge
- * detection. */
- grid_face *middle_face;
-
/* Cache the bounding-box of the grid, so the drawing-code can quickly
* figure out the proper scaling to draw onto a given area. */
int lowest_x, lowest_y, highest_x, highest_y;