~mdw / sgt / puzzles / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Oops: initialise that new 'has_incentre' flag to false, otherwise the
[sgt/puzzles] / grid.c
CommitLineData
7c95608a 1/*
2 * (c) Lambros Lambrou 2008
3 *
4 * Code for working with general grids, which can be any planar graph
5 * with faces, edges and vertices (dots). Includes generators for a few
6 * types of grid, including square, hexagonal, triangular and others.
7 */
8
9#include <stdio.h>
10#include <stdlib.h>
11#include <string.h>
12#include <assert.h>
13#include <ctype.h>
14#include <math.h>
15
16#include "puzzles.h"
17#include "tree234.h"
18#include "grid.h"
19
20/* Debugging options */
21
22/*
23#define DEBUG_GRID
24*/
25
26/* ----------------------------------------------------------------------
27 * Deallocate or dereference a grid
28 */
29void grid_free(grid *g)
30{
31 assert(g->refcount);
32
33 g->refcount--;
34 if (g->refcount == 0) {
35 int i;
36 for (i = 0; i < g->num_faces; i++) {
37 sfree(g->faces[i].dots);
38 sfree(g->faces[i].edges);
39 }
40 for (i = 0; i < g->num_dots; i++) {
41 sfree(g->dots[i].faces);
42 sfree(g->dots[i].edges);
43 }
44 sfree(g->faces);
45 sfree(g->edges);
46 sfree(g->dots);
47 sfree(g);
48 }
49}
50
51/* Used by the other grid generators. Create a brand new grid with nothing
52 * initialised (all lists are NULL) */
b1535c90 53static grid *grid_new(void)
7c95608a 54{
55 grid *g = snew(grid);
56 g->faces = NULL;
57 g->edges = NULL;
58 g->dots = NULL;
59 g->num_faces = g->num_edges = g->num_dots = 0;
7c95608a 60 g->refcount = 1;
61 g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
62 return g;
63}
64
65/* Helper function to calculate perpendicular distance from
66 * a point P to a line AB. A and B mustn't be equal here.
67 *
68 * Well-known formula for area A of a triangle:
69 * / 1 1 1 \
70 * 2A = determinant of matrix | px ax bx |
71 * \ py ay by /
72 *
73 * Also well-known: 2A = base * height
74 * = perpendicular distance * line-length.
75 *
76 * Combining gives: distance = determinant / line-length(a,b)
77 */
b1535c90 78static double point_line_distance(long px, long py,
79 long ax, long ay,
80 long bx, long by)
7c95608a 81{
b1535c90 82 long det = ax*by - bx*ay + bx*py - px*by + px*ay - ax*py;
1515b973 83 double len;
7c95608a 84 det = max(det, -det);
1515b973 85 len = sqrt(SQ(ax - bx) + SQ(ay - by));
7c95608a 86 return det / len;
87}
88
89/* Determine nearest edge to where the user clicked.
90 * (x, y) is the clicked location, converted to grid coordinates.
91 * Returns the nearest edge, or NULL if no edge is reasonably
92 * near the position.
93 *
f839ef77 94 * Just judging edges by perpendicular distance is not quite right -
95 * the edge might be "off to one side". So we insist that the triangle
96 * with (x,y) has acute angles at the edge's dots.
7c95608a 97 *
98 * edge1
99 * *---------*------
100 * |
101 * | *(x,y)
102 * edge2 |
103 * | edge2 is OK, but edge1 is not, even though
104 * | edge1 is perpendicularly closer to (x,y)
105 * *
106 *
107 */
108grid_edge *grid_nearest_edge(grid *g, int x, int y)
109{
7c95608a 110 grid_edge *best_edge;
111 double best_distance = 0;
112 int i;
113
7c95608a 114 best_edge = NULL;
115
f839ef77 116 for (i = 0; i < g->num_edges; i++) {
117 grid_edge *e = &g->edges[i];
b1535c90 118 long e2; /* squared length of edge */
119 long a2, b2; /* squared lengths of other sides */
7c95608a 120 double dist;
121
122 /* See if edge e is eligible - the triangle must have acute angles
123 * at the edge's dots.
124 * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
125 * so detect acute angles by testing for h^2 < a^2 + b^2 */
b1535c90 126 e2 = SQ((long)e->dot1->x - (long)e->dot2->x) + SQ((long)e->dot1->y - (long)e->dot2->y);
127 a2 = SQ((long)e->dot1->x - (long)x) + SQ((long)e->dot1->y - (long)y);
128 b2 = SQ((long)e->dot2->x - (long)x) + SQ((long)e->dot2->y - (long)y);
7c95608a 129 if (a2 >= e2 + b2) continue;
130 if (b2 >= e2 + a2) continue;
131
132 /* e is eligible so far. Now check the edge is reasonably close
133 * to where the user clicked. Don't want to toggle an edge if the
134 * click was way off the grid.
135 * There is room for experimentation here. We could check the
136 * perpendicular distance is within a certain fraction of the length
137 * of the edge. That amounts to testing a rectangular region around
138 * the edge.
139 * Alternatively, we could check that the angle at the point is obtuse.
140 * That would amount to testing a circular region with the edge as
141 * diameter. */
b1535c90 142 dist = point_line_distance((long)x, (long)y,
143 (long)e->dot1->x, (long)e->dot1->y,
144 (long)e->dot2->x, (long)e->dot2->y);
7c95608a 145 /* Is dist more than half edge length ? */
146 if (4 * SQ(dist) > e2)
147 continue;
148
149 if (best_edge == NULL || dist < best_distance) {
150 best_edge = e;
151 best_distance = dist;
152 }
153 }
154 return best_edge;
155}
156
157/* ----------------------------------------------------------------------
158 * Grid generation
159 */
160
161#ifdef DEBUG_GRID
162/* Show the basic grid information, before doing grid_make_consistent */
163static void grid_print_basic(grid *g)
164{
165 /* TODO: Maybe we should generate an SVG image of the dots and lines
166 * of the grid here, before grid_make_consistent.
167 * Would help with debugging grid generation. */
168 int i;
169 printf("--- Basic Grid Data ---\n");
170 for (i = 0; i < g->num_faces; i++) {
171 grid_face *f = g->faces + i;
172 printf("Face %d: dots[", i);
173 int j;
174 for (j = 0; j < f->order; j++) {
175 grid_dot *d = f->dots[j];
176 printf("%s%d", j ? "," : "", (int)(d - g->dots));
177 }
178 printf("]\n");
179 }
7c95608a 180}
181/* Show the derived grid information, computed by grid_make_consistent */
182static void grid_print_derived(grid *g)
183{
184 /* edges */
185 int i;
186 printf("--- Derived Grid Data ---\n");
187 for (i = 0; i < g->num_edges; i++) {
188 grid_edge *e = g->edges + i;
189 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
190 i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots),
191 e->face1 ? (int)(e->face1 - g->faces) : -1,
192 e->face2 ? (int)(e->face2 - g->faces) : -1);
193 }
194 /* faces */
195 for (i = 0; i < g->num_faces; i++) {
196 grid_face *f = g->faces + i;
197 int j;
198 printf("Face %d: faces[", i);
199 for (j = 0; j < f->order; j++) {
200 grid_edge *e = f->edges[j];
201 grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1;
202 printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1);
203 }
204 printf("]\n");
205 }
206 /* dots */
207 for (i = 0; i < g->num_dots; i++) {
208 grid_dot *d = g->dots + i;
209 int j;
210 printf("Dot %d: dots[", i);
211 for (j = 0; j < d->order; j++) {
212 grid_edge *e = d->edges[j];
213 grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1;
214 printf("%s%d", j ? "," : "", (int)(d2 - g->dots));
215 }
216 printf("] faces[");
217 for (j = 0; j < d->order; j++) {
218 grid_face *f = d->faces[j];
219 printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1);
220 }
221 printf("]\n");
222 }
223}
224#endif /* DEBUG_GRID */
225
226/* Helper function for building incomplete-edges list in
227 * grid_make_consistent() */
228static int grid_edge_bydots_cmpfn(void *v1, void *v2)
229{
230 grid_edge *a = v1;
231 grid_edge *b = v2;
232 grid_dot *da, *db;
233
234 /* Pointer subtraction is valid here, because all dots point into the
235 * same dot-list (g->dots).
236 * Edges are not "normalised" - the 2 dots could be stored in any order,
237 * so we need to take this into account when comparing edges. */
238
239 /* Compare first dots */
240 da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2;
241 db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2;
242 if (da != db)
243 return db - da;
244 /* Compare last dots */
245 da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1;
246 db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1;
247 if (da != db)
248 return db - da;
249
250 return 0;
251}
252
253/* Input: grid has its dots and faces initialised:
254 * - dots have (optionally) x and y coordinates, but no edges or faces
255 * (pointers are NULL).
256 * - edges not initialised at all
257 * - faces initialised and know which dots they have (but no edges yet). The
258 * dots around each face are assumed to be clockwise.
259 *
260 * Output: grid is complete and valid with all relationships defined.
261 */
262static void grid_make_consistent(grid *g)
263{
264 int i;
265 tree234 *incomplete_edges;
266 grid_edge *next_new_edge; /* Where new edge will go into g->edges */
267
268#ifdef DEBUG_GRID
269 grid_print_basic(g);
270#endif
271
272 /* ====== Stage 1 ======
273 * Generate edges
274 */
275
276 /* We know how many dots and faces there are, so we can find the exact
277 * number of edges from Euler's polyhedral formula: F + V = E + 2 .
278 * We use "-1", not "-2" here, because Euler's formula includes the
279 * infinite face, which we don't count. */
280 g->num_edges = g->num_faces + g->num_dots - 1;
281 g->edges = snewn(g->num_edges, grid_edge);
282 next_new_edge = g->edges;
283
284 /* Iterate over faces, and over each face's dots, generating edges as we
285 * go. As we find each new edge, we can immediately fill in the edge's
286 * dots, but only one of the edge's faces. Later on in the iteration, we
287 * will find the same edge again (unless it's on the border), but we will
288 * know the other face.
289 * For efficiency, maintain a list of the incomplete edges, sorted by
290 * their dots. */
291 incomplete_edges = newtree234(grid_edge_bydots_cmpfn);
292 for (i = 0; i < g->num_faces; i++) {
293 grid_face *f = g->faces + i;
294 int j;
295 for (j = 0; j < f->order; j++) {
296 grid_edge e; /* fake edge for searching */
297 grid_edge *edge_found;
298 int j2 = j + 1;
299 if (j2 == f->order)
300 j2 = 0;
301 e.dot1 = f->dots[j];
302 e.dot2 = f->dots[j2];
303 /* Use del234 instead of find234, because we always want to
304 * remove the edge if found */
305 edge_found = del234(incomplete_edges, &e);
306 if (edge_found) {
307 /* This edge already added, so fill out missing face.
308 * Edge is already removed from incomplete_edges. */
309 edge_found->face2 = f;
310 } else {
311 assert(next_new_edge - g->edges < g->num_edges);
312 next_new_edge->dot1 = e.dot1;
313 next_new_edge->dot2 = e.dot2;
314 next_new_edge->face1 = f;
315 next_new_edge->face2 = NULL; /* potentially infinite face */
316 add234(incomplete_edges, next_new_edge);
317 ++next_new_edge;
318 }
319 }
320 }
321 freetree234(incomplete_edges);
322
323 /* ====== Stage 2 ======
324 * For each face, build its edge list.
325 */
326
327 /* Allocate space for each edge list. Can do this, because each face's
328 * edge-list is the same size as its dot-list. */
329 for (i = 0; i < g->num_faces; i++) {
330 grid_face *f = g->faces + i;
331 int j;
332 f->edges = snewn(f->order, grid_edge*);
333 /* Preload with NULLs, to help detect potential bugs. */
334 for (j = 0; j < f->order; j++)
335 f->edges[j] = NULL;
336 }
337
338 /* Iterate over each edge, and over both its faces. Add this edge to
339 * the face's edge-list, after finding where it should go in the
340 * sequence. */
341 for (i = 0; i < g->num_edges; i++) {
342 grid_edge *e = g->edges + i;
343 int j;
344 for (j = 0; j < 2; j++) {
345 grid_face *f = j ? e->face2 : e->face1;
346 int k, k2;
347 if (f == NULL) continue;
348 /* Find one of the dots around the face */
349 for (k = 0; k < f->order; k++) {
350 if (f->dots[k] == e->dot1)
351 break; /* found dot1 */
352 }
353 assert(k != f->order); /* Must find the dot around this face */
354
355 /* Labelling scheme: as we walk clockwise around the face,
356 * starting at dot0 (f->dots[0]), we hit:
357 * (dot0), edge0, dot1, edge1, dot2,...
358 *
359 * 0
360 * 0-----1
361 * |
362 * |1
363 * |
364 * 3-----2
365 * 2
366 *
367 * Therefore, edgeK joins dotK and dot{K+1}
368 */
369
370 /* Around this face, either the next dot or the previous dot
371 * must be e->dot2. Otherwise the edge is wrong. */
372 k2 = k + 1;
373 if (k2 == f->order)
374 k2 = 0;
375 if (f->dots[k2] == e->dot2) {
376 /* dot1(k) and dot2(k2) go clockwise around this face, so add
377 * this edge at position k (see diagram). */
378 assert(f->edges[k] == NULL);
379 f->edges[k] = e;
380 continue;
381 }
382 /* Try previous dot */
383 k2 = k - 1;
384 if (k2 == -1)
385 k2 = f->order - 1;
386 if (f->dots[k2] == e->dot2) {
387 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
388 assert(f->edges[k2] == NULL);
389 f->edges[k2] = e;
390 continue;
391 }
392 assert(!"Grid broken: bad edge-face relationship");
393 }
394 }
395
396 /* ====== Stage 3 ======
397 * For each dot, build its edge-list and face-list.
398 */
399
400 /* We don't know how many edges/faces go around each dot, so we can't
401 * allocate the right space for these lists. Pre-compute the sizes by
402 * iterating over each edge and recording a tally against each dot. */
403 for (i = 0; i < g->num_dots; i++) {
404 g->dots[i].order = 0;
405 }
406 for (i = 0; i < g->num_edges; i++) {
407 grid_edge *e = g->edges + i;
408 ++(e->dot1->order);
409 ++(e->dot2->order);
410 }
411 /* Now we have the sizes, pre-allocate the edge and face lists. */
412 for (i = 0; i < g->num_dots; i++) {
413 grid_dot *d = g->dots + i;
414 int j;
415 assert(d->order >= 2); /* sanity check */
416 d->edges = snewn(d->order, grid_edge*);
417 d->faces = snewn(d->order, grid_face*);
418 for (j = 0; j < d->order; j++) {
419 d->edges[j] = NULL;
420 d->faces[j] = NULL;
421 }
422 }
423 /* For each dot, need to find a face that touches it, so we can seed
424 * the edge-face-edge-face process around each dot. */
425 for (i = 0; i < g->num_faces; i++) {
426 grid_face *f = g->faces + i;
427 int j;
428 for (j = 0; j < f->order; j++) {
429 grid_dot *d = f->dots[j];
430 d->faces[0] = f;
431 }
432 }
433 /* Each dot now has a face in its first slot. Generate the remaining
434 * faces and edges around the dot, by searching both clockwise and
435 * anticlockwise from the first face. Need to do both directions,
436 * because of the possibility of hitting the infinite face, which
437 * blocks progress. But there's only one such face, so we will
438 * succeed in finding every edge and face this way. */
439 for (i = 0; i < g->num_dots; i++) {
440 grid_dot *d = g->dots + i;
441 int current_face1 = 0; /* ascends clockwise */
442 int current_face2 = 0; /* descends anticlockwise */
443
444 /* Labelling scheme: as we walk clockwise around the dot, starting
445 * at face0 (d->faces[0]), we hit:
446 * (face0), edge0, face1, edge1, face2,...
447 *
448 * 0
449 * |
450 * 0 | 1
451 * |
452 * -----d-----1
453 * |
454 * | 2
455 * |
456 * 2
457 *
458 * So, for example, face1 should be joined to edge0 and edge1,
459 * and those edges should appear in an anticlockwise sense around
460 * that face (see diagram). */
461
462 /* clockwise search */
463 while (TRUE) {
464 grid_face *f = d->faces[current_face1];
465 grid_edge *e;
466 int j;
467 assert(f != NULL);
468 /* find dot around this face */
469 for (j = 0; j < f->order; j++) {
470 if (f->dots[j] == d)
471 break;
472 }
473 assert(j != f->order); /* must find dot */
474
475 /* Around f, required edge is anticlockwise from the dot. See
476 * the other labelling scheme higher up, for why we subtract 1
477 * from j. */
478 j--;
479 if (j == -1)
480 j = f->order - 1;
481 e = f->edges[j];
482 d->edges[current_face1] = e; /* set edge */
483 current_face1++;
484 if (current_face1 == d->order)
485 break;
486 else {
487 /* set face */
488 d->faces[current_face1] =
489 (e->face1 == f) ? e->face2 : e->face1;
490 if (d->faces[current_face1] == NULL)
491 break; /* cannot progress beyond infinite face */
492 }
493 }
494 /* If the clockwise search made it all the way round, don't need to
495 * bother with the anticlockwise search. */
496 if (current_face1 == d->order)
497 continue; /* this dot is complete, move on to next dot */
498
499 /* anticlockwise search */
500 while (TRUE) {
501 grid_face *f = d->faces[current_face2];
502 grid_edge *e;
503 int j;
504 assert(f != NULL);
505 /* find dot around this face */
506 for (j = 0; j < f->order; j++) {
507 if (f->dots[j] == d)
508 break;
509 }
510 assert(j != f->order); /* must find dot */
511
512 /* Around f, required edge is clockwise from the dot. */
513 e = f->edges[j];
514
515 current_face2--;
516 if (current_face2 == -1)
517 current_face2 = d->order - 1;
518 d->edges[current_face2] = e; /* set edge */
519
520 /* set face */
521 if (current_face2 == current_face1)
522 break;
523 d->faces[current_face2] =
524 (e->face1 == f) ? e->face2 : e->face1;
525 /* There's only 1 infinite face, so we must get all the way
526 * to current_face1 before we hit it. */
527 assert(d->faces[current_face2]);
528 }
529 }
530
531 /* ====== Stage 4 ======
532 * Compute other grid settings
533 */
534
535 /* Bounding rectangle */
536 for (i = 0; i < g->num_dots; i++) {
537 grid_dot *d = g->dots + i;
538 if (i == 0) {
539 g->lowest_x = g->highest_x = d->x;
540 g->lowest_y = g->highest_y = d->y;
541 } else {
542 g->lowest_x = min(g->lowest_x, d->x);
543 g->highest_x = max(g->highest_x, d->x);
544 g->lowest_y = min(g->lowest_y, d->y);
545 g->highest_y = max(g->highest_y, d->y);
546 }
547 }
548
549#ifdef DEBUG_GRID
550 grid_print_derived(g);
551#endif
552}
553
554/* Helpers for making grid-generation easier. These functions are only
555 * intended for use during grid generation. */
556
557/* Comparison function for the (tree234) sorted dot list */
558static int grid_point_cmp_fn(void *v1, void *v2)
559{
560 grid_dot *p1 = v1;
561 grid_dot *p2 = v2;
562 if (p1->y != p2->y)
563 return p2->y - p1->y;
564 else
565 return p2->x - p1->x;
566}
567/* Add a new face to the grid, with its dot list allocated.
568 * Assumes there's enough space allocated for the new face in grid->faces */
569static void grid_face_add_new(grid *g, int face_size)
570{
571 int i;
572 grid_face *new_face = g->faces + g->num_faces;
573 new_face->order = face_size;
574 new_face->dots = snewn(face_size, grid_dot*);
575 for (i = 0; i < face_size; i++)
576 new_face->dots[i] = NULL;
577 new_face->edges = NULL;
a10bec21 578 new_face->has_incentre = FALSE;
7c95608a 579 g->num_faces++;
580}
581/* Assumes dot list has enough space */
582static grid_dot *grid_dot_add_new(grid *g, int x, int y)
583{
584 grid_dot *new_dot = g->dots + g->num_dots;
585 new_dot->order = 0;
586 new_dot->edges = NULL;
587 new_dot->faces = NULL;
588 new_dot->x = x;
589 new_dot->y = y;
590 g->num_dots++;
591 return new_dot;
592}
593/* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
594 * in the dot_list, or add a new dot to the grid (and the dot_list) and
595 * return that.
596 * Assumes g->dots has enough capacity allocated */
597static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y)
598{
3466f373 599 grid_dot test, *ret;
600
601 test.order = 0;
602 test.edges = NULL;
603 test.faces = NULL;
604 test.x = x;
605 test.y = y;
606 ret = find234(dot_list, &test, NULL);
7c95608a 607 if (ret)
608 return ret;
609
610 ret = grid_dot_add_new(g, x, y);
611 add234(dot_list, ret);
612 return ret;
613}
614
615/* Sets the last face of the grid to include this dot, at this position
616 * around the face. Assumes num_faces is at least 1 (a new face has
617 * previously been added, with the required number of dots allocated) */
618static void grid_face_set_dot(grid *g, grid_dot *d, int position)
619{
620 grid_face *last_face = g->faces + g->num_faces - 1;
621 last_face->dots[position] = d;
622}
623
e64991db 624/*
625 * Helper routines for grid_find_incentre.
626 */
627static int solve_2x2_matrix(double mx[4], double vin[2], double vout[2])
628{
629 double inv[4];
630 double det;
631 det = (mx[0]*mx[3] - mx[1]*mx[2]);
632 if (det == 0)
633 return FALSE;
634
635 inv[0] = mx[3] / det;
636 inv[1] = -mx[1] / det;
637 inv[2] = -mx[2] / det;
638 inv[3] = mx[0] / det;
639
640 vout[0] = inv[0]*vin[0] + inv[1]*vin[1];
641 vout[1] = inv[2]*vin[0] + inv[3]*vin[1];
642
643 return TRUE;
644}
645static int solve_3x3_matrix(double mx[9], double vin[3], double vout[3])
646{
647 double inv[9];
648 double det;
649
650 det = (mx[0]*mx[4]*mx[8] + mx[1]*mx[5]*mx[6] + mx[2]*mx[3]*mx[7] -
651 mx[0]*mx[5]*mx[7] - mx[1]*mx[3]*mx[8] - mx[2]*mx[4]*mx[6]);
652 if (det == 0)
653 return FALSE;
654
655 inv[0] = (mx[4]*mx[8] - mx[5]*mx[7]) / det;
656 inv[1] = (mx[2]*mx[7] - mx[1]*mx[8]) / det;
657 inv[2] = (mx[1]*mx[5] - mx[2]*mx[4]) / det;
658 inv[3] = (mx[5]*mx[6] - mx[3]*mx[8]) / det;
659 inv[4] = (mx[0]*mx[8] - mx[2]*mx[6]) / det;
660 inv[5] = (mx[2]*mx[3] - mx[0]*mx[5]) / det;
661 inv[6] = (mx[3]*mx[7] - mx[4]*mx[6]) / det;
662 inv[7] = (mx[1]*mx[6] - mx[0]*mx[7]) / det;
663 inv[8] = (mx[0]*mx[4] - mx[1]*mx[3]) / det;
664
665 vout[0] = inv[0]*vin[0] + inv[1]*vin[1] + inv[2]*vin[2];
666 vout[1] = inv[3]*vin[0] + inv[4]*vin[1] + inv[5]*vin[2];
667 vout[2] = inv[6]*vin[0] + inv[7]*vin[1] + inv[8]*vin[2];
668
669 return TRUE;
670}
671
672void grid_find_incentre(grid_face *f)
673{
674 double xbest, ybest, bestdist;
675 int i, j, k, m;
676 grid_dot *edgedot1[3], *edgedot2[3];
677 grid_dot *dots[3];
678 int nedges, ndots;
679
680 if (f->has_incentre)
681 return;
682
683 /*
684 * Find the point in the polygon with the maximum distance to any
685 * edge or corner.
686 *
687 * Such a point must exist which is in contact with at least three
688 * edges and/or vertices. (Proof: if it's only in contact with two
689 * edges and/or vertices, it can't even be at a _local_ maximum -
690 * any such circle can always be expanded in some direction.) So
691 * we iterate through all 3-subsets of the combined set of edges
692 * and vertices; for each subset we generate one or two candidate
693 * points that might be the incentre, and then we vet each one to
694 * see if it's inside the polygon and what its maximum radius is.
695 *
696 * (There's one case which this algorithm will get noticeably
697 * wrong, and that's when a continuum of equally good answers
698 * exists due to parallel edges. Consider a long thin rectangle,
699 * for instance, or a parallelogram. This algorithm will pick a
700 * point near one end, and choose the end arbitrarily; obviously a
701 * nicer point to choose would be in the centre. To fix this I
702 * would have to introduce a special-case system which detected
703 * parallel edges in advance, set aside all candidate points
704 * generated using both edges in a parallel pair, and generated
705 * some additional candidate points half way between them. Also,
706 * of course, I'd have to cope with rounding error making such a
707 * point look worse than one of its endpoints. So I haven't done
708 * this for the moment, and will cross it if necessary when I come
709 * to it.)
710 *
711 * We don't actually iterate literally over _edges_, in the sense
712 * of grid_edge structures. Instead, we fill in edgedot1[] and
713 * edgedot2[] with a pair of dots adjacent in the face's list of
714 * vertices. This ensures that we get the edges in consistent
715 * orientation, which we could not do from the grid structure
716 * alone. (A moment's consideration of an order-3 vertex should
717 * make it clear that if a notional arrow was written on each
718 * edge, _at least one_ of the three faces bordering that vertex
719 * would have to have the two arrows tip-to-tip or tail-to-tail
720 * rather than tip-to-tail.)
721 */
722 nedges = ndots = 0;
723 bestdist = 0;
724 xbest = ybest = 0;
725
726 for (i = 0; i+2 < 2*f->order; i++) {
727 if (i < f->order) {
728 edgedot1[nedges] = f->dots[i];
729 edgedot2[nedges++] = f->dots[(i+1)%f->order];
730 } else
731 dots[ndots++] = f->dots[i - f->order];
732
733 for (j = i+1; j+1 < 2*f->order; j++) {
734 if (j < f->order) {
735 edgedot1[nedges] = f->dots[j];
736 edgedot2[nedges++] = f->dots[(j+1)%f->order];
737 } else
738 dots[ndots++] = f->dots[j - f->order];
739
740 for (k = j+1; k < 2*f->order; k++) {
741 double cx[2], cy[2]; /* candidate positions */
742 int cn = 0; /* number of candidates */
743
744 if (k < f->order) {
745 edgedot1[nedges] = f->dots[k];
746 edgedot2[nedges++] = f->dots[(k+1)%f->order];
747 } else
748 dots[ndots++] = f->dots[k - f->order];
749
750 /*
751 * Find a point, or pair of points, equidistant from
752 * all the specified edges and/or vertices.
753 */
754 if (nedges == 3) {
755 /*
756 * Three edges. This is a linear matrix equation:
757 * each row of the matrix represents the fact that
758 * the point (x,y) we seek is at distance r from
759 * that edge, and we solve three of those
760 * simultaneously to obtain x,y,r. (We ignore r.)
761 */
762 double matrix[9], vector[3], vector2[3];
763 int m;
764
765 for (m = 0; m < 3; m++) {
766 int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x;
767 int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y;
768 int dx = x2-x1, dy = y2-y1;
769
770 /*
771 * ((x,y) - (x1,y1)) . (dy,-dx) = r |(dx,dy)|
772 *
773 * => x dy - y dx - r |(dx,dy)| = (x1 dy - y1 dx)
774 */
775 matrix[3*m+0] = dy;
776 matrix[3*m+1] = -dx;
777 matrix[3*m+2] = -sqrt((double)dx*dx+(double)dy*dy);
778 vector[m] = (double)x1*dy - (double)y1*dx;
779 }
780
781 if (solve_3x3_matrix(matrix, vector, vector2)) {
782 cx[cn] = vector2[0];
783 cy[cn] = vector2[1];
784 cn++;
785 }
786 } else if (nedges == 2) {
787 /*
788 * Two edges and a dot. This will end up in a
789 * quadratic equation.
790 *
791 * First, look at the two edges. Having our point
792 * be some distance r from both of them gives rise
793 * to a pair of linear equations in x,y,r of the
794 * form
795 *
796 * (x-x1) dy - (y-y1) dx = r sqrt(dx^2+dy^2)
797 *
798 * We eliminate r between those equations to give
799 * us a single linear equation in x,y describing
800 * the locus of points equidistant from both lines
801 * - i.e. the angle bisector.
802 *
803 * We then choose one of x,y to be a parameter t,
804 * and derive linear formulae for x,y,r in terms
805 * of t. This enables us to write down the
806 * circular equation (x-xd)^2+(y-yd)^2=r^2 as a
807 * quadratic in t; solving that and substituting
808 * in for x,y gives us two candidate points.
809 */
810 double eqs[2][4]; /* a,b,c,d : ax+by+cr=d */
811 double eq[3]; /* a,b,c: ax+by=c */
812 double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */
813 double q[3]; /* a,b,c: at^2+bt+c=0 */
814 double disc;
815
816 /* Find equations of the two input lines. */
817 for (m = 0; m < 2; m++) {
818 int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x;
819 int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y;
820 int dx = x2-x1, dy = y2-y1;
821
822 eqs[m][0] = dy;
823 eqs[m][1] = -dx;
824 eqs[m][2] = -sqrt(dx*dx+dy*dy);
825 eqs[m][3] = x1*dy - y1*dx;
826 }
827
828 /* Derive the angle bisector by eliminating r. */
829 eq[0] = eqs[0][0]*eqs[1][2] - eqs[1][0]*eqs[0][2];
830 eq[1] = eqs[0][1]*eqs[1][2] - eqs[1][1]*eqs[0][2];
831 eq[2] = eqs[0][3]*eqs[1][2] - eqs[1][3]*eqs[0][2];
832
833 /* Parametrise x and y in terms of some t. */
834 if (abs(eq[0]) < abs(eq[1])) {
835 /* Parameter is x. */
836 xt[0] = 1; xt[1] = 0;
837 yt[0] = -eq[0]/eq[1]; yt[1] = eq[2]/eq[1];
838 } else {
839 /* Parameter is y. */
840 yt[0] = 1; yt[1] = 0;
841 xt[0] = -eq[1]/eq[0]; xt[1] = eq[2]/eq[0];
842 }
843
844 /* Find a linear representation of r using eqs[0]. */
845 rt[0] = -(eqs[0][0]*xt[0] + eqs[0][1]*yt[0])/eqs[0][2];
846 rt[1] = (eqs[0][3] - eqs[0][0]*xt[1] -
847 eqs[0][1]*yt[1])/eqs[0][2];
848
849 /* Construct the quadratic equation. */
850 q[0] = -rt[0]*rt[0];
851 q[1] = -2*rt[0]*rt[1];
852 q[2] = -rt[1]*rt[1];
853 q[0] += xt[0]*xt[0];
854 q[1] += 2*xt[0]*(xt[1]-dots[0]->x);
855 q[2] += (xt[1]-dots[0]->x)*(xt[1]-dots[0]->x);
856 q[0] += yt[0]*yt[0];
857 q[1] += 2*yt[0]*(yt[1]-dots[0]->y);
858 q[2] += (yt[1]-dots[0]->y)*(yt[1]-dots[0]->y);
859
860 /* And solve it. */
861 disc = q[1]*q[1] - 4*q[0]*q[2];
862 if (disc >= 0) {
863 double t;
864
865 disc = sqrt(disc);
866
867 t = (-q[1] + disc) / (2*q[0]);
868 cx[cn] = xt[0]*t + xt[1];
869 cy[cn] = yt[0]*t + yt[1];
870 cn++;
871
872 t = (-q[1] - disc) / (2*q[0]);
873 cx[cn] = xt[0]*t + xt[1];
874 cy[cn] = yt[0]*t + yt[1];
875 cn++;
876 }
877 } else if (nedges == 1) {
878 /*
879 * Two dots and an edge. This one's another
880 * quadratic equation.
881 *
882 * The point we want must lie on the perpendicular
883 * bisector of the two dots; that much is obvious.
884 * So we can construct a parametrisation of that
885 * bisecting line, giving linear formulae for x,y
886 * in terms of t. We can also express the distance
887 * from the edge as such a linear formula.
888 *
889 * Then we set that equal to the radius of the
890 * circle passing through the two points, which is
891 * a Pythagoras exercise; that gives rise to a
892 * quadratic in t, which we solve.
893 */
894 double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */
895 double q[3]; /* a,b,c: at^2+bt+c=0 */
896 double disc;
897 double halfsep;
898
899 /* Find parametric formulae for x,y. */
900 {
901 int x1 = dots[0]->x, x2 = dots[1]->x;
902 int y1 = dots[0]->y, y2 = dots[1]->y;
903 int dx = x2-x1, dy = y2-y1;
904 double d = sqrt((double)dx*dx + (double)dy*dy);
905
906 xt[1] = (x1+x2)/2.0;
907 yt[1] = (y1+y2)/2.0;
908 /* It's convenient if we have t at standard scale. */
909 xt[0] = -dy/d;
910 yt[0] = dx/d;
911
912 /* Also note down half the separation between
913 * the dots, for use in computing the circle radius. */
914 halfsep = 0.5*d;
915 }
916
917 /* Find a parametric formula for r. */
918 {
919 int x1 = edgedot1[0]->x, x2 = edgedot2[0]->x;
920 int y1 = edgedot1[0]->y, y2 = edgedot2[0]->y;
921 int dx = x2-x1, dy = y2-y1;
922 double d = sqrt((double)dx*dx + (double)dy*dy);
923 rt[0] = (xt[0]*dy - yt[0]*dx) / d;
924 rt[1] = ((xt[1]-x1)*dy - (yt[1]-y1)*dx) / d;
925 }
926
927 /* Construct the quadratic equation. */
928 q[0] = rt[0]*rt[0];
929 q[1] = 2*rt[0]*rt[1];
930 q[2] = rt[1]*rt[1];
931 q[0] -= 1;
932 q[2] -= halfsep*halfsep;
933
934 /* And solve it. */
935 disc = q[1]*q[1] - 4*q[0]*q[2];
936 if (disc >= 0) {
937 double t;
938
939 disc = sqrt(disc);
940
941 t = (-q[1] + disc) / (2*q[0]);
942 cx[cn] = xt[0]*t + xt[1];
943 cy[cn] = yt[0]*t + yt[1];
944 cn++;
945
946 t = (-q[1] - disc) / (2*q[0]);
947 cx[cn] = xt[0]*t + xt[1];
948 cy[cn] = yt[0]*t + yt[1];
949 cn++;
950 }
951 } else if (nedges == 0) {
952 /*
953 * Three dots. This is another linear matrix
954 * equation, this time with each row of the matrix
955 * representing the perpendicular bisector between
956 * two of the points. Of course we only need two
957 * such lines to find their intersection, so we
958 * need only solve a 2x2 matrix equation.
959 */
960
961 double matrix[4], vector[2], vector2[2];
962 int m;
963
964 for (m = 0; m < 2; m++) {
965 int x1 = dots[m]->x, x2 = dots[m+1]->x;
966 int y1 = dots[m]->y, y2 = dots[m+1]->y;
967 int dx = x2-x1, dy = y2-y1;
968
969 /*
970 * ((x,y) - (x1,y1)) . (dx,dy) = 1/2 |(dx,dy)|^2
971 *
972 * => 2x dx + 2y dy = dx^2+dy^2 + (2 x1 dx + 2 y1 dy)
973 */
974 matrix[2*m+0] = 2*dx;
975 matrix[2*m+1] = 2*dy;
976 vector[m] = ((double)dx*dx + (double)dy*dy +
977 2.0*x1*dx + 2.0*y1*dy);
978 }
979
980 if (solve_2x2_matrix(matrix, vector, vector2)) {
981 cx[cn] = vector2[0];
982 cy[cn] = vector2[1];
983 cn++;
984 }
985 }
986
987 /*
988 * Now go through our candidate points and see if any
989 * of them are better than what we've got so far.
990 */
991 for (m = 0; m < cn; m++) {
992 double x = cx[m], y = cy[m];
993
994 /*
995 * First, disqualify the point if it's not inside
996 * the polygon, which we work out by counting the
997 * edges to the right of the point. (For
998 * tiebreaking purposes when edges start or end on
999 * our y-coordinate or go right through it, we
1000 * consider our point to be offset by a small
1001 * _positive_ epsilon in both the x- and
1002 * y-direction.)
1003 */
1004 int e, in = 0;
1005 for (e = 0; e < f->order; e++) {
1006 int xs = f->edges[e]->dot1->x;
1007 int xe = f->edges[e]->dot2->x;
1008 int ys = f->edges[e]->dot1->y;
1009 int ye = f->edges[e]->dot2->y;
1010 if ((y >= ys && y < ye) || (y >= ye && y < ys)) {
1011 /*
1012 * The line goes past our y-position. Now we need
1013 * to know if its x-coordinate when it does so is
1014 * to our right.
1015 *
1016 * The x-coordinate in question is mathematically
1017 * (y - ys) * (xe - xs) / (ye - ys), and we want
1018 * to know whether (x - xs) >= that. Of course we
1019 * avoid the division, so we can work in integers;
1020 * to do this we must multiply both sides of the
1021 * inequality by ye - ys, which means we must
1022 * first check that's not negative.
1023 */
1024 int num = xe - xs, denom = ye - ys;
1025 if (denom < 0) {
1026 num = -num;
1027 denom = -denom;
1028 }
1029 if ((x - xs) * denom >= (y - ys) * num)
1030 in ^= 1;
1031 }
1032 }
1033
1034 if (in) {
1035 double mindist = HUGE_VAL;
1036 int e, d;
1037
1038 /*
1039 * This point is inside the polygon, so now we check
1040 * its minimum distance to every edge and corner.
1041 * First the corners ...
1042 */
1043 for (d = 0; d < f->order; d++) {
1044 int xp = f->dots[d]->x;
1045 int yp = f->dots[d]->y;
1046 double dx = x - xp, dy = y - yp;
1047 double dist = dx*dx + dy*dy;
1048 if (mindist > dist)
1049 mindist = dist;
1050 }
1051
1052 /*
1053 * ... and now also check the perpendicular distance
1054 * to every edge, if the perpendicular lies between
1055 * the edge's endpoints.
1056 */
1057 for (e = 0; e < f->order; e++) {
1058 int xs = f->edges[e]->dot1->x;
1059 int xe = f->edges[e]->dot2->x;
1060 int ys = f->edges[e]->dot1->y;
1061 int ye = f->edges[e]->dot2->y;
1062
1063 /*
1064 * If s and e are our endpoints, and p our
1065 * candidate circle centre, the foot of a
1066 * perpendicular from p to the line se lies
1067 * between s and e if and only if (p-s).(e-s) lies
1068 * strictly between 0 and (e-s).(e-s).
1069 */
1070 int edx = xe - xs, edy = ye - ys;
1071 double pdx = x - xs, pdy = y - ys;
1072 double pde = pdx * edx + pdy * edy;
1073 long ede = (long)edx * edx + (long)edy * edy;
1074 if (0 < pde && pde < ede) {
1075 /*
1076 * Yes, the nearest point on this edge is
1077 * closer than either endpoint, so we must
1078 * take it into account by measuring the
1079 * perpendicular distance to the edge and
1080 * checking its square against mindist.
1081 */
1082
1083 double pdre = pdx * edy - pdy * edx;
1084 double sqlen = pdre * pdre / ede;
1085
1086 if (mindist > sqlen)
1087 mindist = sqlen;
1088 }
1089 }
1090
1091 /*
1092 * Right. Now we know the biggest circle around this
1093 * point, so we can check it against bestdist.
1094 */
1095 if (bestdist < mindist) {
1096 bestdist = mindist;
1097 xbest = x;
1098 ybest = y;
1099 }
1100 }
1101 }
1102
1103 if (k < f->order)
1104 nedges--;
1105 else
1106 ndots--;
1107 }
1108 if (j < f->order)
1109 nedges--;
1110 else
1111 ndots--;
1112 }
1113 if (i < f->order)
1114 nedges--;
1115 else
1116 ndots--;
1117 }
1118
1119 assert(bestdist > 0);
1120
1121 f->has_incentre = TRUE;
1122 f->ix = xbest + 0.5; /* round to nearest */
1123 f->iy = ybest + 0.5;
1124}
1125
7c95608a 1126/* ------ Generate various types of grid ------ */
1127
1128/* General method is to generate faces, by calculating their dot coordinates.
1129 * As new faces are added, we keep track of all the dots so we can tell when
1130 * a new face reuses an existing dot. For example, two squares touching at an
1131 * edge would generate six unique dots: four dots from the first face, then
1132 * two additional dots for the second face, because we detect the other two
1133 * dots have already been taken up. This list is stored in a tree234
1134 * called "points". No extra memory-allocation needed here - we store the
1135 * actual grid_dot* pointers, which all point into the g->dots list.
1136 * For this reason, we have to calculate coordinates in such a way as to
1137 * eliminate any rounding errors, so we can detect when a dot on one
1138 * face precisely lands on a dot of a different face. No floating-point
1139 * arithmetic here!
1140 */
1141
1142grid *grid_new_square(int width, int height)
1143{
1144 int x, y;
1145 /* Side length */
1146 int a = 20;
1147
1148 /* Upper bounds - don't have to be exact */
1149 int max_faces = width * height;
1150 int max_dots = (width + 1) * (height + 1);
1151
1152 tree234 *points;
1153
1154 grid *g = grid_new();
1155 g->tilesize = a;
1156 g->faces = snewn(max_faces, grid_face);
1157 g->dots = snewn(max_dots, grid_dot);
1158
1159 points = newtree234(grid_point_cmp_fn);
1160
1161 /* generate square faces */
1162 for (y = 0; y < height; y++) {
1163 for (x = 0; x < width; x++) {
1164 grid_dot *d;
1165 /* face position */
1166 int px = a * x;
1167 int py = a * y;
1168
1169 grid_face_add_new(g, 4);
1170 d = grid_get_dot(g, points, px, py);
1171 grid_face_set_dot(g, d, 0);
1172 d = grid_get_dot(g, points, px + a, py);
1173 grid_face_set_dot(g, d, 1);
1174 d = grid_get_dot(g, points, px + a, py + a);
1175 grid_face_set_dot(g, d, 2);
1176 d = grid_get_dot(g, points, px, py + a);
1177 grid_face_set_dot(g, d, 3);
1178 }
1179 }
1180
1181 freetree234(points);
1182 assert(g->num_faces <= max_faces);
1183 assert(g->num_dots <= max_dots);
7c95608a 1184
1185 grid_make_consistent(g);
1186 return g;
1187}
1188
1189grid *grid_new_honeycomb(int width, int height)
1190{
1191 int x, y;
1192 /* Vector for side of hexagon - ratio is close to sqrt(3) */
1193 int a = 15;
1194 int b = 26;
1195
1196 /* Upper bounds - don't have to be exact */
1197 int max_faces = width * height;
1198 int max_dots = 2 * (width + 1) * (height + 1);
1199
1200 tree234 *points;
1201
1202 grid *g = grid_new();
1203 g->tilesize = 3 * a;
1204 g->faces = snewn(max_faces, grid_face);
1205 g->dots = snewn(max_dots, grid_dot);
1206
1207 points = newtree234(grid_point_cmp_fn);
1208
1209 /* generate hexagonal faces */
1210 for (y = 0; y < height; y++) {
1211 for (x = 0; x < width; x++) {
1212 grid_dot *d;
1213 /* face centre */
1214 int cx = 3 * a * x;
1215 int cy = 2 * b * y;
1216 if (x % 2)
1217 cy += b;
1218 grid_face_add_new(g, 6);
1219
1220 d = grid_get_dot(g, points, cx - a, cy - b);
1221 grid_face_set_dot(g, d, 0);
1222 d = grid_get_dot(g, points, cx + a, cy - b);
1223 grid_face_set_dot(g, d, 1);
1224 d = grid_get_dot(g, points, cx + 2*a, cy);
1225 grid_face_set_dot(g, d, 2);
1226 d = grid_get_dot(g, points, cx + a, cy + b);
1227 grid_face_set_dot(g, d, 3);
1228 d = grid_get_dot(g, points, cx - a, cy + b);
1229 grid_face_set_dot(g, d, 4);
1230 d = grid_get_dot(g, points, cx - 2*a, cy);
1231 grid_face_set_dot(g, d, 5);
1232 }
1233 }
1234
1235 freetree234(points);
1236 assert(g->num_faces <= max_faces);
1237 assert(g->num_dots <= max_dots);
7c95608a 1238
1239 grid_make_consistent(g);
1240 return g;
1241}
1242
1243/* Doesn't use the previous method of generation, it pre-dates it!
1244 * A triangular grid is just about simple enough to do by "brute force" */
1245grid *grid_new_triangular(int width, int height)
1246{
1247 int x,y;
1248
1249 /* Vector for side of triangle - ratio is close to sqrt(3) */
1250 int vec_x = 15;
1251 int vec_y = 26;
1252
1253 int index;
1254
1255 /* convenient alias */
1256 int w = width + 1;
1257
1258 grid *g = grid_new();
1259 g->tilesize = 18; /* adjust to your taste */
1260
1261 g->num_faces = width * height * 2;
1262 g->num_dots = (width + 1) * (height + 1);
1263 g->faces = snewn(g->num_faces, grid_face);
1264 g->dots = snewn(g->num_dots, grid_dot);
1265
1266 /* generate dots */
1267 index = 0;
1268 for (y = 0; y <= height; y++) {
1269 for (x = 0; x <= width; x++) {
1270 grid_dot *d = g->dots + index;
1271 /* odd rows are offset to the right */
1272 d->order = 0;
1273 d->edges = NULL;
1274 d->faces = NULL;
1275 d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0);
1276 d->y = y * vec_y;
1277 index++;
1278 }
1279 }
1280
1281 /* generate faces */
1282 index = 0;
1283 for (y = 0; y < height; y++) {
1284 for (x = 0; x < width; x++) {
1285 /* initialise two faces for this (x,y) */
1286 grid_face *f1 = g->faces + index;
1287 grid_face *f2 = f1 + 1;
1288 f1->edges = NULL;
1289 f1->order = 3;
1290 f1->dots = snewn(f1->order, grid_dot*);
1291 f2->edges = NULL;
1292 f2->order = 3;
1293 f2->dots = snewn(f2->order, grid_dot*);
1294
1295 /* face descriptions depend on whether the row-number is
1296 * odd or even */
1297 if (y % 2) {
1298 f1->dots[0] = g->dots + y * w + x;
1299 f1->dots[1] = g->dots + (y + 1) * w + x + 1;
1300 f1->dots[2] = g->dots + (y + 1) * w + x;
1301 f2->dots[0] = g->dots + y * w + x;
1302 f2->dots[1] = g->dots + y * w + x + 1;
1303 f2->dots[2] = g->dots + (y + 1) * w + x + 1;
1304 } else {
1305 f1->dots[0] = g->dots + y * w + x;
1306 f1->dots[1] = g->dots + y * w + x + 1;
1307 f1->dots[2] = g->dots + (y + 1) * w + x;
1308 f2->dots[0] = g->dots + y * w + x + 1;
1309 f2->dots[1] = g->dots + (y + 1) * w + x + 1;
1310 f2->dots[2] = g->dots + (y + 1) * w + x;
1311 }
1312 index += 2;
1313 }
1314 }
1315
7c95608a 1316 grid_make_consistent(g);
1317 return g;
1318}
1319
1320grid *grid_new_snubsquare(int width, int height)
1321{
1322 int x, y;
1323 /* Vector for side of triangle - ratio is close to sqrt(3) */
1324 int a = 15;
1325 int b = 26;
1326
1327 /* Upper bounds - don't have to be exact */
1328 int max_faces = 3 * width * height;
1329 int max_dots = 2 * (width + 1) * (height + 1);
1330
1331 tree234 *points;
1332
1333 grid *g = grid_new();
1334 g->tilesize = 18;
1335 g->faces = snewn(max_faces, grid_face);
1336 g->dots = snewn(max_dots, grid_dot);
1337
1338 points = newtree234(grid_point_cmp_fn);
1339
1340 for (y = 0; y < height; y++) {
1341 for (x = 0; x < width; x++) {
1342 grid_dot *d;
1343 /* face position */
1344 int px = (a + b) * x;
1345 int py = (a + b) * y;
1346
1347 /* generate square faces */
1348 grid_face_add_new(g, 4);
1349 if ((x + y) % 2) {
1350 d = grid_get_dot(g, points, px + a, py);
1351 grid_face_set_dot(g, d, 0);
1352 d = grid_get_dot(g, points, px + a + b, py + a);
1353 grid_face_set_dot(g, d, 1);
1354 d = grid_get_dot(g, points, px + b, py + a + b);
1355 grid_face_set_dot(g, d, 2);
1356 d = grid_get_dot(g, points, px, py + b);
1357 grid_face_set_dot(g, d, 3);
1358 } else {
1359 d = grid_get_dot(g, points, px + b, py);
1360 grid_face_set_dot(g, d, 0);
1361 d = grid_get_dot(g, points, px + a + b, py + b);
1362 grid_face_set_dot(g, d, 1);
1363 d = grid_get_dot(g, points, px + a, py + a + b);
1364 grid_face_set_dot(g, d, 2);
1365 d = grid_get_dot(g, points, px, py + a);
1366 grid_face_set_dot(g, d, 3);
1367 }
1368
1369 /* generate up/down triangles */
1370 if (x > 0) {
1371 grid_face_add_new(g, 3);
1372 if ((x + y) % 2) {
1373 d = grid_get_dot(g, points, px + a, py);
1374 grid_face_set_dot(g, d, 0);
1375 d = grid_get_dot(g, points, px, py + b);
1376 grid_face_set_dot(g, d, 1);
1377 d = grid_get_dot(g, points, px - a, py);
1378 grid_face_set_dot(g, d, 2);
1379 } else {
1380 d = grid_get_dot(g, points, px, py + a);
1381 grid_face_set_dot(g, d, 0);
1382 d = grid_get_dot(g, points, px + a, py + a + b);
1383 grid_face_set_dot(g, d, 1);
1384 d = grid_get_dot(g, points, px - a, py + a + b);
1385 grid_face_set_dot(g, d, 2);
1386 }
1387 }
1388
1389 /* generate left/right triangles */
1390 if (y > 0) {
1391 grid_face_add_new(g, 3);
1392 if ((x + y) % 2) {
1393 d = grid_get_dot(g, points, px + a, py);
1394 grid_face_set_dot(g, d, 0);
1395 d = grid_get_dot(g, points, px + a + b, py - a);
1396 grid_face_set_dot(g, d, 1);
1397 d = grid_get_dot(g, points, px + a + b, py + a);
1398 grid_face_set_dot(g, d, 2);
1399 } else {
1400 d = grid_get_dot(g, points, px, py - a);
1401 grid_face_set_dot(g, d, 0);
1402 d = grid_get_dot(g, points, px + b, py);
1403 grid_face_set_dot(g, d, 1);
1404 d = grid_get_dot(g, points, px, py + a);
1405 grid_face_set_dot(g, d, 2);
1406 }
1407 }
1408 }
1409 }
1410
1411 freetree234(points);
1412 assert(g->num_faces <= max_faces);
1413 assert(g->num_dots <= max_dots);
7c95608a 1414
1415 grid_make_consistent(g);
1416 return g;
1417}
1418
1419grid *grid_new_cairo(int width, int height)
1420{
1421 int x, y;
1422 /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
1423 int a = 14;
1424 int b = 31;
1425
1426 /* Upper bounds - don't have to be exact */
1427 int max_faces = 2 * width * height;
1428 int max_dots = 3 * (width + 1) * (height + 1);
1429
1430 tree234 *points;
1431
1432 grid *g = grid_new();
1433 g->tilesize = 40;
1434 g->faces = snewn(max_faces, grid_face);
1435 g->dots = snewn(max_dots, grid_dot);
1436
1437 points = newtree234(grid_point_cmp_fn);
1438
1439 for (y = 0; y < height; y++) {
1440 for (x = 0; x < width; x++) {
1441 grid_dot *d;
1442 /* cell position */
1443 int px = 2 * b * x;
1444 int py = 2 * b * y;
1445
1446 /* horizontal pentagons */
1447 if (y > 0) {
1448 grid_face_add_new(g, 5);
1449 if ((x + y) % 2) {
1450 d = grid_get_dot(g, points, px + a, py - b);
1451 grid_face_set_dot(g, d, 0);
1452 d = grid_get_dot(g, points, px + 2*b - a, py - b);
1453 grid_face_set_dot(g, d, 1);
1454 d = grid_get_dot(g, points, px + 2*b, py);
1455 grid_face_set_dot(g, d, 2);
1456 d = grid_get_dot(g, points, px + b, py + a);
1457 grid_face_set_dot(g, d, 3);
1458 d = grid_get_dot(g, points, px, py);
1459 grid_face_set_dot(g, d, 4);
1460 } else {
1461 d = grid_get_dot(g, points, px, py);
1462 grid_face_set_dot(g, d, 0);
1463 d = grid_get_dot(g, points, px + b, py - a);
1464 grid_face_set_dot(g, d, 1);
1465 d = grid_get_dot(g, points, px + 2*b, py);
1466 grid_face_set_dot(g, d, 2);
1467 d = grid_get_dot(g, points, px + 2*b - a, py + b);
1468 grid_face_set_dot(g, d, 3);
1469 d = grid_get_dot(g, points, px + a, py + b);
1470 grid_face_set_dot(g, d, 4);
1471 }
1472 }
1473 /* vertical pentagons */
1474 if (x > 0) {
1475 grid_face_add_new(g, 5);
1476 if ((x + y) % 2) {
1477 d = grid_get_dot(g, points, px, py);
1478 grid_face_set_dot(g, d, 0);
1479 d = grid_get_dot(g, points, px + b, py + a);
1480 grid_face_set_dot(g, d, 1);
1481 d = grid_get_dot(g, points, px + b, py + 2*b - a);
1482 grid_face_set_dot(g, d, 2);
1483 d = grid_get_dot(g, points, px, py + 2*b);
1484 grid_face_set_dot(g, d, 3);
1485 d = grid_get_dot(g, points, px - a, py + b);
1486 grid_face_set_dot(g, d, 4);
1487 } else {
1488 d = grid_get_dot(g, points, px, py);
1489 grid_face_set_dot(g, d, 0);
1490 d = grid_get_dot(g, points, px + a, py + b);
1491 grid_face_set_dot(g, d, 1);
1492 d = grid_get_dot(g, points, px, py + 2*b);
1493 grid_face_set_dot(g, d, 2);
1494 d = grid_get_dot(g, points, px - b, py + 2*b - a);
1495 grid_face_set_dot(g, d, 3);
1496 d = grid_get_dot(g, points, px - b, py + a);
1497 grid_face_set_dot(g, d, 4);
1498 }
1499 }
1500 }
1501 }
1502
1503 freetree234(points);
1504 assert(g->num_faces <= max_faces);
1505 assert(g->num_dots <= max_dots);
7c95608a 1506
1507 grid_make_consistent(g);
1508 return g;
1509}
1510
1511grid *grid_new_greathexagonal(int width, int height)
1512{
1513 int x, y;
1514 /* Vector for side of triangle - ratio is close to sqrt(3) */
1515 int a = 15;
1516 int b = 26;
1517
1518 /* Upper bounds - don't have to be exact */
1519 int max_faces = 6 * (width + 1) * (height + 1);
1520 int max_dots = 6 * width * height;
1521
1522 tree234 *points;
1523
1524 grid *g = grid_new();
1525 g->tilesize = 18;
1526 g->faces = snewn(max_faces, grid_face);
1527 g->dots = snewn(max_dots, grid_dot);
1528
1529 points = newtree234(grid_point_cmp_fn);
1530
1531 for (y = 0; y < height; y++) {
1532 for (x = 0; x < width; x++) {
1533 grid_dot *d;
1534 /* centre of hexagon */
1535 int px = (3*a + b) * x;
1536 int py = (2*a + 2*b) * y;
1537 if (x % 2)
1538 py += a + b;
1539
1540 /* hexagon */
1541 grid_face_add_new(g, 6);
1542 d = grid_get_dot(g, points, px - a, py - b);
1543 grid_face_set_dot(g, d, 0);
1544 d = grid_get_dot(g, points, px + a, py - b);
1545 grid_face_set_dot(g, d, 1);
1546 d = grid_get_dot(g, points, px + 2*a, py);
1547 grid_face_set_dot(g, d, 2);
1548 d = grid_get_dot(g, points, px + a, py + b);
1549 grid_face_set_dot(g, d, 3);
1550 d = grid_get_dot(g, points, px - a, py + b);
1551 grid_face_set_dot(g, d, 4);
1552 d = grid_get_dot(g, points, px - 2*a, py);
1553 grid_face_set_dot(g, d, 5);
1554
1555 /* square below hexagon */
1556 if (y < height - 1) {
1557 grid_face_add_new(g, 4);
1558 d = grid_get_dot(g, points, px - a, py + b);
1559 grid_face_set_dot(g, d, 0);
1560 d = grid_get_dot(g, points, px + a, py + b);
1561 grid_face_set_dot(g, d, 1);
1562 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1563 grid_face_set_dot(g, d, 2);
1564 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1565 grid_face_set_dot(g, d, 3);
1566 }
1567
1568 /* square below right */
1569 if ((x < width - 1) && (((x % 2) == 0) || (y < height - 1))) {
1570 grid_face_add_new(g, 4);
1571 d = grid_get_dot(g, points, px + 2*a, py);
1572 grid_face_set_dot(g, d, 0);
1573 d = grid_get_dot(g, points, px + 2*a + b, py + a);
1574 grid_face_set_dot(g, d, 1);
1575 d = grid_get_dot(g, points, px + a + b, py + a + b);
1576 grid_face_set_dot(g, d, 2);
1577 d = grid_get_dot(g, points, px + a, py + b);
1578 grid_face_set_dot(g, d, 3);
1579 }
1580
1581 /* square below left */
1582 if ((x > 0) && (((x % 2) == 0) || (y < height - 1))) {
1583 grid_face_add_new(g, 4);
1584 d = grid_get_dot(g, points, px - 2*a, py);
1585 grid_face_set_dot(g, d, 0);
1586 d = grid_get_dot(g, points, px - a, py + b);
1587 grid_face_set_dot(g, d, 1);
1588 d = grid_get_dot(g, points, px - a - b, py + a + b);
1589 grid_face_set_dot(g, d, 2);
1590 d = grid_get_dot(g, points, px - 2*a - b, py + a);
1591 grid_face_set_dot(g, d, 3);
1592 }
1593
1594 /* Triangle below right */
1595 if ((x < width - 1) && (y < height - 1)) {
1596 grid_face_add_new(g, 3);
1597 d = grid_get_dot(g, points, px + a, py + b);
1598 grid_face_set_dot(g, d, 0);
1599 d = grid_get_dot(g, points, px + a + b, py + a + b);
1600 grid_face_set_dot(g, d, 1);
1601 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1602 grid_face_set_dot(g, d, 2);
1603 }
1604
1605 /* Triangle below left */
1606 if ((x > 0) && (y < height - 1)) {
1607 grid_face_add_new(g, 3);
1608 d = grid_get_dot(g, points, px - a, py + b);
1609 grid_face_set_dot(g, d, 0);
1610 d = grid_get_dot(g, points, px - a, py + 2*a + b);
1611 grid_face_set_dot(g, d, 1);
1612 d = grid_get_dot(g, points, px - a - b, py + a + b);
1613 grid_face_set_dot(g, d, 2);
1614 }
1615 }
1616 }
1617
1618 freetree234(points);
1619 assert(g->num_faces <= max_faces);
1620 assert(g->num_dots <= max_dots);
7c95608a 1621
1622 grid_make_consistent(g);
1623 return g;
1624}
1625
1626grid *grid_new_octagonal(int width, int height)
1627{
1628 int x, y;
1629 /* b/a approx sqrt(2) */
1630 int a = 29;
1631 int b = 41;
1632
1633 /* Upper bounds - don't have to be exact */
1634 int max_faces = 2 * width * height;
1635 int max_dots = 4 * (width + 1) * (height + 1);
1636
1637 tree234 *points;
1638
1639 grid *g = grid_new();
1640 g->tilesize = 40;
1641 g->faces = snewn(max_faces, grid_face);
1642 g->dots = snewn(max_dots, grid_dot);
1643
1644 points = newtree234(grid_point_cmp_fn);
1645
1646 for (y = 0; y < height; y++) {
1647 for (x = 0; x < width; x++) {
1648 grid_dot *d;
1649 /* cell position */
1650 int px = (2*a + b) * x;
1651 int py = (2*a + b) * y;
1652 /* octagon */
1653 grid_face_add_new(g, 8);
1654 d = grid_get_dot(g, points, px + a, py);
1655 grid_face_set_dot(g, d, 0);
1656 d = grid_get_dot(g, points, px + a + b, py);
1657 grid_face_set_dot(g, d, 1);
1658 d = grid_get_dot(g, points, px + 2*a + b, py + a);
1659 grid_face_set_dot(g, d, 2);
1660 d = grid_get_dot(g, points, px + 2*a + b, py + a + b);
1661 grid_face_set_dot(g, d, 3);
1662 d = grid_get_dot(g, points, px + a + b, py + 2*a + b);
1663 grid_face_set_dot(g, d, 4);
1664 d = grid_get_dot(g, points, px + a, py + 2*a + b);
1665 grid_face_set_dot(g, d, 5);
1666 d = grid_get_dot(g, points, px, py + a + b);
1667 grid_face_set_dot(g, d, 6);
1668 d = grid_get_dot(g, points, px, py + a);
1669 grid_face_set_dot(g, d, 7);
1670
1671 /* diamond */
1672 if ((x > 0) && (y > 0)) {
1673 grid_face_add_new(g, 4);
1674 d = grid_get_dot(g, points, px, py - a);
1675 grid_face_set_dot(g, d, 0);
1676 d = grid_get_dot(g, points, px + a, py);
1677 grid_face_set_dot(g, d, 1);
1678 d = grid_get_dot(g, points, px, py + a);
1679 grid_face_set_dot(g, d, 2);
1680 d = grid_get_dot(g, points, px - a, py);
1681 grid_face_set_dot(g, d, 3);
1682 }
1683 }
1684 }
1685
1686 freetree234(points);
1687 assert(g->num_faces <= max_faces);
1688 assert(g->num_dots <= max_dots);
7c95608a 1689
1690 grid_make_consistent(g);
1691 return g;
1692}
1693
1694grid *grid_new_kites(int width, int height)
1695{
1696 int x, y;
1697 /* b/a approx sqrt(3) */
1698 int a = 15;
1699 int b = 26;
1700
1701 /* Upper bounds - don't have to be exact */
1702 int max_faces = 6 * width * height;
1703 int max_dots = 6 * (width + 1) * (height + 1);
1704
1705 tree234 *points;
1706
1707 grid *g = grid_new();
1708 g->tilesize = 40;
1709 g->faces = snewn(max_faces, grid_face);
1710 g->dots = snewn(max_dots, grid_dot);
1711
1712 points = newtree234(grid_point_cmp_fn);
1713
1714 for (y = 0; y < height; y++) {
1715 for (x = 0; x < width; x++) {
1716 grid_dot *d;
1717 /* position of order-6 dot */
1718 int px = 4*b * x;
1719 int py = 6*a * y;
1720 if (y % 2)
1721 px += 2*b;
1722
1723 /* kite pointing up-left */
1724 grid_face_add_new(g, 4);
1725 d = grid_get_dot(g, points, px, py);
1726 grid_face_set_dot(g, d, 0);
1727 d = grid_get_dot(g, points, px + 2*b, py);
1728 grid_face_set_dot(g, d, 1);
1729 d = grid_get_dot(g, points, px + 2*b, py + 2*a);
1730 grid_face_set_dot(g, d, 2);
1731 d = grid_get_dot(g, points, px + b, py + 3*a);
1732 grid_face_set_dot(g, d, 3);
1733
1734 /* kite pointing up */
1735 grid_face_add_new(g, 4);
1736 d = grid_get_dot(g, points, px, py);
1737 grid_face_set_dot(g, d, 0);
1738 d = grid_get_dot(g, points, px + b, py + 3*a);
1739 grid_face_set_dot(g, d, 1);
1740 d = grid_get_dot(g, points, px, py + 4*a);
1741 grid_face_set_dot(g, d, 2);
1742 d = grid_get_dot(g, points, px - b, py + 3*a);
1743 grid_face_set_dot(g, d, 3);
1744
1745 /* kite pointing up-right */
1746 grid_face_add_new(g, 4);
1747 d = grid_get_dot(g, points, px, py);
1748 grid_face_set_dot(g, d, 0);
1749 d = grid_get_dot(g, points, px - b, py + 3*a);
1750 grid_face_set_dot(g, d, 1);
1751 d = grid_get_dot(g, points, px - 2*b, py + 2*a);
1752 grid_face_set_dot(g, d, 2);
1753 d = grid_get_dot(g, points, px - 2*b, py);
1754 grid_face_set_dot(g, d, 3);
1755
1756 /* kite pointing down-right */
1757 grid_face_add_new(g, 4);
1758 d = grid_get_dot(g, points, px, py);
1759 grid_face_set_dot(g, d, 0);
1760 d = grid_get_dot(g, points, px - 2*b, py);
1761 grid_face_set_dot(g, d, 1);
1762 d = grid_get_dot(g, points, px - 2*b, py - 2*a);
1763 grid_face_set_dot(g, d, 2);
1764 d = grid_get_dot(g, points, px - b, py - 3*a);
1765 grid_face_set_dot(g, d, 3);
1766
1767 /* kite pointing down */
1768 grid_face_add_new(g, 4);
1769 d = grid_get_dot(g, points, px, py);
1770 grid_face_set_dot(g, d, 0);
1771 d = grid_get_dot(g, points, px - b, py - 3*a);
1772 grid_face_set_dot(g, d, 1);
1773 d = grid_get_dot(g, points, px, py - 4*a);
1774 grid_face_set_dot(g, d, 2);
1775 d = grid_get_dot(g, points, px + b, py - 3*a);
1776 grid_face_set_dot(g, d, 3);
1777
1778 /* kite pointing down-left */
1779 grid_face_add_new(g, 4);
1780 d = grid_get_dot(g, points, px, py);
1781 grid_face_set_dot(g, d, 0);
1782 d = grid_get_dot(g, points, px + b, py - 3*a);
1783 grid_face_set_dot(g, d, 1);
1784 d = grid_get_dot(g, points, px + 2*b, py - 2*a);
1785 grid_face_set_dot(g, d, 2);
1786 d = grid_get_dot(g, points, px + 2*b, py);
1787 grid_face_set_dot(g, d, 3);
1788 }
1789 }
1790
1791 freetree234(points);
1792 assert(g->num_faces <= max_faces);
1793 assert(g->num_dots <= max_dots);
7c95608a 1794
1795 grid_make_consistent(g);
1796 return g;
1797}
1798
e30d39f6 1799grid *grid_new_floret(int width, int height)
1800{
1801 int x, y;
1802 /* Vectors for sides; weird numbers needed to keep puzzle aligned with window
1803 * -py/px is close to tan(30 - atan(sqrt(3)/9))
1804 * using py=26 makes everything lean to the left, rather than right
1805 */
1806 int px = 75, py = -26; /* |( 75, -26)| = 79.43 */
1807 int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
1808 int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */
1809
1810 /* Upper bounds - don't have to be exact */
1811 int max_faces = 6 * width * height;
1812 int max_dots = 9 * (width + 1) * (height + 1);
1813
1814 tree234 *points;
1815
1816 grid *g = grid_new();
1817 g->tilesize = 2 * px;
1818 g->faces = snewn(max_faces, grid_face);
1819 g->dots = snewn(max_dots, grid_dot);
1820
1821 points = newtree234(grid_point_cmp_fn);
1822
1823 /* generate pentagonal faces */
1824 for (y = 0; y < height; y++) {
1825 for (x = 0; x < width; x++) {
1826 grid_dot *d;
1827 /* face centre */
1828 int cx = (6*px+3*qx)/2 * x;
1829 int cy = (4*py-5*qy) * y;
1830 if (x % 2)
1831 cy -= (4*py-5*qy)/2;
1832 else if (y && y == height-1)
1833 continue; /* make better looking grids? try 3x3 for instance */
1834
1835 grid_face_add_new(g, 5);
1836 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
1837 d = grid_get_dot(g, points, cx+2*rx , cy+2*ry ); grid_face_set_dot(g, d, 1);
1838 d = grid_get_dot(g, points, cx+2*rx+qx, cy+2*ry+qy); grid_face_set_dot(g, d, 2);
1839 d = grid_get_dot(g, points, cx+2*qx+rx, cy+2*qy+ry); grid_face_set_dot(g, d, 3);
1840 d = grid_get_dot(g, points, cx+2*qx , cy+2*qy ); grid_face_set_dot(g, d, 4);
1841
1842 grid_face_add_new(g, 5);
1843 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
1844 d = grid_get_dot(g, points, cx+2*qx , cy+2*qy ); grid_face_set_dot(g, d, 1);
1845 d = grid_get_dot(g, points, cx+2*qx+px, cy+2*qy+py); grid_face_set_dot(g, d, 2);
1846 d = grid_get_dot(g, points, cx+2*px+qx, cy+2*py+qy); grid_face_set_dot(g, d, 3);
1847 d = grid_get_dot(g, points, cx+2*px , cy+2*py ); grid_face_set_dot(g, d, 4);
1848
1849 grid_face_add_new(g, 5);
1850 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
1851 d = grid_get_dot(g, points, cx+2*px , cy+2*py ); grid_face_set_dot(g, d, 1);
1852 d = grid_get_dot(g, points, cx+2*px-rx, cy+2*py-ry); grid_face_set_dot(g, d, 2);
1853 d = grid_get_dot(g, points, cx-2*rx+px, cy-2*ry+py); grid_face_set_dot(g, d, 3);
1854 d = grid_get_dot(g, points, cx-2*rx , cy-2*ry ); grid_face_set_dot(g, d, 4);
1855
1856 grid_face_add_new(g, 5);
1857 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
1858 d = grid_get_dot(g, points, cx-2*rx , cy-2*ry ); grid_face_set_dot(g, d, 1);
1859 d = grid_get_dot(g, points, cx-2*rx-qx, cy-2*ry-qy); grid_face_set_dot(g, d, 2);
1860 d = grid_get_dot(g, points, cx-2*qx-rx, cy-2*qy-ry); grid_face_set_dot(g, d, 3);
1861 d = grid_get_dot(g, points, cx-2*qx , cy-2*qy ); grid_face_set_dot(g, d, 4);
1862
1863 grid_face_add_new(g, 5);
1864 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
1865 d = grid_get_dot(g, points, cx-2*qx , cy-2*qy ); grid_face_set_dot(g, d, 1);
1866 d = grid_get_dot(g, points, cx-2*qx-px, cy-2*qy-py); grid_face_set_dot(g, d, 2);
1867 d = grid_get_dot(g, points, cx-2*px-qx, cy-2*py-qy); grid_face_set_dot(g, d, 3);
1868 d = grid_get_dot(g, points, cx-2*px , cy-2*py ); grid_face_set_dot(g, d, 4);
1869
1870 grid_face_add_new(g, 5);
1871 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
1872 d = grid_get_dot(g, points, cx-2*px , cy-2*py ); grid_face_set_dot(g, d, 1);
1873 d = grid_get_dot(g, points, cx-2*px+rx, cy-2*py+ry); grid_face_set_dot(g, d, 2);
1874 d = grid_get_dot(g, points, cx+2*rx-px, cy+2*ry-py); grid_face_set_dot(g, d, 3);
1875 d = grid_get_dot(g, points, cx+2*rx , cy+2*ry ); grid_face_set_dot(g, d, 4);
1876 }
1877 }
1878
1879 freetree234(points);
1880 assert(g->num_faces <= max_faces);
1881 assert(g->num_dots <= max_dots);
e30d39f6 1882
1883 grid_make_consistent(g);
1884 return g;
1885}
1886
918a098a 1887grid *grid_new_dodecagonal(int width, int height)
1888{
1889 int x, y;
1890 /* Vector for side of triangle - ratio is close to sqrt(3) */
1891 int a = 15;
1892 int b = 26;
1893
1894 /* Upper bounds - don't have to be exact */
1895 int max_faces = 3 * width * height;
1896 int max_dots = 14 * width * height;
1897
1898 tree234 *points;
1899
1900 grid *g = grid_new();
1901 g->tilesize = b;
1902 g->faces = snewn(max_faces, grid_face);
1903 g->dots = snewn(max_dots, grid_dot);
1904
1905 points = newtree234(grid_point_cmp_fn);
1906
1907 for (y = 0; y < height; y++) {
1908 for (x = 0; x < width; x++) {
1909 grid_dot *d;
1910 /* centre of dodecagon */
1911 int px = (4*a + 2*b) * x;
1912 int py = (3*a + 2*b) * y;
1913 if (y % 2)
1914 px += 2*a + b;
1915
1916 /* dodecagon */
1917 grid_face_add_new(g, 12);
1918 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
1919 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
1920 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
1921 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
1922 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
1923 d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
1924 d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
1925 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
1926 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
1927 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
1928 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
1929 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
1930
1931 /* triangle below dodecagon */
1932 if ((y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) {
1933 grid_face_add_new(g, 3);
1934 d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0);
1935 d = grid_get_dot(g, points, px , py + (2*a + 2*b)); grid_face_set_dot(g, d, 1);
1936 d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 2);
1937 }
1938
1939 /* triangle above dodecagon */
1940 if ((y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) {
1941 grid_face_add_new(g, 3);
1942 d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0);
1943 d = grid_get_dot(g, points, px , py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
1944 d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 2);
1945 }
1946 }
1947 }
1948
1949 freetree234(points);
1950 assert(g->num_faces <= max_faces);
1951 assert(g->num_dots <= max_dots);
1952
1953 grid_make_consistent(g);
1954 return g;
1955}
1956
1957grid *grid_new_greatdodecagonal(int width, int height)
1958{
1959 int x, y;
1960 /* Vector for side of triangle - ratio is close to sqrt(3) */
1961 int a = 15;
1962 int b = 26;
1963
1964 /* Upper bounds - don't have to be exact */
1965 int max_faces = 30 * width * height;
1966 int max_dots = 200 * width * height;
1967
1968 tree234 *points;
1969
1970 grid *g = grid_new();
1971 g->tilesize = b;
1972 g->faces = snewn(max_faces, grid_face);
1973 g->dots = snewn(max_dots, grid_dot);
1974
1975 points = newtree234(grid_point_cmp_fn);
1976
1977 for (y = 0; y < height; y++) {
1978 for (x = 0; x < width; x++) {
1979 grid_dot *d;
1980 /* centre of dodecagon */
1981 int px = (6*a + 2*b) * x;
1982 int py = (3*a + 3*b) * y;
1983 if (y % 2)
1984 px += 3*a + b;
1985
1986 /* dodecagon */
1987 grid_face_add_new(g, 12);
1988 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
1989 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
1990 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
1991 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
1992 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
1993 d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
1994 d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
1995 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
1996 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
1997 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
1998 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
1999 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
2000
2001 /* hexagon below dodecagon */
2002 if (y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
2003 grid_face_add_new(g, 6);
2004 d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0);
2005 d = grid_get_dot(g, points, px + 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2006 d = grid_get_dot(g, points, px + a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 2);
2007 d = grid_get_dot(g, points, px - a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 3);
2008 d = grid_get_dot(g, points, px - 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 4);
2009 d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 5);
2010 }
2011
2012 /* hexagon above dodecagon */
2013 if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
2014 grid_face_add_new(g, 6);
2015 d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0);
2016 d = grid_get_dot(g, points, px - 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2017 d = grid_get_dot(g, points, px - a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 2);
2018 d = grid_get_dot(g, points, px + a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 3);
2019 d = grid_get_dot(g, points, px + 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 4);
2020 d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 5);
2021 }
2022
2023 /* square on right of dodecagon */
2024 if (x < width - 1) {
2025 grid_face_add_new(g, 4);
2026 d = grid_get_dot(g, points, px + 2*a + b, py - a); grid_face_set_dot(g, d, 0);
2027 d = grid_get_dot(g, points, px + 4*a + b, py - a); grid_face_set_dot(g, d, 1);
2028 d = grid_get_dot(g, points, px + 4*a + b, py + a); grid_face_set_dot(g, d, 2);
2029 d = grid_get_dot(g, points, px + 2*a + b, py + a); grid_face_set_dot(g, d, 3);
2030 }
2031
2032 /* square on top right of dodecagon */
2033 if (y && (x < width - 1 || !(y % 2))) {
2034 grid_face_add_new(g, 4);
2035 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2036 d = grid_get_dot(g, points, px + (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2037 d = grid_get_dot(g, points, px + (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 2);
2038 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 3);
2039 }
2040
2041 /* square on top left of dodecagon */
2042 if (y && (x || (y % 2))) {
2043 grid_face_add_new(g, 4);
2044 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 0);
2045 d = grid_get_dot(g, points, px - (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 1);
2046 d = grid_get_dot(g, points, px - (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 2);
2047 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 3);
2048 }
2049 }
2050 }
2051
2052 freetree234(points);
2053 assert(g->num_faces <= max_faces);
2054 assert(g->num_dots <= max_dots);
2055
2056 grid_make_consistent(g);
2057 return g;
2058}
2059
7c95608a 2060/* ----------- End of grid generators ------------- */
Simon Tatham's portable puzzles collection; import of svn://svn.tartarus.org/sgt/puzzles