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()
59 g
->num_faces
= g
->num_edges
= g
->num_dots
= 0;
60 g
->middle_face
= NULL
;
62 g
->lowest_x
= g
->lowest_y
= g
->highest_x
= g
->highest_y
= 0;
66 /* Helper function to calculate perpendicular distance from
67 * a point P to a line AB. A and B mustn't be equal here.
69 * Well-known formula for area A of a triangle:
71 * 2A = determinant of matrix | px ax bx |
74 * Also well-known: 2A = base * height
75 * = perpendicular distance * line-length.
77 * Combining gives: distance = determinant / line-length(a,b)
79 static double point_line_distance(int px
, int py
,
83 int det
= ax
*by
- bx
*ay
+ bx
*py
- px
*by
+ px
*ay
- ax
*py
;
85 double 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 * This algorithm is nice and generic, and doesn't depend on any particular
95 * geometric layout of the grid:
96 * Start at any dot (pick one next to middle_face).
97 * Walk along a path by choosing, from all nearby dots, the one that is
98 * nearest the target (x,y). Hopefully end up at the dot which is closest
99 * to (x,y). Should work, as long as faces aren't too badly shaped.
100 * Then examine each edge around this dot, and pick whichever one is
101 * closest (perpendicular distance) to (x,y).
102 * Using perpendicular distance is not quite right - the edge might be
103 * "off to one side". So we insist that the triangle with (x,y) has
104 * acute angles at the edge's dots.
111 * | edge2 is OK, but edge1 is not, even though
112 * | edge1 is perpendicularly closer to (x,y)
116 grid_edge
*grid_nearest_edge(grid
*g
, int x
, int y
)
119 grid_edge
*best_edge
;
120 double best_distance
= 0;
123 cur
= g
->middle_face
->dots
[0];
127 int dist
= SQ(cur
->x
- x
) + SQ(cur
->y
- y
);
128 /* Look for nearer dot - if found, store in 'new'. */
131 /* Search all dots in all faces touching this dot. Some shapes
132 * (such as in Cairo) don't quite work properly if we only search
133 * the dot's immediate neighbours. */
134 for (i
= 0; i
< cur
->order
; i
++) {
135 grid_face
*f
= cur
->faces
[i
];
138 for (j
= 0; j
< f
->order
; j
++) {
139 grid_dot
*d
= f
->dots
[j
];
140 if (d
== cur
) continue;
141 int new_dist
= SQ(d
->x
- x
) + SQ(d
->y
- y
);
142 if (new_dist
< dist
) {
144 break; /* found closer dot */
148 break; /* found closer dot */
152 /* Didn't find a closer dot among the neighbours of 'cur' */
159 /* 'cur' is nearest dot, so find which of the dot's edges is closest. */
162 for (i
= 0; i
< cur
->order
; i
++) {
163 grid_edge
*e
= cur
->edges
[i
];
164 int e2
; /* squared length of edge */
165 int a2
, b2
; /* squared lengths of other sides */
168 /* See if edge e is eligible - the triangle must have acute angles
169 * at the edge's dots.
170 * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
171 * so detect acute angles by testing for h^2 < a^2 + b^2 */
172 e2
= SQ(e
->dot1
->x
- e
->dot2
->x
) + SQ(e
->dot1
->y
- e
->dot2
->y
);
173 a2
= SQ(e
->dot1
->x
- x
) + SQ(e
->dot1
->y
- y
);
174 b2
= SQ(e
->dot2
->x
- x
) + SQ(e
->dot2
->y
- y
);
175 if (a2
>= e2
+ b2
) continue;
176 if (b2
>= e2
+ a2
) continue;
178 /* e is eligible so far. Now check the edge is reasonably close
179 * to where the user clicked. Don't want to toggle an edge if the
180 * click was way off the grid.
181 * There is room for experimentation here. We could check the
182 * perpendicular distance is within a certain fraction of the length
183 * of the edge. That amounts to testing a rectangular region around
185 * Alternatively, we could check that the angle at the point is obtuse.
186 * That would amount to testing a circular region with the edge as
188 dist
= point_line_distance(x
, y
,
189 e
->dot1
->x
, e
->dot1
->y
,
190 e
->dot2
->x
, e
->dot2
->y
);
191 /* Is dist more than half edge length ? */
192 if (4 * SQ(dist
) > e2
)
195 if (best_edge
== NULL
|| dist
< best_distance
) {
197 best_distance
= dist
;
203 /* ----------------------------------------------------------------------
208 /* Show the basic grid information, before doing grid_make_consistent */
209 static void grid_print_basic(grid
*g
)
211 /* TODO: Maybe we should generate an SVG image of the dots and lines
212 * of the grid here, before grid_make_consistent.
213 * Would help with debugging grid generation. */
215 printf("--- Basic Grid Data ---\n");
216 for (i
= 0; i
< g
->num_faces
; i
++) {
217 grid_face
*f
= g
->faces
+ i
;
218 printf("Face %d: dots[", i
);
220 for (j
= 0; j
< f
->order
; j
++) {
221 grid_dot
*d
= f
->dots
[j
];
222 printf("%s%d", j ?
"," : "", (int)(d
- g
->dots
));
226 printf("Middle face: %d\n", (int)(g
->middle_face
- g
->faces
));
228 /* Show the derived grid information, computed by grid_make_consistent */
229 static void grid_print_derived(grid
*g
)
233 printf("--- Derived Grid Data ---\n");
234 for (i
= 0; i
< g
->num_edges
; i
++) {
235 grid_edge
*e
= g
->edges
+ i
;
236 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
237 i
, (int)(e
->dot1
- g
->dots
), (int)(e
->dot2
- g
->dots
),
238 e
->face1 ?
(int)(e
->face1
- g
->faces
) : -1,
239 e
->face2 ?
(int)(e
->face2
- g
->faces
) : -1);
242 for (i
= 0; i
< g
->num_faces
; i
++) {
243 grid_face
*f
= g
->faces
+ i
;
245 printf("Face %d: faces[", i
);
246 for (j
= 0; j
< f
->order
; j
++) {
247 grid_edge
*e
= f
->edges
[j
];
248 grid_face
*f2
= (e
->face1
== f
) ? e
->face2
: e
->face1
;
249 printf("%s%d", j ?
"," : "", f2 ?
(int)(f2
- g
->faces
) : -1);
254 for (i
= 0; i
< g
->num_dots
; i
++) {
255 grid_dot
*d
= g
->dots
+ i
;
257 printf("Dot %d: dots[", i
);
258 for (j
= 0; j
< d
->order
; j
++) {
259 grid_edge
*e
= d
->edges
[j
];
260 grid_dot
*d2
= (e
->dot1
== d
) ? e
->dot2
: e
->dot1
;
261 printf("%s%d", j ?
"," : "", (int)(d2
- g
->dots
));
264 for (j
= 0; j
< d
->order
; j
++) {
265 grid_face
*f
= d
->faces
[j
];
266 printf("%s%d", j ?
"," : "", f ?
(int)(f
- g
->faces
) : -1);
271 #endif /* DEBUG_GRID */
273 /* Helper function for building incomplete-edges list in
274 * grid_make_consistent() */
275 static int grid_edge_bydots_cmpfn(void *v1
, void *v2
)
281 /* Pointer subtraction is valid here, because all dots point into the
282 * same dot-list (g->dots).
283 * Edges are not "normalised" - the 2 dots could be stored in any order,
284 * so we need to take this into account when comparing edges. */
286 /* Compare first dots */
287 da
= (a
->dot1
< a
->dot2
) ? a
->dot1
: a
->dot2
;
288 db
= (b
->dot1
< b
->dot2
) ? b
->dot1
: b
->dot2
;
291 /* Compare last dots */
292 da
= (a
->dot1
< a
->dot2
) ? a
->dot2
: a
->dot1
;
293 db
= (b
->dot1
< b
->dot2
) ? b
->dot2
: b
->dot1
;
300 /* Input: grid has its dots and faces initialised:
301 * - dots have (optionally) x and y coordinates, but no edges or faces
302 * (pointers are NULL).
303 * - edges not initialised at all
304 * - faces initialised and know which dots they have (but no edges yet). The
305 * dots around each face are assumed to be clockwise.
307 * Output: grid is complete and valid with all relationships defined.
309 static void grid_make_consistent(grid
*g
)
312 tree234
*incomplete_edges
;
313 grid_edge
*next_new_edge
; /* Where new edge will go into g->edges */
319 /* ====== Stage 1 ======
323 /* We know how many dots and faces there are, so we can find the exact
324 * number of edges from Euler's polyhedral formula: F + V = E + 2 .
325 * We use "-1", not "-2" here, because Euler's formula includes the
326 * infinite face, which we don't count. */
327 g
->num_edges
= g
->num_faces
+ g
->num_dots
- 1;
328 g
->edges
= snewn(g
->num_edges
, grid_edge
);
329 next_new_edge
= g
->edges
;
331 /* Iterate over faces, and over each face's dots, generating edges as we
332 * go. As we find each new edge, we can immediately fill in the edge's
333 * dots, but only one of the edge's faces. Later on in the iteration, we
334 * will find the same edge again (unless it's on the border), but we will
335 * know the other face.
336 * For efficiency, maintain a list of the incomplete edges, sorted by
338 incomplete_edges
= newtree234(grid_edge_bydots_cmpfn
);
339 for (i
= 0; i
< g
->num_faces
; i
++) {
340 grid_face
*f
= g
->faces
+ i
;
342 for (j
= 0; j
< f
->order
; j
++) {
343 grid_edge e
; /* fake edge for searching */
344 grid_edge
*edge_found
;
349 e
.dot2
= f
->dots
[j2
];
350 /* Use del234 instead of find234, because we always want to
351 * remove the edge if found */
352 edge_found
= del234(incomplete_edges
, &e
);
354 /* This edge already added, so fill out missing face.
355 * Edge is already removed from incomplete_edges. */
356 edge_found
->face2
= f
;
358 assert(next_new_edge
- g
->edges
< g
->num_edges
);
359 next_new_edge
->dot1
= e
.dot1
;
360 next_new_edge
->dot2
= e
.dot2
;
361 next_new_edge
->face1
= f
;
362 next_new_edge
->face2
= NULL
; /* potentially infinite face */
363 add234(incomplete_edges
, next_new_edge
);
368 freetree234(incomplete_edges
);
370 /* ====== Stage 2 ======
371 * For each face, build its edge list.
374 /* Allocate space for each edge list. Can do this, because each face's
375 * edge-list is the same size as its dot-list. */
376 for (i
= 0; i
< g
->num_faces
; i
++) {
377 grid_face
*f
= g
->faces
+ i
;
379 f
->edges
= snewn(f
->order
, grid_edge
*);
380 /* Preload with NULLs, to help detect potential bugs. */
381 for (j
= 0; j
< f
->order
; j
++)
385 /* Iterate over each edge, and over both its faces. Add this edge to
386 * the face's edge-list, after finding where it should go in the
388 for (i
= 0; i
< g
->num_edges
; i
++) {
389 grid_edge
*e
= g
->edges
+ i
;
391 for (j
= 0; j
< 2; j
++) {
392 grid_face
*f
= j ? e
->face2
: e
->face1
;
394 if (f
== NULL
) continue;
395 /* Find one of the dots around the face */
396 for (k
= 0; k
< f
->order
; k
++) {
397 if (f
->dots
[k
] == e
->dot1
)
398 break; /* found dot1 */
400 assert(k
!= f
->order
); /* Must find the dot around this face */
402 /* Labelling scheme: as we walk clockwise around the face,
403 * starting at dot0 (f->dots[0]), we hit:
404 * (dot0), edge0, dot1, edge1, dot2,...
414 * Therefore, edgeK joins dotK and dot{K+1}
417 /* Around this face, either the next dot or the previous dot
418 * must be e->dot2. Otherwise the edge is wrong. */
422 if (f
->dots
[k2
] == e
->dot2
) {
423 /* dot1(k) and dot2(k2) go clockwise around this face, so add
424 * this edge at position k (see diagram). */
425 assert(f
->edges
[k
] == NULL
);
429 /* Try previous dot */
433 if (f
->dots
[k2
] == e
->dot2
) {
434 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
435 assert(f
->edges
[k2
] == NULL
);
439 assert(!"Grid broken: bad edge-face relationship");
443 /* ====== Stage 3 ======
444 * For each dot, build its edge-list and face-list.
447 /* We don't know how many edges/faces go around each dot, so we can't
448 * allocate the right space for these lists. Pre-compute the sizes by
449 * iterating over each edge and recording a tally against each dot. */
450 for (i
= 0; i
< g
->num_dots
; i
++) {
451 g
->dots
[i
].order
= 0;
453 for (i
= 0; i
< g
->num_edges
; i
++) {
454 grid_edge
*e
= g
->edges
+ i
;
458 /* Now we have the sizes, pre-allocate the edge and face lists. */
459 for (i
= 0; i
< g
->num_dots
; i
++) {
460 grid_dot
*d
= g
->dots
+ i
;
462 assert(d
->order
>= 2); /* sanity check */
463 d
->edges
= snewn(d
->order
, grid_edge
*);
464 d
->faces
= snewn(d
->order
, grid_face
*);
465 for (j
= 0; j
< d
->order
; j
++) {
470 /* For each dot, need to find a face that touches it, so we can seed
471 * the edge-face-edge-face process around each dot. */
472 for (i
= 0; i
< g
->num_faces
; i
++) {
473 grid_face
*f
= g
->faces
+ i
;
475 for (j
= 0; j
< f
->order
; j
++) {
476 grid_dot
*d
= f
->dots
[j
];
480 /* Each dot now has a face in its first slot. Generate the remaining
481 * faces and edges around the dot, by searching both clockwise and
482 * anticlockwise from the first face. Need to do both directions,
483 * because of the possibility of hitting the infinite face, which
484 * blocks progress. But there's only one such face, so we will
485 * succeed in finding every edge and face this way. */
486 for (i
= 0; i
< g
->num_dots
; i
++) {
487 grid_dot
*d
= g
->dots
+ i
;
488 int current_face1
= 0; /* ascends clockwise */
489 int current_face2
= 0; /* descends anticlockwise */
491 /* Labelling scheme: as we walk clockwise around the dot, starting
492 * at face0 (d->faces[0]), we hit:
493 * (face0), edge0, face1, edge1, face2,...
505 * So, for example, face1 should be joined to edge0 and edge1,
506 * and those edges should appear in an anticlockwise sense around
507 * that face (see diagram). */
509 /* clockwise search */
511 grid_face
*f
= d
->faces
[current_face1
];
515 /* find dot around this face */
516 for (j
= 0; j
< f
->order
; j
++) {
520 assert(j
!= f
->order
); /* must find dot */
522 /* Around f, required edge is anticlockwise from the dot. See
523 * the other labelling scheme higher up, for why we subtract 1
529 d
->edges
[current_face1
] = e
; /* set edge */
531 if (current_face1
== d
->order
)
535 d
->faces
[current_face1
] =
536 (e
->face1
== f
) ? e
->face2
: e
->face1
;
537 if (d
->faces
[current_face1
] == NULL
)
538 break; /* cannot progress beyond infinite face */
541 /* If the clockwise search made it all the way round, don't need to
542 * bother with the anticlockwise search. */
543 if (current_face1
== d
->order
)
544 continue; /* this dot is complete, move on to next dot */
546 /* anticlockwise search */
548 grid_face
*f
= d
->faces
[current_face2
];
552 /* find dot around this face */
553 for (j
= 0; j
< f
->order
; j
++) {
557 assert(j
!= f
->order
); /* must find dot */
559 /* Around f, required edge is clockwise from the dot. */
563 if (current_face2
== -1)
564 current_face2
= d
->order
- 1;
565 d
->edges
[current_face2
] = e
; /* set edge */
568 if (current_face2
== current_face1
)
570 d
->faces
[current_face2
] =
571 (e
->face1
== f
) ? e
->face2
: e
->face1
;
572 /* There's only 1 infinite face, so we must get all the way
573 * to current_face1 before we hit it. */
574 assert(d
->faces
[current_face2
]);
578 /* ====== Stage 4 ======
579 * Compute other grid settings
582 /* Bounding rectangle */
583 for (i
= 0; i
< g
->num_dots
; i
++) {
584 grid_dot
*d
= g
->dots
+ i
;
586 g
->lowest_x
= g
->highest_x
= d
->x
;
587 g
->lowest_y
= g
->highest_y
= d
->y
;
589 g
->lowest_x
= min(g
->lowest_x
, d
->x
);
590 g
->highest_x
= max(g
->highest_x
, d
->x
);
591 g
->lowest_y
= min(g
->lowest_y
, d
->y
);
592 g
->highest_y
= max(g
->highest_y
, d
->y
);
597 grid_print_derived(g
);
601 /* Helpers for making grid-generation easier. These functions are only
602 * intended for use during grid generation. */
604 /* Comparison function for the (tree234) sorted dot list */
605 static int grid_point_cmp_fn(void *v1
, void *v2
)
610 return p2
->y
- p1
->y
;
612 return p2
->x
- p1
->x
;
614 /* Add a new face to the grid, with its dot list allocated.
615 * Assumes there's enough space allocated for the new face in grid->faces */
616 static void grid_face_add_new(grid
*g
, int face_size
)
619 grid_face
*new_face
= g
->faces
+ g
->num_faces
;
620 new_face
->order
= face_size
;
621 new_face
->dots
= snewn(face_size
, grid_dot
*);
622 for (i
= 0; i
< face_size
; i
++)
623 new_face
->dots
[i
] = NULL
;
624 new_face
->edges
= NULL
;
627 /* Assumes dot list has enough space */
628 static grid_dot
*grid_dot_add_new(grid
*g
, int x
, int y
)
630 grid_dot
*new_dot
= g
->dots
+ g
->num_dots
;
632 new_dot
->edges
= NULL
;
633 new_dot
->faces
= NULL
;
639 /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
640 * in the dot_list, or add a new dot to the grid (and the dot_list) and
642 * Assumes g->dots has enough capacity allocated */
643 static grid_dot
*grid_get_dot(grid
*g
, tree234
*dot_list
, int x
, int y
)
645 grid_dot test
= {0, NULL
, NULL
, x
, y
};
646 grid_dot
*ret
= find234(dot_list
, &test
, NULL
);
650 ret
= grid_dot_add_new(g
, x
, y
);
651 add234(dot_list
, ret
);
655 /* Sets the last face of the grid to include this dot, at this position
656 * around the face. Assumes num_faces is at least 1 (a new face has
657 * previously been added, with the required number of dots allocated) */
658 static void grid_face_set_dot(grid
*g
, grid_dot
*d
, int position
)
660 grid_face
*last_face
= g
->faces
+ g
->num_faces
- 1;
661 last_face
->dots
[position
] = d
;
664 /* ------ Generate various types of grid ------ */
666 /* General method is to generate faces, by calculating their dot coordinates.
667 * As new faces are added, we keep track of all the dots so we can tell when
668 * a new face reuses an existing dot. For example, two squares touching at an
669 * edge would generate six unique dots: four dots from the first face, then
670 * two additional dots for the second face, because we detect the other two
671 * dots have already been taken up. This list is stored in a tree234
672 * called "points". No extra memory-allocation needed here - we store the
673 * actual grid_dot* pointers, which all point into the g->dots list.
674 * For this reason, we have to calculate coordinates in such a way as to
675 * eliminate any rounding errors, so we can detect when a dot on one
676 * face precisely lands on a dot of a different face. No floating-point
680 grid
*grid_new_square(int width
, int height
)
686 /* Upper bounds - don't have to be exact */
687 int max_faces
= width
* height
;
688 int max_dots
= (width
+ 1) * (height
+ 1);
692 grid
*g
= grid_new();
694 g
->faces
= snewn(max_faces
, grid_face
);
695 g
->dots
= snewn(max_dots
, grid_dot
);
697 points
= newtree234(grid_point_cmp_fn
);
699 /* generate square faces */
700 for (y
= 0; y
< height
; y
++) {
701 for (x
= 0; x
< width
; x
++) {
707 grid_face_add_new(g
, 4);
708 d
= grid_get_dot(g
, points
, px
, py
);
709 grid_face_set_dot(g
, d
, 0);
710 d
= grid_get_dot(g
, points
, px
+ a
, py
);
711 grid_face_set_dot(g
, d
, 1);
712 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
);
713 grid_face_set_dot(g
, d
, 2);
714 d
= grid_get_dot(g
, points
, px
, py
+ a
);
715 grid_face_set_dot(g
, d
, 3);
720 assert(g
->num_faces
<= max_faces
);
721 assert(g
->num_dots
<= max_dots
);
722 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
724 grid_make_consistent(g
);
728 grid
*grid_new_honeycomb(int width
, int height
)
731 /* Vector for side of hexagon - ratio is close to sqrt(3) */
735 /* Upper bounds - don't have to be exact */
736 int max_faces
= width
* height
;
737 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
741 grid
*g
= grid_new();
743 g
->faces
= snewn(max_faces
, grid_face
);
744 g
->dots
= snewn(max_dots
, grid_dot
);
746 points
= newtree234(grid_point_cmp_fn
);
748 /* generate hexagonal faces */
749 for (y
= 0; y
< height
; y
++) {
750 for (x
= 0; x
< width
; x
++) {
757 grid_face_add_new(g
, 6);
759 d
= grid_get_dot(g
, points
, cx
- a
, cy
- b
);
760 grid_face_set_dot(g
, d
, 0);
761 d
= grid_get_dot(g
, points
, cx
+ a
, cy
- b
);
762 grid_face_set_dot(g
, d
, 1);
763 d
= grid_get_dot(g
, points
, cx
+ 2*a
, cy
);
764 grid_face_set_dot(g
, d
, 2);
765 d
= grid_get_dot(g
, points
, cx
+ a
, cy
+ b
);
766 grid_face_set_dot(g
, d
, 3);
767 d
= grid_get_dot(g
, points
, cx
- a
, cy
+ b
);
768 grid_face_set_dot(g
, d
, 4);
769 d
= grid_get_dot(g
, points
, cx
- 2*a
, cy
);
770 grid_face_set_dot(g
, d
, 5);
775 assert(g
->num_faces
<= max_faces
);
776 assert(g
->num_dots
<= max_dots
);
777 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
779 grid_make_consistent(g
);
783 /* Doesn't use the previous method of generation, it pre-dates it!
784 * A triangular grid is just about simple enough to do by "brute force" */
785 grid
*grid_new_triangular(int width
, int height
)
789 /* Vector for side of triangle - ratio is close to sqrt(3) */
795 /* convenient alias */
798 grid
*g
= grid_new();
799 g
->tilesize
= 18; /* adjust to your taste */
801 g
->num_faces
= width
* height
* 2;
802 g
->num_dots
= (width
+ 1) * (height
+ 1);
803 g
->faces
= snewn(g
->num_faces
, grid_face
);
804 g
->dots
= snewn(g
->num_dots
, grid_dot
);
808 for (y
= 0; y
<= height
; y
++) {
809 for (x
= 0; x
<= width
; x
++) {
810 grid_dot
*d
= g
->dots
+ index
;
811 /* odd rows are offset to the right */
815 d
->x
= x
* 2 * vec_x
+ ((y
% 2) ? vec_x
: 0);
823 for (y
= 0; y
< height
; y
++) {
824 for (x
= 0; x
< width
; x
++) {
825 /* initialise two faces for this (x,y) */
826 grid_face
*f1
= g
->faces
+ index
;
827 grid_face
*f2
= f1
+ 1;
830 f1
->dots
= snewn(f1
->order
, grid_dot
*);
833 f2
->dots
= snewn(f2
->order
, grid_dot
*);
835 /* face descriptions depend on whether the row-number is
838 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
839 f1
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
840 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
841 f2
->dots
[0] = g
->dots
+ y
* w
+ x
;
842 f2
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
843 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
845 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
846 f1
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
847 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
848 f2
->dots
[0] = g
->dots
+ y
* w
+ x
+ 1;
849 f2
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
850 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
856 /* "+ width" takes us to the middle of the row, because each row has
857 * (2*width) faces. */
858 g
->middle_face
= g
->faces
+ (height
/ 2) * 2 * width
+ width
;
860 grid_make_consistent(g
);
864 grid
*grid_new_snubsquare(int width
, int height
)
867 /* Vector for side of triangle - ratio is close to sqrt(3) */
871 /* Upper bounds - don't have to be exact */
872 int max_faces
= 3 * width
* height
;
873 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
877 grid
*g
= grid_new();
879 g
->faces
= snewn(max_faces
, grid_face
);
880 g
->dots
= snewn(max_dots
, grid_dot
);
882 points
= newtree234(grid_point_cmp_fn
);
884 for (y
= 0; y
< height
; y
++) {
885 for (x
= 0; x
< width
; x
++) {
888 int px
= (a
+ b
) * x
;
889 int py
= (a
+ b
) * y
;
891 /* generate square faces */
892 grid_face_add_new(g
, 4);
894 d
= grid_get_dot(g
, points
, px
+ a
, py
);
895 grid_face_set_dot(g
, d
, 0);
896 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
897 grid_face_set_dot(g
, d
, 1);
898 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
+ b
);
899 grid_face_set_dot(g
, d
, 2);
900 d
= grid_get_dot(g
, points
, px
, py
+ b
);
901 grid_face_set_dot(g
, d
, 3);
903 d
= grid_get_dot(g
, points
, px
+ b
, py
);
904 grid_face_set_dot(g
, d
, 0);
905 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ b
);
906 grid_face_set_dot(g
, d
, 1);
907 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
908 grid_face_set_dot(g
, d
, 2);
909 d
= grid_get_dot(g
, points
, px
, py
+ a
);
910 grid_face_set_dot(g
, d
, 3);
913 /* generate up/down triangles */
915 grid_face_add_new(g
, 3);
917 d
= grid_get_dot(g
, points
, px
+ a
, py
);
918 grid_face_set_dot(g
, d
, 0);
919 d
= grid_get_dot(g
, points
, px
, py
+ b
);
920 grid_face_set_dot(g
, d
, 1);
921 d
= grid_get_dot(g
, points
, px
- a
, py
);
922 grid_face_set_dot(g
, d
, 2);
924 d
= grid_get_dot(g
, points
, px
, py
+ a
);
925 grid_face_set_dot(g
, d
, 0);
926 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
927 grid_face_set_dot(g
, d
, 1);
928 d
= grid_get_dot(g
, points
, px
- a
, py
+ a
+ b
);
929 grid_face_set_dot(g
, d
, 2);
933 /* generate left/right triangles */
935 grid_face_add_new(g
, 3);
937 d
= grid_get_dot(g
, points
, px
+ a
, py
);
938 grid_face_set_dot(g
, d
, 0);
939 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
- a
);
940 grid_face_set_dot(g
, d
, 1);
941 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
942 grid_face_set_dot(g
, d
, 2);
944 d
= grid_get_dot(g
, points
, px
, py
- a
);
945 grid_face_set_dot(g
, d
, 0);
946 d
= grid_get_dot(g
, points
, px
+ b
, py
);
947 grid_face_set_dot(g
, d
, 1);
948 d
= grid_get_dot(g
, points
, px
, py
+ a
);
949 grid_face_set_dot(g
, d
, 2);
956 assert(g
->num_faces
<= max_faces
);
957 assert(g
->num_dots
<= max_dots
);
958 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
960 grid_make_consistent(g
);
964 grid
*grid_new_cairo(int width
, int height
)
967 /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
971 /* Upper bounds - don't have to be exact */
972 int max_faces
= 2 * width
* height
;
973 int max_dots
= 3 * (width
+ 1) * (height
+ 1);
977 grid
*g
= grid_new();
979 g
->faces
= snewn(max_faces
, grid_face
);
980 g
->dots
= snewn(max_dots
, grid_dot
);
982 points
= newtree234(grid_point_cmp_fn
);
984 for (y
= 0; y
< height
; y
++) {
985 for (x
= 0; x
< width
; x
++) {
991 /* horizontal pentagons */
993 grid_face_add_new(g
, 5);
995 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
996 grid_face_set_dot(g
, d
, 0);
997 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
- b
);
998 grid_face_set_dot(g
, d
, 1);
999 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1000 grid_face_set_dot(g
, d
, 2);
1001 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1002 grid_face_set_dot(g
, d
, 3);
1003 d
= grid_get_dot(g
, points
, px
, py
);
1004 grid_face_set_dot(g
, d
, 4);
1006 d
= grid_get_dot(g
, points
, px
, py
);
1007 grid_face_set_dot(g
, d
, 0);
1008 d
= grid_get_dot(g
, points
, px
+ b
, py
- a
);
1009 grid_face_set_dot(g
, d
, 1);
1010 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1011 grid_face_set_dot(g
, d
, 2);
1012 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
+ b
);
1013 grid_face_set_dot(g
, d
, 3);
1014 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1015 grid_face_set_dot(g
, d
, 4);
1018 /* vertical pentagons */
1020 grid_face_add_new(g
, 5);
1022 d
= grid_get_dot(g
, points
, px
, py
);
1023 grid_face_set_dot(g
, d
, 0);
1024 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1025 grid_face_set_dot(g
, d
, 1);
1026 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 2*b
- a
);
1027 grid_face_set_dot(g
, d
, 2);
1028 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1029 grid_face_set_dot(g
, d
, 3);
1030 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1031 grid_face_set_dot(g
, d
, 4);
1033 d
= grid_get_dot(g
, points
, px
, py
);
1034 grid_face_set_dot(g
, d
, 0);
1035 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1036 grid_face_set_dot(g
, d
, 1);
1037 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1038 grid_face_set_dot(g
, d
, 2);
1039 d
= grid_get_dot(g
, points
, px
- b
, py
+ 2*b
- a
);
1040 grid_face_set_dot(g
, d
, 3);
1041 d
= grid_get_dot(g
, points
, px
- b
, py
+ a
);
1042 grid_face_set_dot(g
, d
, 4);
1048 freetree234(points
);
1049 assert(g
->num_faces
<= max_faces
);
1050 assert(g
->num_dots
<= max_dots
);
1051 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
1053 grid_make_consistent(g
);
1057 grid
*grid_new_greathexagonal(int width
, int height
)
1060 /* Vector for side of triangle - ratio is close to sqrt(3) */
1064 /* Upper bounds - don't have to be exact */
1065 int max_faces
= 6 * (width
+ 1) * (height
+ 1);
1066 int max_dots
= 6 * width
* height
;
1070 grid
*g
= grid_new();
1072 g
->faces
= snewn(max_faces
, grid_face
);
1073 g
->dots
= snewn(max_dots
, grid_dot
);
1075 points
= newtree234(grid_point_cmp_fn
);
1077 for (y
= 0; y
< height
; y
++) {
1078 for (x
= 0; x
< width
; x
++) {
1080 /* centre of hexagon */
1081 int px
= (3*a
+ b
) * x
;
1082 int py
= (2*a
+ 2*b
) * y
;
1087 grid_face_add_new(g
, 6);
1088 d
= grid_get_dot(g
, points
, px
- a
, py
- b
);
1089 grid_face_set_dot(g
, d
, 0);
1090 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
1091 grid_face_set_dot(g
, d
, 1);
1092 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1093 grid_face_set_dot(g
, d
, 2);
1094 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1095 grid_face_set_dot(g
, d
, 3);
1096 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1097 grid_face_set_dot(g
, d
, 4);
1098 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1099 grid_face_set_dot(g
, d
, 5);
1101 /* square below hexagon */
1102 if (y
< height
- 1) {
1103 grid_face_add_new(g
, 4);
1104 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1105 grid_face_set_dot(g
, d
, 0);
1106 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1107 grid_face_set_dot(g
, d
, 1);
1108 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1109 grid_face_set_dot(g
, d
, 2);
1110 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1111 grid_face_set_dot(g
, d
, 3);
1114 /* square below right */
1115 if ((x
< width
- 1) && (((x
% 2) == 0) || (y
< height
- 1))) {
1116 grid_face_add_new(g
, 4);
1117 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1118 grid_face_set_dot(g
, d
, 0);
1119 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1120 grid_face_set_dot(g
, d
, 1);
1121 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1122 grid_face_set_dot(g
, d
, 2);
1123 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1124 grid_face_set_dot(g
, d
, 3);
1127 /* square below left */
1128 if ((x
> 0) && (((x
% 2) == 0) || (y
< height
- 1))) {
1129 grid_face_add_new(g
, 4);
1130 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1131 grid_face_set_dot(g
, d
, 0);
1132 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1133 grid_face_set_dot(g
, d
, 1);
1134 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1135 grid_face_set_dot(g
, d
, 2);
1136 d
= grid_get_dot(g
, points
, px
- 2*a
- b
, py
+ a
);
1137 grid_face_set_dot(g
, d
, 3);
1140 /* Triangle below right */
1141 if ((x
< width
- 1) && (y
< height
- 1)) {
1142 grid_face_add_new(g
, 3);
1143 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1144 grid_face_set_dot(g
, d
, 0);
1145 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1146 grid_face_set_dot(g
, d
, 1);
1147 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1148 grid_face_set_dot(g
, d
, 2);
1151 /* Triangle below left */
1152 if ((x
> 0) && (y
< height
- 1)) {
1153 grid_face_add_new(g
, 3);
1154 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1155 grid_face_set_dot(g
, d
, 0);
1156 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1157 grid_face_set_dot(g
, d
, 1);
1158 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1159 grid_face_set_dot(g
, d
, 2);
1164 freetree234(points
);
1165 assert(g
->num_faces
<= max_faces
);
1166 assert(g
->num_dots
<= max_dots
);
1167 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
1169 grid_make_consistent(g
);
1173 grid
*grid_new_octagonal(int width
, int height
)
1176 /* b/a approx sqrt(2) */
1180 /* Upper bounds - don't have to be exact */
1181 int max_faces
= 2 * width
* height
;
1182 int max_dots
= 4 * (width
+ 1) * (height
+ 1);
1186 grid
*g
= grid_new();
1188 g
->faces
= snewn(max_faces
, grid_face
);
1189 g
->dots
= snewn(max_dots
, grid_dot
);
1191 points
= newtree234(grid_point_cmp_fn
);
1193 for (y
= 0; y
< height
; y
++) {
1194 for (x
= 0; x
< width
; x
++) {
1197 int px
= (2*a
+ b
) * x
;
1198 int py
= (2*a
+ b
) * y
;
1200 grid_face_add_new(g
, 8);
1201 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1202 grid_face_set_dot(g
, d
, 0);
1203 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
);
1204 grid_face_set_dot(g
, d
, 1);
1205 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1206 grid_face_set_dot(g
, d
, 2);
1207 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
+ b
);
1208 grid_face_set_dot(g
, d
, 3);
1209 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ 2*a
+ b
);
1210 grid_face_set_dot(g
, d
, 4);
1211 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1212 grid_face_set_dot(g
, d
, 5);
1213 d
= grid_get_dot(g
, points
, px
, py
+ a
+ b
);
1214 grid_face_set_dot(g
, d
, 6);
1215 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1216 grid_face_set_dot(g
, d
, 7);
1219 if ((x
> 0) && (y
> 0)) {
1220 grid_face_add_new(g
, 4);
1221 d
= grid_get_dot(g
, points
, px
, py
- a
);
1222 grid_face_set_dot(g
, d
, 0);
1223 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1224 grid_face_set_dot(g
, d
, 1);
1225 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1226 grid_face_set_dot(g
, d
, 2);
1227 d
= grid_get_dot(g
, points
, px
- a
, py
);
1228 grid_face_set_dot(g
, d
, 3);
1233 freetree234(points
);
1234 assert(g
->num_faces
<= max_faces
);
1235 assert(g
->num_dots
<= max_dots
);
1236 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
1238 grid_make_consistent(g
);
1242 grid
*grid_new_kites(int width
, int height
)
1245 /* b/a approx sqrt(3) */
1249 /* Upper bounds - don't have to be exact */
1250 int max_faces
= 6 * width
* height
;
1251 int max_dots
= 6 * (width
+ 1) * (height
+ 1);
1255 grid
*g
= grid_new();
1257 g
->faces
= snewn(max_faces
, grid_face
);
1258 g
->dots
= snewn(max_dots
, grid_dot
);
1260 points
= newtree234(grid_point_cmp_fn
);
1262 for (y
= 0; y
< height
; y
++) {
1263 for (x
= 0; x
< width
; x
++) {
1265 /* position of order-6 dot */
1271 /* kite pointing up-left */
1272 grid_face_add_new(g
, 4);
1273 d
= grid_get_dot(g
, points
, px
, py
);
1274 grid_face_set_dot(g
, d
, 0);
1275 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1276 grid_face_set_dot(g
, d
, 1);
1277 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
+ 2*a
);
1278 grid_face_set_dot(g
, d
, 2);
1279 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1280 grid_face_set_dot(g
, d
, 3);
1282 /* kite pointing up */
1283 grid_face_add_new(g
, 4);
1284 d
= grid_get_dot(g
, points
, px
, py
);
1285 grid_face_set_dot(g
, d
, 0);
1286 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1287 grid_face_set_dot(g
, d
, 1);
1288 d
= grid_get_dot(g
, points
, px
, py
+ 4*a
);
1289 grid_face_set_dot(g
, d
, 2);
1290 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1291 grid_face_set_dot(g
, d
, 3);
1293 /* kite pointing up-right */
1294 grid_face_add_new(g
, 4);
1295 d
= grid_get_dot(g
, points
, px
, py
);
1296 grid_face_set_dot(g
, d
, 0);
1297 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1298 grid_face_set_dot(g
, d
, 1);
1299 d
= grid_get_dot(g
, points
, px
- 2*b
, py
+ 2*a
);
1300 grid_face_set_dot(g
, d
, 2);
1301 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1302 grid_face_set_dot(g
, d
, 3);
1304 /* kite pointing down-right */
1305 grid_face_add_new(g
, 4);
1306 d
= grid_get_dot(g
, points
, px
, py
);
1307 grid_face_set_dot(g
, d
, 0);
1308 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1309 grid_face_set_dot(g
, d
, 1);
1310 d
= grid_get_dot(g
, points
, px
- 2*b
, py
- 2*a
);
1311 grid_face_set_dot(g
, d
, 2);
1312 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1313 grid_face_set_dot(g
, d
, 3);
1315 /* kite pointing down */
1316 grid_face_add_new(g
, 4);
1317 d
= grid_get_dot(g
, points
, px
, py
);
1318 grid_face_set_dot(g
, d
, 0);
1319 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1320 grid_face_set_dot(g
, d
, 1);
1321 d
= grid_get_dot(g
, points
, px
, py
- 4*a
);
1322 grid_face_set_dot(g
, d
, 2);
1323 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1324 grid_face_set_dot(g
, d
, 3);
1326 /* kite pointing down-left */
1327 grid_face_add_new(g
, 4);
1328 d
= grid_get_dot(g
, points
, px
, py
);
1329 grid_face_set_dot(g
, d
, 0);
1330 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1331 grid_face_set_dot(g
, d
, 1);
1332 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
- 2*a
);
1333 grid_face_set_dot(g
, d
, 2);
1334 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1335 grid_face_set_dot(g
, d
, 3);
1339 freetree234(points
);
1340 assert(g
->num_faces
<= max_faces
);
1341 assert(g
->num_dots
<= max_dots
);
1342 g
->middle_face
= g
->faces
+ 6 * ((height
/2) * width
+ (width
/2));
1344 grid_make_consistent(g
);
1348 /* ----------- End of grid generators ------------- */