tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
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 <float.h>
15#include <limits.h>
16#ifdef NO_TGMATH_H
17# include <math.h>
18#else
19# include <tgmath.h>
20#endif
21
22#include "puzzles.h"
23#include "tree234.h"
24#include "grid.h"
25#include "penrose-legacy.h"
26#include "penrose.h"
27#include "hat.h"
28#include "spectre.h"
29
30/* Debugging options */
31
32/*
33#define DEBUG_GRID
34*/
35
36/* ----------------------------------------------------------------------
37 * Deallocate or dereference a grid
38 */
39void grid_free(grid *g)
40{
41 assert(g->refcount);
42
43 g->refcount--;
44 if (g->refcount == 0) {
45 int i;
46 for (i = 0; i < g->num_faces; i++) {
47 sfree(g->faces[i]->dots);
48 sfree(g->faces[i]->edges);
49 sfree(g->faces[i]);
50 }
51 for (i = 0; i < g->num_dots; i++) {
52 sfree(g->dots[i]->faces);
53 sfree(g->dots[i]->edges);
54 sfree(g->dots[i]);
55 }
56 for (i = 0; i < g->num_edges; i++) {
57 sfree(g->edges[i]);
58 }
59 sfree(g->faces);
60 sfree(g->edges);
61 sfree(g->dots);
62 sfree(g);
63 }
64}
65
66/* Used by the other grid generators. Create a brand new grid with nothing
67 * initialised (all lists are NULL) */
68static grid *grid_empty(void)
69{
70 grid *g = snew(grid);
71 g->faces = NULL;
72 g->edges = NULL;
73 g->dots = NULL;
74 g->num_faces = g->num_edges = g->num_dots = 0;
75 g->size_faces = g->size_edges = g->size_dots = 0;
76 g->refcount = 1;
77 g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
78 return g;
79}
80
81/* Helper function to calculate perpendicular distance from
82 * a point P to a line AB. A and B mustn't be equal here.
83 *
84 * Well-known formula for area A of a triangle:
85 * / 1 1 1 \
86 * 2A = determinant of matrix | px ax bx |
87 * \ py ay by /
88 *
89 * Also well-known: 2A = base * height
90 * = perpendicular distance * line-length.
91 *
92 * Combining gives: distance = determinant / line-length(a,b)
93 */
94static double point_line_distance(long px, long py,
95 long ax, long ay,
96 long bx, long by)
97{
98 long det = ax*by - bx*ay + bx*py - px*by + px*ay - ax*py;
99 double len;
100 det = max(det, -det);
101 len = sqrt(SQ(ax - bx) + SQ(ay - by));
102 return det / len;
103}
104
105/* Determine nearest edge to where the user clicked.
106 * (x, y) is the clicked location, converted to grid coordinates.
107 * Returns the nearest edge, or NULL if no edge is reasonably
108 * near the position.
109 *
110 * Just judging edges by perpendicular distance is not quite right -
111 * the edge might be "off to one side". So we insist that the triangle
112 * with (x,y) has acute angles at the edge's dots.
113 *
114 * edge1
115 * *---------*------
116 * |
117 * | *(x,y)
118 * edge2 |
119 * | edge2 is OK, but edge1 is not, even though
120 * | edge1 is perpendicularly closer to (x,y)
121 * *
122 *
123 */
124grid_edge *grid_nearest_edge(grid *g, int x, int y)
125{
126 grid_edge *best_edge;
127 double best_distance = 0;
128 int i;
129
130 best_edge = NULL;
131
132 for (i = 0; i < g->num_edges; i++) {
133 grid_edge *e = g->edges[i];
134 long e2; /* squared length of edge */
135 long a2, b2; /* squared lengths of other sides */
136 double dist;
137
138 /* See if edge e is eligible - the triangle must have acute angles
139 * at the edge's dots.
140 * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
141 * so detect acute angles by testing for h^2 < a^2 + b^2 */
142 e2 = SQ((long)e->dot1->x - (long)e->dot2->x) + SQ((long)e->dot1->y - (long)e->dot2->y);
143 a2 = SQ((long)e->dot1->x - (long)x) + SQ((long)e->dot1->y - (long)y);
144 b2 = SQ((long)e->dot2->x - (long)x) + SQ((long)e->dot2->y - (long)y);
145 if (a2 >= e2 + b2) continue;
146 if (b2 >= e2 + a2) continue;
147
148 /* e is eligible so far. Now check the edge is reasonably close
149 * to where the user clicked. Don't want to toggle an edge if the
150 * click was way off the grid.
151 * There is room for experimentation here. We could check the
152 * perpendicular distance is within a certain fraction of the length
153 * of the edge. That amounts to testing a rectangular region around
154 * the edge.
155 * Alternatively, we could check that the angle at the point is obtuse.
156 * That would amount to testing a circular region with the edge as
157 * diameter. */
158 dist = point_line_distance((long)x, (long)y,
159 (long)e->dot1->x, (long)e->dot1->y,
160 (long)e->dot2->x, (long)e->dot2->y);
161 /* Is dist more than half edge length ? */
162 if (4 * SQ(dist) > e2)
163 continue;
164
165 if (best_edge == NULL || dist < best_distance) {
166 best_edge = e;
167 best_distance = dist;
168 }
169 }
170 return best_edge;
171}
172
173/* ----------------------------------------------------------------------
174 * Grid generation
175 */
176
177#ifdef SVG_GRID
178
179#define SVG_DOTS 1
180#define SVG_EDGES 2
181#define SVG_FACES 4
182
183#define FACE_COLOUR "red"
184#define EDGE_COLOUR "blue"
185#define DOT_COLOUR "black"
186
187static void grid_output_svg(FILE *fp, grid *g, int which)
188{
189 int i, j;
190
191 fprintf(fp,"\
192<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n\
193<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20010904//EN\"\n\
194\"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n\
195\n\
196<svg xmlns=\"http://www.w3.org/2000/svg\"\n\
197xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n");
198
199 if (which & SVG_FACES) {
200 fprintf(fp, "<g>\n");
201 for (i = 0; i < g->num_faces; i++) {
202 grid_face *f = g->faces[i];
203 fprintf(fp, "<polygon points=\"");
204 for (j = 0; j < f->order; j++) {
205 grid_dot *d = f->dots[j];
206 fprintf(fp, "%s%d,%d", (j == 0) ? "" : " ",
207 d->x, d->y);
208 }
209 fprintf(fp, "\" style=\"fill: %s; fill-opacity: 0.2; stroke: %s\" />\n",
210 FACE_COLOUR, FACE_COLOUR);
211 }
212 fprintf(fp, "</g>\n");
213 }
214 if (which & SVG_EDGES) {
215 fprintf(fp, "<g>\n");
216 for (i = 0; i < g->num_edges; i++) {
217 grid_edge *e = g->edges[i];
218 grid_dot *d1 = e->dot1, *d2 = e->dot2;
219
220 fprintf(fp, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" "
221 "style=\"stroke: %s\" />\n",
222 d1->x, d1->y, d2->x, d2->y, EDGE_COLOUR);
223 }
224 fprintf(fp, "</g>\n");
225 }
226
227 if (which & SVG_DOTS) {
228 fprintf(fp, "<g>\n");
229 for (i = 0; i < g->num_dots; i++) {
230 grid_dot *d = g->dots[i];
231 fprintf(fp, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />",
232 d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR);
233 }
234 fprintf(fp, "</g>\n");
235 }
236
237 fprintf(fp, "</svg>\n");
238}
239#endif
240
241#ifdef SVG_GRID
242#include <errno.h>
243
244static void grid_try_svg(grid *g, int which)
245{
246 char *svg = getenv("PUZZLES_SVG_GRID");
247 if (svg) {
248 FILE *svgf = fopen(svg, "w");
249 if (svgf) {
250 grid_output_svg(svgf, g, which);
251 fclose(svgf);
252 } else {
253 fprintf(stderr, "Unable to open file `%s': %s", svg, strerror(errno));
254 }
255 }
256}
257#endif
258
259/* Show the basic grid information, before doing grid_make_consistent */
260static void grid_debug_basic(grid *g)
261{
262 /* TODO: Maybe we should generate an SVG image of the dots and lines
263 * of the grid here, before grid_make_consistent.
264 * Would help with debugging grid generation. */
265#ifdef DEBUG_GRID
266 int i;
267 printf("--- Basic Grid Data ---\n");
268 for (i = 0; i < g->num_dots; i++) {
269 grid_dot *d = g->dots[i];
270 printf("Dot %d at (%d,%d)\n", i, d->x, d->y);
271 }
272 for (i = 0; i < g->num_faces; i++) {
273 grid_face *f = g->faces[i];
274 printf("Face %d: dots[", i);
275 int j;
276 for (j = 0; j < f->order; j++) {
277 grid_dot *d = f->dots[j];
278 printf("%s%d", j ? "," : "", (int)(d->index));
279 }
280 printf("]\n");
281 }
282#endif
283#ifdef SVG_GRID
284 grid_try_svg(g, SVG_FACES);
285#endif
286}
287
288/* Show the derived grid information, computed by grid_make_consistent */
289static void grid_debug_derived(grid *g)
290{
291#ifdef DEBUG_GRID
292 /* edges */
293 int i;
294 printf("--- Derived Grid Data ---\n");
295 for (i = 0; i < g->num_edges; i++) {
296 grid_edge *e = g->edges[i];
297 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
298 i, (int)(e->dot1->index), (int)(e->dot2->index),
299 e->face1 ? (int)(e->face1->index) : -1,
300 e->face2 ? (int)(e->face2->index) : -1);
301 }
302 /* faces */
303 for (i = 0; i < g->num_faces; i++) {
304 grid_face *f = g->faces[i];
305 int j;
306 printf("Face %d: faces[", i);
307 for (j = 0; j < f->order; j++) {
308 grid_edge *e = f->edges[j];
309 grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1;
310 printf("%s%d", j ? "," : "", f2 ? f2->index : -1);
311 }
312 printf("]\n");
313 }
314 /* dots */
315 for (i = 0; i < g->num_dots; i++) {
316 grid_dot *d = g->dots[i];
317 int j;
318 printf("Dot %d: dots[", i);
319 for (j = 0; j < d->order; j++) {
320 grid_edge *e = d->edges[j];
321 grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1;
322 printf("%s%d", j ? "," : "", d2->index);
323 }
324 printf("] faces[");
325 for (j = 0; j < d->order; j++) {
326 grid_face *f = d->faces[j];
327 printf("%s%d", j ? "," : "", f ? f->index : -1);
328 }
329 printf("]\n");
330 }
331#endif
332#ifdef SVG_GRID
333 grid_try_svg(g, SVG_DOTS | SVG_EDGES | SVG_FACES);
334#endif
335}
336
337/* Helper function for building incomplete-edges list in
338 * grid_make_consistent() */
339static int grid_edge_bydots_cmpfn(void *v1, void *v2)
340{
341 grid_edge *a = v1;
342 grid_edge *b = v2;
343 grid_dot *da, *db;
344
345 /* Edges are not "normalised" - the 2 dots could be stored in any order,
346 * so we need to take this into account when comparing edges. */
347
348 /* Compare first dots */
349 da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2;
350 db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2;
351 if (da->index < db->index)
352 return -1;
353 if (da->index > db->index)
354 return +1;
355 /* Compare last dots */
356 da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1;
357 db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1;
358 if (da->index < db->index)
359 return -1;
360 if (da->index > db->index)
361 return +1;
362
363 return 0;
364}
365
366/*
367 * 'Vigorously trim' a grid, by which I mean deleting any isolated or
368 * uninteresting faces. By which, in turn, I mean: ensure that the
369 * grid is composed solely of faces adjacent to at least one
370 * 'landlocked' dot (i.e. one not in contact with the infinite
371 * exterior face), and that all those dots are in a single connected
372 * component.
373 *
374 * This function operates on, and returns, a grid satisfying the
375 * preconditions to grid_make_consistent() rather than the
376 * postconditions. (So call it first.)
377 */
378static void grid_trim_vigorously(grid *g)
379{
380 int *dotpairs, *faces, *dots;
381 DSF *dsf;
382 int i, j, k, size, newfaces, newdots;
383
384 /*
385 * First construct a matrix in which each ordered pair of dots is
386 * mapped to the index of the face in which those dots occur in
387 * that order.
388 */
389 dotpairs = snewn(g->num_dots * g->num_dots, int);
390 for (i = 0; i < g->num_dots; i++)
391 for (j = 0; j < g->num_dots; j++)
392 dotpairs[i*g->num_dots+j] = -1;
393 for (i = 0; i < g->num_faces; i++) {
394 grid_face *f = g->faces[i];
395 int dot0 = f->dots[f->order-1]->index;
396 for (j = 0; j < f->order; j++) {
397 int dot1 = f->dots[j]->index;
398 dotpairs[dot0 * g->num_dots + dot1] = i;
399 dot0 = dot1;
400 }
401 }
402
403 /*
404 * Now we can identify landlocked dots: they're the ones all of
405 * whose edges have a mirror-image counterpart in this matrix.
406 */
407 dots = snewn(g->num_dots, int);
408 for (i = 0; i < g->num_dots; i++) {
409 dots[i] = 1;
410 for (j = 0; j < g->num_dots; j++) {
411 if ((dotpairs[i*g->num_dots+j] >= 0) ^
412 (dotpairs[j*g->num_dots+i] >= 0))
413 dots[i] = 0; /* non-duplicated edge: coastal dot */
414 }
415 }
416
417 /*
418 * Now identify connected pairs of landlocked dots, and form a dsf
419 * unifying them.
420 */
421 dsf = dsf_new(g->num_dots);
422 for (i = 0; i < g->num_dots; i++)
423 for (j = 0; j < i; j++)
424 if (dots[i] && dots[j] &&
425 dotpairs[i*g->num_dots+j] >= 0 &&
426 dotpairs[j*g->num_dots+i] >= 0)
427 dsf_merge(dsf, i, j);
428
429 /*
430 * Now look for the largest component.
431 */
432 size = 0;
433 j = -1;
434 for (i = 0; i < g->num_dots; i++) {
435 int newsize;
436 if (dots[i] && dsf_canonify(dsf, i) == i &&
437 (newsize = dsf_size(dsf, i)) > size) {
438 j = i;
439 size = newsize;
440 }
441 }
442
443 /*
444 * Work out which faces we're going to keep (precisely those with
445 * at least one dot in the same connected component as j) and
446 * which dots (those required by any face we're keeping).
447 *
448 * At this point we reuse the 'dots' array to indicate the dots
449 * we're keeping, rather than the ones that are landlocked.
450 */
451 faces = snewn(g->num_faces, int);
452 for (i = 0; i < g->num_faces; i++)
453 faces[i] = 0;
454 for (i = 0; i < g->num_dots; i++)
455 dots[i] = 0;
456 for (i = 0; i < g->num_faces; i++) {
457 grid_face *f = g->faces[i];
458 bool keep = false;
459 for (k = 0; k < f->order; k++)
460 if (dsf_canonify(dsf, f->dots[k]->index) == j)
461 keep = true;
462 if (keep) {
463 faces[i] = 1;
464 for (k = 0; k < f->order; k++)
465 dots[f->dots[k]->index] = 1;
466 }
467 }
468
469 /*
470 * Compact the faces array, rewriting the faces' indices and
471 * freeing the unwanted ones.
472 */
473 for (i = newfaces = 0; i < g->num_faces; i++) {
474 grid_face *f = g->faces[i];
475 if (faces[i]) {
476 f->index = newfaces++;
477 g->faces[f->index] = f;
478 } else {
479 sfree(f->dots);
480 sfree(f);
481 }
482 }
483 g->num_faces = newfaces;
484
485 /*
486 * Compact the dots array, similarly.
487 */
488 for (i = newdots = 0; i < g->num_dots; i++) {
489 grid_dot *d = g->dots[i];
490 if (dots[i]) {
491 d->index = newdots++;
492 g->dots[d->index] = d;
493 } else {
494 sfree(d->edges);
495 sfree(d->faces);
496 sfree(d);
497 }
498 }
499 g->num_dots = newdots;
500
501 sfree(dotpairs);
502 dsf_free(dsf);
503 sfree(dots);
504 sfree(faces);
505}
506
507/* Input: grid has its dots and faces initialised:
508 * - dots have (optionally) x and y coordinates, but no edges or faces
509 * (pointers are NULL).
510 * - edges not initialised at all
511 * - faces initialised and know which dots they have (but no edges yet). The
512 * dots around each face are assumed to be clockwise.
513 *
514 * Output: grid is complete and valid with all relationships defined.
515 */
516static void grid_make_consistent(grid *g)
517{
518 int i;
519 tree234 *incomplete_edges;
520
521 grid_debug_basic(g);
522
523 /* ====== Stage 1 ======
524 * Generate edges
525 */
526
527 /* Iterate over faces, and over each face's dots, generating edges as we
528 * go. As we find each new edge, we can immediately fill in the edge's
529 * dots, but only one of the edge's faces. Later on in the iteration, we
530 * will find the same edge again (unless it's on the border), but we will
531 * know the other face.
532 * For efficiency, maintain a list of the incomplete edges, sorted by
533 * their dots. */
534 incomplete_edges = newtree234(grid_edge_bydots_cmpfn);
535 for (i = 0; i < g->num_faces; i++) {
536 grid_face *f = g->faces[i];
537 int j;
538 for (j = 0; j < f->order; j++) {
539 grid_edge e; /* fake edge for searching */
540 grid_edge *edge_found;
541 int j2 = j + 1;
542 if (j2 == f->order)
543 j2 = 0;
544 e.dot1 = f->dots[j];
545 e.dot2 = f->dots[j2];
546 /* Use del234 instead of find234, because we always want to
547 * remove the edge if found */
548 edge_found = del234(incomplete_edges, &e);
549 if (edge_found) {
550 /* This edge already added, so fill out missing face.
551 * Edge is already removed from incomplete_edges. */
552 edge_found->face2 = f;
553 } else {
554 grid_edge *new_edge = snew(grid_edge);
555 new_edge->dot1 = e.dot1;
556 new_edge->dot2 = e.dot2;
557 new_edge->face1 = f;
558 new_edge->face2 = NULL; /* potentially infinite face */
559 add234(incomplete_edges, new_edge);
560
561 /* And add it to g->edges. */
562 if (g->num_edges >= g->size_edges) {
563 int increment = g->num_edges / 4 + 128;
564 g->size_edges = (increment < INT_MAX - g->num_edges ?
565 g->num_edges + increment : INT_MAX);
566 g->edges = sresize(g->edges, g->size_edges, grid_edge *);
567 }
568 assert(g->num_edges < INT_MAX);
569 new_edge->index = g->num_edges++;
570 g->edges[new_edge->index] = new_edge;
571 }
572 }
573 }
574 freetree234(incomplete_edges);
575
576 /* ====== Stage 2 ======
577 * For each face, build its edge list.
578 */
579
580 /* Allocate space for each edge list. Can do this, because each face's
581 * edge-list is the same size as its dot-list. */
582 for (i = 0; i < g->num_faces; i++) {
583 grid_face *f = g->faces[i];
584 int j;
585 f->edges = snewn(f->order, grid_edge*);
586 /* Preload with NULLs, to help detect potential bugs. */
587 for (j = 0; j < f->order; j++)
588 f->edges[j] = NULL;
589 }
590
591 /* Iterate over each edge, and over both its faces. Add this edge to
592 * the face's edge-list, after finding where it should go in the
593 * sequence. */
594 for (i = 0; i < g->num_edges; i++) {
595 grid_edge *e = g->edges[i];
596 int j;
597 for (j = 0; j < 2; j++) {
598 grid_face *f = j ? e->face2 : e->face1;
599 int k, k2;
600 if (f == NULL) continue;
601 /* Find one of the dots around the face */
602 for (k = 0; k < f->order; k++) {
603 if (f->dots[k] == e->dot1)
604 break; /* found dot1 */
605 }
606 assert(k != f->order); /* Must find the dot around this face */
607
608 /* Labelling scheme: as we walk clockwise around the face,
609 * starting at dot0 (f->dots[0]), we hit:
610 * (dot0), edge0, dot1, edge1, dot2,...
611 *
612 * 0
613 * 0-----1
614 * |
615 * |1
616 * |
617 * 3-----2
618 * 2
619 *
620 * Therefore, edgeK joins dotK and dot{K+1}
621 */
622
623 /* Around this face, either the next dot or the previous dot
624 * must be e->dot2. Otherwise the edge is wrong. */
625 k2 = k + 1;
626 if (k2 == f->order)
627 k2 = 0;
628 if (f->dots[k2] == e->dot2) {
629 /* dot1(k) and dot2(k2) go clockwise around this face, so add
630 * this edge at position k (see diagram). */
631 assert(f->edges[k] == NULL);
632 f->edges[k] = e;
633 continue;
634 }
635 /* Try previous dot */
636 k2 = k - 1;
637 if (k2 == -1)
638 k2 = f->order - 1;
639 if (f->dots[k2] == e->dot2) {
640 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
641 assert(f->edges[k2] == NULL);
642 f->edges[k2] = e;
643 continue;
644 }
645 assert(!"Grid broken: bad edge-face relationship");
646 }
647 }
648
649 /* ====== Stage 3 ======
650 * For each dot, build its edge-list and face-list.
651 */
652
653 /* We don't know how many edges/faces go around each dot, so we can't
654 * allocate the right space for these lists. Pre-compute the sizes by
655 * iterating over each edge and recording a tally against each dot. */
656 for (i = 0; i < g->num_dots; i++) {
657 g->dots[i]->order = 0;
658 }
659 for (i = 0; i < g->num_edges; i++) {
660 grid_edge *e = g->edges[i];
661 ++(e->dot1->order);
662 ++(e->dot2->order);
663 }
664 /* Now we have the sizes, pre-allocate the edge and face lists. */
665 for (i = 0; i < g->num_dots; i++) {
666 grid_dot *d = g->dots[i];
667 int j;
668 assert(d->order >= 2); /* sanity check */
669 d->edges = snewn(d->order, grid_edge*);
670 d->faces = snewn(d->order, grid_face*);
671 for (j = 0; j < d->order; j++) {
672 d->edges[j] = NULL;
673 d->faces[j] = NULL;
674 }
675 }
676 /* For each dot, need to find a face that touches it, so we can seed
677 * the edge-face-edge-face process around each dot. */
678 for (i = 0; i < g->num_faces; i++) {
679 grid_face *f = g->faces[i];
680 int j;
681 for (j = 0; j < f->order; j++) {
682 grid_dot *d = f->dots[j];
683 d->faces[0] = f;
684 }
685 }
686 /* Each dot now has a face in its first slot. Generate the remaining
687 * faces and edges around the dot, by searching both clockwise and
688 * anticlockwise from the first face. Need to do both directions,
689 * because of the possibility of hitting the infinite face, which
690 * blocks progress. But there's only one such face, so we will
691 * succeed in finding every edge and face this way. */
692 for (i = 0; i < g->num_dots; i++) {
693 grid_dot *d = g->dots[i];
694 int current_face1 = 0; /* ascends clockwise */
695 int current_face2 = 0; /* descends anticlockwise */
696
697 /* Labelling scheme: as we walk clockwise around the dot, starting
698 * at face0 (d->faces[0]), we hit:
699 * (face0), edge0, face1, edge1, face2,...
700 *
701 * 0
702 * |
703 * 0 | 1
704 * |
705 * -----d-----1
706 * |
707 * | 2
708 * |
709 * 2
710 *
711 * So, for example, face1 should be joined to edge0 and edge1,
712 * and those edges should appear in an anticlockwise sense around
713 * that face (see diagram). */
714
715 /* clockwise search */
716 while (true) {
717 grid_face *f = d->faces[current_face1];
718 grid_edge *e;
719 int j;
720 assert(f != NULL);
721 /* find dot around this face */
722 for (j = 0; j < f->order; j++) {
723 if (f->dots[j] == d)
724 break;
725 }
726 assert(j != f->order); /* must find dot */
727
728 /* Around f, required edge is anticlockwise from the dot. See
729 * the other labelling scheme higher up, for why we subtract 1
730 * from j. */
731 j--;
732 if (j == -1)
733 j = f->order - 1;
734 e = f->edges[j];
735 d->edges[current_face1] = e; /* set edge */
736 current_face1++;
737 if (current_face1 == d->order)
738 break;
739 else {
740 /* set face */
741 d->faces[current_face1] =
742 (e->face1 == f) ? e->face2 : e->face1;
743 if (d->faces[current_face1] == NULL)
744 break; /* cannot progress beyond infinite face */
745 }
746 }
747 /* If the clockwise search made it all the way round, don't need to
748 * bother with the anticlockwise search. */
749 if (current_face1 == d->order)
750 continue; /* this dot is complete, move on to next dot */
751
752 /* anticlockwise search */
753 while (true) {
754 grid_face *f = d->faces[current_face2];
755 grid_edge *e;
756 int j;
757 assert(f != NULL);
758 /* find dot around this face */
759 for (j = 0; j < f->order; j++) {
760 if (f->dots[j] == d)
761 break;
762 }
763 assert(j != f->order); /* must find dot */
764
765 /* Around f, required edge is clockwise from the dot. */
766 e = f->edges[j];
767
768 current_face2--;
769 if (current_face2 == -1)
770 current_face2 = d->order - 1;
771 d->edges[current_face2] = e; /* set edge */
772
773 /* set face */
774 if (current_face2 == current_face1)
775 break;
776 d->faces[current_face2] =
777 (e->face1 == f) ? e->face2 : e->face1;
778 /* There's only 1 infinite face, so we must get all the way
779 * to current_face1 before we hit it. */
780 assert(d->faces[current_face2]);
781 }
782 }
783
784 /* ====== Stage 4 ======
785 * Compute other grid settings
786 */
787
788 /* Bounding rectangle */
789 for (i = 0; i < g->num_dots; i++) {
790 grid_dot *d = g->dots[i];
791 if (i == 0) {
792 g->lowest_x = g->highest_x = d->x;
793 g->lowest_y = g->highest_y = d->y;
794 } else {
795 g->lowest_x = min(g->lowest_x, d->x);
796 g->highest_x = max(g->highest_x, d->x);
797 g->lowest_y = min(g->lowest_y, d->y);
798 g->highest_y = max(g->highest_y, d->y);
799 }
800 }
801
802 grid_debug_derived(g);
803}
804
805/* Helpers for making grid-generation easier. These functions are only
806 * intended for use during grid generation. */
807
808/* Comparison function for the (tree234) sorted dot list */
809static int grid_point_cmp_fn(void *v1, void *v2)
810{
811 grid_dot *p1 = v1;
812 grid_dot *p2 = v2;
813 if (p1->y != p2->y)
814 return p2->y - p1->y;
815 else
816 return p2->x - p1->x;
817}
818/* Add a new face to the grid, with its dot list allocated. */
819static void grid_face_add_new(grid *g, int face_size)
820{
821 int i;
822 grid_face *new_face = snew(grid_face);
823 assert(g->num_faces < INT_MAX);
824 if (g->num_faces >= g->size_faces) {
825 int increment = g->num_faces / 4 + 128;
826 g->size_faces = (increment < INT_MAX - g->num_faces ?
827 g->num_faces + increment : INT_MAX);
828 g->faces = sresize(g->faces, g->size_faces, grid_face *);
829 }
830 new_face->index = g->num_faces++;
831 g->faces[new_face->index] = new_face;
832
833 new_face->order = face_size;
834 new_face->dots = snewn(face_size, grid_dot*);
835 for (i = 0; i < face_size; i++)
836 new_face->dots[i] = NULL;
837 new_face->edges = NULL;
838 new_face->has_incentre = false;
839}
840static grid_dot *grid_dot_add_new(grid *g, int x, int y)
841{
842 grid_dot *new_dot = snew(grid_dot);
843 if (g->num_dots >= g->size_dots) {
844 int increment = g->num_dots / 4 + 128;
845 g->size_dots = (increment < INT_MAX - g->num_dots ?
846 g->num_dots + increment : INT_MAX);
847 g->dots = sresize(g->dots, g->size_dots, grid_dot *);
848 }
849 assert(g->num_dots < INT_MAX);
850 new_dot->index = g->num_dots++;
851 g->dots[new_dot->index] = new_dot;
852
853 new_dot->order = 0;
854 new_dot->edges = NULL;
855 new_dot->faces = NULL;
856 new_dot->x = x;
857 new_dot->y = y;
858
859 return new_dot;
860}
861/* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
862 * in the dot_list, or add a new dot to the grid (and the dot_list) and
863 * return that. */
864static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y)
865{
866 grid_dot test, *ret;
867
868 test.order = 0;
869 test.edges = NULL;
870 test.faces = NULL;
871 test.x = x;
872 test.y = y;
873 ret = find234(dot_list, &test, NULL);
874 if (ret)
875 return ret;
876
877 ret = grid_dot_add_new(g, x, y);
878 add234(dot_list, ret);
879 return ret;
880}
881
882/* Sets the last face of the grid to include this dot, at this position
883 * around the face. Assumes num_faces is at least 1 (a new face has
884 * previously been added, with the required number of dots allocated) */
885static void grid_face_set_dot(grid *g, grid_dot *d, int position)
886{
887 grid_face *last_face = g->faces[g->num_faces - 1];
888 last_face->dots[position] = d;
889}
890
891/*
892 * Helper routines for grid_find_incentre.
893 */
894static bool solve_2x2_matrix(double mx[4], double vin[2], double vout[2])
895{
896 double inv[4];
897 double det;
898 det = (mx[0]*mx[3] - mx[1]*mx[2]);
899 if (det == 0)
900 return false;
901
902 inv[0] = mx[3] / det;
903 inv[1] = -mx[1] / det;
904 inv[2] = -mx[2] / det;
905 inv[3] = mx[0] / det;
906
907 vout[0] = inv[0]*vin[0] + inv[1]*vin[1];
908 vout[1] = inv[2]*vin[0] + inv[3]*vin[1];
909
910 return true;
911}
912static bool solve_3x3_matrix(double mx[9], double vin[3], double vout[3])
913{
914 double inv[9];
915 double det;
916
917 det = (mx[0]*mx[4]*mx[8] + mx[1]*mx[5]*mx[6] + mx[2]*mx[3]*mx[7] -
918 mx[0]*mx[5]*mx[7] - mx[1]*mx[3]*mx[8] - mx[2]*mx[4]*mx[6]);
919 if (det == 0)
920 return false;
921
922 inv[0] = (mx[4]*mx[8] - mx[5]*mx[7]) / det;
923 inv[1] = (mx[2]*mx[7] - mx[1]*mx[8]) / det;
924 inv[2] = (mx[1]*mx[5] - mx[2]*mx[4]) / det;
925 inv[3] = (mx[5]*mx[6] - mx[3]*mx[8]) / det;
926 inv[4] = (mx[0]*mx[8] - mx[2]*mx[6]) / det;
927 inv[5] = (mx[2]*mx[3] - mx[0]*mx[5]) / det;
928 inv[6] = (mx[3]*mx[7] - mx[4]*mx[6]) / det;
929 inv[7] = (mx[1]*mx[6] - mx[0]*mx[7]) / det;
930 inv[8] = (mx[0]*mx[4] - mx[1]*mx[3]) / det;
931
932 vout[0] = inv[0]*vin[0] + inv[1]*vin[1] + inv[2]*vin[2];
933 vout[1] = inv[3]*vin[0] + inv[4]*vin[1] + inv[5]*vin[2];
934 vout[2] = inv[6]*vin[0] + inv[7]*vin[1] + inv[8]*vin[2];
935
936 return true;
937}
938
939void grid_find_incentre(grid_face *f)
940{
941 double xbest, ybest, bestdist;
942 int i, j, k, m;
943 grid_dot *edgedot1[3], *edgedot2[3];
944 grid_dot *dots[3];
945 int nedges, ndots;
946
947 if (f->has_incentre)
948 return;
949
950 /*
951 * Find the point in the polygon with the maximum distance to any
952 * edge or corner.
953 *
954 * Such a point must exist which is in contact with at least three
955 * edges and/or vertices. (Proof: if it's only in contact with two
956 * edges and/or vertices, it can't even be at a _local_ maximum -
957 * any such circle can always be expanded in some direction.) So
958 * we iterate through all 3-subsets of the combined set of edges
959 * and vertices; for each subset we generate one or two candidate
960 * points that might be the incentre, and then we vet each one to
961 * see if it's inside the polygon and what its maximum radius is.
962 *
963 * (There's one case which this algorithm will get noticeably
964 * wrong, and that's when a continuum of equally good answers
965 * exists due to parallel edges. Consider a long thin rectangle,
966 * for instance, or a parallelogram. This algorithm will pick a
967 * point near one end, and choose the end arbitrarily; obviously a
968 * nicer point to choose would be in the centre. To fix this I
969 * would have to introduce a special-case system which detected
970 * parallel edges in advance, set aside all candidate points
971 * generated using both edges in a parallel pair, and generated
972 * some additional candidate points half way between them. Also,
973 * of course, I'd have to cope with rounding error making such a
974 * point look worse than one of its endpoints. So I haven't done
975 * this for the moment, and will cross it if necessary when I come
976 * to it.)
977 *
978 * We don't actually iterate literally over _edges_, in the sense
979 * of grid_edge structures. Instead, we fill in edgedot1[] and
980 * edgedot2[] with a pair of dots adjacent in the face's list of
981 * vertices. This ensures that we get the edges in consistent
982 * orientation, which we could not do from the grid structure
983 * alone. (A moment's consideration of an order-3 vertex should
984 * make it clear that if a notional arrow was written on each
985 * edge, _at least one_ of the three faces bordering that vertex
986 * would have to have the two arrows tip-to-tip or tail-to-tail
987 * rather than tip-to-tail.)
988 */
989 nedges = ndots = 0;
990 bestdist = 0;
991 xbest = ybest = 0;
992
993 for (i = 0; i+2 < 2*f->order; i++) {
994 if (i < f->order) {
995 edgedot1[nedges] = f->dots[i];
996 edgedot2[nedges++] = f->dots[(i+1)%f->order];
997 } else
998 dots[ndots++] = f->dots[i - f->order];
999
1000 for (j = i+1; j+1 < 2*f->order; j++) {
1001 if (j < f->order) {
1002 edgedot1[nedges] = f->dots[j];
1003 edgedot2[nedges++] = f->dots[(j+1)%f->order];
1004 } else
1005 dots[ndots++] = f->dots[j - f->order];
1006
1007 for (k = j+1; k < 2*f->order; k++) {
1008 double cx[2], cy[2]; /* candidate positions */
1009 int cn = 0; /* number of candidates */
1010
1011 if (k < f->order) {
1012 edgedot1[nedges] = f->dots[k];
1013 edgedot2[nedges++] = f->dots[(k+1)%f->order];
1014 } else
1015 dots[ndots++] = f->dots[k - f->order];
1016
1017 /*
1018 * Find a point, or pair of points, equidistant from
1019 * all the specified edges and/or vertices.
1020 */
1021 if (nedges == 3) {
1022 /*
1023 * Three edges. This is a linear matrix equation:
1024 * each row of the matrix represents the fact that
1025 * the point (x,y) we seek is at distance r from
1026 * that edge, and we solve three of those
1027 * simultaneously to obtain x,y,r. (We ignore r.)
1028 */
1029 double matrix[9], vector[3], vector2[3];
1030 int m;
1031
1032 for (m = 0; m < 3; m++) {
1033 int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x;
1034 int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y;
1035 int dx = x2-x1, dy = y2-y1;
1036
1037 /*
1038 * ((x,y) - (x1,y1)) . (dy,-dx) = r |(dx,dy)|
1039 *
1040 * => x dy - y dx - r |(dx,dy)| = (x1 dy - y1 dx)
1041 */
1042 matrix[3*m+0] = dy;
1043 matrix[3*m+1] = -dx;
1044 matrix[3*m+2] = -sqrt((double)dx*dx+(double)dy*dy);
1045 vector[m] = (double)x1*dy - (double)y1*dx;
1046 }
1047
1048 if (solve_3x3_matrix(matrix, vector, vector2)) {
1049 cx[cn] = vector2[0];
1050 cy[cn] = vector2[1];
1051 cn++;
1052 }
1053 } else if (nedges == 2) {
1054 /*
1055 * Two edges and a dot. This will end up in a
1056 * quadratic equation.
1057 *
1058 * First, look at the two edges. Having our point
1059 * be some distance r from both of them gives rise
1060 * to a pair of linear equations in x,y,r of the
1061 * form
1062 *
1063 * (x-x1) dy - (y-y1) dx = r sqrt(dx^2+dy^2)
1064 *
1065 * We eliminate r between those equations to give
1066 * us a single linear equation in x,y describing
1067 * the locus of points equidistant from both lines
1068 * - i.e. the angle bisector.
1069 *
1070 * We then choose one of x,y to be a parameter t,
1071 * and derive linear formulae for x,y,r in terms
1072 * of t. This enables us to write down the
1073 * circular equation (x-xd)^2+(y-yd)^2=r^2 as a
1074 * quadratic in t; solving that and substituting
1075 * in for x,y gives us two candidate points.
1076 */
1077 double eqs[2][4]; /* a,b,c,d : ax+by+cr=d */
1078 double eq[3]; /* a,b,c: ax+by=c */
1079 double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */
1080 double q[3]; /* a,b,c: at^2+bt+c=0 */
1081 double disc;
1082
1083 /* Find equations of the two input lines. */
1084 for (m = 0; m < 2; m++) {
1085 int x1 = edgedot1[m]->x, x2 = edgedot2[m]->x;
1086 int y1 = edgedot1[m]->y, y2 = edgedot2[m]->y;
1087 int dx = x2-x1, dy = y2-y1;
1088
1089 eqs[m][0] = dy;
1090 eqs[m][1] = -dx;
1091 eqs[m][2] = -sqrt(dx*dx+dy*dy);
1092 eqs[m][3] = x1*dy - y1*dx;
1093 }
1094
1095 /* Derive the angle bisector by eliminating r. */
1096 eq[0] = eqs[0][0]*eqs[1][2] - eqs[1][0]*eqs[0][2];
1097 eq[1] = eqs[0][1]*eqs[1][2] - eqs[1][1]*eqs[0][2];
1098 eq[2] = eqs[0][3]*eqs[1][2] - eqs[1][3]*eqs[0][2];
1099
1100 /* Parametrise x and y in terms of some t. */
1101 if (fabs(eq[0]) < fabs(eq[1])) {
1102 /* Parameter is x. */
1103 xt[0] = 1; xt[1] = 0;
1104 yt[0] = -eq[0]/eq[1]; yt[1] = eq[2]/eq[1];
1105 } else {
1106 /* Parameter is y. */
1107 yt[0] = 1; yt[1] = 0;
1108 xt[0] = -eq[1]/eq[0]; xt[1] = eq[2]/eq[0];
1109 }
1110
1111 /* Find a linear representation of r using eqs[0]. */
1112 rt[0] = -(eqs[0][0]*xt[0] + eqs[0][1]*yt[0])/eqs[0][2];
1113 rt[1] = (eqs[0][3] - eqs[0][0]*xt[1] -
1114 eqs[0][1]*yt[1])/eqs[0][2];
1115
1116 /* Construct the quadratic equation. */
1117 q[0] = -rt[0]*rt[0];
1118 q[1] = -2*rt[0]*rt[1];
1119 q[2] = -rt[1]*rt[1];
1120 q[0] += xt[0]*xt[0];
1121 q[1] += 2*xt[0]*(xt[1]-dots[0]->x);
1122 q[2] += (xt[1]-dots[0]->x)*(xt[1]-dots[0]->x);
1123 q[0] += yt[0]*yt[0];
1124 q[1] += 2*yt[0]*(yt[1]-dots[0]->y);
1125 q[2] += (yt[1]-dots[0]->y)*(yt[1]-dots[0]->y);
1126
1127 /* And solve it. */
1128 disc = q[1]*q[1] - 4*q[0]*q[2];
1129 if (disc >= 0) {
1130 double t;
1131
1132 disc = sqrt(disc);
1133
1134 t = (-q[1] + disc) / (2*q[0]);
1135 cx[cn] = xt[0]*t + xt[1];
1136 cy[cn] = yt[0]*t + yt[1];
1137 cn++;
1138
1139 t = (-q[1] - disc) / (2*q[0]);
1140 cx[cn] = xt[0]*t + xt[1];
1141 cy[cn] = yt[0]*t + yt[1];
1142 cn++;
1143 }
1144 } else if (nedges == 1) {
1145 /*
1146 * Two dots and an edge. This one's another
1147 * quadratic equation.
1148 *
1149 * The point we want must lie on the perpendicular
1150 * bisector of the two dots; that much is obvious.
1151 * So we can construct a parametrisation of that
1152 * bisecting line, giving linear formulae for x,y
1153 * in terms of t. We can also express the distance
1154 * from the edge as such a linear formula.
1155 *
1156 * Then we set that equal to the radius of the
1157 * circle passing through the two points, which is
1158 * a Pythagoras exercise; that gives rise to a
1159 * quadratic in t, which we solve.
1160 */
1161 double xt[2], yt[2], rt[2]; /* a,b: {x,y,r}=at+b */
1162 double q[3]; /* a,b,c: at^2+bt+c=0 */
1163 double disc;
1164 double halfsep;
1165
1166 /* Find parametric formulae for x,y. */
1167 {
1168 int x1 = dots[0]->x, x2 = dots[1]->x;
1169 int y1 = dots[0]->y, y2 = dots[1]->y;
1170 int dx = x2-x1, dy = y2-y1;
1171 double d = sqrt((double)dx*dx + (double)dy*dy);
1172
1173 xt[1] = (x1+x2)/2.0;
1174 yt[1] = (y1+y2)/2.0;
1175 /* It's convenient if we have t at standard scale. */
1176 xt[0] = -dy/d;
1177 yt[0] = dx/d;
1178
1179 /* Also note down half the separation between
1180 * the dots, for use in computing the circle radius. */
1181 halfsep = 0.5*d;
1182 }
1183
1184 /* Find a parametric formula for r. */
1185 {
1186 int x1 = edgedot1[0]->x, x2 = edgedot2[0]->x;
1187 int y1 = edgedot1[0]->y, y2 = edgedot2[0]->y;
1188 int dx = x2-x1, dy = y2-y1;
1189 double d = sqrt((double)dx*dx + (double)dy*dy);
1190 rt[0] = (xt[0]*dy - yt[0]*dx) / d;
1191 rt[1] = ((xt[1]-x1)*dy - (yt[1]-y1)*dx) / d;
1192 }
1193
1194 /* Construct the quadratic equation. */
1195 q[0] = rt[0]*rt[0];
1196 q[1] = 2*rt[0]*rt[1];
1197 q[2] = rt[1]*rt[1];
1198 q[0] -= 1;
1199 q[2] -= halfsep*halfsep;
1200
1201 /* And solve it. */
1202 disc = q[1]*q[1] - 4*q[0]*q[2];
1203 if (disc >= 0) {
1204 double t;
1205
1206 disc = sqrt(disc);
1207
1208 t = (-q[1] + disc) / (2*q[0]);
1209 cx[cn] = xt[0]*t + xt[1];
1210 cy[cn] = yt[0]*t + yt[1];
1211 cn++;
1212
1213 t = (-q[1] - disc) / (2*q[0]);
1214 cx[cn] = xt[0]*t + xt[1];
1215 cy[cn] = yt[0]*t + yt[1];
1216 cn++;
1217 }
1218 } else if (nedges == 0) {
1219 /*
1220 * Three dots. This is another linear matrix
1221 * equation, this time with each row of the matrix
1222 * representing the perpendicular bisector between
1223 * two of the points. Of course we only need two
1224 * such lines to find their intersection, so we
1225 * need only solve a 2x2 matrix equation.
1226 */
1227
1228 double matrix[4], vector[2], vector2[2];
1229 int m;
1230
1231 for (m = 0; m < 2; m++) {
1232 int x1 = dots[m]->x, x2 = dots[m+1]->x;
1233 int y1 = dots[m]->y, y2 = dots[m+1]->y;
1234 int dx = x2-x1, dy = y2-y1;
1235
1236 /*
1237 * ((x,y) - (x1,y1)) . (dx,dy) = 1/2 |(dx,dy)|^2
1238 *
1239 * => 2x dx + 2y dy = dx^2+dy^2 + (2 x1 dx + 2 y1 dy)
1240 */
1241 matrix[2*m+0] = 2*dx;
1242 matrix[2*m+1] = 2*dy;
1243 vector[m] = ((double)dx*dx + (double)dy*dy +
1244 2.0*x1*dx + 2.0*y1*dy);
1245 }
1246
1247 if (solve_2x2_matrix(matrix, vector, vector2)) {
1248 cx[cn] = vector2[0];
1249 cy[cn] = vector2[1];
1250 cn++;
1251 }
1252 }
1253
1254 /*
1255 * Now go through our candidate points and see if any
1256 * of them are better than what we've got so far.
1257 */
1258 for (m = 0; m < cn; m++) {
1259 double x = cx[m], y = cy[m];
1260
1261 /*
1262 * First, disqualify the point if it's not inside
1263 * the polygon, which we work out by counting the
1264 * edges to the right of the point. (For
1265 * tiebreaking purposes when edges start or end on
1266 * our y-coordinate or go right through it, we
1267 * consider our point to be offset by a small
1268 * _positive_ epsilon in both the x- and
1269 * y-direction.)
1270 */
1271 int e;
1272 bool in = false;
1273 for (e = 0; e < f->order; e++) {
1274 int xs = f->edges[e]->dot1->x;
1275 int xe = f->edges[e]->dot2->x;
1276 int ys = f->edges[e]->dot1->y;
1277 int ye = f->edges[e]->dot2->y;
1278 if ((y >= ys && y < ye) || (y >= ye && y < ys)) {
1279 /*
1280 * The line goes past our y-position. Now we need
1281 * to know if its x-coordinate when it does so is
1282 * to our right.
1283 *
1284 * The x-coordinate in question is mathematically
1285 * (y - ys) * (xe - xs) / (ye - ys), and we want
1286 * to know whether (x - xs) >= that. Of course we
1287 * avoid the division, so we can work in integers;
1288 * to do this we must multiply both sides of the
1289 * inequality by ye - ys, which means we must
1290 * first check that's not negative.
1291 */
1292 int num = xe - xs, denom = ye - ys;
1293 if (denom < 0) {
1294 num = -num;
1295 denom = -denom;
1296 }
1297 if ((x - xs) * denom >= (y - ys) * num)
1298 in = !in;
1299 }
1300 }
1301
1302 if (in) {
1303#ifdef HUGE_VAL
1304 double mindist = HUGE_VAL;
1305#else
1306#ifdef DBL_MAX
1307 double mindist = DBL_MAX;
1308#else
1309#error No way to get maximum floating-point number.
1310#endif
1311#endif
1312 int e, d;
1313
1314 /*
1315 * This point is inside the polygon, so now we check
1316 * its minimum distance to every edge and corner.
1317 * First the corners ...
1318 */
1319 for (d = 0; d < f->order; d++) {
1320 int xp = f->dots[d]->x;
1321 int yp = f->dots[d]->y;
1322 double dx = x - xp, dy = y - yp;
1323 double dist = dx*dx + dy*dy;
1324 if (mindist > dist)
1325 mindist = dist;
1326 }
1327
1328 /*
1329 * ... and now also check the perpendicular distance
1330 * to every edge, if the perpendicular lies between
1331 * the edge's endpoints.
1332 */
1333 for (e = 0; e < f->order; e++) {
1334 int xs = f->edges[e]->dot1->x;
1335 int xe = f->edges[e]->dot2->x;
1336 int ys = f->edges[e]->dot1->y;
1337 int ye = f->edges[e]->dot2->y;
1338
1339 /*
1340 * If s and e are our endpoints, and p our
1341 * candidate circle centre, the foot of a
1342 * perpendicular from p to the line se lies
1343 * between s and e if and only if (p-s).(e-s) lies
1344 * strictly between 0 and (e-s).(e-s).
1345 */
1346 int edx = xe - xs, edy = ye - ys;
1347 double pdx = x - xs, pdy = y - ys;
1348 double pde = pdx * edx + pdy * edy;
1349 long ede = (long)edx * edx + (long)edy * edy;
1350 if (0 < pde && pde < ede) {
1351 /*
1352 * Yes, the nearest point on this edge is
1353 * closer than either endpoint, so we must
1354 * take it into account by measuring the
1355 * perpendicular distance to the edge and
1356 * checking its square against mindist.
1357 */
1358
1359 double pdre = pdx * edy - pdy * edx;
1360 double sqlen = pdre * pdre / ede;
1361
1362 if (mindist > sqlen)
1363 mindist = sqlen;
1364 }
1365 }
1366
1367 /*
1368 * Right. Now we know the biggest circle around this
1369 * point, so we can check it against bestdist.
1370 */
1371 if (bestdist < mindist) {
1372 bestdist = mindist;
1373 xbest = x;
1374 ybest = y;
1375 }
1376 }
1377 }
1378
1379 if (k < f->order)
1380 nedges--;
1381 else
1382 ndots--;
1383 }
1384 if (j < f->order)
1385 nedges--;
1386 else
1387 ndots--;
1388 }
1389 if (i < f->order)
1390 nedges--;
1391 else
1392 ndots--;
1393 }
1394
1395 assert(bestdist > 0);
1396
1397 f->has_incentre = true;
1398 f->ix = xbest + 0.5; /* round to nearest */
1399 f->iy = ybest + 0.5;
1400}
1401
1402/* ------ Generate various types of grid ------ */
1403
1404/* General method is to generate faces, by calculating their dot coordinates.
1405 * As new faces are added, we keep track of all the dots so we can tell when
1406 * a new face reuses an existing dot. For example, two squares touching at an
1407 * edge would generate six unique dots: four dots from the first face, then
1408 * two additional dots for the second face, because we detect the other two
1409 * dots have already been taken up. This list is stored in a tree234
1410 * called "points". No extra memory-allocation needed here - we store the
1411 * actual grid_dot* pointers, which all point into the g->dots list.
1412 * For this reason, we have to calculate coordinates in such a way as to
1413 * eliminate any rounding errors, so we can detect when a dot on one
1414 * face precisely lands on a dot of a different face. No floating-point
1415 * arithmetic here!
1416 */
1417
1418#define SQUARE_TILESIZE 20
1419
1420static const char *grid_validate_params_square(int width, int height)
1421{
1422 if (width > INT_MAX / SQUARE_TILESIZE || /* xextent */
1423 height > INT_MAX / SQUARE_TILESIZE || /* yextent */
1424 width + 1 > INT_MAX / (height + 1)) /* max_dots */
1425 return "Grid size must not be unreasonably large";
1426 return NULL;
1427}
1428
1429static void grid_size_square(int width, int height,
1430 int *tilesize, int *xextent, int *yextent)
1431{
1432 int a = SQUARE_TILESIZE;
1433
1434 *tilesize = a;
1435 *xextent = width * a;
1436 *yextent = height * a;
1437}
1438
1439static grid *grid_new_square(int width, int height, const char *desc)
1440{
1441 int x, y;
1442 /* Side length */
1443 int a = SQUARE_TILESIZE;
1444
1445 tree234 *points;
1446
1447 grid *g = grid_empty();
1448 g->tilesize = a;
1449
1450 points = newtree234(grid_point_cmp_fn);
1451
1452 /* generate square faces */
1453 for (y = 0; y < height; y++) {
1454 for (x = 0; x < width; x++) {
1455 grid_dot *d;
1456 /* face position */
1457 int px = a * x;
1458 int py = a * y;
1459
1460 grid_face_add_new(g, 4);
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 + a, py);
1464 grid_face_set_dot(g, d, 1);
1465 d = grid_get_dot(g, points, px + a, py + a);
1466 grid_face_set_dot(g, d, 2);
1467 d = grid_get_dot(g, points, px, py + a);
1468 grid_face_set_dot(g, d, 3);
1469 }
1470 }
1471
1472 freetree234(points);
1473
1474 grid_make_consistent(g);
1475 return g;
1476}
1477
1478#define HONEY_TILESIZE 45
1479/* Vector for side of hexagon - ratio is close to sqrt(3) */
1480#define HONEY_A 15
1481#define HONEY_B 26
1482
1483static const char *grid_validate_params_honeycomb(int width, int height)
1484{
1485 int a = HONEY_A;
1486 int b = HONEY_B;
1487
1488 if (width - 1 > (INT_MAX - 4*a) / (3 * a) || /* xextent */
1489 height - 1 > (INT_MAX - 3*b) / (2 * b) || /* yextent */
1490 width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */
1491 return "Grid size must not be unreasonably large";
1492 return NULL;
1493}
1494
1495static void grid_size_honeycomb(int width, int height,
1496 int *tilesize, int *xextent, int *yextent)
1497{
1498 int a = HONEY_A;
1499 int b = HONEY_B;
1500
1501 *tilesize = HONEY_TILESIZE;
1502 *xextent = (3 * a * (width-1)) + 4*a;
1503 *yextent = (2 * b * (height-1)) + 3*b;
1504}
1505
1506static grid *grid_new_honeycomb(int width, int height, const char *desc)
1507{
1508 int x, y;
1509 int a = HONEY_A;
1510 int b = HONEY_B;
1511
1512 tree234 *points;
1513
1514 grid *g = grid_empty();
1515 g->tilesize = HONEY_TILESIZE;
1516
1517 points = newtree234(grid_point_cmp_fn);
1518
1519 /* generate hexagonal faces */
1520 for (y = 0; y < height; y++) {
1521 for (x = 0; x < width; x++) {
1522 grid_dot *d;
1523 /* face centre */
1524 int cx = 3 * a * x;
1525 int cy = 2 * b * y;
1526 if (x % 2)
1527 cy += b;
1528 grid_face_add_new(g, 6);
1529
1530 d = grid_get_dot(g, points, cx - a, cy - b);
1531 grid_face_set_dot(g, d, 0);
1532 d = grid_get_dot(g, points, cx + a, cy - b);
1533 grid_face_set_dot(g, d, 1);
1534 d = grid_get_dot(g, points, cx + 2*a, cy);
1535 grid_face_set_dot(g, d, 2);
1536 d = grid_get_dot(g, points, cx + a, cy + b);
1537 grid_face_set_dot(g, d, 3);
1538 d = grid_get_dot(g, points, cx - a, cy + b);
1539 grid_face_set_dot(g, d, 4);
1540 d = grid_get_dot(g, points, cx - 2*a, cy);
1541 grid_face_set_dot(g, d, 5);
1542 }
1543 }
1544
1545 freetree234(points);
1546
1547 grid_make_consistent(g);
1548 return g;
1549}
1550
1551#define TRIANGLE_TILESIZE 18
1552/* Vector for side of triangle - ratio is close to sqrt(3) */
1553#define TRIANGLE_VEC_X 15
1554#define TRIANGLE_VEC_Y 26
1555
1556static const char *grid_validate_params_triangular(int width, int height)
1557{
1558 int vec_x = TRIANGLE_VEC_X;
1559 int vec_y = TRIANGLE_VEC_Y;
1560
1561 if (width > INT_MAX / (2 * vec_x) - 1 || /* xextent */
1562 height > INT_MAX / vec_y || /* yextent */
1563 width + 1 > INT_MAX / 4 / (height + 1)) /* max_dots */
1564 return "Grid size must not be unreasonably large";
1565 return NULL;
1566}
1567
1568static void grid_size_triangular(int width, int height,
1569 int *tilesize, int *xextent, int *yextent)
1570{
1571 int vec_x = TRIANGLE_VEC_X;
1572 int vec_y = TRIANGLE_VEC_Y;
1573
1574 *tilesize = TRIANGLE_TILESIZE;
1575 *xextent = (width+1) * 2 * vec_x;
1576 *yextent = height * vec_y;
1577}
1578
1579static const char *grid_validate_desc_triangular(grid_type type, int width,
1580 int height, const char *desc)
1581{
1582 /*
1583 * Triangular grids: an absent description is valid (indicating
1584 * the old-style approach which had 'ears', i.e. triangles
1585 * connected to only one other face, at some grid corners), and so
1586 * is a description reading just "0" (indicating the new-style
1587 * approach in which those ears are trimmed off). Anything else is
1588 * illegal.
1589 */
1590
1591 if (!desc || !strcmp(desc, "0"))
1592 return NULL;
1593
1594 return "Unrecognised grid description.";
1595}
1596
1597/* Doesn't use the previous method of generation, it pre-dates it!
1598 * A triangular grid is just about simple enough to do by "brute force" */
1599static grid *grid_new_triangular(int width, int height, const char *desc)
1600{
1601 int x,y;
1602 int version = (desc == NULL ? -1 : atoi(desc));
1603
1604 /* Vector for side of triangle - ratio is close to sqrt(3) */
1605 int vec_x = TRIANGLE_VEC_X;
1606 int vec_y = TRIANGLE_VEC_Y;
1607
1608 int index;
1609
1610 /* convenient alias */
1611 int w = width + 1;
1612
1613 grid *g = grid_empty();
1614 g->tilesize = TRIANGLE_TILESIZE;
1615
1616 if (version == -1) {
1617 /*
1618 * Old-style triangular grid generation, preserved as-is for
1619 * backwards compatibility with old game ids, in which it's
1620 * just a little asymmetric and there are 'ears' (faces linked
1621 * to only one other face) at two grid corners.
1622 *
1623 * Example old-style game ids, which should still work, and in
1624 * which you should see the ears in the TL/BR corners on the
1625 * first one and in the TL/BL corners on the second:
1626 *
1627 * 5x5t1:2c2a1a2a201a1a1a1112a1a2b1211f0b21a2a2a0a
1628 * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e
1629 */
1630
1631 g->num_faces = g->size_faces = width * height * 2;
1632 g->num_dots = g->size_dots = (width + 1) * (height + 1);
1633 g->faces = snewn(g->size_faces, grid_face *);
1634 g->dots = snewn(g->size_dots, grid_dot *);
1635
1636 /* generate dots */
1637 index = 0;
1638 for (y = 0; y <= height; y++) {
1639 for (x = 0; x <= width; x++) {
1640 grid_dot *d = snew(grid_dot);
1641 d->index = index;
1642 g->dots[d->index] = d;
1643 /* odd rows are offset to the right */
1644 d->order = 0;
1645 d->edges = NULL;
1646 d->faces = NULL;
1647 d->x = x * 2 * vec_x + ((y % 2) ? vec_x : 0);
1648 d->y = y * vec_y;
1649 index++;
1650 }
1651 }
1652
1653 /* generate faces */
1654 index = 0;
1655 for (y = 0; y < height; y++) {
1656 for (x = 0; x < width; x++) {
1657 /* initialise two faces for this (x,y) */
1658 grid_face *f1 = snew(grid_face), *f2 = snew(grid_face);
1659 f1->index = index;
1660 f2->index = index + 1;
1661 g->faces[f1->index] = f1;
1662 g->faces[f2->index] = f2;
1663 f1->edges = NULL;
1664 f1->order = 3;
1665 f1->dots = snewn(f1->order, grid_dot*);
1666 f1->has_incentre = false;
1667 f2->edges = NULL;
1668 f2->order = 3;
1669 f2->dots = snewn(f2->order, grid_dot*);
1670 f2->has_incentre = false;
1671
1672 /* face descriptions depend on whether the row-number is
1673 * odd or even */
1674 if (y % 2) {
1675 f1->dots[0] = g->dots[y * w + x];
1676 f1->dots[1] = g->dots[(y + 1) * w + x + 1];
1677 f1->dots[2] = g->dots[(y + 1) * w + x];
1678 f2->dots[0] = g->dots[y * w + x];
1679 f2->dots[1] = g->dots[y * w + x + 1];
1680 f2->dots[2] = g->dots[(y + 1) * w + x + 1];
1681 } else {
1682 f1->dots[0] = g->dots[y * w + x];
1683 f1->dots[1] = g->dots[y * w + x + 1];
1684 f1->dots[2] = g->dots[(y + 1) * w + x];
1685 f2->dots[0] = g->dots[y * w + x + 1];
1686 f2->dots[1] = g->dots[(y + 1) * w + x + 1];
1687 f2->dots[2] = g->dots[(y + 1) * w + x];
1688 }
1689 index += 2;
1690 }
1691 }
1692 } else {
1693 /*
1694 * New-style approach, in which there are never any 'ears',
1695 * and if height is even then the grid is nicely 4-way
1696 * symmetric.
1697 *
1698 * Example new-style grids:
1699 *
1700 * 5x5t1:0_21120b11a1a01a1a00c1a0b211021c1h1a2a1a0a
1701 * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1
1702 */
1703 tree234 *points = newtree234(grid_point_cmp_fn);
1704
1705 for (y = 0; y < height; y++) {
1706 /*
1707 * Each row contains (width+1) triangles one way up, and
1708 * (width) triangles the other way up. Which way up is
1709 * which varies with parity of y. Also, the dots around
1710 * each face will flip direction with parity of y, so we
1711 * set up n1 and n2 to cope with that easily.
1712 */
1713 int y0, y1, n1, n2;
1714 y0 = y1 = y * vec_y;
1715 if (y % 2) {
1716 y1 += vec_y;
1717 n1 = 2; n2 = 1;
1718 } else {
1719 y0 += vec_y;
1720 n1 = 1; n2 = 2;
1721 }
1722
1723 for (x = 0; x <= width; x++) {
1724 int x0 = 2*x * vec_x, x1 = x0 + vec_x, x2 = x1 + vec_x;
1725
1726 /*
1727 * If the grid has odd height, then we skip the first
1728 * and last triangles on this row, otherwise they'll
1729 * end up as ears.
1730 */
1731 if (height % 2 == 1 && y == height-1 && (x == 0 || x == width))
1732 continue;
1733
1734 grid_face_add_new(g, 3);
1735 grid_face_set_dot(g, grid_get_dot(g, points, x0, y0), 0);
1736 grid_face_set_dot(g, grid_get_dot(g, points, x1, y1), n1);
1737 grid_face_set_dot(g, grid_get_dot(g, points, x2, y0), n2);
1738 }
1739
1740 for (x = 0; x < width; x++) {
1741 int x0 = (2*x+1) * vec_x, x1 = x0 + vec_x, x2 = x1 + vec_x;
1742
1743 grid_face_add_new(g, 3);
1744 grid_face_set_dot(g, grid_get_dot(g, points, x0, y1), 0);
1745 grid_face_set_dot(g, grid_get_dot(g, points, x1, y0), n2);
1746 grid_face_set_dot(g, grid_get_dot(g, points, x2, y1), n1);
1747 }
1748 }
1749
1750 freetree234(points);
1751 }
1752
1753 grid_make_consistent(g);
1754 return g;
1755}
1756
1757#define SNUBSQUARE_TILESIZE 18
1758/* Vector for side of triangle - ratio is close to sqrt(3) */
1759#define SNUBSQUARE_A 15
1760#define SNUBSQUARE_B 26
1761
1762static const char *grid_validate_params_snubsquare(int width, int height)
1763{
1764 int a = SNUBSQUARE_A;
1765 int b = SNUBSQUARE_B;
1766
1767 if (width-1 > (INT_MAX - (a + b)) / (a+b) || /* xextent */
1768 height > (INT_MAX - (a + b)) / (a+b) || /* yextent */
1769 width > INT_MAX / 3 / height || /* max_faces */
1770 width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */
1771 return "Grid size must not be unreasonably large";
1772 return NULL;
1773}
1774
1775static void grid_size_snubsquare(int width, int height,
1776 int *tilesize, int *xextent, int *yextent)
1777{
1778 int a = SNUBSQUARE_A;
1779 int b = SNUBSQUARE_B;
1780
1781 *tilesize = SNUBSQUARE_TILESIZE;
1782 *xextent = (a+b) * (width-1) + a + b;
1783 *yextent = (a+b) * (height-1) + a + b;
1784}
1785
1786static grid *grid_new_snubsquare(int width, int height, const char *desc)
1787{
1788 int x, y;
1789 int a = SNUBSQUARE_A;
1790 int b = SNUBSQUARE_B;
1791
1792 tree234 *points;
1793
1794 grid *g = grid_empty();
1795 g->tilesize = SNUBSQUARE_TILESIZE;
1796
1797 points = newtree234(grid_point_cmp_fn);
1798
1799 for (y = 0; y < height; y++) {
1800 for (x = 0; x < width; x++) {
1801 grid_dot *d;
1802 /* face position */
1803 int px = (a + b) * x;
1804 int py = (a + b) * y;
1805
1806 /* generate square faces */
1807 grid_face_add_new(g, 4);
1808 if ((x + y) % 2) {
1809 d = grid_get_dot(g, points, px + a, py);
1810 grid_face_set_dot(g, d, 0);
1811 d = grid_get_dot(g, points, px + a + b, py + a);
1812 grid_face_set_dot(g, d, 1);
1813 d = grid_get_dot(g, points, px + b, py + a + b);
1814 grid_face_set_dot(g, d, 2);
1815 d = grid_get_dot(g, points, px, py + b);
1816 grid_face_set_dot(g, d, 3);
1817 } else {
1818 d = grid_get_dot(g, points, px + b, py);
1819 grid_face_set_dot(g, d, 0);
1820 d = grid_get_dot(g, points, px + a + b, py + b);
1821 grid_face_set_dot(g, d, 1);
1822 d = grid_get_dot(g, points, px + a, py + a + b);
1823 grid_face_set_dot(g, d, 2);
1824 d = grid_get_dot(g, points, px, py + a);
1825 grid_face_set_dot(g, d, 3);
1826 }
1827
1828 /* generate up/down triangles */
1829 if (x > 0) {
1830 grid_face_add_new(g, 3);
1831 if ((x + y) % 2) {
1832 d = grid_get_dot(g, points, px + a, py);
1833 grid_face_set_dot(g, d, 0);
1834 d = grid_get_dot(g, points, px, py + b);
1835 grid_face_set_dot(g, d, 1);
1836 d = grid_get_dot(g, points, px - a, py);
1837 grid_face_set_dot(g, d, 2);
1838 } else {
1839 d = grid_get_dot(g, points, px, py + a);
1840 grid_face_set_dot(g, d, 0);
1841 d = grid_get_dot(g, points, px + a, py + a + b);
1842 grid_face_set_dot(g, d, 1);
1843 d = grid_get_dot(g, points, px - a, py + a + b);
1844 grid_face_set_dot(g, d, 2);
1845 }
1846 }
1847
1848 /* generate left/right triangles */
1849 if (y > 0) {
1850 grid_face_add_new(g, 3);
1851 if ((x + y) % 2) {
1852 d = grid_get_dot(g, points, px + a, py);
1853 grid_face_set_dot(g, d, 0);
1854 d = grid_get_dot(g, points, px + a + b, py - a);
1855 grid_face_set_dot(g, d, 1);
1856 d = grid_get_dot(g, points, px + a + b, py + a);
1857 grid_face_set_dot(g, d, 2);
1858 } else {
1859 d = grid_get_dot(g, points, px, py - a);
1860 grid_face_set_dot(g, d, 0);
1861 d = grid_get_dot(g, points, px + b, py);
1862 grid_face_set_dot(g, d, 1);
1863 d = grid_get_dot(g, points, px, py + a);
1864 grid_face_set_dot(g, d, 2);
1865 }
1866 }
1867 }
1868 }
1869
1870 freetree234(points);
1871
1872 grid_make_consistent(g);
1873 return g;
1874}
1875
1876#define CAIRO_TILESIZE 40
1877/* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
1878#define CAIRO_A 14
1879#define CAIRO_B 31
1880
1881static const char *grid_validate_params_cairo(int width, int height)
1882{
1883 int b = CAIRO_B; /* a unused in determining grid size. */
1884
1885 if (width - 1 > (INT_MAX - 2*b) / (2*b) || /* xextent */
1886 height - 1 > (INT_MAX - 2*b) / (2*b) || /* yextent */
1887 width > INT_MAX / 2 / height || /* max_faces */
1888 width + 1 > INT_MAX / 3 / (height + 1)) /* max_dots */
1889 return "Grid size must not be unreasonably large";
1890 return NULL;
1891}
1892
1893static void grid_size_cairo(int width, int height,
1894 int *tilesize, int *xextent, int *yextent)
1895{
1896 int b = CAIRO_B; /* a unused in determining grid size. */
1897
1898 *tilesize = CAIRO_TILESIZE;
1899 *xextent = 2*b*(width-1) + 2*b;
1900 *yextent = 2*b*(height-1) + 2*b;
1901}
1902
1903static grid *grid_new_cairo(int width, int height, const char *desc)
1904{
1905 int x, y;
1906 int a = CAIRO_A;
1907 int b = CAIRO_B;
1908
1909 tree234 *points;
1910
1911 grid *g = grid_empty();
1912 g->tilesize = CAIRO_TILESIZE;
1913
1914 points = newtree234(grid_point_cmp_fn);
1915
1916 for (y = 0; y < height; y++) {
1917 for (x = 0; x < width; x++) {
1918 grid_dot *d;
1919 /* cell position */
1920 int px = 2 * b * x;
1921 int py = 2 * b * y;
1922
1923 /* horizontal pentagons */
1924 if (y > 0) {
1925 grid_face_add_new(g, 5);
1926 if ((x + y) % 2) {
1927 d = grid_get_dot(g, points, px + a, py - b);
1928 grid_face_set_dot(g, d, 0);
1929 d = grid_get_dot(g, points, px + 2*b - a, py - b);
1930 grid_face_set_dot(g, d, 1);
1931 d = grid_get_dot(g, points, px + 2*b, py);
1932 grid_face_set_dot(g, d, 2);
1933 d = grid_get_dot(g, points, px + b, py + a);
1934 grid_face_set_dot(g, d, 3);
1935 d = grid_get_dot(g, points, px, py);
1936 grid_face_set_dot(g, d, 4);
1937 } else {
1938 d = grid_get_dot(g, points, px, py);
1939 grid_face_set_dot(g, d, 0);
1940 d = grid_get_dot(g, points, px + b, py - a);
1941 grid_face_set_dot(g, d, 1);
1942 d = grid_get_dot(g, points, px + 2*b, py);
1943 grid_face_set_dot(g, d, 2);
1944 d = grid_get_dot(g, points, px + 2*b - a, py + b);
1945 grid_face_set_dot(g, d, 3);
1946 d = grid_get_dot(g, points, px + a, py + b);
1947 grid_face_set_dot(g, d, 4);
1948 }
1949 }
1950 /* vertical pentagons */
1951 if (x > 0) {
1952 grid_face_add_new(g, 5);
1953 if ((x + y) % 2) {
1954 d = grid_get_dot(g, points, px, py);
1955 grid_face_set_dot(g, d, 0);
1956 d = grid_get_dot(g, points, px + b, py + a);
1957 grid_face_set_dot(g, d, 1);
1958 d = grid_get_dot(g, points, px + b, py + 2*b - a);
1959 grid_face_set_dot(g, d, 2);
1960 d = grid_get_dot(g, points, px, py + 2*b);
1961 grid_face_set_dot(g, d, 3);
1962 d = grid_get_dot(g, points, px - a, py + b);
1963 grid_face_set_dot(g, d, 4);
1964 } else {
1965 d = grid_get_dot(g, points, px, py);
1966 grid_face_set_dot(g, d, 0);
1967 d = grid_get_dot(g, points, px + a, py + b);
1968 grid_face_set_dot(g, d, 1);
1969 d = grid_get_dot(g, points, px, py + 2*b);
1970 grid_face_set_dot(g, d, 2);
1971 d = grid_get_dot(g, points, px - b, py + 2*b - a);
1972 grid_face_set_dot(g, d, 3);
1973 d = grid_get_dot(g, points, px - b, py + a);
1974 grid_face_set_dot(g, d, 4);
1975 }
1976 }
1977 }
1978 }
1979
1980 freetree234(points);
1981
1982 grid_make_consistent(g);
1983 return g;
1984}
1985
1986#define GREATHEX_TILESIZE 18
1987/* Vector for side of triangle - ratio is close to sqrt(3) */
1988#define GREATHEX_A 15
1989#define GREATHEX_B 26
1990
1991static const char *grid_validate_params_greathexagonal(int width, int height)
1992{
1993 int a = GREATHEX_A;
1994 int b = GREATHEX_B;
1995
1996 if (width-1 > (INT_MAX - 4*a) / (3*a + b) || /* xextent */
1997 height-1 > (INT_MAX - (3*b + a)) / (2*a + 2*b) || /* yextent */
1998 width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */
1999 return "Grid size must not be unreasonably large";
2000 return NULL;
2001}
2002
2003static void grid_size_greathexagonal(int width, int height,
2004 int *tilesize, int *xextent, int *yextent)
2005{
2006 int a = GREATHEX_A;
2007 int b = GREATHEX_B;
2008
2009 *tilesize = GREATHEX_TILESIZE;
2010 *xextent = (3*a + b) * (width-1) + 4*a;
2011 *yextent = (2*a + 2*b) * (height-1) + 3*b + a;
2012}
2013
2014static grid *grid_new_greathexagonal(int width, int height, const char *desc)
2015{
2016 int x, y;
2017 int a = GREATHEX_A;
2018 int b = GREATHEX_B;
2019
2020 tree234 *points;
2021
2022 grid *g = grid_empty();
2023 g->tilesize = GREATHEX_TILESIZE;
2024
2025 points = newtree234(grid_point_cmp_fn);
2026
2027 for (y = 0; y < height; y++) {
2028 for (x = 0; x < width; x++) {
2029 grid_dot *d;
2030 /* centre of hexagon */
2031 int px = (3*a + b) * x;
2032 int py = (2*a + 2*b) * y;
2033 if (x % 2)
2034 py += a + b;
2035
2036 /* hexagon */
2037 grid_face_add_new(g, 6);
2038 d = grid_get_dot(g, points, px - a, py - b);
2039 grid_face_set_dot(g, d, 0);
2040 d = grid_get_dot(g, points, px + a, py - b);
2041 grid_face_set_dot(g, d, 1);
2042 d = grid_get_dot(g, points, px + 2*a, py);
2043 grid_face_set_dot(g, d, 2);
2044 d = grid_get_dot(g, points, px + a, py + b);
2045 grid_face_set_dot(g, d, 3);
2046 d = grid_get_dot(g, points, px - a, py + b);
2047 grid_face_set_dot(g, d, 4);
2048 d = grid_get_dot(g, points, px - 2*a, py);
2049 grid_face_set_dot(g, d, 5);
2050
2051 /* square below hexagon */
2052 if (y < height - 1) {
2053 grid_face_add_new(g, 4);
2054 d = grid_get_dot(g, points, px - a, py + b);
2055 grid_face_set_dot(g, d, 0);
2056 d = grid_get_dot(g, points, px + a, py + b);
2057 grid_face_set_dot(g, d, 1);
2058 d = grid_get_dot(g, points, px + a, py + 2*a + b);
2059 grid_face_set_dot(g, d, 2);
2060 d = grid_get_dot(g, points, px - a, py + 2*a + b);
2061 grid_face_set_dot(g, d, 3);
2062 }
2063
2064 /* square below right */
2065 if ((x < width - 1) && (((x % 2) == 0) || (y < height - 1))) {
2066 grid_face_add_new(g, 4);
2067 d = grid_get_dot(g, points, px + 2*a, py);
2068 grid_face_set_dot(g, d, 0);
2069 d = grid_get_dot(g, points, px + 2*a + b, py + a);
2070 grid_face_set_dot(g, d, 1);
2071 d = grid_get_dot(g, points, px + a + b, py + a + b);
2072 grid_face_set_dot(g, d, 2);
2073 d = grid_get_dot(g, points, px + a, py + b);
2074 grid_face_set_dot(g, d, 3);
2075 }
2076
2077 /* square below left */
2078 if ((x > 0) && (((x % 2) == 0) || (y < height - 1))) {
2079 grid_face_add_new(g, 4);
2080 d = grid_get_dot(g, points, px - 2*a, py);
2081 grid_face_set_dot(g, d, 0);
2082 d = grid_get_dot(g, points, px - a, py + b);
2083 grid_face_set_dot(g, d, 1);
2084 d = grid_get_dot(g, points, px - a - b, py + a + b);
2085 grid_face_set_dot(g, d, 2);
2086 d = grid_get_dot(g, points, px - 2*a - b, py + a);
2087 grid_face_set_dot(g, d, 3);
2088 }
2089
2090 /* Triangle below right */
2091 if ((x < width - 1) && (y < height - 1)) {
2092 grid_face_add_new(g, 3);
2093 d = grid_get_dot(g, points, px + a, py + b);
2094 grid_face_set_dot(g, d, 0);
2095 d = grid_get_dot(g, points, px + a + b, py + a + b);
2096 grid_face_set_dot(g, d, 1);
2097 d = grid_get_dot(g, points, px + a, py + 2*a + b);
2098 grid_face_set_dot(g, d, 2);
2099 }
2100
2101 /* Triangle below left */
2102 if ((x > 0) && (y < height - 1)) {
2103 grid_face_add_new(g, 3);
2104 d = grid_get_dot(g, points, px - a, py + b);
2105 grid_face_set_dot(g, d, 0);
2106 d = grid_get_dot(g, points, px - a, py + 2*a + b);
2107 grid_face_set_dot(g, d, 1);
2108 d = grid_get_dot(g, points, px - a - b, py + a + b);
2109 grid_face_set_dot(g, d, 2);
2110 }
2111 }
2112 }
2113
2114 freetree234(points);
2115
2116 grid_make_consistent(g);
2117 return g;
2118}
2119
2120#define KAGOME_TILESIZE 18
2121/* Vector for side of triangle - ratio is close to sqrt(3) */
2122#define KAGOME_A 15
2123#define KAGOME_B 26
2124
2125static const char *grid_validate_params_kagome(int width, int height)
2126{
2127 int a = KAGOME_A;
2128 int b = KAGOME_B;
2129
2130 if (width-1 > (INT_MAX - 6*a) / (4*a) || /* xextent */
2131 height-1 > (INT_MAX - 2*b) / (2*b) || /* yextent */
2132 width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */
2133 return "Grid size must not be unreasonably large";
2134 return NULL;
2135}
2136
2137static void grid_size_kagome(int width, int height,
2138 int *tilesize, int *xextent, int *yextent)
2139{
2140 int a = KAGOME_A;
2141 int b = KAGOME_B;
2142
2143 *tilesize = KAGOME_TILESIZE;
2144 *xextent = (4*a) * (width-1) + 6*a;
2145 *yextent = (2*b) * (height-1) + 2*b;
2146}
2147
2148static grid *grid_new_kagome(int width, int height, const char *desc)
2149{
2150 int x, y;
2151 int a = KAGOME_A;
2152 int b = KAGOME_B;
2153
2154 tree234 *points;
2155
2156 grid *g = grid_empty();
2157 g->tilesize = KAGOME_TILESIZE;
2158
2159 points = newtree234(grid_point_cmp_fn);
2160
2161 for (y = 0; y < height; y++) {
2162 for (x = 0; x < width; x++) {
2163 grid_dot *d;
2164 /* centre of hexagon */
2165 int px = (4*a) * x;
2166 int py = (2*b) * y;
2167 if (y % 2)
2168 px += 2*a;
2169
2170 /* hexagon */
2171 grid_face_add_new(g, 6);
2172 d = grid_get_dot(g, points, px + a, py - b); grid_face_set_dot(g, d, 0);
2173 d = grid_get_dot(g, points, px + 2*a, py ); grid_face_set_dot(g, d, 1);
2174 d = grid_get_dot(g, points, px + a, py + b); grid_face_set_dot(g, d, 2);
2175 d = grid_get_dot(g, points, px - a, py + b); grid_face_set_dot(g, d, 3);
2176 d = grid_get_dot(g, points, px - 2*a, py ); grid_face_set_dot(g, d, 4);
2177 d = grid_get_dot(g, points, px - a, py - b); grid_face_set_dot(g, d, 5);
2178
2179 /* Triangle above right */
2180 if ((x < width - 1) || (!(y % 2) && y)) {
2181 grid_face_add_new(g, 3);
2182 d = grid_get_dot(g, points, px + 3*a, py - b); grid_face_set_dot(g, d, 0);
2183 d = grid_get_dot(g, points, px + 2*a, py ); grid_face_set_dot(g, d, 1);
2184 d = grid_get_dot(g, points, px + a, py - b); grid_face_set_dot(g, d, 2);
2185 }
2186
2187 /* Triangle below right */
2188 if ((x < width - 1) || (!(y % 2) && (y < height - 1))) {
2189 grid_face_add_new(g, 3);
2190 d = grid_get_dot(g, points, px + 3*a, py + b); grid_face_set_dot(g, d, 0);
2191 d = grid_get_dot(g, points, px + a, py + b); grid_face_set_dot(g, d, 1);
2192 d = grid_get_dot(g, points, px + 2*a, py ); grid_face_set_dot(g, d, 2);
2193 }
2194
2195 /* Left triangles */
2196 if (!x && (y % 2)) {
2197 /* Triangle above left */
2198 grid_face_add_new(g, 3);
2199 d = grid_get_dot(g, points, px - a, py - b); grid_face_set_dot(g, d, 0);
2200 d = grid_get_dot(g, points, px - 2*a, py ); grid_face_set_dot(g, d, 1);
2201 d = grid_get_dot(g, points, px - 3*a, py - b); grid_face_set_dot(g, d, 2);
2202
2203 /* Triangle below left */
2204 if (y < height - 1) {
2205 grid_face_add_new(g, 3);
2206 d = grid_get_dot(g, points, px - a, py + b); grid_face_set_dot(g, d, 0);
2207 d = grid_get_dot(g, points, px - 3*a, py + b); grid_face_set_dot(g, d, 1);
2208 d = grid_get_dot(g, points, px - 2*a, py ); grid_face_set_dot(g, d, 2);
2209 }
2210 }
2211 }
2212 }
2213
2214 freetree234(points);
2215
2216 grid_make_consistent(g);
2217 return g;
2218}
2219
2220#define OCTAGONAL_TILESIZE 40
2221/* b/a approx sqrt(2) */
2222#define OCTAGONAL_A 29
2223#define OCTAGONAL_B 41
2224
2225static const char *grid_validate_params_octagonal(int width, int height)
2226{
2227 int a = OCTAGONAL_A;
2228 int b = OCTAGONAL_B;
2229
2230 if (width > INT_MAX / (2*a + b) || /* xextent */
2231 height > INT_MAX / (2*a + b) || /* yextent */
2232 height + 1 > INT_MAX / 4 / (width + 1)) /* max_dots */
2233 return "Grid size must not be unreasonably large";
2234 return NULL;
2235}
2236
2237static void grid_size_octagonal(int width, int height,
2238 int *tilesize, int *xextent, int *yextent)
2239{
2240 int a = OCTAGONAL_A;
2241 int b = OCTAGONAL_B;
2242
2243 *tilesize = OCTAGONAL_TILESIZE;
2244 *xextent = (2*a + b) * width;
2245 *yextent = (2*a + b) * height;
2246}
2247
2248static grid *grid_new_octagonal(int width, int height, const char *desc)
2249{
2250 int x, y;
2251 int a = OCTAGONAL_A;
2252 int b = OCTAGONAL_B;
2253
2254 tree234 *points;
2255
2256 grid *g = grid_empty();
2257 g->tilesize = OCTAGONAL_TILESIZE;
2258
2259 points = newtree234(grid_point_cmp_fn);
2260
2261 for (y = 0; y < height; y++) {
2262 for (x = 0; x < width; x++) {
2263 grid_dot *d;
2264 /* cell position */
2265 int px = (2*a + b) * x;
2266 int py = (2*a + b) * y;
2267 /* octagon */
2268 grid_face_add_new(g, 8);
2269 d = grid_get_dot(g, points, px + a, py);
2270 grid_face_set_dot(g, d, 0);
2271 d = grid_get_dot(g, points, px + a + b, py);
2272 grid_face_set_dot(g, d, 1);
2273 d = grid_get_dot(g, points, px + 2*a + b, py + a);
2274 grid_face_set_dot(g, d, 2);
2275 d = grid_get_dot(g, points, px + 2*a + b, py + a + b);
2276 grid_face_set_dot(g, d, 3);
2277 d = grid_get_dot(g, points, px + a + b, py + 2*a + b);
2278 grid_face_set_dot(g, d, 4);
2279 d = grid_get_dot(g, points, px + a, py + 2*a + b);
2280 grid_face_set_dot(g, d, 5);
2281 d = grid_get_dot(g, points, px, py + a + b);
2282 grid_face_set_dot(g, d, 6);
2283 d = grid_get_dot(g, points, px, py + a);
2284 grid_face_set_dot(g, d, 7);
2285
2286 /* diamond */
2287 if ((x > 0) && (y > 0)) {
2288 grid_face_add_new(g, 4);
2289 d = grid_get_dot(g, points, px, py - a);
2290 grid_face_set_dot(g, d, 0);
2291 d = grid_get_dot(g, points, px + a, py);
2292 grid_face_set_dot(g, d, 1);
2293 d = grid_get_dot(g, points, px, py + a);
2294 grid_face_set_dot(g, d, 2);
2295 d = grid_get_dot(g, points, px - a, py);
2296 grid_face_set_dot(g, d, 3);
2297 }
2298 }
2299 }
2300
2301 freetree234(points);
2302
2303 grid_make_consistent(g);
2304 return g;
2305}
2306
2307#define KITE_TILESIZE 40
2308/* b/a approx sqrt(3) */
2309#define KITE_A 15
2310#define KITE_B 26
2311
2312static const char *grid_validate_params_kites(int width, int height)
2313{
2314 int a = KITE_A;
2315 int b = KITE_B;
2316
2317 if (width > (INT_MAX - 2*b) / (4*b) || /* xextent */
2318 height - 1 > (INT_MAX - 8*a) / (6*a) || /* yextent */
2319 width + 1 > INT_MAX / 6 / (height + 1)) /* max_dots */
2320 return "Grid size must not be unreasonably large";
2321 return NULL;
2322}
2323
2324static void grid_size_kites(int width, int height,
2325 int *tilesize, int *xextent, int *yextent)
2326{
2327 int a = KITE_A;
2328 int b = KITE_B;
2329
2330 *tilesize = KITE_TILESIZE;
2331 *xextent = 4*b * width + 2*b;
2332 *yextent = 6*a * (height-1) + 8*a;
2333}
2334
2335static grid *grid_new_kites(int width, int height, const char *desc)
2336{
2337 int x, y;
2338 int a = KITE_A;
2339 int b = KITE_B;
2340
2341 tree234 *points;
2342
2343 grid *g = grid_empty();
2344 g->tilesize = KITE_TILESIZE;
2345
2346 points = newtree234(grid_point_cmp_fn);
2347
2348 for (y = 0; y < height; y++) {
2349 for (x = 0; x < width; x++) {
2350 grid_dot *d;
2351 /* position of order-6 dot */
2352 int px = 4*b * x;
2353 int py = 6*a * y;
2354 if (y % 2)
2355 px += 2*b;
2356
2357 /* kite pointing up-left */
2358 grid_face_add_new(g, 4);
2359 d = grid_get_dot(g, points, px, py);
2360 grid_face_set_dot(g, d, 0);
2361 d = grid_get_dot(g, points, px + 2*b, py);
2362 grid_face_set_dot(g, d, 1);
2363 d = grid_get_dot(g, points, px + 2*b, py + 2*a);
2364 grid_face_set_dot(g, d, 2);
2365 d = grid_get_dot(g, points, px + b, py + 3*a);
2366 grid_face_set_dot(g, d, 3);
2367
2368 /* kite pointing up */
2369 grid_face_add_new(g, 4);
2370 d = grid_get_dot(g, points, px, py);
2371 grid_face_set_dot(g, d, 0);
2372 d = grid_get_dot(g, points, px + b, py + 3*a);
2373 grid_face_set_dot(g, d, 1);
2374 d = grid_get_dot(g, points, px, py + 4*a);
2375 grid_face_set_dot(g, d, 2);
2376 d = grid_get_dot(g, points, px - b, py + 3*a);
2377 grid_face_set_dot(g, d, 3);
2378
2379 /* kite pointing up-right */
2380 grid_face_add_new(g, 4);
2381 d = grid_get_dot(g, points, px, py);
2382 grid_face_set_dot(g, d, 0);
2383 d = grid_get_dot(g, points, px - b, py + 3*a);
2384 grid_face_set_dot(g, d, 1);
2385 d = grid_get_dot(g, points, px - 2*b, py + 2*a);
2386 grid_face_set_dot(g, d, 2);
2387 d = grid_get_dot(g, points, px - 2*b, py);
2388 grid_face_set_dot(g, d, 3);
2389
2390 /* kite pointing down-right */
2391 grid_face_add_new(g, 4);
2392 d = grid_get_dot(g, points, px, py);
2393 grid_face_set_dot(g, d, 0);
2394 d = grid_get_dot(g, points, px - 2*b, py);
2395 grid_face_set_dot(g, d, 1);
2396 d = grid_get_dot(g, points, px - 2*b, py - 2*a);
2397 grid_face_set_dot(g, d, 2);
2398 d = grid_get_dot(g, points, px - b, py - 3*a);
2399 grid_face_set_dot(g, d, 3);
2400
2401 /* kite pointing down */
2402 grid_face_add_new(g, 4);
2403 d = grid_get_dot(g, points, px, py);
2404 grid_face_set_dot(g, d, 0);
2405 d = grid_get_dot(g, points, px - b, py - 3*a);
2406 grid_face_set_dot(g, d, 1);
2407 d = grid_get_dot(g, points, px, py - 4*a);
2408 grid_face_set_dot(g, d, 2);
2409 d = grid_get_dot(g, points, px + b, py - 3*a);
2410 grid_face_set_dot(g, d, 3);
2411
2412 /* kite pointing down-left */
2413 grid_face_add_new(g, 4);
2414 d = grid_get_dot(g, points, px, py);
2415 grid_face_set_dot(g, d, 0);
2416 d = grid_get_dot(g, points, px + b, py - 3*a);
2417 grid_face_set_dot(g, d, 1);
2418 d = grid_get_dot(g, points, px + 2*b, py - 2*a);
2419 grid_face_set_dot(g, d, 2);
2420 d = grid_get_dot(g, points, px + 2*b, py);
2421 grid_face_set_dot(g, d, 3);
2422 }
2423 }
2424
2425 freetree234(points);
2426
2427 grid_make_consistent(g);
2428 return g;
2429}
2430
2431#define FLORET_TILESIZE 150
2432/* -py/px is close to tan(30 - atan(sqrt(3)/9))
2433 * using py=26 makes everything lean to the left, rather than right
2434 */
2435#define FLORET_PX 75
2436#define FLORET_PY -26
2437
2438static const char *grid_validate_params_floret(int width, int height)
2439{
2440 int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */
2441 int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
2442 int ry = qy-py;
2443 /* rx unused in determining grid size. */
2444
2445 if (width - 1 > (INT_MAX - (4*px + 2*qx)) / ((6*px+3*qx)/2) ||/* xextent */
2446 height - 1 > (INT_MAX - (4*ry - 2*qy)) / (5*qy-4*py) || /* yextent */
2447 width + 1 > INT_MAX / 9 / (height + 1)) /* max_dots */
2448 return "Grid size must not be unreasonably large";
2449 return NULL;
2450}
2451
2452static void grid_size_floret(int width, int height,
2453 int *tilesize, int *xextent, int *yextent)
2454{
2455 int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */
2456 int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
2457 int ry = qy-py;
2458 /* rx unused in determining grid size. */
2459
2460 *tilesize = FLORET_TILESIZE;
2461 *xextent = (6*px+3*qx)/2 * (width-1) + 4*px + 2*qx;
2462 *yextent = (5*qy-4*py) * (height-1) + 4*ry + 2*qy;
2463 if (height == 1)
2464 *yextent += (5*qy-4*py)/2;
2465}
2466
2467static grid *grid_new_floret(int width, int height, const char *desc)
2468{
2469 int x, y;
2470 /* Vectors for sides; weird numbers needed to keep puzzle aligned with window
2471 * -py/px is close to tan(30 - atan(sqrt(3)/9))
2472 * using py=26 makes everything lean to the left, rather than right
2473 */
2474 int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */
2475 int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
2476 int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */
2477
2478 tree234 *points;
2479
2480 grid *g = grid_empty();
2481 g->tilesize = FLORET_TILESIZE;
2482
2483 points = newtree234(grid_point_cmp_fn);
2484
2485 /* generate pentagonal faces */
2486 for (y = 0; y < height; y++) {
2487 for (x = 0; x < width; x++) {
2488 grid_dot *d;
2489 /* face centre */
2490 int cx = (6*px+3*qx)/2 * x;
2491 int cy = (4*py-5*qy) * y;
2492 if (x % 2)
2493 cy -= (4*py-5*qy)/2;
2494 else if (y && y == height-1 && width > 1)
2495 continue; /* make better looking grids? try 3x3 for instance */
2496
2497 grid_face_add_new(g, 5);
2498 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
2499 d = grid_get_dot(g, points, cx+2*rx , cy+2*ry ); grid_face_set_dot(g, d, 1);
2500 d = grid_get_dot(g, points, cx+2*rx+qx, cy+2*ry+qy); grid_face_set_dot(g, d, 2);
2501 d = grid_get_dot(g, points, cx+2*qx+rx, cy+2*qy+ry); grid_face_set_dot(g, d, 3);
2502 d = grid_get_dot(g, points, cx+2*qx , cy+2*qy ); grid_face_set_dot(g, d, 4);
2503
2504 grid_face_add_new(g, 5);
2505 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
2506 d = grid_get_dot(g, points, cx+2*qx , cy+2*qy ); grid_face_set_dot(g, d, 1);
2507 d = grid_get_dot(g, points, cx+2*qx+px, cy+2*qy+py); grid_face_set_dot(g, d, 2);
2508 d = grid_get_dot(g, points, cx+2*px+qx, cy+2*py+qy); grid_face_set_dot(g, d, 3);
2509 d = grid_get_dot(g, points, cx+2*px , cy+2*py ); grid_face_set_dot(g, d, 4);
2510
2511 grid_face_add_new(g, 5);
2512 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
2513 d = grid_get_dot(g, points, cx+2*px , cy+2*py ); grid_face_set_dot(g, d, 1);
2514 d = grid_get_dot(g, points, cx+2*px-rx, cy+2*py-ry); grid_face_set_dot(g, d, 2);
2515 d = grid_get_dot(g, points, cx-2*rx+px, cy-2*ry+py); grid_face_set_dot(g, d, 3);
2516 d = grid_get_dot(g, points, cx-2*rx , cy-2*ry ); grid_face_set_dot(g, d, 4);
2517
2518 grid_face_add_new(g, 5);
2519 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
2520 d = grid_get_dot(g, points, cx-2*rx , cy-2*ry ); grid_face_set_dot(g, d, 1);
2521 d = grid_get_dot(g, points, cx-2*rx-qx, cy-2*ry-qy); grid_face_set_dot(g, d, 2);
2522 d = grid_get_dot(g, points, cx-2*qx-rx, cy-2*qy-ry); grid_face_set_dot(g, d, 3);
2523 d = grid_get_dot(g, points, cx-2*qx , cy-2*qy ); grid_face_set_dot(g, d, 4);
2524
2525 grid_face_add_new(g, 5);
2526 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
2527 d = grid_get_dot(g, points, cx-2*qx , cy-2*qy ); grid_face_set_dot(g, d, 1);
2528 d = grid_get_dot(g, points, cx-2*qx-px, cy-2*qy-py); grid_face_set_dot(g, d, 2);
2529 d = grid_get_dot(g, points, cx-2*px-qx, cy-2*py-qy); grid_face_set_dot(g, d, 3);
2530 d = grid_get_dot(g, points, cx-2*px , cy-2*py ); grid_face_set_dot(g, d, 4);
2531
2532 grid_face_add_new(g, 5);
2533 d = grid_get_dot(g, points, cx , cy ); grid_face_set_dot(g, d, 0);
2534 d = grid_get_dot(g, points, cx-2*px , cy-2*py ); grid_face_set_dot(g, d, 1);
2535 d = grid_get_dot(g, points, cx-2*px+rx, cy-2*py+ry); grid_face_set_dot(g, d, 2);
2536 d = grid_get_dot(g, points, cx+2*rx-px, cy+2*ry-py); grid_face_set_dot(g, d, 3);
2537 d = grid_get_dot(g, points, cx+2*rx , cy+2*ry ); grid_face_set_dot(g, d, 4);
2538 }
2539 }
2540
2541 freetree234(points);
2542
2543 grid_make_consistent(g);
2544 return g;
2545}
2546
2547/* DODEC_* are used for dodecagonal and great-dodecagonal grids. */
2548#define DODEC_TILESIZE 26
2549/* Vector for side of triangle - ratio is close to sqrt(3) */
2550#define DODEC_A 15
2551#define DODEC_B 26
2552
2553static const char *grid_validate_params_dodecagonal(int width, int height)
2554{
2555 int a = DODEC_A;
2556 int b = DODEC_B;
2557
2558 if (width - 1 > (INT_MAX - 3*(2*a + b)) / (4*a + 2*b) || /* xextent */
2559 height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 2*b) || /* yextent */
2560 width > INT_MAX / 14 / height) /* max_dots */
2561 return "Grid size must not be unreasonably large";
2562 return NULL;
2563}
2564
2565static void grid_size_dodecagonal(int width, int height,
2566 int *tilesize, int *xextent, int *yextent)
2567{
2568 int a = DODEC_A;
2569 int b = DODEC_B;
2570
2571 *tilesize = DODEC_TILESIZE;
2572 *xextent = (4*a + 2*b) * (width-1) + 3*(2*a + b);
2573 *yextent = (3*a + 2*b) * (height-1) + 2*(2*a + b);
2574}
2575
2576static grid *grid_new_dodecagonal(int width, int height, const char *desc)
2577{
2578 int x, y;
2579 int a = DODEC_A;
2580 int b = DODEC_B;
2581
2582 tree234 *points;
2583
2584 grid *g = grid_empty();
2585 g->tilesize = DODEC_TILESIZE;
2586
2587 points = newtree234(grid_point_cmp_fn);
2588
2589 for (y = 0; y < height; y++) {
2590 for (x = 0; x < width; x++) {
2591 grid_dot *d;
2592 /* centre of dodecagon */
2593 int px = (4*a + 2*b) * x;
2594 int py = (3*a + 2*b) * y;
2595 if (y % 2)
2596 px += 2*a + b;
2597
2598 /* dodecagon */
2599 grid_face_add_new(g, 12);
2600 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2601 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
2602 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
2603 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
2604 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
2605 d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
2606 d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
2607 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
2608 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
2609 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
2610 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
2611 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
2612
2613 /* triangle below dodecagon */
2614 if ((y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) {
2615 grid_face_add_new(g, 3);
2616 d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0);
2617 d = grid_get_dot(g, points, px , py + (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2618 d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 2);
2619 }
2620
2621 /* triangle above dodecagon */
2622 if ((y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2)))) {
2623 grid_face_add_new(g, 3);
2624 d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0);
2625 d = grid_get_dot(g, points, px , py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2626 d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 2);
2627 }
2628 }
2629 }
2630
2631 freetree234(points);
2632
2633 grid_make_consistent(g);
2634 return g;
2635}
2636
2637static const char *grid_validate_params_greatdodecagonal(int width, int height)
2638{
2639 int a = DODEC_A;
2640 int b = DODEC_B;
2641
2642 if (width - 1 > (INT_MAX - (2*(2*a + b) + 3*a + b)) / (6*a + 2*b) ||
2643 height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 3*b) || /* yextent */
2644 width > INT_MAX / 200 / height) /* max_dots */
2645 return "Grid size must not be unreasonably large";
2646 return NULL;
2647}
2648
2649static void grid_size_greatdodecagonal(int width, int height,
2650 int *tilesize, int *xextent, int *yextent)
2651{
2652 int a = DODEC_A;
2653 int b = DODEC_B;
2654
2655 *tilesize = DODEC_TILESIZE;
2656 *xextent = (6*a + 2*b) * (width-1) + 2*(2*a + b) + 3*a + b;
2657 *yextent = (3*a + 3*b) * (height-1) + 2*(2*a + b);
2658}
2659
2660static grid *grid_new_greatdodecagonal(int width, int height, const char *desc)
2661{
2662 int x, y;
2663 /* Vector for side of triangle - ratio is close to sqrt(3) */
2664 int a = DODEC_A;
2665 int b = DODEC_B;
2666
2667 tree234 *points;
2668
2669 grid *g = grid_empty();
2670 g->tilesize = DODEC_TILESIZE;
2671
2672 points = newtree234(grid_point_cmp_fn);
2673
2674 for (y = 0; y < height; y++) {
2675 for (x = 0; x < width; x++) {
2676 grid_dot *d;
2677 /* centre of dodecagon */
2678 int px = (6*a + 2*b) * x;
2679 int py = (3*a + 3*b) * y;
2680 if (y % 2)
2681 px += 3*a + b;
2682
2683 /* dodecagon */
2684 grid_face_add_new(g, 12);
2685 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2686 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
2687 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
2688 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
2689 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
2690 d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
2691 d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
2692 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
2693 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
2694 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
2695 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
2696 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
2697
2698 /* hexagon below dodecagon */
2699 if (y < height - 1 && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
2700 grid_face_add_new(g, 6);
2701 d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0);
2702 d = grid_get_dot(g, points, px + 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2703 d = grid_get_dot(g, points, px + a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 2);
2704 d = grid_get_dot(g, points, px - a, py + (2*a + 3*b)); grid_face_set_dot(g, d, 3);
2705 d = grid_get_dot(g, points, px - 2*a, py + (2*a + 2*b)); grid_face_set_dot(g, d, 4);
2706 d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 5);
2707 }
2708
2709 /* hexagon above dodecagon */
2710 if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
2711 grid_face_add_new(g, 6);
2712 d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 0);
2713 d = grid_get_dot(g, points, px - 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2714 d = grid_get_dot(g, points, px - a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 2);
2715 d = grid_get_dot(g, points, px + a, py - (2*a + 3*b)); grid_face_set_dot(g, d, 3);
2716 d = grid_get_dot(g, points, px + 2*a, py - (2*a + 2*b)); grid_face_set_dot(g, d, 4);
2717 d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 5);
2718 }
2719
2720 /* square on right of dodecagon */
2721 if (x < width - 1) {
2722 grid_face_add_new(g, 4);
2723 d = grid_get_dot(g, points, px + 2*a + b, py - a); grid_face_set_dot(g, d, 0);
2724 d = grid_get_dot(g, points, px + 4*a + b, py - a); grid_face_set_dot(g, d, 1);
2725 d = grid_get_dot(g, points, px + 4*a + b, py + a); grid_face_set_dot(g, d, 2);
2726 d = grid_get_dot(g, points, px + 2*a + b, py + a); grid_face_set_dot(g, d, 3);
2727 }
2728
2729 /* square on top right of dodecagon */
2730 if (y && (x < width - 1 || !(y % 2))) {
2731 grid_face_add_new(g, 4);
2732 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2733 d = grid_get_dot(g, points, px + (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 1);
2734 d = grid_get_dot(g, points, px + (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 2);
2735 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 3);
2736 }
2737
2738 /* square on top left of dodecagon */
2739 if (y && (x || (y % 2))) {
2740 grid_face_add_new(g, 4);
2741 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 0);
2742 d = grid_get_dot(g, points, px - (2*a + b), py - ( a + 2*b)); grid_face_set_dot(g, d, 1);
2743 d = grid_get_dot(g, points, px - (2*a ), py - (2*a + 2*b)); grid_face_set_dot(g, d, 2);
2744 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 3);
2745 }
2746 }
2747 }
2748
2749 freetree234(points);
2750
2751 grid_make_consistent(g);
2752 return g;
2753}
2754
2755static const char *grid_validate_params_greatgreatdodecagonal(
2756 int width, int height)
2757{
2758 int a = DODEC_A;
2759 int b = DODEC_B;
2760
2761 if (width-1 > (INT_MAX - (2*(2*a + b) + 2*a + 2*b)) / (4*a + 4*b) ||
2762 height-1 > (INT_MAX - 2*(2*a + b)) / (6*a + 2*b) || /* yextent */
2763 width > INT_MAX / 300 / height) /* max_dots */
2764 return "Grid size must not be unreasonably large";
2765 return NULL;
2766}
2767
2768static void grid_size_greatgreatdodecagonal(int width, int height,
2769 int *tilesize, int *xextent, int *yextent)
2770{
2771 int a = DODEC_A;
2772 int b = DODEC_B;
2773
2774 *tilesize = DODEC_TILESIZE;
2775 *xextent = (4*a + 4*b) * (width-1) + 2*(2*a + b) + 2*a + 2*b;
2776 *yextent = (6*a + 2*b) * (height-1) + 2*(2*a + b);
2777}
2778
2779static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *desc)
2780{
2781 int x, y;
2782 /* Vector for side of triangle - ratio is close to sqrt(3) */
2783 int a = DODEC_A;
2784 int b = DODEC_B;
2785
2786 tree234 *points;
2787
2788 grid *g = grid_empty();
2789 g->tilesize = DODEC_TILESIZE;
2790
2791 points = newtree234(grid_point_cmp_fn);
2792
2793 for (y = 0; y < height; y++) {
2794 for (x = 0; x < width; x++) {
2795 grid_dot *d;
2796 /* centre of dodecagon */
2797 int px = (4*a + 4*b) * x;
2798 int py = (6*a + 2*b) * y;
2799 if (y % 2)
2800 px += 2*a + 2*b;
2801
2802 /* dodecagon */
2803 grid_face_add_new(g, 12);
2804 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2805 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
2806 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
2807 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
2808 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
2809 d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
2810 d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
2811 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
2812 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
2813 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
2814 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
2815 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
2816
2817 /* hexagon on top right of dodecagon */
2818 if (y && (x < width - 1 || !(y % 2))) {
2819 grid_face_add_new(g, 6);
2820 d = grid_get_dot(g, points, px + (a + 2*b), py - (4*a + b)); grid_face_set_dot(g, d, 0);
2821 d = grid_get_dot(g, points, px + (a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 1);
2822 d = grid_get_dot(g, points, px + (a + b), py - ( a + b)); grid_face_set_dot(g, d, 2);
2823 d = grid_get_dot(g, points, px + (a ), py - (2*a + b)); grid_face_set_dot(g, d, 3);
2824 d = grid_get_dot(g, points, px + (a ), py - (4*a + b)); grid_face_set_dot(g, d, 4);
2825 d = grid_get_dot(g, points, px + (a + b), py - (5*a + b)); grid_face_set_dot(g, d, 5);
2826 }
2827
2828 /* hexagon on right of dodecagon*/
2829 if (x < width - 1) {
2830 grid_face_add_new(g, 6);
2831 d = grid_get_dot(g, points, px + (2*a + 3*b), py - a); grid_face_set_dot(g, d, 0);
2832 d = grid_get_dot(g, points, px + (2*a + 3*b), py + a); grid_face_set_dot(g, d, 1);
2833 d = grid_get_dot(g, points, px + (2*a + 2*b), py + 2*a); grid_face_set_dot(g, d, 2);
2834 d = grid_get_dot(g, points, px + (2*a + b), py + a); grid_face_set_dot(g, d, 3);
2835 d = grid_get_dot(g, points, px + (2*a + b), py - a); grid_face_set_dot(g, d, 4);
2836 d = grid_get_dot(g, points, px + (2*a + 2*b), py - 2*a); grid_face_set_dot(g, d, 5);
2837 }
2838
2839 /* hexagon on bottom right of dodecagon */
2840 if ((y < height - 1) && (x < width - 1 || !(y % 2))) {
2841 grid_face_add_new(g, 6);
2842 d = grid_get_dot(g, points, px + (a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0);
2843 d = grid_get_dot(g, points, px + (a + 2*b), py + (4*a + b)); grid_face_set_dot(g, d, 1);
2844 d = grid_get_dot(g, points, px + (a + b), py + (5*a + b)); grid_face_set_dot(g, d, 2);
2845 d = grid_get_dot(g, points, px + (a ), py + (4*a + b)); grid_face_set_dot(g, d, 3);
2846 d = grid_get_dot(g, points, px + (a ), py + (2*a + b)); grid_face_set_dot(g, d, 4);
2847 d = grid_get_dot(g, points, px + (a + b), py + ( a + b)); grid_face_set_dot(g, d, 5);
2848 }
2849
2850 /* square on top right of dodecagon */
2851 if (y && (x < width - 1 )) {
2852 grid_face_add_new(g, 4);
2853 d = grid_get_dot(g, points, px + ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2854 d = grid_get_dot(g, points, px + (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 1);
2855 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
2856 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 3);
2857 }
2858
2859 /* square on bottom right of dodecagon */
2860 if ((y < height - 1) && (x < width - 1 )) {
2861 grid_face_add_new(g, 4);
2862 d = grid_get_dot(g, points, px + (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 0);
2863 d = grid_get_dot(g, points, px + ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 1);
2864 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 2);
2865 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
2866 }
2867
2868 /* square below dodecagon */
2869 if ((y < height - 1) && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
2870 grid_face_add_new(g, 4);
2871 d = grid_get_dot(g, points, px + a, py + (2*a + b)); grid_face_set_dot(g, d, 0);
2872 d = grid_get_dot(g, points, px + a, py + (4*a + b)); grid_face_set_dot(g, d, 1);
2873 d = grid_get_dot(g, points, px - a, py + (4*a + b)); grid_face_set_dot(g, d, 2);
2874 d = grid_get_dot(g, points, px - a, py + (2*a + b)); grid_face_set_dot(g, d, 3);
2875 }
2876
2877 /* square on bottom left of dodecagon */
2878 if (x && (y < height - 1)) {
2879 grid_face_add_new(g, 4);
2880 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 0);
2881 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 1);
2882 d = grid_get_dot(g, points, px - ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 2);
2883 d = grid_get_dot(g, points, px - (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 3);
2884 }
2885
2886 /* square on top left of dodecagon */
2887 if (x && y) {
2888 grid_face_add_new(g, 4);
2889 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 0);
2890 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 1);
2891 d = grid_get_dot(g, points, px - (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 2);
2892 d = grid_get_dot(g, points, px - ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 3);
2893
2894 }
2895
2896 /* square above dodecagon */
2897 if (y && (x < width - 1 || !(y % 2)) && (x > 0 || (y % 2))) {
2898 grid_face_add_new(g, 4);
2899 d = grid_get_dot(g, points, px + a, py - (4*a + b)); grid_face_set_dot(g, d, 0);
2900 d = grid_get_dot(g, points, px + a, py - (2*a + b)); grid_face_set_dot(g, d, 1);
2901 d = grid_get_dot(g, points, px - a, py - (2*a + b)); grid_face_set_dot(g, d, 2);
2902 d = grid_get_dot(g, points, px - a, py - (4*a + b)); grid_face_set_dot(g, d, 3);
2903 }
2904
2905 /* upper triangle (v) */
2906 if (y && (x < width - 1)) {
2907 grid_face_add_new(g, 3);
2908 d = grid_get_dot(g, points, px + (3*a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2909 d = grid_get_dot(g, points, px + (2*a + 2*b), py - (2*a )); grid_face_set_dot(g, d, 1);
2910 d = grid_get_dot(g, points, px + ( a + 2*b), py - (2*a + b)); grid_face_set_dot(g, d, 2);
2911 }
2912
2913 /* lower triangle (^) */
2914 if ((y < height - 1) && (x < width - 1)) {
2915 grid_face_add_new(g, 3);
2916 d = grid_get_dot(g, points, px + (3*a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0);
2917 d = grid_get_dot(g, points, px + ( a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 1);
2918 d = grid_get_dot(g, points, px + (2*a + 2*b), py + (2*a )); grid_face_set_dot(g, d, 2);
2919 }
2920 }
2921 }
2922
2923 freetree234(points);
2924
2925 grid_make_consistent(g);
2926 return g;
2927}
2928
2929static const char *grid_validate_params_compassdodecagonal(
2930 int width, int height)
2931{
2932 int a = DODEC_A;
2933 int b = DODEC_B;
2934
2935 if (width > INT_MAX / (4*a + 2*b) || /* xextent */
2936 height > INT_MAX / (4*a + 2*b) || /* yextent */
2937 width > INT_MAX / 18 / height) /* max_dots */
2938 return "Grid must not be unreasonably large";
2939 return NULL;
2940}
2941
2942static void grid_size_compassdodecagonal(int width, int height,
2943 int *tilesize, int *xextent, int *yextent)
2944{
2945 int a = DODEC_A;
2946 int b = DODEC_B;
2947
2948 *tilesize = DODEC_TILESIZE;
2949 *xextent = (4*a + 2*b) * width;
2950 *yextent = (4*a + 2*b) * height;
2951}
2952
2953static grid *grid_new_compassdodecagonal(int width, int height, const char *desc)
2954{
2955 int x, y;
2956 /* Vector for side of triangle - ratio is close to sqrt(3) */
2957 int a = DODEC_A;
2958 int b = DODEC_B;
2959
2960 tree234 *points;
2961
2962 grid *g = grid_empty();
2963 g->tilesize = DODEC_TILESIZE;
2964
2965 points = newtree234(grid_point_cmp_fn);
2966
2967 for (y = 0; y < height; y++) {
2968 for (x = 0; x < width; x++) {
2969 grid_dot *d;
2970 /* centre of dodecagon */
2971 int px = (4*a + 2*b) * x;
2972 int py = (4*a + 2*b) * y;
2973
2974 /* dodecagon */
2975 grid_face_add_new(g, 12);
2976 d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0);
2977 d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1);
2978 d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2);
2979 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3);
2980 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4);
2981 d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5);
2982 d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6);
2983 d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7);
2984 d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8);
2985 d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9);
2986 d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10);
2987 d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11);
2988
2989 if (x < width - 1 && y < height - 1) {
2990 /* north triangle */
2991 grid_face_add_new(g, 3);
2992 d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 0);
2993 d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 1);
2994 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 2);
2995
2996 /* east triangle */
2997 grid_face_add_new(g, 3);
2998 d = grid_get_dot(g, points, px + (3*a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0);
2999 d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1);
3000 d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 2);
3001
3002 /* south triangle */
3003 grid_face_add_new(g, 3);
3004 d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 0);
3005 d = grid_get_dot(g, points, px + (2*a + b), py + (3*a + 2*b)); grid_face_set_dot(g, d, 1);
3006 d = grid_get_dot(g, points, px + ( a + b), py + (3*a + b)); grid_face_set_dot(g, d, 2);
3007
3008 /* west triangle */
3009 grid_face_add_new(g, 3);
3010 d = grid_get_dot(g, points, px + (a + b), py + ( a + b)); grid_face_set_dot(g, d, 0);
3011 d = grid_get_dot(g, points, px + (a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1);
3012 d = grid_get_dot(g, points, px + (a ), py + (2*a + b)); grid_face_set_dot(g, d, 2);
3013
3014 /* square in center */
3015 grid_face_add_new(g, 4);
3016 d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 0);
3017 d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1);
3018 d = grid_get_dot(g, points, px + ( a + b), py + (3*a + b)); grid_face_set_dot(g, d, 2);
3019 d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 3);
3020 }
3021 }
3022 }
3023
3024 freetree234(points);
3025
3026 grid_make_consistent(g);
3027 return g;
3028}
3029
3030/*
3031 * Penrose tilings. For historical reasons, we support two totally
3032 * different generation algorithms: the legacy one is only supported
3033 * by grid_new_penrose, for backwards compatibility with game
3034 * descriptions generated before we switched. New grid generation uses
3035 * only the new system.
3036 */
3037
3038#define PENROSE_TILESIZE 100
3039
3040static const char *grid_validate_params_penrose(int width, int height)
3041{
3042 int l = PENROSE_TILESIZE;
3043
3044 if (width > INT_MAX / l || /* xextent */
3045 height > INT_MAX / l || /* yextent */
3046 width > INT_MAX / (3 * 3 * 4 * height)) /* max_dots */
3047 return "Grid must not be unreasonably large";
3048 return NULL;
3049}
3050
3051static void grid_size_penrose(int width, int height,
3052 int *tilesize, int *xextent, int *yextent)
3053{
3054 int l = PENROSE_TILESIZE;
3055
3056 *tilesize = l;
3057 *xextent = l * width;
3058 *yextent = l * height;
3059}
3060
3061/*
3062 * Legacy generation by selecting a patch of tiling from the expansion
3063 * of a big triangle.
3064 */
3065
3066typedef struct penrose_legacy_set_faces_ctx {
3067 int xmin, xmax, ymin, ymax;
3068
3069 grid *g;
3070 tree234 *points;
3071} penrose_legacy_set_faces_ctx;
3072
3073static double round_int_nearest_away(double r)
3074{
3075 return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
3076}
3077
3078static int penrose_legacy_set_faces(penrose_legacy_state *state, vector *vs,
3079 int n, int depth)
3080{
3081 penrose_legacy_set_faces_ctx *sf_ctx =
3082 (penrose_legacy_set_faces_ctx *)state->ctx;
3083 int i;
3084 int xs[4], ys[4];
3085
3086 if (depth < state->max_depth) return 0;
3087#ifdef DEBUG_PENROSE
3088 if (n != 4) return 0; /* triangles are sent as debugging. */
3089#endif
3090
3091 for (i = 0; i < n; i++) {
3092 double tx = penrose_legacy_vx(vs, i), ty = penrose_legacy_vy(vs, i);
3093
3094 xs[i] = (int)round_int_nearest_away(tx);
3095 ys[i] = (int)round_int_nearest_away(ty);
3096
3097 if (xs[i] < sf_ctx->xmin || xs[i] > sf_ctx->xmax) return 0;
3098 if (ys[i] < sf_ctx->ymin || ys[i] > sf_ctx->ymax) return 0;
3099 }
3100
3101 grid_face_add_new(sf_ctx->g, n);
3102 debug(("penrose: new face l=%f gen=%d...",
3103 penrose_legacy_side_length(state->start_size, depth), depth));
3104 for (i = 0; i < n; i++) {
3105 grid_dot *d = grid_get_dot(sf_ctx->g, sf_ctx->points,
3106 xs[i], ys[i]);
3107 grid_face_set_dot(sf_ctx->g, d, i);
3108 debug((" ... dot 0x%x (%d,%d) (was %2.2f,%2.2f)",
3109 d, d->x, d->y, penrose_legacy_vx(vs, i),
3110 penrose_legacy_vy(vs, i)));
3111 }
3112
3113 return 0;
3114}
3115
3116static grid *grid_new_penrose_legacy(int width, int height, int which,
3117 const char *desc);
3118
3119static const char *grid_validate_desc_penrose_legacy(
3120 grid_type type, int width, int height, const char *desc)
3121{
3122 int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff, inner_radius;
3123 double outer_radius;
3124 int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
3125 grid *g;
3126
3127 if (!desc)
3128 return "Missing grid description string.";
3129
3130 penrose_legacy_calculate_size(which, tilesize, width, height,
3131 &outer_radius, &startsz, &depth);
3132 inner_radius = (int)(outer_radius - sqrt(width*width + height*height));
3133
3134 if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3)
3135 return "Invalid format grid description string.";
3136
3137 if (sqrt(xoff*xoff + yoff*yoff) > inner_radius)
3138 return "Patch offset out of bounds.";
3139 if ((aoff % 36) != 0 || aoff < 0 || aoff >= 360)
3140 return "Angle offset out of bounds.";
3141
3142 /*
3143 * Test-generate to ensure these parameters don't end us up with
3144 * no grid at all.
3145 */
3146 g = grid_new_penrose_legacy(width, height, which, desc);
3147 if (!g)
3148 return "Patch coordinates do not identify a usable grid fragment";
3149 grid_free(g);
3150
3151 return NULL;
3152}
3153
3154static grid *grid_new_penrose_legacy(int width, int height, int which,
3155 const char *desc)
3156{
3157 int tilesize = PENROSE_TILESIZE;
3158 int xsz, ysz, xoff, yoff, aoff;
3159 double rradius;
3160
3161 tree234 *points;
3162 grid *g;
3163
3164 penrose_legacy_state ps;
3165 penrose_legacy_set_faces_ctx sf_ctx;
3166
3167 penrose_legacy_calculate_size(which, tilesize, width, height,
3168 &rradius, &ps.start_size, &ps.max_depth);
3169
3170 debug(("penrose: w%d h%d, tile size %d, start size %d, depth %d",
3171 width, height, tilesize, ps.start_size, ps.max_depth));
3172
3173 ps.new_tile = penrose_legacy_set_faces;
3174 ps.ctx = &sf_ctx;
3175
3176 g = grid_empty();
3177 g->tilesize = tilesize;
3178
3179 points = newtree234(grid_point_cmp_fn);
3180
3181 memset(&sf_ctx, 0, sizeof(sf_ctx));
3182 sf_ctx.g = g;
3183 sf_ctx.points = points;
3184
3185 if (desc != NULL) {
3186 if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3)
3187 assert(!"Invalid grid description.");
3188 } else {
3189 xoff = yoff = aoff = 0;
3190 }
3191
3192 xsz = width * tilesize;
3193 ysz = height * tilesize;
3194
3195 sf_ctx.xmin = xoff - xsz/2;
3196 sf_ctx.xmax = xoff + xsz/2;
3197 sf_ctx.ymin = yoff - ysz/2;
3198 sf_ctx.ymax = yoff + ysz/2;
3199
3200 debug(("penrose: centre (%f, %f) xsz %f ysz %f",
3201 0.0, 0.0, xsz, ysz));
3202 debug(("penrose: x range (%f --> %f), y range (%f --> %f)",
3203 sf_ctx.xmin, sf_ctx.xmax, sf_ctx.ymin, sf_ctx.ymax));
3204
3205 penrose_legacy(&ps, which, aoff);
3206
3207 freetree234(points);
3208
3209 debug(("penrose: %d faces total (equivalent to %d wide by %d high)",
3210 g->num_faces, g->num_faces/height, g->num_faces/width));
3211
3212 /*
3213 * Return NULL if we ended up with an empty grid, either because
3214 * the initial generation was over too small a rectangle to
3215 * encompass any face or because grid_trim_vigorously ended up
3216 * removing absolutely everything.
3217 */
3218 if (g->num_faces == 0 || g->num_dots == 0) {
3219 grid_free(g);
3220 return NULL;
3221 }
3222 grid_trim_vigorously(g);
3223 if (g->num_faces == 0 || g->num_dots == 0) {
3224 grid_free(g);
3225 return NULL;
3226 }
3227
3228 grid_make_consistent(g);
3229
3230 /*
3231 * Centre the grid in its originally promised rectangle.
3232 */
3233 g->lowest_x -= ((sf_ctx.xmax - sf_ctx.xmin) -
3234 (g->highest_x - g->lowest_x)) / 2;
3235 g->highest_x = g->lowest_x + (sf_ctx.xmax - sf_ctx.xmin);
3236 g->lowest_y -= ((sf_ctx.ymax - sf_ctx.ymin) -
3237 (g->highest_y - g->lowest_y)) / 2;
3238 g->highest_y = g->lowest_y + (sf_ctx.ymax - sf_ctx.ymin);
3239
3240 return g;
3241}
3242
3243/*
3244 * Combinatorial-coordinate generation.
3245 *
3246 * We receive coordinates from the generator in the form of x,y pairs
3247 * each of which is an integer combination of 1 and sqrt(5), but those
3248 * pairs have different scale units in the x and y directions. The
3249 * scale units are 1/4 for x and sin(pi/5)/2 for y, which makes their
3250 * ratio equal to 2 sin(pi/5) ~= 1.1756. We fudge that irrational
3251 * aspect ratio into a rational approximation, by simply taking a pair
3252 * of integer scale factors for the x and y dimensions; this distorts
3253 * the output tiling slightly, but the distortion is consistent, and
3254 * doesn't accumulate over a large patch of tiling, so it won't make
3255 * anything end up totally out of place.
3256 *
3257 * (However, we compute the subsequent combination of 1 and sqrt(5)
3258 * exactly, because using an approximation to sqrt(5) _could_ mean
3259 * that in a sufficiently large patch of tiling two such combinations
3260 * ended up misordered.)
3261 *
3262 * Adding to the confusion, we also flip round the x and y
3263 * coordinates, because it's slightly nicer to have vertical edges in
3264 * the tiling rather than horizontal ones. (Both for aesthetics, and
3265 * also because if two P3 thin rhombs are separated by a horizontal
3266 * line and both contain numeric clues then the clue numbers look a
3267 * bit crowded, due to digits being taller than they are wide.)
3268 *
3269 * Finally, we have different base unit sizes for the two tiling
3270 * types, because sensible sizes for the two are actually different.
3271 * Each of P2 and P3 can be subdivided into the other, via dividing
3272 * the larger triangle type in two, so that L large and S small become
3273 * L+S large and L small. In the limit, this means that you expect the
3274 * number of triangles (hence tiles) to grow by a factor of phi in
3275 * each of those subdivisions (and hence by a factor of phi^2 in a
3276 * full subdivision of P2 to a finer P2). So a sensible size ratio
3277 * between the two tilings is one that makes them fit about the same
3278 * number of tiles into the same area - and since tile area is
3279 * proportional to _square_ of length, it follows that the P2 and P3
3280 * length unit should differ by a factor of sqrt(phi).
3281 */
3282#define PENROSE_XUNIT_P2 37
3283#define PENROSE_YUNIT_P2 44
3284#define PENROSE_XUNIT_P3 30
3285#define PENROSE_YUNIT_P3 35
3286
3287struct size { int w, h; };
3288static struct size api_size_penrose(int width, int height, int which)
3289{
3290 int xunit = (which == PENROSE_P2 ? PENROSE_XUNIT_P2 : PENROSE_XUNIT_P3);
3291 int yunit = (which == PENROSE_P2 ? PENROSE_YUNIT_P2 : PENROSE_YUNIT_P3);
3292 struct size size = {
3293 width * PENROSE_TILESIZE / yunit,
3294 height * PENROSE_TILESIZE / xunit,
3295 };
3296 return size;
3297}
3298
3299static grid *grid_new_penrose(int width, int height, int which,
3300 const char *desc); /* forward reference */
3301
3302static char *grid_new_desc_penrose(grid_type type, int width, int height,
3303 random_state *rs)
3304{
3305 char *buf;
3306 struct PenrosePatchParams params;
3307 int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
3308 struct size size = api_size_penrose(width, height, which);
3309
3310 penrose_tiling_randomise(¶ms, which, size.h, size.w, rs);
3311
3312 buf = snewn(params.ncoords + 3, char);
3313 buf[0] = '0' + params.orientation;
3314 buf[1] = '0' + params.start_vertex;
3315 memcpy(buf + 2, params.coords, params.ncoords);
3316 buf[2 + params.ncoords] = '\0';
3317
3318 sfree(params.coords);
3319 return buf;
3320}
3321
3322/* Shared code between validating and reading grid descs.
3323 * Always allocates params->coords, whether or not it returns an error. */
3324static const char *grid_desc_to_penrose_params(
3325 const char *desc, int which, struct PenrosePatchParams *params)
3326{
3327 int i;
3328
3329 if (!*desc)
3330 return "empty grid description";
3331
3332 params->ncoords = strlen(desc) - 2;
3333 params->coords = snewn(params->ncoords, char);
3334
3335 {
3336 char c = desc[0];
3337 if (isdigit((unsigned char)c))
3338 params->orientation = c - '0';
3339 else
3340 return "expected digit at start of grid description";
3341
3342 c = desc[1];
3343 if (c >= '0' && c < '3')
3344 params->start_vertex = c - '0';
3345 else
3346 return "expected digit as second char of grid description";
3347 }
3348
3349 for (i = 0; i < params->ncoords; i++) {
3350 char c = desc[i+2];
3351 if (!penrose_valid_letter(c, which))
3352 return "expected tile letter in grid description";
3353 params->coords[i] = c;
3354 }
3355
3356 return NULL;
3357}
3358
3359static const char *grid_validate_desc_penrose(grid_type type,
3360 int width, int height,
3361 const char *desc)
3362{
3363 struct PenrosePatchParams params;
3364 const char *error = NULL;
3365 int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3);
3366
3367 if (!desc)
3368 return "Missing grid description string.";
3369
3370 if (*desc == 'G')
3371 return grid_validate_desc_penrose_legacy(type, width, height, desc);
3372
3373 error = grid_desc_to_penrose_params(desc, which, ¶ms);
3374 if (!error)
3375 error = penrose_tiling_params_invalid(¶ms, which);
3376
3377 sfree(params.coords);
3378 return error;
3379}
3380
3381struct penrosecontext {
3382 grid *g;
3383 tree234 *points;
3384 int xunit, yunit;
3385};
3386
3387static void grid_penrose_callback(void *vctx, const int *coords)
3388{
3389 struct penrosecontext *ctx = (struct penrosecontext *)vctx;
3390 size_t i;
3391
3392 grid_face_add_new(ctx->g, 4);
3393 for (i = 0; i < 4; i++) {
3394 grid_dot *d = grid_get_dot(
3395 ctx->g, ctx->points,
3396 coords[4*i+2] * ctx->yunit + n_times_root_k(
3397 coords[4*i+3] * ctx->yunit, 5),
3398 coords[4*i+0] * ctx->xunit + n_times_root_k(
3399 coords[4*i+1] * ctx->xunit, 5));
3400 grid_face_set_dot(ctx->g, d, i);
3401 }
3402}
3403
3404static grid *grid_new_penrose(int width, int height, int which,
3405 const char *desc)
3406{
3407 struct PenrosePatchParams params;
3408 const char *error = NULL;
3409 struct penrosecontext ctx[1];
3410 struct size size;
3411
3412 if (*desc == 'G')
3413 return grid_new_penrose_legacy(width, height, which, desc);
3414
3415 error = grid_desc_to_penrose_params(desc, which, ¶ms);
3416 assert(error == NULL && "grid_validate_desc_penrose should have failed");
3417
3418 ctx->g = grid_empty();
3419 ctx->g->tilesize = PENROSE_TILESIZE;
3420
3421 ctx->points = newtree234(grid_point_cmp_fn);
3422
3423 ctx->xunit = (which == PENROSE_P2 ? PENROSE_XUNIT_P2 : PENROSE_XUNIT_P3);
3424 ctx->yunit = (which == PENROSE_P2 ? PENROSE_YUNIT_P2 : PENROSE_YUNIT_P3);
3425
3426 size = api_size_penrose(width, height, which);
3427 penrose_tiling_generate(¶ms, size.h, size.w,
3428 grid_penrose_callback, ctx);
3429
3430 freetree234(ctx->points);
3431 sfree(params.coords);
3432
3433 grid_trim_vigorously(ctx->g);
3434 grid_make_consistent(ctx->g);
3435
3436 /*
3437 * Centre the grid in its originally promised rectangle.
3438 */
3439 {
3440 int w = width * PENROSE_TILESIZE, h = height * PENROSE_TILESIZE;
3441 ctx->g->lowest_x -= (w - (ctx->g->highest_x - ctx->g->lowest_x))/2;
3442 ctx->g->lowest_y -= (h - (ctx->g->highest_y - ctx->g->lowest_y))/2;
3443 ctx->g->highest_x = ctx->g->lowest_x + w;
3444 ctx->g->highest_y = ctx->g->lowest_y + h;
3445 }
3446
3447 return ctx->g;
3448}
3449
3450static const char *grid_validate_params_penrose_p2_kite(int width, int height)
3451{
3452 return grid_validate_params_penrose(width, height);
3453}
3454
3455static const char *grid_validate_params_penrose_p3_thick(int width, int height)
3456{
3457 return grid_validate_params_penrose(width, height);
3458}
3459
3460static void grid_size_penrose_p2_kite(int width, int height,
3461 int *tilesize, int *xextent, int *yextent)
3462{
3463 grid_size_penrose(width, height, tilesize, xextent, yextent);
3464}
3465
3466static void grid_size_penrose_p3_thick(int width, int height,
3467 int *tilesize, int *xextent, int *yextent)
3468{
3469 grid_size_penrose(width, height, tilesize, xextent, yextent);
3470}
3471
3472static grid *grid_new_penrose_p2_kite(int width, int height, const char *desc)
3473{
3474 return grid_new_penrose(width, height, PENROSE_P2, desc);
3475}
3476
3477static grid *grid_new_penrose_p3_thick(int width, int height, const char *desc)
3478{
3479 return grid_new_penrose(width, height, PENROSE_P3, desc);
3480}
3481
3482#define HATS_TILESIZE 32
3483#define HATS_XSQUARELEN 4
3484#define HATS_YSQUARELEN 6
3485#define HATS_XUNIT 14
3486#define HATS_YUNIT 8
3487
3488static const char *grid_validate_params_hats(
3489 int width, int height)
3490{
3491 int l = HATS_TILESIZE;
3492
3493 if (width > INT_MAX / l || /* xextent */
3494 height > INT_MAX / l || /* yextent */
3495 width > INT_MAX / (6 * height)) /* max_dots */
3496 return "Grid must not be unreasonably large";
3497 return NULL;
3498}
3499
3500static void grid_size_hats(int width, int height,
3501 int *tilesize, int *xextent, int *yextent)
3502{
3503 *tilesize = HATS_TILESIZE;
3504 *xextent = width * HATS_XUNIT * HATS_XSQUARELEN;
3505 *yextent = height * HATS_YUNIT * HATS_YSQUARELEN;
3506}
3507
3508static char *grid_new_desc_hats(
3509 grid_type type, int width, int height, random_state *rs)
3510{
3511 char *buf, *p;
3512 size_t bufmax, i;
3513 struct HatPatchParams hp;
3514
3515 hat_tiling_randomise(&hp, width, height, rs);
3516
3517 bufmax = 3 * hp.ncoords + 2;
3518 buf = snewn(bufmax, char);
3519 p = buf;
3520 for (i = 0; i < hp.ncoords; i++) {
3521 assert(hp.coords[i] < 100); /* at most 2 digits */
3522 assert(p - buf <= bufmax-4); /* room for 2 digits, comma and NUL */
3523 p += sprintf(p, "%d,", (int)hp.coords[i]);
3524 }
3525 assert(p - buf <= bufmax-2); /* room for final letter and NUL */
3526 p[0] = hp.final_metatile;
3527 p[1] = '\0';
3528
3529 sfree(hp.coords);
3530 return buf;
3531}
3532
3533/* Shared code between validating and reading grid descs.
3534 * Always allocates hp->coords, whether or not it returns an error. */
3535static const char *grid_desc_to_hat_params(
3536 const char *desc, struct HatPatchParams *hp)
3537{
3538 size_t maxcoords;
3539 const char *p = desc;
3540
3541 maxcoords = (strlen(desc) + 1) / 2;
3542 hp->coords = snewn(maxcoords, unsigned char);
3543 hp->ncoords = 0;
3544
3545 while (isdigit((unsigned char)*p)) {
3546 const char *p_orig = p;
3547 int n = atoi(p);
3548 while (*p && isdigit((unsigned char)*p)) p++;
3549 if (*p != ',')
3550 return "expected ',' in grid description";
3551 if (p - p_orig > 2 || n > 0xFF)
3552 return "too-large coordinate in grid description";
3553 p++; /* eat the comma */
3554
3555 /* This assert should be guaranteed by the way we calculated
3556 * maxcoords, so a failure of this check is a bug in this
3557 * function, not an indication of an invalid input string */
3558 assert(hp->ncoords < maxcoords);
3559 hp->coords[hp->ncoords++] = n;
3560 }
3561
3562 if (*p == 'H' || *p == 'T' || *p == 'P' || *p == 'F')
3563 hp->final_metatile = *p;
3564 else
3565 return "invalid character in grid description";
3566
3567 return NULL;
3568}
3569
3570static const char *grid_validate_desc_hats(
3571 grid_type type, int width, int height, const char *desc)
3572{
3573 struct HatPatchParams hp;
3574 const char *error = NULL;
3575
3576 if (!desc)
3577 return "Missing grid description string.";
3578
3579 error = grid_desc_to_hat_params(desc, &hp);
3580 if (!error)
3581 error = hat_tiling_params_invalid(&hp);
3582
3583 sfree(hp.coords);
3584 return error;
3585}
3586
3587struct hatcontext {
3588 grid *g;
3589 tree234 *points;
3590};
3591
3592static void grid_hats_callback(void *vctx, size_t nvertices, int *coords)
3593{
3594 struct hatcontext *ctx = (struct hatcontext *)vctx;
3595 size_t i;
3596
3597 grid_face_add_new(ctx->g, nvertices);
3598 for (i = 0; i < nvertices; i++) {
3599 grid_dot *d = grid_get_dot(
3600 ctx->g, ctx->points,
3601 coords[2*i] * HATS_XUNIT,
3602 coords[2*i+1] * HATS_YUNIT);
3603 grid_face_set_dot(ctx->g, d, i);
3604 }
3605}
3606
3607static grid *grid_new_hats(int width, int height, const char *desc)
3608{
3609 struct HatPatchParams hp;
3610 const char *error = NULL;
3611
3612 error = grid_desc_to_hat_params(desc, &hp);
3613 assert(error == NULL && "grid_validate_desc_hats should have failed");
3614
3615 struct hatcontext ctx[1];
3616
3617 ctx->g = grid_empty();
3618 ctx->g->tilesize = HATS_TILESIZE;
3619
3620 ctx->points = newtree234(grid_point_cmp_fn);
3621
3622 hat_tiling_generate(&hp, width, height, grid_hats_callback, ctx);
3623
3624 freetree234(ctx->points);
3625 sfree(hp.coords);
3626
3627 grid_trim_vigorously(ctx->g);
3628 grid_make_consistent(ctx->g);
3629 return ctx->g;
3630}
3631
3632#define SPECTRE_TILESIZE 32
3633#define SPECTRE_SQUARELEN 7
3634#define SPECTRE_UNIT 8
3635
3636static const char *grid_validate_params_spectres(
3637 int width, int height)
3638{
3639 int l = SPECTRE_UNIT * SPECTRE_SQUARELEN;
3640
3641 if (width > INT_MAX / l || /* xextent */
3642 height > INT_MAX / l || /* yextent */
3643 width > (INT_MAX / SPECTRE_SQUARELEN /
3644 SPECTRE_SQUARELEN / height)) /* max_faces */
3645 return "Grid must not be unreasonably large";
3646 return NULL;
3647}
3648
3649static void grid_size_spectres(int width, int height,
3650 int *tilesize, int *xextent, int *yextent)
3651{
3652 *tilesize = SPECTRE_TILESIZE;
3653 *xextent = width * SPECTRE_UNIT * SPECTRE_SQUARELEN;
3654 *yextent = height * SPECTRE_UNIT * SPECTRE_SQUARELEN;
3655}
3656
3657static char *grid_new_desc_spectres(
3658 grid_type type, int width, int height, random_state *rs)
3659{
3660 char *buf;
3661 size_t i;
3662 struct SpectrePatchParams sp;
3663
3664 spectre_tiling_randomise(&sp, width * SPECTRE_SQUARELEN,
3665 height * SPECTRE_SQUARELEN, rs);
3666
3667 buf = snewn(sp.ncoords + 3, char);
3668 buf[0] = (sp.orientation < 10 ? '0' + sp.orientation :
3669 'A' + sp.orientation - 10);
3670 for (i = 0; i < sp.ncoords; i++) {
3671 assert(sp.coords[i] < 10); /* all indices are 1 digit */
3672 buf[i+1] = '0' + sp.coords[i];
3673 }
3674 buf[sp.ncoords+1] = sp.final_hex;
3675 buf[sp.ncoords+2] = '\0';
3676
3677 sfree(sp.coords);
3678 return buf;
3679}
3680
3681/* Shared code between validating and reading grid descs.
3682 * Always allocates sp->coords, whether or not it returns an error. */
3683static const char *grid_desc_to_spectre_params(
3684 const char *desc, struct SpectrePatchParams *sp)
3685{
3686 size_t i;
3687
3688 if (!*desc)
3689 return "empty grid description";
3690
3691 sp->ncoords = strlen(desc) - 2;
3692 sp->coords = snewn(sp->ncoords, unsigned char);
3693
3694 {
3695 char c = desc[0];
3696 if (isdigit((unsigned char)c))
3697 sp->orientation = c - '0';
3698 else if (c == 'A' || c == 'B')
3699 sp->orientation = 10 + c - 'A';
3700 else
3701 return "expected digit or A,B at start of grid description";
3702 }
3703
3704 for (i = 0; i < sp->ncoords; i++) {
3705 char c = desc[i+1];
3706 if (!isdigit((unsigned char)c))
3707 return "expected digit in grid description";
3708 sp->coords[i] = c - '0';
3709 }
3710
3711 sp->final_hex = desc[sp->ncoords+1];
3712
3713 return NULL;
3714}
3715
3716static const char *grid_validate_desc_spectres(
3717 grid_type type, int width, int height, const char *desc)
3718{
3719 struct SpectrePatchParams sp;
3720 const char *error = NULL;
3721
3722 if (!desc)
3723 return "Missing grid description string.";
3724
3725 error = grid_desc_to_spectre_params(desc, &sp);
3726 if (!error)
3727 error = spectre_tiling_params_invalid(&sp);
3728
3729 sfree(sp.coords);
3730 return error;
3731}
3732
3733struct spectrecontext {
3734 grid *g;
3735 tree234 *points;
3736};
3737
3738static void grid_spectres_callback(void *vctx, const int *coords)
3739{
3740 struct spectrecontext *ctx = (struct spectrecontext *)vctx;
3741 size_t i;
3742
3743 grid_face_add_new(ctx->g, SPECTRE_NVERTICES);
3744 for (i = 0; i < SPECTRE_NVERTICES; i++) {
3745 grid_dot *d = grid_get_dot(
3746 ctx->g, ctx->points,
3747 (coords[4*i+0] * SPECTRE_UNIT +
3748 n_times_root_k(coords[4*i+1] * SPECTRE_UNIT, 3)),
3749 (coords[4*i+2] * SPECTRE_UNIT +
3750 n_times_root_k(coords[4*i+3] * SPECTRE_UNIT, 3)));
3751 grid_face_set_dot(ctx->g, d, i);
3752 }
3753}
3754
3755static grid *grid_new_spectres(int width, int height, const char *desc)
3756{
3757 struct SpectrePatchParams sp;
3758 const char *error = NULL;
3759 int width2 = width * SPECTRE_SQUARELEN;
3760 int height2 = height * SPECTRE_SQUARELEN;
3761
3762 error = grid_desc_to_spectre_params(desc, &sp);
3763 assert(error == NULL && "grid_validate_desc_spectres should have failed");
3764
3765 struct spectrecontext ctx[1];
3766
3767 ctx->g = grid_empty();
3768 ctx->g->tilesize = SPECTRE_TILESIZE;
3769
3770 ctx->points = newtree234(grid_point_cmp_fn);
3771
3772 spectre_tiling_generate(&sp, width2, height2, grid_spectres_callback, ctx);
3773
3774 freetree234(ctx->points);
3775 sfree(sp.coords);
3776
3777 grid_trim_vigorously(ctx->g);
3778 grid_make_consistent(ctx->g);
3779
3780 /*
3781 * As with the Penrose tiling, we're likely to have different
3782 * sized margins due to the lack of a neat grid that this tiling
3783 * fits on. So now we know what tiles we're left with, recentre
3784 * them.
3785 */
3786 {
3787 int w = width2 * SPECTRE_UNIT, h = height2 * SPECTRE_UNIT;
3788 ctx->g->lowest_x -= (w - (ctx->g->highest_x - ctx->g->lowest_x))/2;
3789 ctx->g->lowest_y -= (h - (ctx->g->highest_y - ctx->g->lowest_y))/2;
3790 ctx->g->highest_x = ctx->g->lowest_x + w;
3791 ctx->g->highest_y = ctx->g->lowest_y + h;
3792 }
3793
3794 return ctx->g;
3795}
3796
3797/* ----------- End of grid generators ------------- */
3798
3799#define FNVAL(upper,lower) &grid_validate_params_ ## lower,
3800#define FNNEW(upper,lower) &grid_new_ ## lower,
3801#define FNSZ(upper,lower) &grid_size_ ## lower,
3802
3803static const char *(*(grid_validate_paramses[]))(int, int) =
3804 { GRIDGEN_LIST(FNVAL) };
3805static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) };
3806static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) };
3807
3808/* Work out if a grid can be made, and complain if not. */
3809
3810const char *grid_validate_params(grid_type type, int width, int height)
3811{
3812 if (width <= 0 || height <= 0)
3813 return "Width and height must both be positive";
3814 return grid_validate_paramses[type](width, height);
3815}
3816
3817char *grid_new_desc(grid_type type, int width, int height, random_state *rs)
3818{
3819 if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) {
3820 return grid_new_desc_penrose(type, width, height, rs);
3821 } else if (type == GRID_HATS) {
3822 return grid_new_desc_hats(type, width, height, rs);
3823 } else if (type == GRID_SPECTRES) {
3824 return grid_new_desc_spectres(type, width, height, rs);
3825 } else if (type == GRID_TRIANGULAR) {
3826 return dupstr("0"); /* up-to-date version of triangular grid */
3827 } else {
3828 return NULL;
3829 }
3830}
3831
3832const char *grid_validate_desc(grid_type type, int width, int height,
3833 const char *desc)
3834{
3835 if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) {
3836 return grid_validate_desc_penrose(type, width, height, desc);
3837 } else if (type == GRID_HATS) {
3838 return grid_validate_desc_hats(type, width, height, desc);
3839 } else if (type == GRID_SPECTRES) {
3840 return grid_validate_desc_spectres(type, width, height, desc);
3841 } else if (type == GRID_TRIANGULAR) {
3842 return grid_validate_desc_triangular(type, width, height, desc);
3843 } else {
3844 if (desc != NULL)
3845 return "Grid description strings not used with this grid type";
3846 return NULL;
3847 }
3848}
3849
3850grid *grid_new(grid_type type, int width, int height, const char *desc)
3851{
3852 const char *err = grid_validate_desc(type, width, height, desc);
3853 if (err) assert(!"Invalid grid description.");
3854
3855 return grid_news[type](width, height, desc);
3856}
3857
3858void grid_compute_size(grid_type type, int width, int height,
3859 int *tilesize, int *xextent, int *yextent)
3860{
3861 grid_sizes[type](width, height, tilesize, xextent, yextent);
3862}
3863
3864/* ----------- End of grid helpers ------------- */
3865
3866/* vim: set shiftwidth=4 tabstop=8: */