2 * (c) Lambros Lambrou 2008
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.
22 /* Debugging options */
28 /* ----------------------------------------------------------------------
29 * Deallocate or dereference a grid
31 void grid_free(grid
*g
)
36 if (g
->refcount
== 0) {
38 for (i
= 0; i
< g
->num_faces
; i
++) {
39 sfree(g
->faces
[i
].dots
);
40 sfree(g
->faces
[i
].edges
);
42 for (i
= 0; i
< g
->num_dots
; i
++) {
43 sfree(g
->dots
[i
].faces
);
44 sfree(g
->dots
[i
].edges
);
53 /* Used by the other grid generators. Create a brand new grid with nothing
54 * initialised (all lists are NULL) */
55 static grid
*grid_empty(void)
61 g
->num_faces
= g
->num_edges
= g
->num_dots
= 0;
63 g
->lowest_x
= g
->lowest_y
= g
->highest_x
= g
->highest_y
= 0;
67 /* Helper function to calculate perpendicular distance from
68 * a point P to a line AB. A and B mustn't be equal here.
70 * Well-known formula for area A of a triangle:
72 * 2A = determinant of matrix | px ax bx |
75 * Also well-known: 2A = base * height
76 * = perpendicular distance * line-length.
78 * Combining gives: distance = determinant / line-length(a,b)
80 static double point_line_distance(long px
, long py
,
84 long det
= ax
*by
- bx
*ay
+ bx
*py
- px
*by
+ px
*ay
- ax
*py
;
87 len
= sqrt(SQ(ax
- bx
) + SQ(ay
- by
));
91 /* Determine nearest edge to where the user clicked.
92 * (x, y) is the clicked location, converted to grid coordinates.
93 * Returns the nearest edge, or NULL if no edge is reasonably
96 * Just judging edges by perpendicular distance is not quite right -
97 * the edge might be "off to one side". So we insist that the triangle
98 * with (x,y) has acute angles at the edge's dots.
105 * | edge2 is OK, but edge1 is not, even though
106 * | edge1 is perpendicularly closer to (x,y)
110 grid_edge
*grid_nearest_edge(grid
*g
, int x
, int y
)
112 grid_edge
*best_edge
;
113 double best_distance
= 0;
118 for (i
= 0; i
< g
->num_edges
; i
++) {
119 grid_edge
*e
= &g
->edges
[i
];
120 long e2
; /* squared length of edge */
121 long a2
, b2
; /* squared lengths of other sides */
124 /* See if edge e is eligible - the triangle must have acute angles
125 * at the edge's dots.
126 * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
127 * so detect acute angles by testing for h^2 < a^2 + b^2 */
128 e2
= SQ((long)e
->dot1
->x
- (long)e
->dot2
->x
) + SQ((long)e
->dot1
->y
- (long)e
->dot2
->y
);
129 a2
= SQ((long)e
->dot1
->x
- (long)x
) + SQ((long)e
->dot1
->y
- (long)y
);
130 b2
= SQ((long)e
->dot2
->x
- (long)x
) + SQ((long)e
->dot2
->y
- (long)y
);
131 if (a2
>= e2
+ b2
) continue;
132 if (b2
>= e2
+ a2
) continue;
134 /* e is eligible so far. Now check the edge is reasonably close
135 * to where the user clicked. Don't want to toggle an edge if the
136 * click was way off the grid.
137 * There is room for experimentation here. We could check the
138 * perpendicular distance is within a certain fraction of the length
139 * of the edge. That amounts to testing a rectangular region around
141 * Alternatively, we could check that the angle at the point is obtuse.
142 * That would amount to testing a circular region with the edge as
144 dist
= point_line_distance((long)x
, (long)y
,
145 (long)e
->dot1
->x
, (long)e
->dot1
->y
,
146 (long)e
->dot2
->x
, (long)e
->dot2
->y
);
147 /* Is dist more than half edge length ? */
148 if (4 * SQ(dist
) > e2
)
151 if (best_edge
== NULL
|| dist
< best_distance
) {
153 best_distance
= dist
;
159 /* ----------------------------------------------------------------------
169 #define FACE_COLOUR "red"
170 #define EDGE_COLOUR "blue"
171 #define DOT_COLOUR "black"
173 static void grid_output_svg(FILE *fp
, grid
*g
, int which
)
178 <?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n\
179 <!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20010904//EN\"\n\
180 \"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n\
182 <svg xmlns=\"http://www.w3.org/2000/svg\"\n\
183 xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n");
185 if (which
& SVG_FACES
) {
186 fprintf(fp
, "<g>\n");
187 for (i
= 0; i
< g
->num_faces
; i
++) {
188 grid_face
*f
= g
->faces
+ i
;
189 fprintf(fp
, "<polygon points=\"");
190 for (j
= 0; j
< f
->order
; j
++) {
191 grid_dot
*d
= f
->dots
[j
];
192 fprintf(fp
, "%s%d,%d", (j
== 0) ?
"" : " ",
195 fprintf(fp
, "\" style=\"fill: %s; fill-opacity: 0.2; stroke: %s\" />\n",
196 FACE_COLOUR
, FACE_COLOUR
);
198 fprintf(fp
, "</g>\n");
200 if (which
& SVG_EDGES
) {
201 fprintf(fp
, "<g>\n");
202 for (i
= 0; i
< g
->num_edges
; i
++) {
203 grid_edge
*e
= g
->edges
+ i
;
204 grid_dot
*d1
= e
->dot1
, *d2
= e
->dot2
;
206 fprintf(fp
, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" "
207 "style=\"stroke: %s\" />\n",
208 d1
->x
, d1
->y
, d2
->x
, d2
->y
, EDGE_COLOUR
);
210 fprintf(fp
, "</g>\n");
213 if (which
& SVG_DOTS
) {
214 fprintf(fp
, "<g>\n");
215 for (i
= 0; i
< g
->num_dots
; i
++) {
216 grid_dot
*d
= g
->dots
+ i
;
217 fprintf(fp
, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />",
218 d
->x
, d
->y
, g
->tilesize
/20, g
->tilesize
/20, DOT_COLOUR
);
220 fprintf(fp
, "</g>\n");
223 fprintf(fp
, "</svg>\n");
230 static void grid_try_svg(grid
*g
, int which
)
232 char *svg
= getenv("PUZZLES_SVG_GRID");
234 FILE *svgf
= fopen(svg
, "w");
236 grid_output_svg(svgf
, g
, which
);
239 fprintf(stderr
, "Unable to open file `%s': %s", svg
, strerror(errno
));
245 /* Show the basic grid information, before doing grid_make_consistent */
246 static void grid_debug_basic(grid
*g
)
248 /* TODO: Maybe we should generate an SVG image of the dots and lines
249 * of the grid here, before grid_make_consistent.
250 * Would help with debugging grid generation. */
253 printf("--- Basic Grid Data ---\n");
254 for (i
= 0; i
< g
->num_faces
; i
++) {
255 grid_face
*f
= g
->faces
+ i
;
256 printf("Face %d: dots[", i
);
258 for (j
= 0; j
< f
->order
; j
++) {
259 grid_dot
*d
= f
->dots
[j
];
260 printf("%s%d", j ?
"," : "", (int)(d
- g
->dots
));
266 grid_try_svg(g
, SVG_FACES
);
270 /* Show the derived grid information, computed by grid_make_consistent */
271 static void grid_debug_derived(grid
*g
)
276 printf("--- Derived Grid Data ---\n");
277 for (i
= 0; i
< g
->num_edges
; i
++) {
278 grid_edge
*e
= g
->edges
+ i
;
279 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
280 i
, (int)(e
->dot1
- g
->dots
), (int)(e
->dot2
- g
->dots
),
281 e
->face1 ?
(int)(e
->face1
- g
->faces
) : -1,
282 e
->face2 ?
(int)(e
->face2
- g
->faces
) : -1);
285 for (i
= 0; i
< g
->num_faces
; i
++) {
286 grid_face
*f
= g
->faces
+ i
;
288 printf("Face %d: faces[", i
);
289 for (j
= 0; j
< f
->order
; j
++) {
290 grid_edge
*e
= f
->edges
[j
];
291 grid_face
*f2
= (e
->face1
== f
) ? e
->face2
: e
->face1
;
292 printf("%s%d", j ?
"," : "", f2 ?
(int)(f2
- g
->faces
) : -1);
297 for (i
= 0; i
< g
->num_dots
; i
++) {
298 grid_dot
*d
= g
->dots
+ i
;
300 printf("Dot %d: dots[", i
);
301 for (j
= 0; j
< d
->order
; j
++) {
302 grid_edge
*e
= d
->edges
[j
];
303 grid_dot
*d2
= (e
->dot1
== d
) ? e
->dot2
: e
->dot1
;
304 printf("%s%d", j ?
"," : "", (int)(d2
- g
->dots
));
307 for (j
= 0; j
< d
->order
; j
++) {
308 grid_face
*f
= d
->faces
[j
];
309 printf("%s%d", j ?
"," : "", f ?
(int)(f
- g
->faces
) : -1);
315 grid_try_svg(g
, SVG_DOTS
| SVG_EDGES
| SVG_FACES
);
319 /* Helper function for building incomplete-edges list in
320 * grid_make_consistent() */
321 static int grid_edge_bydots_cmpfn(void *v1
, void *v2
)
327 /* Pointer subtraction is valid here, because all dots point into the
328 * same dot-list (g->dots).
329 * Edges are not "normalised" - the 2 dots could be stored in any order,
330 * so we need to take this into account when comparing edges. */
332 /* Compare first dots */
333 da
= (a
->dot1
< a
->dot2
) ? a
->dot1
: a
->dot2
;
334 db
= (b
->dot1
< b
->dot2
) ? b
->dot1
: b
->dot2
;
337 /* Compare last dots */
338 da
= (a
->dot1
< a
->dot2
) ? a
->dot2
: a
->dot1
;
339 db
= (b
->dot1
< b
->dot2
) ? b
->dot2
: b
->dot1
;
347 * 'Vigorously trim' a grid, by which I mean deleting any isolated or
348 * uninteresting faces. By which, in turn, I mean: ensure that the
349 * grid is composed solely of faces adjacent to at least one
350 * 'landlocked' dot (i.e. one not in contact with the infinite
351 * exterior face), and that all those dots are in a single connected
354 * This function operates on, and returns, a grid satisfying the
355 * preconditions to grid_make_consistent() rather than the
356 * postconditions. (So call it first.)
358 static void grid_trim_vigorously(grid
*g
)
360 int *dotpairs
, *faces
, *dots
;
362 int i
, j
, k
, size
, newfaces
, newdots
;
365 * First construct a matrix in which each ordered pair of dots is
366 * mapped to the index of the face in which those dots occur in
369 dotpairs
= snewn(g
->num_dots
* g
->num_dots
, int);
370 for (i
= 0; i
< g
->num_dots
; i
++)
371 for (j
= 0; j
< g
->num_dots
; j
++)
372 dotpairs
[i
*g
->num_dots
+j
] = -1;
373 for (i
= 0; i
< g
->num_faces
; i
++) {
374 grid_face
*f
= g
->faces
+ i
;
375 int dot0
= f
->dots
[f
->order
-1] - g
->dots
;
376 for (j
= 0; j
< f
->order
; j
++) {
377 int dot1
= f
->dots
[j
] - g
->dots
;
378 dotpairs
[dot0
* g
->num_dots
+ dot1
] = i
;
384 * Now we can identify landlocked dots: they're the ones all of
385 * whose edges have a mirror-image counterpart in this matrix.
387 dots
= snewn(g
->num_dots
, int);
388 for (i
= 0; i
< g
->num_dots
; i
++) {
390 for (j
= 0; j
< g
->num_dots
; j
++) {
391 if ((dotpairs
[i
*g
->num_dots
+j
] >= 0) ^
392 (dotpairs
[j
*g
->num_dots
+i
] >= 0))
393 dots
[i
] = FALSE
; /* non-duplicated edge: coastal dot */
398 * Now identify connected pairs of landlocked dots, and form a dsf
401 dsf
= snew_dsf(g
->num_dots
);
402 for (i
= 0; i
< g
->num_dots
; i
++)
403 for (j
= 0; j
< i
; j
++)
404 if (dots
[i
] && dots
[j
] &&
405 dotpairs
[i
*g
->num_dots
+j
] >= 0 &&
406 dotpairs
[j
*g
->num_dots
+i
] >= 0)
407 dsf_merge(dsf
, i
, j
);
410 * Now look for the largest component.
414 for (i
= 0; i
< g
->num_dots
; i
++) {
416 if (dots
[i
] && dsf_canonify(dsf
, i
) == i
&&
417 (newsize
= dsf_size(dsf
, i
)) > size
) {
424 * Work out which faces we're going to keep (precisely those with
425 * at least one dot in the same connected component as j) and
426 * which dots (those required by any face we're keeping).
428 * At this point we reuse the 'dots' array to indicate the dots
429 * we're keeping, rather than the ones that are landlocked.
431 faces
= snewn(g
->num_faces
, int);
432 for (i
= 0; i
< g
->num_faces
; i
++)
434 for (i
= 0; i
< g
->num_dots
; i
++)
436 for (i
= 0; i
< g
->num_faces
; i
++) {
437 grid_face
*f
= g
->faces
+ i
;
439 for (k
= 0; k
< f
->order
; k
++)
440 if (dsf_canonify(dsf
, f
->dots
[k
] - g
->dots
) == j
)
444 for (k
= 0; k
< f
->order
; k
++)
445 dots
[f
->dots
[k
]-g
->dots
] = TRUE
;
450 * Work out the new indices of those faces and dots, when we
451 * compact the arrays containing them.
453 for (i
= newfaces
= 0; i
< g
->num_faces
; i
++)
454 faces
[i
] = (faces
[i
] ? newfaces
++ : -1);
455 for (i
= newdots
= 0; i
< g
->num_dots
; i
++)
456 dots
[i
] = (dots
[i
] ? newdots
++ : -1);
459 * Free the dynamically allocated 'dots' pointer lists in faces
460 * we're going to discard.
462 for (i
= 0; i
< g
->num_faces
; i
++)
464 sfree(g
->faces
[i
].dots
);
467 * Go through and compact the arrays.
469 for (i
= 0; i
< g
->num_dots
; i
++)
471 grid_dot
*dnew
= g
->dots
+ dots
[i
], *dold
= g
->dots
+ i
;
472 *dnew
= *dold
; /* structure copy */
474 for (i
= 0; i
< g
->num_faces
; i
++)
476 grid_face
*fnew
= g
->faces
+ faces
[i
], *fold
= g
->faces
+ i
;
477 *fnew
= *fold
; /* structure copy */
478 for (j
= 0; j
< fnew
->order
; j
++) {
480 * Reindex the dots in this face.
482 k
= fnew
->dots
[j
] - g
->dots
;
483 fnew
->dots
[j
] = g
->dots
+ dots
[k
];
486 g
->num_faces
= newfaces
;
487 g
->num_dots
= newdots
;
495 /* Input: grid has its dots and faces initialised:
496 * - dots have (optionally) x and y coordinates, but no edges or faces
497 * (pointers are NULL).
498 * - edges not initialised at all
499 * - faces initialised and know which dots they have (but no edges yet). The
500 * dots around each face are assumed to be clockwise.
502 * Output: grid is complete and valid with all relationships defined.
504 static void grid_make_consistent(grid
*g
)
507 tree234
*incomplete_edges
;
508 grid_edge
*next_new_edge
; /* Where new edge will go into g->edges */
512 /* ====== Stage 1 ======
516 /* We know how many dots and faces there are, so we can find the exact
517 * number of edges from Euler's polyhedral formula: F + V = E + 2 .
518 * We use "-1", not "-2" here, because Euler's formula includes the
519 * infinite face, which we don't count. */
520 g
->num_edges
= g
->num_faces
+ g
->num_dots
- 1;
521 assert(g
->num_edges
> 2);
522 g
->edges
= snewn(g
->num_edges
, grid_edge
);
523 next_new_edge
= g
->edges
;
525 /* Iterate over faces, and over each face's dots, generating edges as we
526 * go. As we find each new edge, we can immediately fill in the edge's
527 * dots, but only one of the edge's faces. Later on in the iteration, we
528 * will find the same edge again (unless it's on the border), but we will
529 * know the other face.
530 * For efficiency, maintain a list of the incomplete edges, sorted by
532 incomplete_edges
= newtree234(grid_edge_bydots_cmpfn
);
533 for (i
= 0; i
< g
->num_faces
; i
++) {
534 grid_face
*f
= g
->faces
+ i
;
536 for (j
= 0; j
< f
->order
; j
++) {
537 grid_edge e
; /* fake edge for searching */
538 grid_edge
*edge_found
;
543 e
.dot2
= f
->dots
[j2
];
544 /* Use del234 instead of find234, because we always want to
545 * remove the edge if found */
546 edge_found
= del234(incomplete_edges
, &e
);
548 /* This edge already added, so fill out missing face.
549 * Edge is already removed from incomplete_edges. */
550 edge_found
->face2
= f
;
552 assert(next_new_edge
- g
->edges
< g
->num_edges
);
553 next_new_edge
->dot1
= e
.dot1
;
554 next_new_edge
->dot2
= e
.dot2
;
555 next_new_edge
->face1
= f
;
556 next_new_edge
->face2
= NULL
; /* potentially infinite face */
557 add234(incomplete_edges
, next_new_edge
);
562 freetree234(incomplete_edges
);
564 /* ====== Stage 2 ======
565 * For each face, build its edge list.
568 /* Allocate space for each edge list. Can do this, because each face's
569 * edge-list is the same size as its dot-list. */
570 for (i
= 0; i
< g
->num_faces
; i
++) {
571 grid_face
*f
= g
->faces
+ i
;
573 f
->edges
= snewn(f
->order
, grid_edge
*);
574 /* Preload with NULLs, to help detect potential bugs. */
575 for (j
= 0; j
< f
->order
; j
++)
579 /* Iterate over each edge, and over both its faces. Add this edge to
580 * the face's edge-list, after finding where it should go in the
582 for (i
= 0; i
< g
->num_edges
; i
++) {
583 grid_edge
*e
= g
->edges
+ i
;
585 for (j
= 0; j
< 2; j
++) {
586 grid_face
*f
= j ? e
->face2
: e
->face1
;
588 if (f
== NULL
) continue;
589 /* Find one of the dots around the face */
590 for (k
= 0; k
< f
->order
; k
++) {
591 if (f
->dots
[k
] == e
->dot1
)
592 break; /* found dot1 */
594 assert(k
!= f
->order
); /* Must find the dot around this face */
596 /* Labelling scheme: as we walk clockwise around the face,
597 * starting at dot0 (f->dots[0]), we hit:
598 * (dot0), edge0, dot1, edge1, dot2,...
608 * Therefore, edgeK joins dotK and dot{K+1}
611 /* Around this face, either the next dot or the previous dot
612 * must be e->dot2. Otherwise the edge is wrong. */
616 if (f
->dots
[k2
] == e
->dot2
) {
617 /* dot1(k) and dot2(k2) go clockwise around this face, so add
618 * this edge at position k (see diagram). */
619 assert(f
->edges
[k
] == NULL
);
623 /* Try previous dot */
627 if (f
->dots
[k2
] == e
->dot2
) {
628 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
629 assert(f
->edges
[k2
] == NULL
);
633 assert(!"Grid broken: bad edge-face relationship");
637 /* ====== Stage 3 ======
638 * For each dot, build its edge-list and face-list.
641 /* We don't know how many edges/faces go around each dot, so we can't
642 * allocate the right space for these lists. Pre-compute the sizes by
643 * iterating over each edge and recording a tally against each dot. */
644 for (i
= 0; i
< g
->num_dots
; i
++) {
645 g
->dots
[i
].order
= 0;
647 for (i
= 0; i
< g
->num_edges
; i
++) {
648 grid_edge
*e
= g
->edges
+ i
;
652 /* Now we have the sizes, pre-allocate the edge and face lists. */
653 for (i
= 0; i
< g
->num_dots
; i
++) {
654 grid_dot
*d
= g
->dots
+ i
;
656 assert(d
->order
>= 2); /* sanity check */
657 d
->edges
= snewn(d
->order
, grid_edge
*);
658 d
->faces
= snewn(d
->order
, grid_face
*);
659 for (j
= 0; j
< d
->order
; j
++) {
664 /* For each dot, need to find a face that touches it, so we can seed
665 * the edge-face-edge-face process around each dot. */
666 for (i
= 0; i
< g
->num_faces
; i
++) {
667 grid_face
*f
= g
->faces
+ i
;
669 for (j
= 0; j
< f
->order
; j
++) {
670 grid_dot
*d
= f
->dots
[j
];
674 /* Each dot now has a face in its first slot. Generate the remaining
675 * faces and edges around the dot, by searching both clockwise and
676 * anticlockwise from the first face. Need to do both directions,
677 * because of the possibility of hitting the infinite face, which
678 * blocks progress. But there's only one such face, so we will
679 * succeed in finding every edge and face this way. */
680 for (i
= 0; i
< g
->num_dots
; i
++) {
681 grid_dot
*d
= g
->dots
+ i
;
682 int current_face1
= 0; /* ascends clockwise */
683 int current_face2
= 0; /* descends anticlockwise */
685 /* Labelling scheme: as we walk clockwise around the dot, starting
686 * at face0 (d->faces[0]), we hit:
687 * (face0), edge0, face1, edge1, face2,...
699 * So, for example, face1 should be joined to edge0 and edge1,
700 * and those edges should appear in an anticlockwise sense around
701 * that face (see diagram). */
703 /* clockwise search */
705 grid_face
*f
= d
->faces
[current_face1
];
709 /* find dot around this face */
710 for (j
= 0; j
< f
->order
; j
++) {
714 assert(j
!= f
->order
); /* must find dot */
716 /* Around f, required edge is anticlockwise from the dot. See
717 * the other labelling scheme higher up, for why we subtract 1
723 d
->edges
[current_face1
] = e
; /* set edge */
725 if (current_face1
== d
->order
)
729 d
->faces
[current_face1
] =
730 (e
->face1
== f
) ? e
->face2
: e
->face1
;
731 if (d
->faces
[current_face1
] == NULL
)
732 break; /* cannot progress beyond infinite face */
735 /* If the clockwise search made it all the way round, don't need to
736 * bother with the anticlockwise search. */
737 if (current_face1
== d
->order
)
738 continue; /* this dot is complete, move on to next dot */
740 /* anticlockwise search */
742 grid_face
*f
= d
->faces
[current_face2
];
746 /* find dot around this face */
747 for (j
= 0; j
< f
->order
; j
++) {
751 assert(j
!= f
->order
); /* must find dot */
753 /* Around f, required edge is clockwise from the dot. */
757 if (current_face2
== -1)
758 current_face2
= d
->order
- 1;
759 d
->edges
[current_face2
] = e
; /* set edge */
762 if (current_face2
== current_face1
)
764 d
->faces
[current_face2
] =
765 (e
->face1
== f
) ? e
->face2
: e
->face1
;
766 /* There's only 1 infinite face, so we must get all the way
767 * to current_face1 before we hit it. */
768 assert(d
->faces
[current_face2
]);
772 /* ====== Stage 4 ======
773 * Compute other grid settings
776 /* Bounding rectangle */
777 for (i
= 0; i
< g
->num_dots
; i
++) {
778 grid_dot
*d
= g
->dots
+ i
;
780 g
->lowest_x
= g
->highest_x
= d
->x
;
781 g
->lowest_y
= g
->highest_y
= d
->y
;
783 g
->lowest_x
= min(g
->lowest_x
, d
->x
);
784 g
->highest_x
= max(g
->highest_x
, d
->x
);
785 g
->lowest_y
= min(g
->lowest_y
, d
->y
);
786 g
->highest_y
= max(g
->highest_y
, d
->y
);
790 grid_debug_derived(g
);
793 /* Helpers for making grid-generation easier. These functions are only
794 * intended for use during grid generation. */
796 /* Comparison function for the (tree234) sorted dot list */
797 static int grid_point_cmp_fn(void *v1
, void *v2
)
802 return p2
->y
- p1
->y
;
804 return p2
->x
- p1
->x
;
806 /* Add a new face to the grid, with its dot list allocated.
807 * Assumes there's enough space allocated for the new face in grid->faces */
808 static void grid_face_add_new(grid
*g
, int face_size
)
811 grid_face
*new_face
= g
->faces
+ g
->num_faces
;
812 new_face
->order
= face_size
;
813 new_face
->dots
= snewn(face_size
, grid_dot
*);
814 for (i
= 0; i
< face_size
; i
++)
815 new_face
->dots
[i
] = NULL
;
816 new_face
->edges
= NULL
;
817 new_face
->has_incentre
= FALSE
;
820 /* Assumes dot list has enough space */
821 static grid_dot
*grid_dot_add_new(grid
*g
, int x
, int y
)
823 grid_dot
*new_dot
= g
->dots
+ g
->num_dots
;
825 new_dot
->edges
= NULL
;
826 new_dot
->faces
= NULL
;
832 /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
833 * in the dot_list, or add a new dot to the grid (and the dot_list) and
835 * Assumes g->dots has enough capacity allocated */
836 static grid_dot
*grid_get_dot(grid
*g
, tree234
*dot_list
, int x
, int y
)
845 ret
= find234(dot_list
, &test
, NULL
);
849 ret
= grid_dot_add_new(g
, x
, y
);
850 add234(dot_list
, ret
);
854 /* Sets the last face of the grid to include this dot, at this position
855 * around the face. Assumes num_faces is at least 1 (a new face has
856 * previously been added, with the required number of dots allocated) */
857 static void grid_face_set_dot(grid
*g
, grid_dot
*d
, int position
)
859 grid_face
*last_face
= g
->faces
+ g
->num_faces
- 1;
860 last_face
->dots
[position
] = d
;
864 * Helper routines for grid_find_incentre.
866 static int solve_2x2_matrix(double mx
[4], double vin
[2], double vout
[2])
870 det
= (mx
[0]*mx
[3] - mx
[1]*mx
[2]);
874 inv
[0] = mx
[3] / det
;
875 inv
[1] = -mx
[1] / det
;
876 inv
[2] = -mx
[2] / det
;
877 inv
[3] = mx
[0] / det
;
879 vout
[0] = inv
[0]*vin
[0] + inv
[1]*vin
[1];
880 vout
[1] = inv
[2]*vin
[0] + inv
[3]*vin
[1];
884 static int solve_3x3_matrix(double mx
[9], double vin
[3], double vout
[3])
889 det
= (mx
[0]*mx
[4]*mx
[8] + mx
[1]*mx
[5]*mx
[6] + mx
[2]*mx
[3]*mx
[7] -
890 mx
[0]*mx
[5]*mx
[7] - mx
[1]*mx
[3]*mx
[8] - mx
[2]*mx
[4]*mx
[6]);
894 inv
[0] = (mx
[4]*mx
[8] - mx
[5]*mx
[7]) / det
;
895 inv
[1] = (mx
[2]*mx
[7] - mx
[1]*mx
[8]) / det
;
896 inv
[2] = (mx
[1]*mx
[5] - mx
[2]*mx
[4]) / det
;
897 inv
[3] = (mx
[5]*mx
[6] - mx
[3]*mx
[8]) / det
;
898 inv
[4] = (mx
[0]*mx
[8] - mx
[2]*mx
[6]) / det
;
899 inv
[5] = (mx
[2]*mx
[3] - mx
[0]*mx
[5]) / det
;
900 inv
[6] = (mx
[3]*mx
[7] - mx
[4]*mx
[6]) / det
;
901 inv
[7] = (mx
[1]*mx
[6] - mx
[0]*mx
[7]) / det
;
902 inv
[8] = (mx
[0]*mx
[4] - mx
[1]*mx
[3]) / det
;
904 vout
[0] = inv
[0]*vin
[0] + inv
[1]*vin
[1] + inv
[2]*vin
[2];
905 vout
[1] = inv
[3]*vin
[0] + inv
[4]*vin
[1] + inv
[5]*vin
[2];
906 vout
[2] = inv
[6]*vin
[0] + inv
[7]*vin
[1] + inv
[8]*vin
[2];
911 void grid_find_incentre(grid_face
*f
)
913 double xbest
, ybest
, bestdist
;
915 grid_dot
*edgedot1
[3], *edgedot2
[3];
923 * Find the point in the polygon with the maximum distance to any
926 * Such a point must exist which is in contact with at least three
927 * edges and/or vertices. (Proof: if it's only in contact with two
928 * edges and/or vertices, it can't even be at a _local_ maximum -
929 * any such circle can always be expanded in some direction.) So
930 * we iterate through all 3-subsets of the combined set of edges
931 * and vertices; for each subset we generate one or two candidate
932 * points that might be the incentre, and then we vet each one to
933 * see if it's inside the polygon and what its maximum radius is.
935 * (There's one case which this algorithm will get noticeably
936 * wrong, and that's when a continuum of equally good answers
937 * exists due to parallel edges. Consider a long thin rectangle,
938 * for instance, or a parallelogram. This algorithm will pick a
939 * point near one end, and choose the end arbitrarily; obviously a
940 * nicer point to choose would be in the centre. To fix this I
941 * would have to introduce a special-case system which detected
942 * parallel edges in advance, set aside all candidate points
943 * generated using both edges in a parallel pair, and generated
944 * some additional candidate points half way between them. Also,
945 * of course, I'd have to cope with rounding error making such a
946 * point look worse than one of its endpoints. So I haven't done
947 * this for the moment, and will cross it if necessary when I come
950 * We don't actually iterate literally over _edges_, in the sense
951 * of grid_edge structures. Instead, we fill in edgedot1[] and
952 * edgedot2[] with a pair of dots adjacent in the face's list of
953 * vertices. This ensures that we get the edges in consistent
954 * orientation, which we could not do from the grid structure
955 * alone. (A moment's consideration of an order-3 vertex should
956 * make it clear that if a notional arrow was written on each
957 * edge, _at least one_ of the three faces bordering that vertex
958 * would have to have the two arrows tip-to-tip or tail-to-tail
959 * rather than tip-to-tail.)
965 for (i
= 0; i
+2 < 2*f
->order
; i
++) {
967 edgedot1
[nedges
] = f
->dots
[i
];
968 edgedot2
[nedges
++] = f
->dots
[(i
+1)%f
->order
];
970 dots
[ndots
++] = f
->dots
[i
- f
->order
];
972 for (j
= i
+1; j
+1 < 2*f
->order
; j
++) {
974 edgedot1
[nedges
] = f
->dots
[j
];
975 edgedot2
[nedges
++] = f
->dots
[(j
+1)%f
->order
];
977 dots
[ndots
++] = f
->dots
[j
- f
->order
];
979 for (k
= j
+1; k
< 2*f
->order
; k
++) {
980 double cx
[2], cy
[2]; /* candidate positions */
981 int cn
= 0; /* number of candidates */
984 edgedot1
[nedges
] = f
->dots
[k
];
985 edgedot2
[nedges
++] = f
->dots
[(k
+1)%f
->order
];
987 dots
[ndots
++] = f
->dots
[k
- f
->order
];
990 * Find a point, or pair of points, equidistant from
991 * all the specified edges and/or vertices.
995 * Three edges. This is a linear matrix equation:
996 * each row of the matrix represents the fact that
997 * the point (x,y) we seek is at distance r from
998 * that edge, and we solve three of those
999 * simultaneously to obtain x,y,r. (We ignore r.)
1001 double matrix
[9], vector
[3], vector2
[3];
1004 for (m
= 0; m
< 3; m
++) {
1005 int x1
= edgedot1
[m
]->x
, x2
= edgedot2
[m
]->x
;
1006 int y1
= edgedot1
[m
]->y
, y2
= edgedot2
[m
]->y
;
1007 int dx
= x2
-x1
, dy
= y2
-y1
;
1010 * ((x,y) - (x1,y1)) . (dy,-dx) = r |(dx,dy)|
1012 * => x dy - y dx - r |(dx,dy)| = (x1 dy - y1 dx)
1015 matrix
[3*m
+1] = -dx
;
1016 matrix
[3*m
+2] = -sqrt((double)dx
*dx
+(double)dy
*dy
);
1017 vector
[m
] = (double)x1
*dy
- (double)y1
*dx
;
1020 if (solve_3x3_matrix(matrix
, vector
, vector2
)) {
1021 cx
[cn
] = vector2
[0];
1022 cy
[cn
] = vector2
[1];
1025 } else if (nedges
== 2) {
1027 * Two edges and a dot. This will end up in a
1028 * quadratic equation.
1030 * First, look at the two edges. Having our point
1031 * be some distance r from both of them gives rise
1032 * to a pair of linear equations in x,y,r of the
1035 * (x-x1) dy - (y-y1) dx = r sqrt(dx^2+dy^2)
1037 * We eliminate r between those equations to give
1038 * us a single linear equation in x,y describing
1039 * the locus of points equidistant from both lines
1040 * - i.e. the angle bisector.
1042 * We then choose one of x,y to be a parameter t,
1043 * and derive linear formulae for x,y,r in terms
1044 * of t. This enables us to write down the
1045 * circular equation (x-xd)^2+(y-yd)^2=r^2 as a
1046 * quadratic in t; solving that and substituting
1047 * in for x,y gives us two candidate points.
1049 double eqs
[2][4]; /* a,b,c,d : ax+by+cr=d */
1050 double eq
[3]; /* a,b,c: ax+by=c */
1051 double xt
[2], yt
[2], rt
[2]; /* a,b: {x,y,r}=at+b */
1052 double q
[3]; /* a,b,c: at^2+bt+c=0 */
1055 /* Find equations of the two input lines. */
1056 for (m
= 0; m
< 2; m
++) {
1057 int x1
= edgedot1
[m
]->x
, x2
= edgedot2
[m
]->x
;
1058 int y1
= edgedot1
[m
]->y
, y2
= edgedot2
[m
]->y
;
1059 int dx
= x2
-x1
, dy
= y2
-y1
;
1063 eqs
[m
][2] = -sqrt(dx
*dx
+dy
*dy
);
1064 eqs
[m
][3] = x1
*dy
- y1
*dx
;
1067 /* Derive the angle bisector by eliminating r. */
1068 eq
[0] = eqs
[0][0]*eqs
[1][2] - eqs
[1][0]*eqs
[0][2];
1069 eq
[1] = eqs
[0][1]*eqs
[1][2] - eqs
[1][1]*eqs
[0][2];
1070 eq
[2] = eqs
[0][3]*eqs
[1][2] - eqs
[1][3]*eqs
[0][2];
1072 /* Parametrise x and y in terms of some t. */
1073 if (abs(eq
[0]) < abs(eq
[1])) {
1074 /* Parameter is x. */
1075 xt
[0] = 1; xt
[1] = 0;
1076 yt
[0] = -eq
[0]/eq
[1]; yt
[1] = eq
[2]/eq
[1];
1078 /* Parameter is y. */
1079 yt
[0] = 1; yt
[1] = 0;
1080 xt
[0] = -eq
[1]/eq
[0]; xt
[1] = eq
[2]/eq
[0];
1083 /* Find a linear representation of r using eqs[0]. */
1084 rt
[0] = -(eqs
[0][0]*xt
[0] + eqs
[0][1]*yt
[0])/eqs
[0][2];
1085 rt
[1] = (eqs
[0][3] - eqs
[0][0]*xt
[1] -
1086 eqs
[0][1]*yt
[1])/eqs
[0][2];
1088 /* Construct the quadratic equation. */
1089 q
[0] = -rt
[0]*rt
[0];
1090 q
[1] = -2*rt
[0]*rt
[1];
1091 q
[2] = -rt
[1]*rt
[1];
1092 q
[0] += xt
[0]*xt
[0];
1093 q
[1] += 2*xt
[0]*(xt
[1]-dots
[0]->x
);
1094 q
[2] += (xt
[1]-dots
[0]->x
)*(xt
[1]-dots
[0]->x
);
1095 q
[0] += yt
[0]*yt
[0];
1096 q
[1] += 2*yt
[0]*(yt
[1]-dots
[0]->y
);
1097 q
[2] += (yt
[1]-dots
[0]->y
)*(yt
[1]-dots
[0]->y
);
1100 disc
= q
[1]*q
[1] - 4*q
[0]*q
[2];
1106 t
= (-q
[1] + disc
) / (2*q
[0]);
1107 cx
[cn
] = xt
[0]*t
+ xt
[1];
1108 cy
[cn
] = yt
[0]*t
+ yt
[1];
1111 t
= (-q
[1] - disc
) / (2*q
[0]);
1112 cx
[cn
] = xt
[0]*t
+ xt
[1];
1113 cy
[cn
] = yt
[0]*t
+ yt
[1];
1116 } else if (nedges
== 1) {
1118 * Two dots and an edge. This one's another
1119 * quadratic equation.
1121 * The point we want must lie on the perpendicular
1122 * bisector of the two dots; that much is obvious.
1123 * So we can construct a parametrisation of that
1124 * bisecting line, giving linear formulae for x,y
1125 * in terms of t. We can also express the distance
1126 * from the edge as such a linear formula.
1128 * Then we set that equal to the radius of the
1129 * circle passing through the two points, which is
1130 * a Pythagoras exercise; that gives rise to a
1131 * quadratic in t, which we solve.
1133 double xt
[2], yt
[2], rt
[2]; /* a,b: {x,y,r}=at+b */
1134 double q
[3]; /* a,b,c: at^2+bt+c=0 */
1138 /* Find parametric formulae for x,y. */
1140 int x1
= dots
[0]->x
, x2
= dots
[1]->x
;
1141 int y1
= dots
[0]->y
, y2
= dots
[1]->y
;
1142 int dx
= x2
-x1
, dy
= y2
-y1
;
1143 double d
= sqrt((double)dx
*dx
+ (double)dy
*dy
);
1145 xt
[1] = (x1
+x2
)/2.0;
1146 yt
[1] = (y1
+y2
)/2.0;
1147 /* It's convenient if we have t at standard scale. */
1151 /* Also note down half the separation between
1152 * the dots, for use in computing the circle radius. */
1156 /* Find a parametric formula for r. */
1158 int x1
= edgedot1
[0]->x
, x2
= edgedot2
[0]->x
;
1159 int y1
= edgedot1
[0]->y
, y2
= edgedot2
[0]->y
;
1160 int dx
= x2
-x1
, dy
= y2
-y1
;
1161 double d
= sqrt((double)dx
*dx
+ (double)dy
*dy
);
1162 rt
[0] = (xt
[0]*dy
- yt
[0]*dx
) / d
;
1163 rt
[1] = ((xt
[1]-x1
)*dy
- (yt
[1]-y1
)*dx
) / d
;
1166 /* Construct the quadratic equation. */
1168 q
[1] = 2*rt
[0]*rt
[1];
1171 q
[2] -= halfsep
*halfsep
;
1174 disc
= q
[1]*q
[1] - 4*q
[0]*q
[2];
1180 t
= (-q
[1] + disc
) / (2*q
[0]);
1181 cx
[cn
] = xt
[0]*t
+ xt
[1];
1182 cy
[cn
] = yt
[0]*t
+ yt
[1];
1185 t
= (-q
[1] - disc
) / (2*q
[0]);
1186 cx
[cn
] = xt
[0]*t
+ xt
[1];
1187 cy
[cn
] = yt
[0]*t
+ yt
[1];
1190 } else if (nedges
== 0) {
1192 * Three dots. This is another linear matrix
1193 * equation, this time with each row of the matrix
1194 * representing the perpendicular bisector between
1195 * two of the points. Of course we only need two
1196 * such lines to find their intersection, so we
1197 * need only solve a 2x2 matrix equation.
1200 double matrix
[4], vector
[2], vector2
[2];
1203 for (m
= 0; m
< 2; m
++) {
1204 int x1
= dots
[m
]->x
, x2
= dots
[m
+1]->x
;
1205 int y1
= dots
[m
]->y
, y2
= dots
[m
+1]->y
;
1206 int dx
= x2
-x1
, dy
= y2
-y1
;
1209 * ((x,y) - (x1,y1)) . (dx,dy) = 1/2 |(dx,dy)|^2
1211 * => 2x dx + 2y dy = dx^2+dy^2 + (2 x1 dx + 2 y1 dy)
1213 matrix
[2*m
+0] = 2*dx
;
1214 matrix
[2*m
+1] = 2*dy
;
1215 vector
[m
] = ((double)dx
*dx
+ (double)dy
*dy
+
1216 2.0*x1
*dx
+ 2.0*y1
*dy
);
1219 if (solve_2x2_matrix(matrix
, vector
, vector2
)) {
1220 cx
[cn
] = vector2
[0];
1221 cy
[cn
] = vector2
[1];
1227 * Now go through our candidate points and see if any
1228 * of them are better than what we've got so far.
1230 for (m
= 0; m
< cn
; m
++) {
1231 double x
= cx
[m
], y
= cy
[m
];
1234 * First, disqualify the point if it's not inside
1235 * the polygon, which we work out by counting the
1236 * edges to the right of the point. (For
1237 * tiebreaking purposes when edges start or end on
1238 * our y-coordinate or go right through it, we
1239 * consider our point to be offset by a small
1240 * _positive_ epsilon in both the x- and
1244 for (e
= 0; e
< f
->order
; e
++) {
1245 int xs
= f
->edges
[e
]->dot1
->x
;
1246 int xe
= f
->edges
[e
]->dot2
->x
;
1247 int ys
= f
->edges
[e
]->dot1
->y
;
1248 int ye
= f
->edges
[e
]->dot2
->y
;
1249 if ((y
>= ys
&& y
< ye
) || (y
>= ye
&& y
< ys
)) {
1251 * The line goes past our y-position. Now we need
1252 * to know if its x-coordinate when it does so is
1255 * The x-coordinate in question is mathematically
1256 * (y - ys) * (xe - xs) / (ye - ys), and we want
1257 * to know whether (x - xs) >= that. Of course we
1258 * avoid the division, so we can work in integers;
1259 * to do this we must multiply both sides of the
1260 * inequality by ye - ys, which means we must
1261 * first check that's not negative.
1263 int num
= xe
- xs
, denom
= ye
- ys
;
1268 if ((x
- xs
) * denom
>= (y
- ys
) * num
)
1275 double mindist
= HUGE_VAL
;
1278 double mindist
= DBL_MAX
;
1280 #error No way to get maximum floating-point number.
1286 * This point is inside the polygon, so now we check
1287 * its minimum distance to every edge and corner.
1288 * First the corners ...
1290 for (d
= 0; d
< f
->order
; d
++) {
1291 int xp
= f
->dots
[d
]->x
;
1292 int yp
= f
->dots
[d
]->y
;
1293 double dx
= x
- xp
, dy
= y
- yp
;
1294 double dist
= dx
*dx
+ dy
*dy
;
1300 * ... and now also check the perpendicular distance
1301 * to every edge, if the perpendicular lies between
1302 * the edge's endpoints.
1304 for (e
= 0; e
< f
->order
; e
++) {
1305 int xs
= f
->edges
[e
]->dot1
->x
;
1306 int xe
= f
->edges
[e
]->dot2
->x
;
1307 int ys
= f
->edges
[e
]->dot1
->y
;
1308 int ye
= f
->edges
[e
]->dot2
->y
;
1311 * If s and e are our endpoints, and p our
1312 * candidate circle centre, the foot of a
1313 * perpendicular from p to the line se lies
1314 * between s and e if and only if (p-s).(e-s) lies
1315 * strictly between 0 and (e-s).(e-s).
1317 int edx
= xe
- xs
, edy
= ye
- ys
;
1318 double pdx
= x
- xs
, pdy
= y
- ys
;
1319 double pde
= pdx
* edx
+ pdy
* edy
;
1320 long ede
= (long)edx
* edx
+ (long)edy
* edy
;
1321 if (0 < pde
&& pde
< ede
) {
1323 * Yes, the nearest point on this edge is
1324 * closer than either endpoint, so we must
1325 * take it into account by measuring the
1326 * perpendicular distance to the edge and
1327 * checking its square against mindist.
1330 double pdre
= pdx
* edy
- pdy
* edx
;
1331 double sqlen
= pdre
* pdre
/ ede
;
1333 if (mindist
> sqlen
)
1339 * Right. Now we know the biggest circle around this
1340 * point, so we can check it against bestdist.
1342 if (bestdist
< mindist
) {
1366 assert(bestdist
> 0);
1368 f
->has_incentre
= TRUE
;
1369 f
->ix
= xbest
+ 0.5; /* round to nearest */
1370 f
->iy
= ybest
+ 0.5;
1373 /* Generate the dual to a grid
1374 * Returns a new dynamically-allocated grid whose dots are the
1375 * faces of the input, and whose faces are the dots of the input.
1376 * A few modifications are made: dots on input that have only two
1377 * edges are deleted, and the infinite exterior face is also removed
1378 * before conversion.
1380 static grid
*grid_dual(grid
*g
)
1386 new_g
= grid_empty();
1387 new_g
->tilesize
= g
->tilesize
;
1388 new_g
->faces
= snewn(g
->num_dots
, grid_face
);
1389 new_g
->dots
= snewn(g
->num_faces
, grid_dot
);
1390 debug(("taking the dual of a grid with %d faces and %d dots\n",
1391 g
->num_faces
,g
->num_dots
));
1393 points
= newtree234(grid_point_cmp_fn
);
1395 for (i
=0;i
<g
->num_faces
;i
++)
1397 grid_find_incentre(&(g
->faces
[i
]));
1399 for (i
=0;i
<g
->num_dots
;i
++)
1407 for (j
=0;j
<d
->order
;j
++)
1409 if (!d
->faces
[j
]) order
--;
1413 grid_face_add_new(new_g
, order
);
1414 for (j
=0;j
<d
->order
;j
++)
1419 new_d
= grid_get_dot(new_g
, points
,
1420 d
->faces
[j
]->ix
, d
->faces
[j
]->iy
);
1421 grid_face_set_dot(new_g
, new_d
, j
);
1427 freetree234(points
);
1428 assert(new_g
->num_faces
<= g
->num_dots
);
1429 assert(new_g
->num_dots
<= g
->num_faces
);
1431 debug(("dual has %d faces and %d dots\n",
1432 new_g
->num_faces
,new_g
->num_dots
));
1433 grid_make_consistent(new_g
);
1436 /* ------ Generate various types of grid ------ */
1438 /* General method is to generate faces, by calculating their dot coordinates.
1439 * As new faces are added, we keep track of all the dots so we can tell when
1440 * a new face reuses an existing dot. For example, two squares touching at an
1441 * edge would generate six unique dots: four dots from the first face, then
1442 * two additional dots for the second face, because we detect the other two
1443 * dots have already been taken up. This list is stored in a tree234
1444 * called "points". No extra memory-allocation needed here - we store the
1445 * actual grid_dot* pointers, which all point into the g->dots list.
1446 * For this reason, we have to calculate coordinates in such a way as to
1447 * eliminate any rounding errors, so we can detect when a dot on one
1448 * face precisely lands on a dot of a different face. No floating-point
1452 #define SQUARE_TILESIZE 20
1454 static void grid_size_square(int width
, int height
,
1455 int *tilesize
, int *xextent
, int *yextent
)
1457 int a
= SQUARE_TILESIZE
;
1460 *xextent
= width
* a
;
1461 *yextent
= height
* a
;
1464 static grid
*grid_new_square(int width
, int height
, char *desc
)
1468 int a
= SQUARE_TILESIZE
;
1470 /* Upper bounds - don't have to be exact */
1471 int max_faces
= width
* height
;
1472 int max_dots
= (width
+ 1) * (height
+ 1);
1476 grid
*g
= grid_empty();
1478 g
->faces
= snewn(max_faces
, grid_face
);
1479 g
->dots
= snewn(max_dots
, grid_dot
);
1481 points
= newtree234(grid_point_cmp_fn
);
1483 /* generate square faces */
1484 for (y
= 0; y
< height
; y
++) {
1485 for (x
= 0; x
< width
; x
++) {
1491 grid_face_add_new(g
, 4);
1492 d
= grid_get_dot(g
, points
, px
, py
);
1493 grid_face_set_dot(g
, d
, 0);
1494 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1495 grid_face_set_dot(g
, d
, 1);
1496 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
);
1497 grid_face_set_dot(g
, d
, 2);
1498 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1499 grid_face_set_dot(g
, d
, 3);
1503 freetree234(points
);
1504 assert(g
->num_faces
<= max_faces
);
1505 assert(g
->num_dots
<= max_dots
);
1507 grid_make_consistent(g
);
1511 #define HONEY_TILESIZE 45
1512 /* Vector for side of hexagon - ratio is close to sqrt(3) */
1516 static void grid_size_honeycomb(int width
, int height
,
1517 int *tilesize
, int *xextent
, int *yextent
)
1522 *tilesize
= HONEY_TILESIZE
;
1523 *xextent
= (3 * a
* (width
-1)) + 4*a
;
1524 *yextent
= (2 * b
* (height
-1)) + 3*b
;
1527 static grid
*grid_new_honeycomb(int width
, int height
, char *desc
)
1533 /* Upper bounds - don't have to be exact */
1534 int max_faces
= width
* height
;
1535 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
1539 grid
*g
= grid_empty();
1540 g
->tilesize
= HONEY_TILESIZE
;
1541 g
->faces
= snewn(max_faces
, grid_face
);
1542 g
->dots
= snewn(max_dots
, grid_dot
);
1544 points
= newtree234(grid_point_cmp_fn
);
1546 /* generate hexagonal faces */
1547 for (y
= 0; y
< height
; y
++) {
1548 for (x
= 0; x
< width
; x
++) {
1555 grid_face_add_new(g
, 6);
1557 d
= grid_get_dot(g
, points
, cx
- a
, cy
- b
);
1558 grid_face_set_dot(g
, d
, 0);
1559 d
= grid_get_dot(g
, points
, cx
+ a
, cy
- b
);
1560 grid_face_set_dot(g
, d
, 1);
1561 d
= grid_get_dot(g
, points
, cx
+ 2*a
, cy
);
1562 grid_face_set_dot(g
, d
, 2);
1563 d
= grid_get_dot(g
, points
, cx
+ a
, cy
+ b
);
1564 grid_face_set_dot(g
, d
, 3);
1565 d
= grid_get_dot(g
, points
, cx
- a
, cy
+ b
);
1566 grid_face_set_dot(g
, d
, 4);
1567 d
= grid_get_dot(g
, points
, cx
- 2*a
, cy
);
1568 grid_face_set_dot(g
, d
, 5);
1572 freetree234(points
);
1573 assert(g
->num_faces
<= max_faces
);
1574 assert(g
->num_dots
<= max_dots
);
1576 grid_make_consistent(g
);
1580 #define TRIANGLE_TILESIZE 18
1581 /* Vector for side of triangle - ratio is close to sqrt(3) */
1582 #define TRIANGLE_VEC_X 15
1583 #define TRIANGLE_VEC_Y 26
1585 static void grid_size_triangular(int width
, int height
,
1586 int *tilesize
, int *xextent
, int *yextent
)
1588 int vec_x
= TRIANGLE_VEC_X
;
1589 int vec_y
= TRIANGLE_VEC_Y
;
1591 *tilesize
= TRIANGLE_TILESIZE
;
1592 *xextent
= width
* 2 * vec_x
+ vec_x
;
1593 *yextent
= height
* vec_y
;
1596 /* Doesn't use the previous method of generation, it pre-dates it!
1597 * A triangular grid is just about simple enough to do by "brute force" */
1598 static grid
*grid_new_triangular(int width
, int height
, char *desc
)
1602 /* Vector for side of triangle - ratio is close to sqrt(3) */
1603 int vec_x
= TRIANGLE_VEC_X
;
1604 int vec_y
= TRIANGLE_VEC_Y
;
1608 /* convenient alias */
1611 grid
*g
= grid_empty();
1612 g
->tilesize
= TRIANGLE_TILESIZE
;
1614 g
->num_faces
= width
* height
* 2;
1615 g
->num_dots
= (width
+ 1) * (height
+ 1);
1616 g
->faces
= snewn(g
->num_faces
, grid_face
);
1617 g
->dots
= snewn(g
->num_dots
, grid_dot
);
1621 for (y
= 0; y
<= height
; y
++) {
1622 for (x
= 0; x
<= width
; x
++) {
1623 grid_dot
*d
= g
->dots
+ index
;
1624 /* odd rows are offset to the right */
1628 d
->x
= x
* 2 * vec_x
+ ((y
% 2) ? vec_x
: 0);
1634 /* generate faces */
1636 for (y
= 0; y
< height
; y
++) {
1637 for (x
= 0; x
< width
; x
++) {
1638 /* initialise two faces for this (x,y) */
1639 grid_face
*f1
= g
->faces
+ index
;
1640 grid_face
*f2
= f1
+ 1;
1643 f1
->dots
= snewn(f1
->order
, grid_dot
*);
1644 f1
->has_incentre
= FALSE
;
1647 f2
->dots
= snewn(f2
->order
, grid_dot
*);
1648 f2
->has_incentre
= FALSE
;
1650 /* face descriptions depend on whether the row-number is
1653 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
1654 f1
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
1655 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
1656 f2
->dots
[0] = g
->dots
+ y
* w
+ x
;
1657 f2
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
1658 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
1660 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
1661 f1
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
1662 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
1663 f2
->dots
[0] = g
->dots
+ y
* w
+ x
+ 1;
1664 f2
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
1665 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
1671 grid_make_consistent(g
);
1675 #define SNUBSQUARE_TILESIZE 18
1676 /* Vector for side of triangle - ratio is close to sqrt(3) */
1677 #define SNUBSQUARE_A 15
1678 #define SNUBSQUARE_B 26
1680 static void grid_size_snubsquare(int width
, int height
,
1681 int *tilesize
, int *xextent
, int *yextent
)
1683 int a
= SNUBSQUARE_A
;
1684 int b
= SNUBSQUARE_B
;
1686 *tilesize
= SNUBSQUARE_TILESIZE
;
1687 *xextent
= (a
+b
) * (width
-1) + a
+ b
;
1688 *yextent
= (a
+b
) * (height
-1) + a
+ b
;
1691 static grid
*grid_new_snubsquare(int width
, int height
, char *desc
)
1694 int a
= SNUBSQUARE_A
;
1695 int b
= SNUBSQUARE_B
;
1697 /* Upper bounds - don't have to be exact */
1698 int max_faces
= 3 * width
* height
;
1699 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
1703 grid
*g
= grid_empty();
1704 g
->tilesize
= SNUBSQUARE_TILESIZE
;
1705 g
->faces
= snewn(max_faces
, grid_face
);
1706 g
->dots
= snewn(max_dots
, grid_dot
);
1708 points
= newtree234(grid_point_cmp_fn
);
1710 for (y
= 0; y
< height
; y
++) {
1711 for (x
= 0; x
< width
; x
++) {
1714 int px
= (a
+ b
) * x
;
1715 int py
= (a
+ b
) * y
;
1717 /* generate square faces */
1718 grid_face_add_new(g
, 4);
1720 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1721 grid_face_set_dot(g
, d
, 0);
1722 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
1723 grid_face_set_dot(g
, d
, 1);
1724 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
+ b
);
1725 grid_face_set_dot(g
, d
, 2);
1726 d
= grid_get_dot(g
, points
, px
, py
+ b
);
1727 grid_face_set_dot(g
, d
, 3);
1729 d
= grid_get_dot(g
, points
, px
+ b
, py
);
1730 grid_face_set_dot(g
, d
, 0);
1731 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ b
);
1732 grid_face_set_dot(g
, d
, 1);
1733 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
1734 grid_face_set_dot(g
, d
, 2);
1735 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1736 grid_face_set_dot(g
, d
, 3);
1739 /* generate up/down triangles */
1741 grid_face_add_new(g
, 3);
1743 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1744 grid_face_set_dot(g
, d
, 0);
1745 d
= grid_get_dot(g
, points
, px
, py
+ b
);
1746 grid_face_set_dot(g
, d
, 1);
1747 d
= grid_get_dot(g
, points
, px
- a
, py
);
1748 grid_face_set_dot(g
, d
, 2);
1750 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1751 grid_face_set_dot(g
, d
, 0);
1752 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
1753 grid_face_set_dot(g
, d
, 1);
1754 d
= grid_get_dot(g
, points
, px
- a
, py
+ a
+ b
);
1755 grid_face_set_dot(g
, d
, 2);
1759 /* generate left/right triangles */
1761 grid_face_add_new(g
, 3);
1763 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1764 grid_face_set_dot(g
, d
, 0);
1765 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
- a
);
1766 grid_face_set_dot(g
, d
, 1);
1767 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
1768 grid_face_set_dot(g
, d
, 2);
1770 d
= grid_get_dot(g
, points
, px
, py
- a
);
1771 grid_face_set_dot(g
, d
, 0);
1772 d
= grid_get_dot(g
, points
, px
+ b
, py
);
1773 grid_face_set_dot(g
, d
, 1);
1774 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1775 grid_face_set_dot(g
, d
, 2);
1781 freetree234(points
);
1782 assert(g
->num_faces
<= max_faces
);
1783 assert(g
->num_dots
<= max_dots
);
1785 grid_make_consistent(g
);
1789 #define CAIRO_TILESIZE 40
1790 /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
1794 static void grid_size_cairo(int width
, int height
,
1795 int *tilesize
, int *xextent
, int *yextent
)
1797 int b
= CAIRO_B
; /* a unused in determining grid size. */
1799 *tilesize
= CAIRO_TILESIZE
;
1800 *xextent
= 2*b
*(width
-1) + 2*b
;
1801 *yextent
= 2*b
*(height
-1) + 2*b
;
1804 static grid
*grid_new_cairo(int width
, int height
, char *desc
)
1810 /* Upper bounds - don't have to be exact */
1811 int max_faces
= 2 * width
* height
;
1812 int max_dots
= 3 * (width
+ 1) * (height
+ 1);
1816 grid
*g
= grid_empty();
1817 g
->tilesize
= CAIRO_TILESIZE
;
1818 g
->faces
= snewn(max_faces
, grid_face
);
1819 g
->dots
= snewn(max_dots
, grid_dot
);
1821 points
= newtree234(grid_point_cmp_fn
);
1823 for (y
= 0; y
< height
; y
++) {
1824 for (x
= 0; x
< width
; x
++) {
1830 /* horizontal pentagons */
1832 grid_face_add_new(g
, 5);
1834 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
1835 grid_face_set_dot(g
, d
, 0);
1836 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
- b
);
1837 grid_face_set_dot(g
, d
, 1);
1838 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1839 grid_face_set_dot(g
, d
, 2);
1840 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1841 grid_face_set_dot(g
, d
, 3);
1842 d
= grid_get_dot(g
, points
, px
, py
);
1843 grid_face_set_dot(g
, d
, 4);
1845 d
= grid_get_dot(g
, points
, px
, py
);
1846 grid_face_set_dot(g
, d
, 0);
1847 d
= grid_get_dot(g
, points
, px
+ b
, py
- a
);
1848 grid_face_set_dot(g
, d
, 1);
1849 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1850 grid_face_set_dot(g
, d
, 2);
1851 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
+ b
);
1852 grid_face_set_dot(g
, d
, 3);
1853 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1854 grid_face_set_dot(g
, d
, 4);
1857 /* vertical pentagons */
1859 grid_face_add_new(g
, 5);
1861 d
= grid_get_dot(g
, points
, px
, py
);
1862 grid_face_set_dot(g
, d
, 0);
1863 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1864 grid_face_set_dot(g
, d
, 1);
1865 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 2*b
- a
);
1866 grid_face_set_dot(g
, d
, 2);
1867 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1868 grid_face_set_dot(g
, d
, 3);
1869 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1870 grid_face_set_dot(g
, d
, 4);
1872 d
= grid_get_dot(g
, points
, px
, py
);
1873 grid_face_set_dot(g
, d
, 0);
1874 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1875 grid_face_set_dot(g
, d
, 1);
1876 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1877 grid_face_set_dot(g
, d
, 2);
1878 d
= grid_get_dot(g
, points
, px
- b
, py
+ 2*b
- a
);
1879 grid_face_set_dot(g
, d
, 3);
1880 d
= grid_get_dot(g
, points
, px
- b
, py
+ a
);
1881 grid_face_set_dot(g
, d
, 4);
1887 freetree234(points
);
1888 assert(g
->num_faces
<= max_faces
);
1889 assert(g
->num_dots
<= max_dots
);
1891 grid_make_consistent(g
);
1895 #define GREATHEX_TILESIZE 18
1896 /* Vector for side of triangle - ratio is close to sqrt(3) */
1897 #define GREATHEX_A 15
1898 #define GREATHEX_B 26
1900 static void grid_size_greathexagonal(int width
, int height
,
1901 int *tilesize
, int *xextent
, int *yextent
)
1906 *tilesize
= GREATHEX_TILESIZE
;
1907 *xextent
= (3*a
+ b
) * (width
-1) + 4*a
;
1908 *yextent
= (2*a
+ 2*b
) * (height
-1) + 3*b
+ a
;
1911 static grid
*grid_new_greathexagonal(int width
, int height
, char *desc
)
1917 /* Upper bounds - don't have to be exact */
1918 int max_faces
= 6 * (width
+ 1) * (height
+ 1);
1919 int max_dots
= 6 * width
* height
;
1923 grid
*g
= grid_empty();
1924 g
->tilesize
= GREATHEX_TILESIZE
;
1925 g
->faces
= snewn(max_faces
, grid_face
);
1926 g
->dots
= snewn(max_dots
, grid_dot
);
1928 points
= newtree234(grid_point_cmp_fn
);
1930 for (y
= 0; y
< height
; y
++) {
1931 for (x
= 0; x
< width
; x
++) {
1933 /* centre of hexagon */
1934 int px
= (3*a
+ b
) * x
;
1935 int py
= (2*a
+ 2*b
) * y
;
1940 grid_face_add_new(g
, 6);
1941 d
= grid_get_dot(g
, points
, px
- a
, py
- b
);
1942 grid_face_set_dot(g
, d
, 0);
1943 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
1944 grid_face_set_dot(g
, d
, 1);
1945 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1946 grid_face_set_dot(g
, d
, 2);
1947 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1948 grid_face_set_dot(g
, d
, 3);
1949 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1950 grid_face_set_dot(g
, d
, 4);
1951 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1952 grid_face_set_dot(g
, d
, 5);
1954 /* square below hexagon */
1955 if (y
< height
- 1) {
1956 grid_face_add_new(g
, 4);
1957 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1958 grid_face_set_dot(g
, d
, 0);
1959 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1960 grid_face_set_dot(g
, d
, 1);
1961 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1962 grid_face_set_dot(g
, d
, 2);
1963 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1964 grid_face_set_dot(g
, d
, 3);
1967 /* square below right */
1968 if ((x
< width
- 1) && (((x
% 2) == 0) || (y
< height
- 1))) {
1969 grid_face_add_new(g
, 4);
1970 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1971 grid_face_set_dot(g
, d
, 0);
1972 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1973 grid_face_set_dot(g
, d
, 1);
1974 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1975 grid_face_set_dot(g
, d
, 2);
1976 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1977 grid_face_set_dot(g
, d
, 3);
1980 /* square below left */
1981 if ((x
> 0) && (((x
% 2) == 0) || (y
< height
- 1))) {
1982 grid_face_add_new(g
, 4);
1983 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1984 grid_face_set_dot(g
, d
, 0);
1985 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1986 grid_face_set_dot(g
, d
, 1);
1987 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1988 grid_face_set_dot(g
, d
, 2);
1989 d
= grid_get_dot(g
, points
, px
- 2*a
- b
, py
+ a
);
1990 grid_face_set_dot(g
, d
, 3);
1993 /* Triangle below right */
1994 if ((x
< width
- 1) && (y
< height
- 1)) {
1995 grid_face_add_new(g
, 3);
1996 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1997 grid_face_set_dot(g
, d
, 0);
1998 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1999 grid_face_set_dot(g
, d
, 1);
2000 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
2001 grid_face_set_dot(g
, d
, 2);
2004 /* Triangle below left */
2005 if ((x
> 0) && (y
< height
- 1)) {
2006 grid_face_add_new(g
, 3);
2007 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
2008 grid_face_set_dot(g
, d
, 0);
2009 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
2010 grid_face_set_dot(g
, d
, 1);
2011 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
2012 grid_face_set_dot(g
, d
, 2);
2017 freetree234(points
);
2018 assert(g
->num_faces
<= max_faces
);
2019 assert(g
->num_dots
<= max_dots
);
2021 grid_make_consistent(g
);
2024 #define OCTAGONAL_TILESIZE 40
2025 /* b/a approx sqrt(2) */
2026 #define OCTAGONAL_A 29
2027 #define OCTAGONAL_B 41
2029 static void grid_size_octagonal(int width
, int height
,
2030 int *tilesize
, int *xextent
, int *yextent
)
2032 int a
= OCTAGONAL_A
;
2033 int b
= OCTAGONAL_B
;
2035 *tilesize
= OCTAGONAL_TILESIZE
;
2036 *xextent
= (2*a
+ b
) * width
;
2037 *yextent
= (2*a
+ b
) * height
;
2040 static grid
*grid_new_octagonal(int width
, int height
, char *desc
)
2043 int a
= OCTAGONAL_A
;
2044 int b
= OCTAGONAL_B
;
2046 /* Upper bounds - don't have to be exact */
2047 int max_faces
= 2 * width
* height
;
2048 int max_dots
= 4 * (width
+ 1) * (height
+ 1);
2052 grid
*g
= grid_empty();
2053 g
->tilesize
= OCTAGONAL_TILESIZE
;
2054 g
->faces
= snewn(max_faces
, grid_face
);
2055 g
->dots
= snewn(max_dots
, grid_dot
);
2057 points
= newtree234(grid_point_cmp_fn
);
2059 for (y
= 0; y
< height
; y
++) {
2060 for (x
= 0; x
< width
; x
++) {
2063 int px
= (2*a
+ b
) * x
;
2064 int py
= (2*a
+ b
) * y
;
2066 grid_face_add_new(g
, 8);
2067 d
= grid_get_dot(g
, points
, px
+ a
, py
);
2068 grid_face_set_dot(g
, d
, 0);
2069 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
);
2070 grid_face_set_dot(g
, d
, 1);
2071 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
2072 grid_face_set_dot(g
, d
, 2);
2073 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
+ b
);
2074 grid_face_set_dot(g
, d
, 3);
2075 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ 2*a
+ b
);
2076 grid_face_set_dot(g
, d
, 4);
2077 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
2078 grid_face_set_dot(g
, d
, 5);
2079 d
= grid_get_dot(g
, points
, px
, py
+ a
+ b
);
2080 grid_face_set_dot(g
, d
, 6);
2081 d
= grid_get_dot(g
, points
, px
, py
+ a
);
2082 grid_face_set_dot(g
, d
, 7);
2085 if ((x
> 0) && (y
> 0)) {
2086 grid_face_add_new(g
, 4);
2087 d
= grid_get_dot(g
, points
, px
, py
- a
);
2088 grid_face_set_dot(g
, d
, 0);
2089 d
= grid_get_dot(g
, points
, px
+ a
, py
);
2090 grid_face_set_dot(g
, d
, 1);
2091 d
= grid_get_dot(g
, points
, px
, py
+ a
);
2092 grid_face_set_dot(g
, d
, 2);
2093 d
= grid_get_dot(g
, points
, px
- a
, py
);
2094 grid_face_set_dot(g
, d
, 3);
2099 freetree234(points
);
2100 assert(g
->num_faces
<= max_faces
);
2101 assert(g
->num_dots
<= max_dots
);
2103 grid_make_consistent(g
);
2107 #define DUAL_OCTAGONAL_TILESIZE OCTAGONAL_TILESIZE
2108 /* b/a approx sqrt(2) */
2109 #define DUAL_OCTAGONAL_A OCTAGONAL_A
2110 #define DUAL_OCTAGONAL_B OCTAGONAL_B
2112 static void grid_size_dual_octagonal(int width
, int height
,
2113 int *tilesize
, int *xextent
, int *yextent
)
2115 grid_size_octagonal(width
, height
, tilesize
, xextent
, yextent
);
2118 static grid
*grid_new_dual_octagonal(int width
, int height
, char *desc
)
2123 orig
= grid_new_octagonal(width
, height
, desc
);
2125 g
= grid_dual(orig
);
2131 #define KITE_TILESIZE 40
2132 /* b/a approx sqrt(3) */
2136 static void grid_size_kites(int width
, int height
,
2137 int *tilesize
, int *xextent
, int *yextent
)
2142 *tilesize
= KITE_TILESIZE
;
2143 *xextent
= 4*b
* width
+ 2*b
;
2144 *yextent
= 6*a
* (height
-1) + 8*a
;
2147 static grid
*grid_new_kites(int width
, int height
, char *desc
)
2153 /* Upper bounds - don't have to be exact */
2154 int max_faces
= 6 * width
* height
;
2155 int max_dots
= 6 * (width
+ 1) * (height
+ 1);
2159 grid
*g
= grid_empty();
2160 g
->tilesize
= KITE_TILESIZE
;
2161 g
->faces
= snewn(max_faces
, grid_face
);
2162 g
->dots
= snewn(max_dots
, grid_dot
);
2164 points
= newtree234(grid_point_cmp_fn
);
2166 for (y
= 0; y
< height
; y
++) {
2167 for (x
= 0; x
< width
; x
++) {
2169 /* position of order-6 dot */
2175 /* kite pointing up-left */
2176 grid_face_add_new(g
, 4);
2177 d
= grid_get_dot(g
, points
, px
, py
);
2178 grid_face_set_dot(g
, d
, 0);
2179 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
2180 grid_face_set_dot(g
, d
, 1);
2181 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
+ 2*a
);
2182 grid_face_set_dot(g
, d
, 2);
2183 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
2184 grid_face_set_dot(g
, d
, 3);
2186 /* kite pointing up */
2187 grid_face_add_new(g
, 4);
2188 d
= grid_get_dot(g
, points
, px
, py
);
2189 grid_face_set_dot(g
, d
, 0);
2190 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
2191 grid_face_set_dot(g
, d
, 1);
2192 d
= grid_get_dot(g
, points
, px
, py
+ 4*a
);
2193 grid_face_set_dot(g
, d
, 2);
2194 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
2195 grid_face_set_dot(g
, d
, 3);
2197 /* kite pointing up-right */
2198 grid_face_add_new(g
, 4);
2199 d
= grid_get_dot(g
, points
, px
, py
);
2200 grid_face_set_dot(g
, d
, 0);
2201 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
2202 grid_face_set_dot(g
, d
, 1);
2203 d
= grid_get_dot(g
, points
, px
- 2*b
, py
+ 2*a
);
2204 grid_face_set_dot(g
, d
, 2);
2205 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
2206 grid_face_set_dot(g
, d
, 3);
2208 /* kite pointing down-right */
2209 grid_face_add_new(g
, 4);
2210 d
= grid_get_dot(g
, points
, px
, py
);
2211 grid_face_set_dot(g
, d
, 0);
2212 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
2213 grid_face_set_dot(g
, d
, 1);
2214 d
= grid_get_dot(g
, points
, px
- 2*b
, py
- 2*a
);
2215 grid_face_set_dot(g
, d
, 2);
2216 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
2217 grid_face_set_dot(g
, d
, 3);
2219 /* kite pointing down */
2220 grid_face_add_new(g
, 4);
2221 d
= grid_get_dot(g
, points
, px
, py
);
2222 grid_face_set_dot(g
, d
, 0);
2223 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
2224 grid_face_set_dot(g
, d
, 1);
2225 d
= grid_get_dot(g
, points
, px
, py
- 4*a
);
2226 grid_face_set_dot(g
, d
, 2);
2227 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
2228 grid_face_set_dot(g
, d
, 3);
2230 /* kite pointing down-left */
2231 grid_face_add_new(g
, 4);
2232 d
= grid_get_dot(g
, points
, px
, py
);
2233 grid_face_set_dot(g
, d
, 0);
2234 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
2235 grid_face_set_dot(g
, d
, 1);
2236 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
- 2*a
);
2237 grid_face_set_dot(g
, d
, 2);
2238 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
2239 grid_face_set_dot(g
, d
, 3);
2243 freetree234(points
);
2244 assert(g
->num_faces
<= max_faces
);
2245 assert(g
->num_dots
<= max_dots
);
2247 grid_make_consistent(g
);
2251 #define FLORET_TILESIZE 150
2252 /* -py/px is close to tan(30 - atan(sqrt(3)/9))
2253 * using py=26 makes everything lean to the left, rather than right
2255 #define FLORET_PX 75
2256 #define FLORET_PY -26
2258 static void grid_size_floret(int width
, int height
,
2259 int *tilesize
, int *xextent
, int *yextent
)
2261 int px
= FLORET_PX
, py
= FLORET_PY
; /* |( 75, -26)| = 79.43 */
2262 int qx
= 4*px
/5, qy
= -py
*2; /* |( 60, 52)| = 79.40 */
2264 /* rx unused in determining grid size. */
2266 *tilesize
= FLORET_TILESIZE
;
2267 *xextent
= (6*px
+3*qx
)/2 * (width
-1) + 4*qx
+ 2*px
;
2268 *yextent
= (5*qy
-4*py
) * (height
-1) + 4*qy
+ 2*ry
;
2271 static grid
*grid_new_floret(int width
, int height
, char *desc
)
2274 /* Vectors for sides; weird numbers needed to keep puzzle aligned with window
2275 * -py/px is close to tan(30 - atan(sqrt(3)/9))
2276 * using py=26 makes everything lean to the left, rather than right
2278 int px
= FLORET_PX
, py
= FLORET_PY
; /* |( 75, -26)| = 79.43 */
2279 int qx
= 4*px
/5, qy
= -py
*2; /* |( 60, 52)| = 79.40 */
2280 int rx
= qx
-px
, ry
= qy
-py
; /* |(-15, 78)| = 79.38 */
2282 /* Upper bounds - don't have to be exact */
2283 int max_faces
= 6 * width
* height
;
2284 int max_dots
= 9 * (width
+ 1) * (height
+ 1);
2288 grid
*g
= grid_empty();
2289 g
->tilesize
= FLORET_TILESIZE
;
2290 g
->faces
= snewn(max_faces
, grid_face
);
2291 g
->dots
= snewn(max_dots
, grid_dot
);
2293 points
= newtree234(grid_point_cmp_fn
);
2295 /* generate pentagonal faces */
2296 for (y
= 0; y
< height
; y
++) {
2297 for (x
= 0; x
< width
; x
++) {
2300 int cx
= (6*px
+3*qx
)/2 * x
;
2301 int cy
= (4*py
-5*qy
) * y
;
2303 cy
-= (4*py
-5*qy
)/2;
2304 else if (y
&& y
== height
-1)
2305 continue; /* make better looking grids? try 3x3 for instance */
2307 grid_face_add_new(g
, 5);
2308 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
2309 d
= grid_get_dot(g
, points
, cx
+2*rx
, cy
+2*ry
); grid_face_set_dot(g
, d
, 1);
2310 d
= grid_get_dot(g
, points
, cx
+2*rx
+qx
, cy
+2*ry
+qy
); grid_face_set_dot(g
, d
, 2);
2311 d
= grid_get_dot(g
, points
, cx
+2*qx
+rx
, cy
+2*qy
+ry
); grid_face_set_dot(g
, d
, 3);
2312 d
= grid_get_dot(g
, points
, cx
+2*qx
, cy
+2*qy
); grid_face_set_dot(g
, d
, 4);
2314 grid_face_add_new(g
, 5);
2315 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
2316 d
= grid_get_dot(g
, points
, cx
+2*qx
, cy
+2*qy
); grid_face_set_dot(g
, d
, 1);
2317 d
= grid_get_dot(g
, points
, cx
+2*qx
+px
, cy
+2*qy
+py
); grid_face_set_dot(g
, d
, 2);
2318 d
= grid_get_dot(g
, points
, cx
+2*px
+qx
, cy
+2*py
+qy
); grid_face_set_dot(g
, d
, 3);
2319 d
= grid_get_dot(g
, points
, cx
+2*px
, cy
+2*py
); grid_face_set_dot(g
, d
, 4);
2321 grid_face_add_new(g
, 5);
2322 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
2323 d
= grid_get_dot(g
, points
, cx
+2*px
, cy
+2*py
); grid_face_set_dot(g
, d
, 1);
2324 d
= grid_get_dot(g
, points
, cx
+2*px
-rx
, cy
+2*py
-ry
); grid_face_set_dot(g
, d
, 2);
2325 d
= grid_get_dot(g
, points
, cx
-2*rx
+px
, cy
-2*ry
+py
); grid_face_set_dot(g
, d
, 3);
2326 d
= grid_get_dot(g
, points
, cx
-2*rx
, cy
-2*ry
); grid_face_set_dot(g
, d
, 4);
2328 grid_face_add_new(g
, 5);
2329 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
2330 d
= grid_get_dot(g
, points
, cx
-2*rx
, cy
-2*ry
); grid_face_set_dot(g
, d
, 1);
2331 d
= grid_get_dot(g
, points
, cx
-2*rx
-qx
, cy
-2*ry
-qy
); grid_face_set_dot(g
, d
, 2);
2332 d
= grid_get_dot(g
, points
, cx
-2*qx
-rx
, cy
-2*qy
-ry
); grid_face_set_dot(g
, d
, 3);
2333 d
= grid_get_dot(g
, points
, cx
-2*qx
, cy
-2*qy
); grid_face_set_dot(g
, d
, 4);
2335 grid_face_add_new(g
, 5);
2336 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
2337 d
= grid_get_dot(g
, points
, cx
-2*qx
, cy
-2*qy
); grid_face_set_dot(g
, d
, 1);
2338 d
= grid_get_dot(g
, points
, cx
-2*qx
-px
, cy
-2*qy
-py
); grid_face_set_dot(g
, d
, 2);
2339 d
= grid_get_dot(g
, points
, cx
-2*px
-qx
, cy
-2*py
-qy
); grid_face_set_dot(g
, d
, 3);
2340 d
= grid_get_dot(g
, points
, cx
-2*px
, cy
-2*py
); grid_face_set_dot(g
, d
, 4);
2342 grid_face_add_new(g
, 5);
2343 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
2344 d
= grid_get_dot(g
, points
, cx
-2*px
, cy
-2*py
); grid_face_set_dot(g
, d
, 1);
2345 d
= grid_get_dot(g
, points
, cx
-2*px
+rx
, cy
-2*py
+ry
); grid_face_set_dot(g
, d
, 2);
2346 d
= grid_get_dot(g
, points
, cx
+2*rx
-px
, cy
+2*ry
-py
); grid_face_set_dot(g
, d
, 3);
2347 d
= grid_get_dot(g
, points
, cx
+2*rx
, cy
+2*ry
); grid_face_set_dot(g
, d
, 4);
2351 freetree234(points
);
2352 assert(g
->num_faces
<= max_faces
);
2353 assert(g
->num_dots
<= max_dots
);
2355 grid_make_consistent(g
);
2359 /* DODEC_* are used for dodecagonal and great-dodecagonal grids. */
2360 #define DODEC_TILESIZE 26
2361 /* Vector for side of triangle - ratio is close to sqrt(3) */
2365 static void grid_size_dodecagonal(int width
, int height
,
2366 int *tilesize
, int *xextent
, int *yextent
)
2371 *tilesize
= DODEC_TILESIZE
;
2372 *xextent
= (4*a
+ 2*b
) * (width
-1) + 3*(2*a
+ b
);
2373 *yextent
= (3*a
+ 2*b
) * (height
-1) + 2*(2*a
+ b
);
2376 static grid
*grid_new_dodecagonal(int width
, int height
, char *desc
)
2382 /* Upper bounds - don't have to be exact */
2383 int max_faces
= 3 * width
* height
;
2384 int max_dots
= 14 * width
* height
;
2388 grid
*g
= grid_empty();
2389 g
->tilesize
= DODEC_TILESIZE
;
2390 g
->faces
= snewn(max_faces
, grid_face
);
2391 g
->dots
= snewn(max_dots
, grid_dot
);
2393 points
= newtree234(grid_point_cmp_fn
);
2395 for (y
= 0; y
< height
; y
++) {
2396 for (x
= 0; x
< width
; x
++) {
2398 /* centre of dodecagon */
2399 int px
= (4*a
+ 2*b
) * x
;
2400 int py
= (3*a
+ 2*b
) * y
;
2405 grid_face_add_new(g
, 12);
2406 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2407 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 1);
2408 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 2);
2409 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 3);
2410 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 4);
2411 d
= grid_get_dot(g
, points
, px
+ ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
2412 d
= grid_get_dot(g
, points
, px
- ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 6);
2413 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 7);
2414 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 8);
2415 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 9);
2416 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 10);
2417 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 11);
2419 /* triangle below dodecagon */
2420 if ((y
< height
- 1 && (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2)))) {
2421 grid_face_add_new(g
, 3);
2422 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2423 d
= grid_get_dot(g
, points
, px
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2424 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 2);
2427 /* triangle above dodecagon */
2428 if ((y
&& (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2)))) {
2429 grid_face_add_new(g
, 3);
2430 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2431 d
= grid_get_dot(g
, points
, px
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2432 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 2);
2437 freetree234(points
);
2438 assert(g
->num_faces
<= max_faces
);
2439 assert(g
->num_dots
<= max_dots
);
2441 grid_make_consistent(g
);
2445 static void grid_size_greatdodecagonal(int width
, int height
,
2446 int *tilesize
, int *xextent
, int *yextent
)
2451 *tilesize
= DODEC_TILESIZE
;
2452 *xextent
= (6*a
+ 2*b
) * (width
-1) + 2*(2*a
+ b
) + 3*a
+ b
;
2453 *yextent
= (3*a
+ 3*b
) * (height
-1) + 2*(2*a
+ b
);
2456 static grid
*grid_new_greatdodecagonal(int width
, int height
, char *desc
)
2459 /* Vector for side of triangle - ratio is close to sqrt(3) */
2463 /* Upper bounds - don't have to be exact */
2464 int max_faces
= 30 * width
* height
;
2465 int max_dots
= 200 * width
* height
;
2469 grid
*g
= grid_empty();
2470 g
->tilesize
= DODEC_TILESIZE
;
2471 g
->faces
= snewn(max_faces
, grid_face
);
2472 g
->dots
= snewn(max_dots
, grid_dot
);
2474 points
= newtree234(grid_point_cmp_fn
);
2476 for (y
= 0; y
< height
; y
++) {
2477 for (x
= 0; x
< width
; x
++) {
2479 /* centre of dodecagon */
2480 int px
= (6*a
+ 2*b
) * x
;
2481 int py
= (3*a
+ 3*b
) * y
;
2486 grid_face_add_new(g
, 12);
2487 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2488 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 1);
2489 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 2);
2490 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 3);
2491 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 4);
2492 d
= grid_get_dot(g
, points
, px
+ ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
2493 d
= grid_get_dot(g
, points
, px
- ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 6);
2494 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 7);
2495 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 8);
2496 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 9);
2497 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 10);
2498 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 11);
2500 /* hexagon below dodecagon */
2501 if (y
< height
- 1 && (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2))) {
2502 grid_face_add_new(g
, 6);
2503 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2504 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2505 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 2);
2506 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 3);
2507 d
= grid_get_dot(g
, points
, px
- 2*a
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 4);
2508 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
2511 /* hexagon above dodecagon */
2512 if (y
&& (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2))) {
2513 grid_face_add_new(g
, 6);
2514 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2515 d
= grid_get_dot(g
, points
, px
- 2*a
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2516 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 2);
2517 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 3);
2518 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 4);
2519 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
2522 /* square on right of dodecagon */
2523 if (x
< width
- 1) {
2524 grid_face_add_new(g
, 4);
2525 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
- a
); grid_face_set_dot(g
, d
, 0);
2526 d
= grid_get_dot(g
, points
, px
+ 4*a
+ b
, py
- a
); grid_face_set_dot(g
, d
, 1);
2527 d
= grid_get_dot(g
, points
, px
+ 4*a
+ b
, py
+ a
); grid_face_set_dot(g
, d
, 2);
2528 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
); grid_face_set_dot(g
, d
, 3);
2531 /* square on top right of dodecagon */
2532 if (y
&& (x
< width
- 1 || !(y
% 2))) {
2533 grid_face_add_new(g
, 4);
2534 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2535 d
= grid_get_dot(g
, points
, px
+ (2*a
), py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2536 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
+ 2*b
)); grid_face_set_dot(g
, d
, 2);
2537 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 3);
2540 /* square on top left of dodecagon */
2541 if (y
&& (x
|| (y
% 2))) {
2542 grid_face_add_new(g
, 4);
2543 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 0);
2544 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2545 d
= grid_get_dot(g
, points
, px
- (2*a
), py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 2);
2546 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 3);
2551 freetree234(points
);
2552 assert(g
->num_faces
<= max_faces
);
2553 assert(g
->num_dots
<= max_dots
);
2555 grid_make_consistent(g
);
2559 typedef struct setface_ctx
2561 int xmin
, xmax
, ymin
, ymax
;
2567 static double round_int_nearest_away(double r
)
2569 return (r
> 0.0) ?
floor(r
+ 0.5) : ceil(r
- 0.5);
2572 static int set_faces(penrose_state
*state
, vector
*vs
, int n
, int depth
)
2574 setface_ctx
*sf_ctx
= (setface_ctx
*)state
->ctx
;
2578 if (depth
< state
->max_depth
) return 0;
2579 #ifdef DEBUG_PENROSE
2580 if (n
!= 4) return 0; /* triangles are sent as debugging. */
2583 for (i
= 0; i
< n
; i
++) {
2584 double tx
= v_x(vs
, i
), ty
= v_y(vs
, i
);
2586 xs
[i
] = (int)round_int_nearest_away(tx
);
2587 ys
[i
] = (int)round_int_nearest_away(ty
);
2589 if (xs
[i
] < sf_ctx
->xmin
|| xs
[i
] > sf_ctx
->xmax
) return 0;
2590 if (ys
[i
] < sf_ctx
->ymin
|| ys
[i
] > sf_ctx
->ymax
) return 0;
2593 grid_face_add_new(sf_ctx
->g
, n
);
2594 debug(("penrose: new face l=%f gen=%d...",
2595 penrose_side_length(state
->start_size
, depth
), depth
));
2596 for (i
= 0; i
< n
; i
++) {
2597 grid_dot
*d
= grid_get_dot(sf_ctx
->g
, sf_ctx
->points
,
2599 grid_face_set_dot(sf_ctx
->g
, d
, i
);
2600 debug((" ... dot 0x%x (%d,%d) (was %2.2f,%2.2f)",
2601 d
, d
->x
, d
->y
, v_x(vs
, i
), v_y(vs
, i
)));
2607 #define PENROSE_TILESIZE 100
2609 static void grid_size_penrose(int width
, int height
,
2610 int *tilesize
, int *xextent
, int *yextent
)
2612 int l
= PENROSE_TILESIZE
;
2615 *xextent
= l
* width
;
2616 *yextent
= l
* height
;
2619 static char *grid_new_desc_penrose(grid_type type
, int width
, int height
, random_state
*rs
)
2621 int tilesize
= PENROSE_TILESIZE
, startsz
, depth
, xoff
, yoff
, aoff
;
2622 double outer_radius
;
2625 int which
= (type
== GRID_PENROSE_P2 ? PENROSE_P2
: PENROSE_P3
);
2627 /* We want to produce a random bit of penrose tiling, so we calculate
2628 * a random offset (within the patch that penrose.c calculates for us)
2629 * and an angle (multiple of 36) to rotate the patch. */
2631 penrose_calculate_size(which
, tilesize
, width
, height
,
2632 &outer_radius
, &startsz
, &depth
);
2634 /* Calculate radius of (circumcircle of) patch, subtract from
2635 * radius calculated. */
2636 inner_radius
= (int)(outer_radius
- sqrt(width
*width
+ height
*height
));
2638 /* Pick a random offset (the easy way: choose within outer square,
2639 * discarding while it's outside the circle) */
2641 xoff
= random_upto(rs
, 2*inner_radius
) - inner_radius
;
2642 yoff
= random_upto(rs
, 2*inner_radius
) - inner_radius
;
2643 } while (sqrt(xoff
*xoff
+yoff
*yoff
) > inner_radius
);
2645 aoff
= random_upto(rs
, 360/36) * 36;
2647 debug(("grid_desc: ts %d, %dx%d patch, orad %2.2f irad %d",
2648 tilesize
, width
, height
, outer_radius
, inner_radius
));
2649 debug((" -> xoff %d yoff %d aoff %d", xoff
, yoff
, aoff
));
2651 sprintf(gd
, "G%d,%d,%d", xoff
, yoff
, aoff
);
2656 static char *grid_validate_desc_penrose(grid_type type
, int width
, int height
, char *desc
)
2658 int tilesize
= PENROSE_TILESIZE
, startsz
, depth
, xoff
, yoff
, aoff
, inner_radius
;
2659 double outer_radius
;
2660 int which
= (type
== GRID_PENROSE_P2 ? PENROSE_P2
: PENROSE_P3
);
2663 return "Missing grid description string.";
2665 penrose_calculate_size(which
, tilesize
, width
, height
,
2666 &outer_radius
, &startsz
, &depth
);
2667 inner_radius
= (int)(outer_radius
- sqrt(width
*width
+ height
*height
));
2669 if (sscanf(desc
, "G%d,%d,%d", &xoff
, &yoff
, &aoff
) != 3)
2670 return "Invalid format grid description string.";
2672 if (sqrt(xoff
*xoff
+ yoff
*yoff
) > inner_radius
)
2673 return "Patch offset out of bounds.";
2674 if ((aoff
% 36) != 0 || aoff
< 0 || aoff
>= 360)
2675 return "Angle offset out of bounds.";
2681 * We're asked for a grid of a particular size, and we generate enough
2682 * of the tiling so we can be sure to have enough random grid from which
2686 static grid
*grid_new_penrose(int width
, int height
, int which
, char *desc
)
2688 int max_faces
, max_dots
, tilesize
= PENROSE_TILESIZE
;
2689 int xsz
, ysz
, xoff
, yoff
, aoff
;
2698 penrose_calculate_size(which
, tilesize
, width
, height
,
2699 &rradius
, &ps
.start_size
, &ps
.max_depth
);
2701 debug(("penrose: w%d h%d, tile size %d, start size %d, depth %d",
2702 width
, height
, tilesize
, ps
.start_size
, ps
.max_depth
));
2704 ps
.new_tile
= set_faces
;
2707 max_faces
= (width
*3) * (height
*3); /* somewhat paranoid... */
2708 max_dots
= max_faces
* 4; /* ditto... */
2711 g
->tilesize
= tilesize
;
2712 g
->faces
= snewn(max_faces
, grid_face
);
2713 g
->dots
= snewn(max_dots
, grid_dot
);
2715 points
= newtree234(grid_point_cmp_fn
);
2717 memset(&sf_ctx
, 0, sizeof(sf_ctx
));
2719 sf_ctx
.points
= points
;
2722 if (sscanf(desc
, "G%d,%d,%d", &xoff
, &yoff
, &aoff
) != 3)
2723 assert(!"Invalid grid description.");
2728 xsz
= width
* tilesize
;
2729 ysz
= height
* tilesize
;
2731 sf_ctx
.xmin
= xoff
- xsz
/2;
2732 sf_ctx
.xmax
= xoff
+ xsz
/2;
2733 sf_ctx
.ymin
= yoff
- ysz
/2;
2734 sf_ctx
.ymax
= yoff
+ ysz
/2;
2736 debug(("penrose: centre (%f, %f) xsz %f ysz %f",
2737 0.0, 0.0, xsz
, ysz
));
2738 debug(("penrose: x range (%f --> %f), y range (%f --> %f)",
2739 sf_ctx
.xmin
, sf_ctx
.xmax
, sf_ctx
.ymin
, sf_ctx
.ymax
));
2741 penrose(&ps
, which
, aoff
);
2743 freetree234(points
);
2744 assert(g
->num_faces
<= max_faces
);
2745 assert(g
->num_dots
<= max_dots
);
2747 debug(("penrose: %d faces total (equivalent to %d wide by %d high)",
2748 g
->num_faces
, g
->num_faces
/height
, g
->num_faces
/width
));
2750 grid_trim_vigorously(g
);
2751 grid_make_consistent(g
);
2754 * Centre the grid in its originally promised rectangle.
2756 g
->lowest_x
-= ((sf_ctx
.xmax
- sf_ctx
.xmin
) -
2757 (g
->highest_x
- g
->lowest_x
)) / 2;
2758 g
->highest_x
= g
->lowest_x
+ (sf_ctx
.xmax
- sf_ctx
.xmin
);
2759 g
->lowest_y
-= ((sf_ctx
.ymax
- sf_ctx
.ymin
) -
2760 (g
->highest_y
- g
->lowest_y
)) / 2;
2761 g
->highest_y
= g
->lowest_y
+ (sf_ctx
.ymax
- sf_ctx
.ymin
);
2766 static void grid_size_penrose_p2_kite(int width
, int height
,
2767 int *tilesize
, int *xextent
, int *yextent
)
2769 grid_size_penrose(width
, height
, tilesize
, xextent
, yextent
);
2772 static void grid_size_penrose_p3_thick(int width
, int height
,
2773 int *tilesize
, int *xextent
, int *yextent
)
2775 grid_size_penrose(width
, height
, tilesize
, xextent
, yextent
);
2778 static grid
*grid_new_penrose_p2_kite(int width
, int height
, char *desc
)
2780 return grid_new_penrose(width
, height
, PENROSE_P2
, desc
);
2783 static grid
*grid_new_penrose_p3_thick(int width
, int height
, char *desc
)
2785 return grid_new_penrose(width
, height
, PENROSE_P3
, desc
);
2788 /* ----------- End of grid generators ------------- */
2790 #define FNNEW(upper,lower) &grid_new_ ## lower,
2791 #define FNSZ(upper,lower) &grid_size_ ## lower,
2793 static grid
*(*(grid_news
[]))(int, int, char*) = { GRIDGEN_LIST(FNNEW
) };
2794 static void(*(grid_sizes
[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ
) };
2796 char *grid_new_desc(grid_type type
, int width
, int height
, random_state
*rs
)
2798 if (type
!= GRID_PENROSE_P2
&& type
!= GRID_PENROSE_P3
)
2801 return grid_new_desc_penrose(type
, width
, height
, rs
);
2804 char *grid_validate_desc(grid_type type
, int width
, int height
, char *desc
)
2806 if (type
!= GRID_PENROSE_P2
&& type
!= GRID_PENROSE_P3
) {
2808 return "Grid description strings not used with this grid type";
2812 return grid_validate_desc_penrose(type
, width
, height
, desc
);
2815 grid
*grid_new(grid_type type
, int width
, int height
, char *desc
)
2817 char *err
= grid_validate_desc(type
, width
, height
, desc
);
2818 if (err
) assert(!"Invalid grid description.");
2820 return grid_news
[type
](width
, height
, desc
);
2823 void grid_compute_size(grid_type type
, int width
, int height
,
2824 int *tilesize
, int *xextent
, int *yextent
)
2826 grid_sizes
[type
](width
, height
, tilesize
, xextent
, yextent
);
2829 /* ----------- End of grid helpers ------------- */
2831 /* vim: set shiftwidth=4 tabstop=8: */