1e5fe6f4dec0572982d7ecf0805a3776abc2fb6e
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.
20 /* Debugging options */
26 /* ----------------------------------------------------------------------
27 * Deallocate or dereference a grid
29 void grid_free(grid
*g
)
34 if (g
->refcount
== 0) {
36 for (i
= 0; i
< g
->num_faces
; i
++) {
37 sfree(g
->faces
[i
].dots
);
38 sfree(g
->faces
[i
].edges
);
40 for (i
= 0; i
< g
->num_dots
; i
++) {
41 sfree(g
->dots
[i
].faces
);
42 sfree(g
->dots
[i
].edges
);
51 /* Used by the other grid generators. Create a brand new grid with nothing
52 * initialised (all lists are NULL) */
53 static grid
*grid_new(void)
59 g
->num_faces
= g
->num_edges
= g
->num_dots
= 0;
61 g
->lowest_x
= g
->lowest_y
= g
->highest_x
= g
->highest_y
= 0;
65 /* Helper function to calculate perpendicular distance from
66 * a point P to a line AB. A and B mustn't be equal here.
68 * Well-known formula for area A of a triangle:
70 * 2A = determinant of matrix | px ax bx |
73 * Also well-known: 2A = base * height
74 * = perpendicular distance * line-length.
76 * Combining gives: distance = determinant / line-length(a,b)
78 static double point_line_distance(long px
, long py
,
82 long det
= ax
*by
- bx
*ay
+ bx
*py
- px
*by
+ px
*ay
- ax
*py
;
85 len
= sqrt(SQ(ax
- bx
) + SQ(ay
- by
));
89 /* Determine nearest edge to where the user clicked.
90 * (x, y) is the clicked location, converted to grid coordinates.
91 * Returns the nearest edge, or NULL if no edge is reasonably
94 * Just judging edges by perpendicular distance is not quite right -
95 * the edge might be "off to one side". So we insist that the triangle
96 * with (x,y) has acute angles at the edge's dots.
103 * | edge2 is OK, but edge1 is not, even though
104 * | edge1 is perpendicularly closer to (x,y)
108 grid_edge
*grid_nearest_edge(grid
*g
, int x
, int y
)
110 grid_edge
*best_edge
;
111 double best_distance
= 0;
116 for (i
= 0; i
< g
->num_edges
; i
++) {
117 grid_edge
*e
= &g
->edges
[i
];
118 long e2
; /* squared length of edge */
119 long a2
, b2
; /* squared lengths of other sides */
122 /* See if edge e is eligible - the triangle must have acute angles
123 * at the edge's dots.
124 * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
125 * so detect acute angles by testing for h^2 < a^2 + b^2 */
126 e2
= SQ((long)e
->dot1
->x
- (long)e
->dot2
->x
) + SQ((long)e
->dot1
->y
- (long)e
->dot2
->y
);
127 a2
= SQ((long)e
->dot1
->x
- (long)x
) + SQ((long)e
->dot1
->y
- (long)y
);
128 b2
= SQ((long)e
->dot2
->x
- (long)x
) + SQ((long)e
->dot2
->y
- (long)y
);
129 if (a2
>= e2
+ b2
) continue;
130 if (b2
>= e2
+ a2
) continue;
132 /* e is eligible so far. Now check the edge is reasonably close
133 * to where the user clicked. Don't want to toggle an edge if the
134 * click was way off the grid.
135 * There is room for experimentation here. We could check the
136 * perpendicular distance is within a certain fraction of the length
137 * of the edge. That amounts to testing a rectangular region around
139 * Alternatively, we could check that the angle at the point is obtuse.
140 * That would amount to testing a circular region with the edge as
142 dist
= point_line_distance((long)x
, (long)y
,
143 (long)e
->dot1
->x
, (long)e
->dot1
->y
,
144 (long)e
->dot2
->x
, (long)e
->dot2
->y
);
145 /* Is dist more than half edge length ? */
146 if (4 * SQ(dist
) > e2
)
149 if (best_edge
== NULL
|| dist
< best_distance
) {
151 best_distance
= dist
;
157 /* ----------------------------------------------------------------------
162 /* Show the basic grid information, before doing grid_make_consistent */
163 static void grid_print_basic(grid
*g
)
165 /* TODO: Maybe we should generate an SVG image of the dots and lines
166 * of the grid here, before grid_make_consistent.
167 * Would help with debugging grid generation. */
169 printf("--- Basic Grid Data ---\n");
170 for (i
= 0; i
< g
->num_faces
; i
++) {
171 grid_face
*f
= g
->faces
+ i
;
172 printf("Face %d: dots[", i
);
174 for (j
= 0; j
< f
->order
; j
++) {
175 grid_dot
*d
= f
->dots
[j
];
176 printf("%s%d", j ?
"," : "", (int)(d
- g
->dots
));
181 /* Show the derived grid information, computed by grid_make_consistent */
182 static void grid_print_derived(grid
*g
)
186 printf("--- Derived Grid Data ---\n");
187 for (i
= 0; i
< g
->num_edges
; i
++) {
188 grid_edge
*e
= g
->edges
+ i
;
189 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
190 i
, (int)(e
->dot1
- g
->dots
), (int)(e
->dot2
- g
->dots
),
191 e
->face1 ?
(int)(e
->face1
- g
->faces
) : -1,
192 e
->face2 ?
(int)(e
->face2
- g
->faces
) : -1);
195 for (i
= 0; i
< g
->num_faces
; i
++) {
196 grid_face
*f
= g
->faces
+ i
;
198 printf("Face %d: faces[", i
);
199 for (j
= 0; j
< f
->order
; j
++) {
200 grid_edge
*e
= f
->edges
[j
];
201 grid_face
*f2
= (e
->face1
== f
) ? e
->face2
: e
->face1
;
202 printf("%s%d", j ?
"," : "", f2 ?
(int)(f2
- g
->faces
) : -1);
207 for (i
= 0; i
< g
->num_dots
; i
++) {
208 grid_dot
*d
= g
->dots
+ i
;
210 printf("Dot %d: dots[", i
);
211 for (j
= 0; j
< d
->order
; j
++) {
212 grid_edge
*e
= d
->edges
[j
];
213 grid_dot
*d2
= (e
->dot1
== d
) ? e
->dot2
: e
->dot1
;
214 printf("%s%d", j ?
"," : "", (int)(d2
- g
->dots
));
217 for (j
= 0; j
< d
->order
; j
++) {
218 grid_face
*f
= d
->faces
[j
];
219 printf("%s%d", j ?
"," : "", f ?
(int)(f
- g
->faces
) : -1);
224 #endif /* DEBUG_GRID */
226 /* Helper function for building incomplete-edges list in
227 * grid_make_consistent() */
228 static int grid_edge_bydots_cmpfn(void *v1
, void *v2
)
234 /* Pointer subtraction is valid here, because all dots point into the
235 * same dot-list (g->dots).
236 * Edges are not "normalised" - the 2 dots could be stored in any order,
237 * so we need to take this into account when comparing edges. */
239 /* Compare first dots */
240 da
= (a
->dot1
< a
->dot2
) ? a
->dot1
: a
->dot2
;
241 db
= (b
->dot1
< b
->dot2
) ? b
->dot1
: b
->dot2
;
244 /* Compare last dots */
245 da
= (a
->dot1
< a
->dot2
) ? a
->dot2
: a
->dot1
;
246 db
= (b
->dot1
< b
->dot2
) ? b
->dot2
: b
->dot1
;
253 /* Input: grid has its dots and faces initialised:
254 * - dots have (optionally) x and y coordinates, but no edges or faces
255 * (pointers are NULL).
256 * - edges not initialised at all
257 * - faces initialised and know which dots they have (but no edges yet). The
258 * dots around each face are assumed to be clockwise.
260 * Output: grid is complete and valid with all relationships defined.
262 static void grid_make_consistent(grid
*g
)
265 tree234
*incomplete_edges
;
266 grid_edge
*next_new_edge
; /* Where new edge will go into g->edges */
272 /* ====== Stage 1 ======
276 /* We know how many dots and faces there are, so we can find the exact
277 * number of edges from Euler's polyhedral formula: F + V = E + 2 .
278 * We use "-1", not "-2" here, because Euler's formula includes the
279 * infinite face, which we don't count. */
280 g
->num_edges
= g
->num_faces
+ g
->num_dots
- 1;
281 g
->edges
= snewn(g
->num_edges
, grid_edge
);
282 next_new_edge
= g
->edges
;
284 /* Iterate over faces, and over each face's dots, generating edges as we
285 * go. As we find each new edge, we can immediately fill in the edge's
286 * dots, but only one of the edge's faces. Later on in the iteration, we
287 * will find the same edge again (unless it's on the border), but we will
288 * know the other face.
289 * For efficiency, maintain a list of the incomplete edges, sorted by
291 incomplete_edges
= newtree234(grid_edge_bydots_cmpfn
);
292 for (i
= 0; i
< g
->num_faces
; i
++) {
293 grid_face
*f
= g
->faces
+ i
;
295 for (j
= 0; j
< f
->order
; j
++) {
296 grid_edge e
; /* fake edge for searching */
297 grid_edge
*edge_found
;
302 e
.dot2
= f
->dots
[j2
];
303 /* Use del234 instead of find234, because we always want to
304 * remove the edge if found */
305 edge_found
= del234(incomplete_edges
, &e
);
307 /* This edge already added, so fill out missing face.
308 * Edge is already removed from incomplete_edges. */
309 edge_found
->face2
= f
;
311 assert(next_new_edge
- g
->edges
< g
->num_edges
);
312 next_new_edge
->dot1
= e
.dot1
;
313 next_new_edge
->dot2
= e
.dot2
;
314 next_new_edge
->face1
= f
;
315 next_new_edge
->face2
= NULL
; /* potentially infinite face */
316 add234(incomplete_edges
, next_new_edge
);
321 freetree234(incomplete_edges
);
323 /* ====== Stage 2 ======
324 * For each face, build its edge list.
327 /* Allocate space for each edge list. Can do this, because each face's
328 * edge-list is the same size as its dot-list. */
329 for (i
= 0; i
< g
->num_faces
; i
++) {
330 grid_face
*f
= g
->faces
+ i
;
332 f
->edges
= snewn(f
->order
, grid_edge
*);
333 /* Preload with NULLs, to help detect potential bugs. */
334 for (j
= 0; j
< f
->order
; j
++)
338 /* Iterate over each edge, and over both its faces. Add this edge to
339 * the face's edge-list, after finding where it should go in the
341 for (i
= 0; i
< g
->num_edges
; i
++) {
342 grid_edge
*e
= g
->edges
+ i
;
344 for (j
= 0; j
< 2; j
++) {
345 grid_face
*f
= j ? e
->face2
: e
->face1
;
347 if (f
== NULL
) continue;
348 /* Find one of the dots around the face */
349 for (k
= 0; k
< f
->order
; k
++) {
350 if (f
->dots
[k
] == e
->dot1
)
351 break; /* found dot1 */
353 assert(k
!= f
->order
); /* Must find the dot around this face */
355 /* Labelling scheme: as we walk clockwise around the face,
356 * starting at dot0 (f->dots[0]), we hit:
357 * (dot0), edge0, dot1, edge1, dot2,...
367 * Therefore, edgeK joins dotK and dot{K+1}
370 /* Around this face, either the next dot or the previous dot
371 * must be e->dot2. Otherwise the edge is wrong. */
375 if (f
->dots
[k2
] == e
->dot2
) {
376 /* dot1(k) and dot2(k2) go clockwise around this face, so add
377 * this edge at position k (see diagram). */
378 assert(f
->edges
[k
] == NULL
);
382 /* Try previous dot */
386 if (f
->dots
[k2
] == e
->dot2
) {
387 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
388 assert(f
->edges
[k2
] == NULL
);
392 assert(!"Grid broken: bad edge-face relationship");
396 /* ====== Stage 3 ======
397 * For each dot, build its edge-list and face-list.
400 /* We don't know how many edges/faces go around each dot, so we can't
401 * allocate the right space for these lists. Pre-compute the sizes by
402 * iterating over each edge and recording a tally against each dot. */
403 for (i
= 0; i
< g
->num_dots
; i
++) {
404 g
->dots
[i
].order
= 0;
406 for (i
= 0; i
< g
->num_edges
; i
++) {
407 grid_edge
*e
= g
->edges
+ i
;
411 /* Now we have the sizes, pre-allocate the edge and face lists. */
412 for (i
= 0; i
< g
->num_dots
; i
++) {
413 grid_dot
*d
= g
->dots
+ i
;
415 assert(d
->order
>= 2); /* sanity check */
416 d
->edges
= snewn(d
->order
, grid_edge
*);
417 d
->faces
= snewn(d
->order
, grid_face
*);
418 for (j
= 0; j
< d
->order
; j
++) {
423 /* For each dot, need to find a face that touches it, so we can seed
424 * the edge-face-edge-face process around each dot. */
425 for (i
= 0; i
< g
->num_faces
; i
++) {
426 grid_face
*f
= g
->faces
+ i
;
428 for (j
= 0; j
< f
->order
; j
++) {
429 grid_dot
*d
= f
->dots
[j
];
433 /* Each dot now has a face in its first slot. Generate the remaining
434 * faces and edges around the dot, by searching both clockwise and
435 * anticlockwise from the first face. Need to do both directions,
436 * because of the possibility of hitting the infinite face, which
437 * blocks progress. But there's only one such face, so we will
438 * succeed in finding every edge and face this way. */
439 for (i
= 0; i
< g
->num_dots
; i
++) {
440 grid_dot
*d
= g
->dots
+ i
;
441 int current_face1
= 0; /* ascends clockwise */
442 int current_face2
= 0; /* descends anticlockwise */
444 /* Labelling scheme: as we walk clockwise around the dot, starting
445 * at face0 (d->faces[0]), we hit:
446 * (face0), edge0, face1, edge1, face2,...
458 * So, for example, face1 should be joined to edge0 and edge1,
459 * and those edges should appear in an anticlockwise sense around
460 * that face (see diagram). */
462 /* clockwise search */
464 grid_face
*f
= d
->faces
[current_face1
];
468 /* find dot around this face */
469 for (j
= 0; j
< f
->order
; j
++) {
473 assert(j
!= f
->order
); /* must find dot */
475 /* Around f, required edge is anticlockwise from the dot. See
476 * the other labelling scheme higher up, for why we subtract 1
482 d
->edges
[current_face1
] = e
; /* set edge */
484 if (current_face1
== d
->order
)
488 d
->faces
[current_face1
] =
489 (e
->face1
== f
) ? e
->face2
: e
->face1
;
490 if (d
->faces
[current_face1
] == NULL
)
491 break; /* cannot progress beyond infinite face */
494 /* If the clockwise search made it all the way round, don't need to
495 * bother with the anticlockwise search. */
496 if (current_face1
== d
->order
)
497 continue; /* this dot is complete, move on to next dot */
499 /* anticlockwise search */
501 grid_face
*f
= d
->faces
[current_face2
];
505 /* find dot around this face */
506 for (j
= 0; j
< f
->order
; j
++) {
510 assert(j
!= f
->order
); /* must find dot */
512 /* Around f, required edge is clockwise from the dot. */
516 if (current_face2
== -1)
517 current_face2
= d
->order
- 1;
518 d
->edges
[current_face2
] = e
; /* set edge */
521 if (current_face2
== current_face1
)
523 d
->faces
[current_face2
] =
524 (e
->face1
== f
) ? e
->face2
: e
->face1
;
525 /* There's only 1 infinite face, so we must get all the way
526 * to current_face1 before we hit it. */
527 assert(d
->faces
[current_face2
]);
531 /* ====== Stage 4 ======
532 * Compute other grid settings
535 /* Bounding rectangle */
536 for (i
= 0; i
< g
->num_dots
; i
++) {
537 grid_dot
*d
= g
->dots
+ i
;
539 g
->lowest_x
= g
->highest_x
= d
->x
;
540 g
->lowest_y
= g
->highest_y
= d
->y
;
542 g
->lowest_x
= min(g
->lowest_x
, d
->x
);
543 g
->highest_x
= max(g
->highest_x
, d
->x
);
544 g
->lowest_y
= min(g
->lowest_y
, d
->y
);
545 g
->highest_y
= max(g
->highest_y
, d
->y
);
550 grid_print_derived(g
);
554 /* Helpers for making grid-generation easier. These functions are only
555 * intended for use during grid generation. */
557 /* Comparison function for the (tree234) sorted dot list */
558 static int grid_point_cmp_fn(void *v1
, void *v2
)
563 return p2
->y
- p1
->y
;
565 return p2
->x
- p1
->x
;
567 /* Add a new face to the grid, with its dot list allocated.
568 * Assumes there's enough space allocated for the new face in grid->faces */
569 static void grid_face_add_new(grid
*g
, int face_size
)
572 grid_face
*new_face
= g
->faces
+ g
->num_faces
;
573 new_face
->order
= face_size
;
574 new_face
->dots
= snewn(face_size
, grid_dot
*);
575 for (i
= 0; i
< face_size
; i
++)
576 new_face
->dots
[i
] = NULL
;
577 new_face
->edges
= NULL
;
580 /* Assumes dot list has enough space */
581 static grid_dot
*grid_dot_add_new(grid
*g
, int x
, int y
)
583 grid_dot
*new_dot
= g
->dots
+ g
->num_dots
;
585 new_dot
->edges
= NULL
;
586 new_dot
->faces
= NULL
;
592 /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
593 * in the dot_list, or add a new dot to the grid (and the dot_list) and
595 * Assumes g->dots has enough capacity allocated */
596 static grid_dot
*grid_get_dot(grid
*g
, tree234
*dot_list
, int x
, int y
)
605 ret
= find234(dot_list
, &test
, NULL
);
609 ret
= grid_dot_add_new(g
, x
, y
);
610 add234(dot_list
, ret
);
614 /* Sets the last face of the grid to include this dot, at this position
615 * around the face. Assumes num_faces is at least 1 (a new face has
616 * previously been added, with the required number of dots allocated) */
617 static void grid_face_set_dot(grid
*g
, grid_dot
*d
, int position
)
619 grid_face
*last_face
= g
->faces
+ g
->num_faces
- 1;
620 last_face
->dots
[position
] = d
;
623 /* ------ Generate various types of grid ------ */
625 /* General method is to generate faces, by calculating their dot coordinates.
626 * As new faces are added, we keep track of all the dots so we can tell when
627 * a new face reuses an existing dot. For example, two squares touching at an
628 * edge would generate six unique dots: four dots from the first face, then
629 * two additional dots for the second face, because we detect the other two
630 * dots have already been taken up. This list is stored in a tree234
631 * called "points". No extra memory-allocation needed here - we store the
632 * actual grid_dot* pointers, which all point into the g->dots list.
633 * For this reason, we have to calculate coordinates in such a way as to
634 * eliminate any rounding errors, so we can detect when a dot on one
635 * face precisely lands on a dot of a different face. No floating-point
639 grid
*grid_new_square(int width
, int height
)
645 /* Upper bounds - don't have to be exact */
646 int max_faces
= width
* height
;
647 int max_dots
= (width
+ 1) * (height
+ 1);
651 grid
*g
= grid_new();
653 g
->faces
= snewn(max_faces
, grid_face
);
654 g
->dots
= snewn(max_dots
, grid_dot
);
656 points
= newtree234(grid_point_cmp_fn
);
658 /* generate square faces */
659 for (y
= 0; y
< height
; y
++) {
660 for (x
= 0; x
< width
; x
++) {
666 grid_face_add_new(g
, 4);
667 d
= grid_get_dot(g
, points
, px
, py
);
668 grid_face_set_dot(g
, d
, 0);
669 d
= grid_get_dot(g
, points
, px
+ a
, py
);
670 grid_face_set_dot(g
, d
, 1);
671 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
);
672 grid_face_set_dot(g
, d
, 2);
673 d
= grid_get_dot(g
, points
, px
, py
+ a
);
674 grid_face_set_dot(g
, d
, 3);
679 assert(g
->num_faces
<= max_faces
);
680 assert(g
->num_dots
<= max_dots
);
682 grid_make_consistent(g
);
686 grid
*grid_new_honeycomb(int width
, int height
)
689 /* Vector for side of hexagon - ratio is close to sqrt(3) */
693 /* Upper bounds - don't have to be exact */
694 int max_faces
= width
* height
;
695 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
699 grid
*g
= grid_new();
701 g
->faces
= snewn(max_faces
, grid_face
);
702 g
->dots
= snewn(max_dots
, grid_dot
);
704 points
= newtree234(grid_point_cmp_fn
);
706 /* generate hexagonal faces */
707 for (y
= 0; y
< height
; y
++) {
708 for (x
= 0; x
< width
; x
++) {
715 grid_face_add_new(g
, 6);
717 d
= grid_get_dot(g
, points
, cx
- a
, cy
- b
);
718 grid_face_set_dot(g
, d
, 0);
719 d
= grid_get_dot(g
, points
, cx
+ a
, cy
- b
);
720 grid_face_set_dot(g
, d
, 1);
721 d
= grid_get_dot(g
, points
, cx
+ 2*a
, cy
);
722 grid_face_set_dot(g
, d
, 2);
723 d
= grid_get_dot(g
, points
, cx
+ a
, cy
+ b
);
724 grid_face_set_dot(g
, d
, 3);
725 d
= grid_get_dot(g
, points
, cx
- a
, cy
+ b
);
726 grid_face_set_dot(g
, d
, 4);
727 d
= grid_get_dot(g
, points
, cx
- 2*a
, cy
);
728 grid_face_set_dot(g
, d
, 5);
733 assert(g
->num_faces
<= max_faces
);
734 assert(g
->num_dots
<= max_dots
);
736 grid_make_consistent(g
);
740 /* Doesn't use the previous method of generation, it pre-dates it!
741 * A triangular grid is just about simple enough to do by "brute force" */
742 grid
*grid_new_triangular(int width
, int height
)
746 /* Vector for side of triangle - ratio is close to sqrt(3) */
752 /* convenient alias */
755 grid
*g
= grid_new();
756 g
->tilesize
= 18; /* adjust to your taste */
758 g
->num_faces
= width
* height
* 2;
759 g
->num_dots
= (width
+ 1) * (height
+ 1);
760 g
->faces
= snewn(g
->num_faces
, grid_face
);
761 g
->dots
= snewn(g
->num_dots
, grid_dot
);
765 for (y
= 0; y
<= height
; y
++) {
766 for (x
= 0; x
<= width
; x
++) {
767 grid_dot
*d
= g
->dots
+ index
;
768 /* odd rows are offset to the right */
772 d
->x
= x
* 2 * vec_x
+ ((y
% 2) ? vec_x
: 0);
780 for (y
= 0; y
< height
; y
++) {
781 for (x
= 0; x
< width
; x
++) {
782 /* initialise two faces for this (x,y) */
783 grid_face
*f1
= g
->faces
+ index
;
784 grid_face
*f2
= f1
+ 1;
787 f1
->dots
= snewn(f1
->order
, grid_dot
*);
790 f2
->dots
= snewn(f2
->order
, grid_dot
*);
792 /* face descriptions depend on whether the row-number is
795 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
796 f1
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
797 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
798 f2
->dots
[0] = g
->dots
+ y
* w
+ x
;
799 f2
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
800 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
802 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
803 f1
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
804 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
805 f2
->dots
[0] = g
->dots
+ y
* w
+ x
+ 1;
806 f2
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
807 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
813 grid_make_consistent(g
);
817 grid
*grid_new_snubsquare(int width
, int height
)
820 /* Vector for side of triangle - ratio is close to sqrt(3) */
824 /* Upper bounds - don't have to be exact */
825 int max_faces
= 3 * width
* height
;
826 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
830 grid
*g
= grid_new();
832 g
->faces
= snewn(max_faces
, grid_face
);
833 g
->dots
= snewn(max_dots
, grid_dot
);
835 points
= newtree234(grid_point_cmp_fn
);
837 for (y
= 0; y
< height
; y
++) {
838 for (x
= 0; x
< width
; x
++) {
841 int px
= (a
+ b
) * x
;
842 int py
= (a
+ b
) * y
;
844 /* generate square faces */
845 grid_face_add_new(g
, 4);
847 d
= grid_get_dot(g
, points
, px
+ a
, py
);
848 grid_face_set_dot(g
, d
, 0);
849 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
850 grid_face_set_dot(g
, d
, 1);
851 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
+ b
);
852 grid_face_set_dot(g
, d
, 2);
853 d
= grid_get_dot(g
, points
, px
, py
+ b
);
854 grid_face_set_dot(g
, d
, 3);
856 d
= grid_get_dot(g
, points
, px
+ b
, py
);
857 grid_face_set_dot(g
, d
, 0);
858 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ b
);
859 grid_face_set_dot(g
, d
, 1);
860 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
861 grid_face_set_dot(g
, d
, 2);
862 d
= grid_get_dot(g
, points
, px
, py
+ a
);
863 grid_face_set_dot(g
, d
, 3);
866 /* generate up/down triangles */
868 grid_face_add_new(g
, 3);
870 d
= grid_get_dot(g
, points
, px
+ a
, py
);
871 grid_face_set_dot(g
, d
, 0);
872 d
= grid_get_dot(g
, points
, px
, py
+ b
);
873 grid_face_set_dot(g
, d
, 1);
874 d
= grid_get_dot(g
, points
, px
- a
, py
);
875 grid_face_set_dot(g
, d
, 2);
877 d
= grid_get_dot(g
, points
, px
, py
+ a
);
878 grid_face_set_dot(g
, d
, 0);
879 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
880 grid_face_set_dot(g
, d
, 1);
881 d
= grid_get_dot(g
, points
, px
- a
, py
+ a
+ b
);
882 grid_face_set_dot(g
, d
, 2);
886 /* generate left/right triangles */
888 grid_face_add_new(g
, 3);
890 d
= grid_get_dot(g
, points
, px
+ a
, py
);
891 grid_face_set_dot(g
, d
, 0);
892 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
- a
);
893 grid_face_set_dot(g
, d
, 1);
894 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
895 grid_face_set_dot(g
, d
, 2);
897 d
= grid_get_dot(g
, points
, px
, py
- a
);
898 grid_face_set_dot(g
, d
, 0);
899 d
= grid_get_dot(g
, points
, px
+ b
, py
);
900 grid_face_set_dot(g
, d
, 1);
901 d
= grid_get_dot(g
, points
, px
, py
+ a
);
902 grid_face_set_dot(g
, d
, 2);
909 assert(g
->num_faces
<= max_faces
);
910 assert(g
->num_dots
<= max_dots
);
912 grid_make_consistent(g
);
916 grid
*grid_new_cairo(int width
, int height
)
919 /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
923 /* Upper bounds - don't have to be exact */
924 int max_faces
= 2 * width
* height
;
925 int max_dots
= 3 * (width
+ 1) * (height
+ 1);
929 grid
*g
= grid_new();
931 g
->faces
= snewn(max_faces
, grid_face
);
932 g
->dots
= snewn(max_dots
, grid_dot
);
934 points
= newtree234(grid_point_cmp_fn
);
936 for (y
= 0; y
< height
; y
++) {
937 for (x
= 0; x
< width
; x
++) {
943 /* horizontal pentagons */
945 grid_face_add_new(g
, 5);
947 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
948 grid_face_set_dot(g
, d
, 0);
949 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
- b
);
950 grid_face_set_dot(g
, d
, 1);
951 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
952 grid_face_set_dot(g
, d
, 2);
953 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
954 grid_face_set_dot(g
, d
, 3);
955 d
= grid_get_dot(g
, points
, px
, py
);
956 grid_face_set_dot(g
, d
, 4);
958 d
= grid_get_dot(g
, points
, px
, py
);
959 grid_face_set_dot(g
, d
, 0);
960 d
= grid_get_dot(g
, points
, px
+ b
, py
- a
);
961 grid_face_set_dot(g
, d
, 1);
962 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
963 grid_face_set_dot(g
, d
, 2);
964 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
+ b
);
965 grid_face_set_dot(g
, d
, 3);
966 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
967 grid_face_set_dot(g
, d
, 4);
970 /* vertical pentagons */
972 grid_face_add_new(g
, 5);
974 d
= grid_get_dot(g
, points
, px
, py
);
975 grid_face_set_dot(g
, d
, 0);
976 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
977 grid_face_set_dot(g
, d
, 1);
978 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 2*b
- a
);
979 grid_face_set_dot(g
, d
, 2);
980 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
981 grid_face_set_dot(g
, d
, 3);
982 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
983 grid_face_set_dot(g
, d
, 4);
985 d
= grid_get_dot(g
, points
, px
, py
);
986 grid_face_set_dot(g
, d
, 0);
987 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
988 grid_face_set_dot(g
, d
, 1);
989 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
990 grid_face_set_dot(g
, d
, 2);
991 d
= grid_get_dot(g
, points
, px
- b
, py
+ 2*b
- a
);
992 grid_face_set_dot(g
, d
, 3);
993 d
= grid_get_dot(g
, points
, px
- b
, py
+ a
);
994 grid_face_set_dot(g
, d
, 4);
1000 freetree234(points
);
1001 assert(g
->num_faces
<= max_faces
);
1002 assert(g
->num_dots
<= max_dots
);
1004 grid_make_consistent(g
);
1008 grid
*grid_new_greathexagonal(int width
, int height
)
1011 /* Vector for side of triangle - ratio is close to sqrt(3) */
1015 /* Upper bounds - don't have to be exact */
1016 int max_faces
= 6 * (width
+ 1) * (height
+ 1);
1017 int max_dots
= 6 * width
* height
;
1021 grid
*g
= grid_new();
1023 g
->faces
= snewn(max_faces
, grid_face
);
1024 g
->dots
= snewn(max_dots
, grid_dot
);
1026 points
= newtree234(grid_point_cmp_fn
);
1028 for (y
= 0; y
< height
; y
++) {
1029 for (x
= 0; x
< width
; x
++) {
1031 /* centre of hexagon */
1032 int px
= (3*a
+ b
) * x
;
1033 int py
= (2*a
+ 2*b
) * y
;
1038 grid_face_add_new(g
, 6);
1039 d
= grid_get_dot(g
, points
, px
- a
, py
- b
);
1040 grid_face_set_dot(g
, d
, 0);
1041 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
1042 grid_face_set_dot(g
, d
, 1);
1043 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1044 grid_face_set_dot(g
, d
, 2);
1045 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1046 grid_face_set_dot(g
, d
, 3);
1047 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1048 grid_face_set_dot(g
, d
, 4);
1049 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1050 grid_face_set_dot(g
, d
, 5);
1052 /* square below hexagon */
1053 if (y
< height
- 1) {
1054 grid_face_add_new(g
, 4);
1055 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1056 grid_face_set_dot(g
, d
, 0);
1057 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1058 grid_face_set_dot(g
, d
, 1);
1059 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1060 grid_face_set_dot(g
, d
, 2);
1061 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1062 grid_face_set_dot(g
, d
, 3);
1065 /* square below right */
1066 if ((x
< width
- 1) && (((x
% 2) == 0) || (y
< height
- 1))) {
1067 grid_face_add_new(g
, 4);
1068 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1069 grid_face_set_dot(g
, d
, 0);
1070 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1071 grid_face_set_dot(g
, d
, 1);
1072 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1073 grid_face_set_dot(g
, d
, 2);
1074 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1075 grid_face_set_dot(g
, d
, 3);
1078 /* square below left */
1079 if ((x
> 0) && (((x
% 2) == 0) || (y
< height
- 1))) {
1080 grid_face_add_new(g
, 4);
1081 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1082 grid_face_set_dot(g
, d
, 0);
1083 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1084 grid_face_set_dot(g
, d
, 1);
1085 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1086 grid_face_set_dot(g
, d
, 2);
1087 d
= grid_get_dot(g
, points
, px
- 2*a
- b
, py
+ a
);
1088 grid_face_set_dot(g
, d
, 3);
1091 /* Triangle below right */
1092 if ((x
< width
- 1) && (y
< height
- 1)) {
1093 grid_face_add_new(g
, 3);
1094 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1095 grid_face_set_dot(g
, d
, 0);
1096 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1097 grid_face_set_dot(g
, d
, 1);
1098 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1099 grid_face_set_dot(g
, d
, 2);
1102 /* Triangle below left */
1103 if ((x
> 0) && (y
< height
- 1)) {
1104 grid_face_add_new(g
, 3);
1105 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1106 grid_face_set_dot(g
, d
, 0);
1107 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1108 grid_face_set_dot(g
, d
, 1);
1109 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1110 grid_face_set_dot(g
, d
, 2);
1115 freetree234(points
);
1116 assert(g
->num_faces
<= max_faces
);
1117 assert(g
->num_dots
<= max_dots
);
1119 grid_make_consistent(g
);
1123 grid
*grid_new_octagonal(int width
, int height
)
1126 /* b/a approx sqrt(2) */
1130 /* Upper bounds - don't have to be exact */
1131 int max_faces
= 2 * width
* height
;
1132 int max_dots
= 4 * (width
+ 1) * (height
+ 1);
1136 grid
*g
= grid_new();
1138 g
->faces
= snewn(max_faces
, grid_face
);
1139 g
->dots
= snewn(max_dots
, grid_dot
);
1141 points
= newtree234(grid_point_cmp_fn
);
1143 for (y
= 0; y
< height
; y
++) {
1144 for (x
= 0; x
< width
; x
++) {
1147 int px
= (2*a
+ b
) * x
;
1148 int py
= (2*a
+ b
) * y
;
1150 grid_face_add_new(g
, 8);
1151 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1152 grid_face_set_dot(g
, d
, 0);
1153 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
);
1154 grid_face_set_dot(g
, d
, 1);
1155 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1156 grid_face_set_dot(g
, d
, 2);
1157 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
+ b
);
1158 grid_face_set_dot(g
, d
, 3);
1159 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ 2*a
+ b
);
1160 grid_face_set_dot(g
, d
, 4);
1161 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1162 grid_face_set_dot(g
, d
, 5);
1163 d
= grid_get_dot(g
, points
, px
, py
+ a
+ b
);
1164 grid_face_set_dot(g
, d
, 6);
1165 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1166 grid_face_set_dot(g
, d
, 7);
1169 if ((x
> 0) && (y
> 0)) {
1170 grid_face_add_new(g
, 4);
1171 d
= grid_get_dot(g
, points
, px
, py
- a
);
1172 grid_face_set_dot(g
, d
, 0);
1173 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1174 grid_face_set_dot(g
, d
, 1);
1175 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1176 grid_face_set_dot(g
, d
, 2);
1177 d
= grid_get_dot(g
, points
, px
- a
, py
);
1178 grid_face_set_dot(g
, d
, 3);
1183 freetree234(points
);
1184 assert(g
->num_faces
<= max_faces
);
1185 assert(g
->num_dots
<= max_dots
);
1187 grid_make_consistent(g
);
1191 grid
*grid_new_kites(int width
, int height
)
1194 /* b/a approx sqrt(3) */
1198 /* Upper bounds - don't have to be exact */
1199 int max_faces
= 6 * width
* height
;
1200 int max_dots
= 6 * (width
+ 1) * (height
+ 1);
1204 grid
*g
= grid_new();
1206 g
->faces
= snewn(max_faces
, grid_face
);
1207 g
->dots
= snewn(max_dots
, grid_dot
);
1209 points
= newtree234(grid_point_cmp_fn
);
1211 for (y
= 0; y
< height
; y
++) {
1212 for (x
= 0; x
< width
; x
++) {
1214 /* position of order-6 dot */
1220 /* kite pointing up-left */
1221 grid_face_add_new(g
, 4);
1222 d
= grid_get_dot(g
, points
, px
, py
);
1223 grid_face_set_dot(g
, d
, 0);
1224 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1225 grid_face_set_dot(g
, d
, 1);
1226 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
+ 2*a
);
1227 grid_face_set_dot(g
, d
, 2);
1228 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1229 grid_face_set_dot(g
, d
, 3);
1231 /* kite pointing up */
1232 grid_face_add_new(g
, 4);
1233 d
= grid_get_dot(g
, points
, px
, py
);
1234 grid_face_set_dot(g
, d
, 0);
1235 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1236 grid_face_set_dot(g
, d
, 1);
1237 d
= grid_get_dot(g
, points
, px
, py
+ 4*a
);
1238 grid_face_set_dot(g
, d
, 2);
1239 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1240 grid_face_set_dot(g
, d
, 3);
1242 /* kite pointing up-right */
1243 grid_face_add_new(g
, 4);
1244 d
= grid_get_dot(g
, points
, px
, py
);
1245 grid_face_set_dot(g
, d
, 0);
1246 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1247 grid_face_set_dot(g
, d
, 1);
1248 d
= grid_get_dot(g
, points
, px
- 2*b
, py
+ 2*a
);
1249 grid_face_set_dot(g
, d
, 2);
1250 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1251 grid_face_set_dot(g
, d
, 3);
1253 /* kite pointing down-right */
1254 grid_face_add_new(g
, 4);
1255 d
= grid_get_dot(g
, points
, px
, py
);
1256 grid_face_set_dot(g
, d
, 0);
1257 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1258 grid_face_set_dot(g
, d
, 1);
1259 d
= grid_get_dot(g
, points
, px
- 2*b
, py
- 2*a
);
1260 grid_face_set_dot(g
, d
, 2);
1261 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1262 grid_face_set_dot(g
, d
, 3);
1264 /* kite pointing down */
1265 grid_face_add_new(g
, 4);
1266 d
= grid_get_dot(g
, points
, px
, py
);
1267 grid_face_set_dot(g
, d
, 0);
1268 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1269 grid_face_set_dot(g
, d
, 1);
1270 d
= grid_get_dot(g
, points
, px
, py
- 4*a
);
1271 grid_face_set_dot(g
, d
, 2);
1272 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1273 grid_face_set_dot(g
, d
, 3);
1275 /* kite pointing down-left */
1276 grid_face_add_new(g
, 4);
1277 d
= grid_get_dot(g
, points
, px
, py
);
1278 grid_face_set_dot(g
, d
, 0);
1279 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1280 grid_face_set_dot(g
, d
, 1);
1281 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
- 2*a
);
1282 grid_face_set_dot(g
, d
, 2);
1283 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1284 grid_face_set_dot(g
, d
, 3);
1288 freetree234(points
);
1289 assert(g
->num_faces
<= max_faces
);
1290 assert(g
->num_dots
<= max_dots
);
1292 grid_make_consistent(g
);
1296 grid
*grid_new_floret(int width
, int height
)
1299 /* Vectors for sides; weird numbers needed to keep puzzle aligned with window
1300 * -py/px is close to tan(30 - atan(sqrt(3)/9))
1301 * using py=26 makes everything lean to the left, rather than right
1303 int px
= 75, py
= -26; /* |( 75, -26)| = 79.43 */
1304 int qx
= 4*px
/5, qy
= -py
*2; /* |( 60, 52)| = 79.40 */
1305 int rx
= qx
-px
, ry
= qy
-py
; /* |(-15, 78)| = 79.38 */
1307 /* Upper bounds - don't have to be exact */
1308 int max_faces
= 6 * width
* height
;
1309 int max_dots
= 9 * (width
+ 1) * (height
+ 1);
1313 grid
*g
= grid_new();
1314 g
->tilesize
= 2 * px
;
1315 g
->faces
= snewn(max_faces
, grid_face
);
1316 g
->dots
= snewn(max_dots
, grid_dot
);
1318 points
= newtree234(grid_point_cmp_fn
);
1320 /* generate pentagonal faces */
1321 for (y
= 0; y
< height
; y
++) {
1322 for (x
= 0; x
< width
; x
++) {
1325 int cx
= (6*px
+3*qx
)/2 * x
;
1326 int cy
= (4*py
-5*qy
) * y
;
1328 cy
-= (4*py
-5*qy
)/2;
1329 else if (y
&& y
== height
-1)
1330 continue; /* make better looking grids? try 3x3 for instance */
1332 grid_face_add_new(g
, 5);
1333 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1334 d
= grid_get_dot(g
, points
, cx
+2*rx
, cy
+2*ry
); grid_face_set_dot(g
, d
, 1);
1335 d
= grid_get_dot(g
, points
, cx
+2*rx
+qx
, cy
+2*ry
+qy
); grid_face_set_dot(g
, d
, 2);
1336 d
= grid_get_dot(g
, points
, cx
+2*qx
+rx
, cy
+2*qy
+ry
); grid_face_set_dot(g
, d
, 3);
1337 d
= grid_get_dot(g
, points
, cx
+2*qx
, cy
+2*qy
); grid_face_set_dot(g
, d
, 4);
1339 grid_face_add_new(g
, 5);
1340 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1341 d
= grid_get_dot(g
, points
, cx
+2*qx
, cy
+2*qy
); grid_face_set_dot(g
, d
, 1);
1342 d
= grid_get_dot(g
, points
, cx
+2*qx
+px
, cy
+2*qy
+py
); grid_face_set_dot(g
, d
, 2);
1343 d
= grid_get_dot(g
, points
, cx
+2*px
+qx
, cy
+2*py
+qy
); grid_face_set_dot(g
, d
, 3);
1344 d
= grid_get_dot(g
, points
, cx
+2*px
, cy
+2*py
); grid_face_set_dot(g
, d
, 4);
1346 grid_face_add_new(g
, 5);
1347 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1348 d
= grid_get_dot(g
, points
, cx
+2*px
, cy
+2*py
); grid_face_set_dot(g
, d
, 1);
1349 d
= grid_get_dot(g
, points
, cx
+2*px
-rx
, cy
+2*py
-ry
); grid_face_set_dot(g
, d
, 2);
1350 d
= grid_get_dot(g
, points
, cx
-2*rx
+px
, cy
-2*ry
+py
); grid_face_set_dot(g
, d
, 3);
1351 d
= grid_get_dot(g
, points
, cx
-2*rx
, cy
-2*ry
); grid_face_set_dot(g
, d
, 4);
1353 grid_face_add_new(g
, 5);
1354 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1355 d
= grid_get_dot(g
, points
, cx
-2*rx
, cy
-2*ry
); grid_face_set_dot(g
, d
, 1);
1356 d
= grid_get_dot(g
, points
, cx
-2*rx
-qx
, cy
-2*ry
-qy
); grid_face_set_dot(g
, d
, 2);
1357 d
= grid_get_dot(g
, points
, cx
-2*qx
-rx
, cy
-2*qy
-ry
); grid_face_set_dot(g
, d
, 3);
1358 d
= grid_get_dot(g
, points
, cx
-2*qx
, cy
-2*qy
); grid_face_set_dot(g
, d
, 4);
1360 grid_face_add_new(g
, 5);
1361 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1362 d
= grid_get_dot(g
, points
, cx
-2*qx
, cy
-2*qy
); grid_face_set_dot(g
, d
, 1);
1363 d
= grid_get_dot(g
, points
, cx
-2*qx
-px
, cy
-2*qy
-py
); grid_face_set_dot(g
, d
, 2);
1364 d
= grid_get_dot(g
, points
, cx
-2*px
-qx
, cy
-2*py
-qy
); grid_face_set_dot(g
, d
, 3);
1365 d
= grid_get_dot(g
, points
, cx
-2*px
, cy
-2*py
); grid_face_set_dot(g
, d
, 4);
1367 grid_face_add_new(g
, 5);
1368 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1369 d
= grid_get_dot(g
, points
, cx
-2*px
, cy
-2*py
); grid_face_set_dot(g
, d
, 1);
1370 d
= grid_get_dot(g
, points
, cx
-2*px
+rx
, cy
-2*py
+ry
); grid_face_set_dot(g
, d
, 2);
1371 d
= grid_get_dot(g
, points
, cx
+2*rx
-px
, cy
+2*ry
-py
); grid_face_set_dot(g
, d
, 3);
1372 d
= grid_get_dot(g
, points
, cx
+2*rx
, cy
+2*ry
); grid_face_set_dot(g
, d
, 4);
1376 freetree234(points
);
1377 assert(g
->num_faces
<= max_faces
);
1378 assert(g
->num_dots
<= max_dots
);
1380 grid_make_consistent(g
);
1384 grid
*grid_new_dodecagonal(int width
, int height
)
1387 /* Vector for side of triangle - ratio is close to sqrt(3) */
1391 /* Upper bounds - don't have to be exact */
1392 int max_faces
= 3 * width
* height
;
1393 int max_dots
= 14 * width
* height
;
1397 grid
*g
= grid_new();
1399 g
->faces
= snewn(max_faces
, grid_face
);
1400 g
->dots
= snewn(max_dots
, grid_dot
);
1402 points
= newtree234(grid_point_cmp_fn
);
1404 for (y
= 0; y
< height
; y
++) {
1405 for (x
= 0; x
< width
; x
++) {
1407 /* centre of dodecagon */
1408 int px
= (4*a
+ 2*b
) * x
;
1409 int py
= (3*a
+ 2*b
) * y
;
1414 grid_face_add_new(g
, 12);
1415 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1416 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 1);
1417 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 2);
1418 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 3);
1419 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 4);
1420 d
= grid_get_dot(g
, points
, px
+ ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
1421 d
= grid_get_dot(g
, points
, px
- ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 6);
1422 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 7);
1423 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 8);
1424 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 9);
1425 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 10);
1426 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 11);
1428 /* triangle below dodecagon */
1429 if ((y
< height
- 1 && (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2)))) {
1430 grid_face_add_new(g
, 3);
1431 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1432 d
= grid_get_dot(g
, points
, px
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1433 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 2);
1436 /* triangle above dodecagon */
1437 if ((y
&& (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2)))) {
1438 grid_face_add_new(g
, 3);
1439 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1440 d
= grid_get_dot(g
, points
, px
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1441 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 2);
1446 freetree234(points
);
1447 assert(g
->num_faces
<= max_faces
);
1448 assert(g
->num_dots
<= max_dots
);
1450 grid_make_consistent(g
);
1454 grid
*grid_new_greatdodecagonal(int width
, int height
)
1457 /* Vector for side of triangle - ratio is close to sqrt(3) */
1461 /* Upper bounds - don't have to be exact */
1462 int max_faces
= 30 * width
* height
;
1463 int max_dots
= 200 * width
* height
;
1467 grid
*g
= grid_new();
1469 g
->faces
= snewn(max_faces
, grid_face
);
1470 g
->dots
= snewn(max_dots
, grid_dot
);
1472 points
= newtree234(grid_point_cmp_fn
);
1474 for (y
= 0; y
< height
; y
++) {
1475 for (x
= 0; x
< width
; x
++) {
1477 /* centre of dodecagon */
1478 int px
= (6*a
+ 2*b
) * x
;
1479 int py
= (3*a
+ 3*b
) * y
;
1484 grid_face_add_new(g
, 12);
1485 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1486 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 1);
1487 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 2);
1488 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 3);
1489 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 4);
1490 d
= grid_get_dot(g
, points
, px
+ ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
1491 d
= grid_get_dot(g
, points
, px
- ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 6);
1492 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 7);
1493 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 8);
1494 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 9);
1495 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 10);
1496 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 11);
1498 /* hexagon below dodecagon */
1499 if (y
< height
- 1 && (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2))) {
1500 grid_face_add_new(g
, 6);
1501 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1502 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1503 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 2);
1504 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 3);
1505 d
= grid_get_dot(g
, points
, px
- 2*a
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 4);
1506 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
1509 /* hexagon above dodecagon */
1510 if (y
&& (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2))) {
1511 grid_face_add_new(g
, 6);
1512 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1513 d
= grid_get_dot(g
, points
, px
- 2*a
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1514 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 2);
1515 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 3);
1516 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 4);
1517 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
1520 /* square on right of dodecagon */
1521 if (x
< width
- 1) {
1522 grid_face_add_new(g
, 4);
1523 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
- a
); grid_face_set_dot(g
, d
, 0);
1524 d
= grid_get_dot(g
, points
, px
+ 4*a
+ b
, py
- a
); grid_face_set_dot(g
, d
, 1);
1525 d
= grid_get_dot(g
, points
, px
+ 4*a
+ b
, py
+ a
); grid_face_set_dot(g
, d
, 2);
1526 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
); grid_face_set_dot(g
, d
, 3);
1529 /* square on top right of dodecagon */
1530 if (y
&& (x
< width
- 1 || !(y
% 2))) {
1531 grid_face_add_new(g
, 4);
1532 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1533 d
= grid_get_dot(g
, points
, px
+ (2*a
), py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1534 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
+ 2*b
)); grid_face_set_dot(g
, d
, 2);
1535 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 3);
1538 /* square on top left of dodecagon */
1539 if (y
&& (x
|| (y
% 2))) {
1540 grid_face_add_new(g
, 4);
1541 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 0);
1542 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1543 d
= grid_get_dot(g
, points
, px
- (2*a
), py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 2);
1544 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 3);
1549 freetree234(points
);
1550 assert(g
->num_faces
<= max_faces
);
1551 assert(g
->num_dots
<= max_dots
);
1553 grid_make_consistent(g
);
1557 /* ----------- End of grid generators ------------- */