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;
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(long px
, long py
,
83 long det
= ax
*by
- bx
*ay
+ bx
*py
- px
*by
+ px
*ay
- ax
*py
;
86 len
= sqrt(SQ(ax
- bx
) + SQ(ay
- by
));
90 /* Determine nearest edge to where the user clicked.
91 * (x, y) is the clicked location, converted to grid coordinates.
92 * Returns the nearest edge, or NULL if no edge is reasonably
95 * This algorithm is nice and generic, and doesn't depend on any particular
96 * geometric layout of the grid:
97 * Start at any dot (pick one next to middle_face).
98 * Walk along a path by choosing, from all nearby dots, the one that is
99 * nearest the target (x,y). Hopefully end up at the dot which is closest
100 * to (x,y). Should work, as long as faces aren't too badly shaped.
101 * Then examine each edge around this dot, and pick whichever one is
102 * closest (perpendicular distance) to (x,y).
103 * Using perpendicular distance is not quite right - the edge might be
104 * "off to one side". So we insist that the triangle with (x,y) has
105 * acute angles at the edge's dots.
112 * | edge2 is OK, but edge1 is not, even though
113 * | edge1 is perpendicularly closer to (x,y)
117 grid_edge
*grid_nearest_edge(grid
*g
, int x
, int y
)
120 grid_edge
*best_edge
;
121 double best_distance
= 0;
124 cur
= g
->middle_face
->dots
[0];
128 long dist
= SQ((long)cur
->x
- (long)x
) + SQ((long)cur
->y
- (long)y
);
129 /* Look for nearer dot - if found, store in 'new'. */
132 /* Search all dots in all faces touching this dot. Some shapes
133 * (such as in Cairo) don't quite work properly if we only search
134 * the dot's immediate neighbours. */
135 for (i
= 0; i
< cur
->order
; i
++) {
136 grid_face
*f
= cur
->faces
[i
];
139 for (j
= 0; j
< f
->order
; j
++) {
141 grid_dot
*d
= f
->dots
[j
];
142 if (d
== cur
) continue;
143 new_dist
= SQ((long)d
->x
- (long)x
) + SQ((long)d
->y
- (long)y
);
144 if (new_dist
< dist
) {
146 break; /* found closer dot */
150 break; /* found closer dot */
154 /* Didn't find a closer dot among the neighbours of 'cur' */
160 /* 'cur' is nearest dot, so find which of the dot's edges is closest. */
163 for (i
= 0; i
< cur
->order
; i
++) {
164 grid_edge
*e
= cur
->edges
[i
];
165 long e2
; /* squared length of edge */
166 long a2
, b2
; /* squared lengths of other sides */
169 /* See if edge e is eligible - the triangle must have acute angles
170 * at the edge's dots.
171 * Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
172 * so detect acute angles by testing for h^2 < a^2 + b^2 */
173 e2
= SQ((long)e
->dot1
->x
- (long)e
->dot2
->x
) + SQ((long)e
->dot1
->y
- (long)e
->dot2
->y
);
174 a2
= SQ((long)e
->dot1
->x
- (long)x
) + SQ((long)e
->dot1
->y
- (long)y
);
175 b2
= SQ((long)e
->dot2
->x
- (long)x
) + SQ((long)e
->dot2
->y
- (long)y
);
176 if (a2
>= e2
+ b2
) continue;
177 if (b2
>= e2
+ a2
) continue;
179 /* e is eligible so far. Now check the edge is reasonably close
180 * to where the user clicked. Don't want to toggle an edge if the
181 * click was way off the grid.
182 * There is room for experimentation here. We could check the
183 * perpendicular distance is within a certain fraction of the length
184 * of the edge. That amounts to testing a rectangular region around
186 * Alternatively, we could check that the angle at the point is obtuse.
187 * That would amount to testing a circular region with the edge as
189 dist
= point_line_distance((long)x
, (long)y
,
190 (long)e
->dot1
->x
, (long)e
->dot1
->y
,
191 (long)e
->dot2
->x
, (long)e
->dot2
->y
);
192 /* Is dist more than half edge length ? */
193 if (4 * SQ(dist
) > e2
)
196 if (best_edge
== NULL
|| dist
< best_distance
) {
198 best_distance
= dist
;
204 /* ----------------------------------------------------------------------
209 /* Show the basic grid information, before doing grid_make_consistent */
210 static void grid_print_basic(grid
*g
)
212 /* TODO: Maybe we should generate an SVG image of the dots and lines
213 * of the grid here, before grid_make_consistent.
214 * Would help with debugging grid generation. */
216 printf("--- Basic Grid Data ---\n");
217 for (i
= 0; i
< g
->num_faces
; i
++) {
218 grid_face
*f
= g
->faces
+ i
;
219 printf("Face %d: dots[", i
);
221 for (j
= 0; j
< f
->order
; j
++) {
222 grid_dot
*d
= f
->dots
[j
];
223 printf("%s%d", j ?
"," : "", (int)(d
- g
->dots
));
227 printf("Middle face: %d\n", (int)(g
->middle_face
- g
->faces
));
229 /* Show the derived grid information, computed by grid_make_consistent */
230 static void grid_print_derived(grid
*g
)
234 printf("--- Derived Grid Data ---\n");
235 for (i
= 0; i
< g
->num_edges
; i
++) {
236 grid_edge
*e
= g
->edges
+ i
;
237 printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
238 i
, (int)(e
->dot1
- g
->dots
), (int)(e
->dot2
- g
->dots
),
239 e
->face1 ?
(int)(e
->face1
- g
->faces
) : -1,
240 e
->face2 ?
(int)(e
->face2
- g
->faces
) : -1);
243 for (i
= 0; i
< g
->num_faces
; i
++) {
244 grid_face
*f
= g
->faces
+ i
;
246 printf("Face %d: faces[", i
);
247 for (j
= 0; j
< f
->order
; j
++) {
248 grid_edge
*e
= f
->edges
[j
];
249 grid_face
*f2
= (e
->face1
== f
) ? e
->face2
: e
->face1
;
250 printf("%s%d", j ?
"," : "", f2 ?
(int)(f2
- g
->faces
) : -1);
255 for (i
= 0; i
< g
->num_dots
; i
++) {
256 grid_dot
*d
= g
->dots
+ i
;
258 printf("Dot %d: dots[", i
);
259 for (j
= 0; j
< d
->order
; j
++) {
260 grid_edge
*e
= d
->edges
[j
];
261 grid_dot
*d2
= (e
->dot1
== d
) ? e
->dot2
: e
->dot1
;
262 printf("%s%d", j ?
"," : "", (int)(d2
- g
->dots
));
265 for (j
= 0; j
< d
->order
; j
++) {
266 grid_face
*f
= d
->faces
[j
];
267 printf("%s%d", j ?
"," : "", f ?
(int)(f
- g
->faces
) : -1);
272 #endif /* DEBUG_GRID */
274 /* Helper function for building incomplete-edges list in
275 * grid_make_consistent() */
276 static int grid_edge_bydots_cmpfn(void *v1
, void *v2
)
282 /* Pointer subtraction is valid here, because all dots point into the
283 * same dot-list (g->dots).
284 * Edges are not "normalised" - the 2 dots could be stored in any order,
285 * so we need to take this into account when comparing edges. */
287 /* Compare first dots */
288 da
= (a
->dot1
< a
->dot2
) ? a
->dot1
: a
->dot2
;
289 db
= (b
->dot1
< b
->dot2
) ? b
->dot1
: b
->dot2
;
292 /* Compare last dots */
293 da
= (a
->dot1
< a
->dot2
) ? a
->dot2
: a
->dot1
;
294 db
= (b
->dot1
< b
->dot2
) ? b
->dot2
: b
->dot1
;
301 /* Input: grid has its dots and faces initialised:
302 * - dots have (optionally) x and y coordinates, but no edges or faces
303 * (pointers are NULL).
304 * - edges not initialised at all
305 * - faces initialised and know which dots they have (but no edges yet). The
306 * dots around each face are assumed to be clockwise.
308 * Output: grid is complete and valid with all relationships defined.
310 static void grid_make_consistent(grid
*g
)
313 tree234
*incomplete_edges
;
314 grid_edge
*next_new_edge
; /* Where new edge will go into g->edges */
320 /* ====== Stage 1 ======
324 /* We know how many dots and faces there are, so we can find the exact
325 * number of edges from Euler's polyhedral formula: F + V = E + 2 .
326 * We use "-1", not "-2" here, because Euler's formula includes the
327 * infinite face, which we don't count. */
328 g
->num_edges
= g
->num_faces
+ g
->num_dots
- 1;
329 g
->edges
= snewn(g
->num_edges
, grid_edge
);
330 next_new_edge
= g
->edges
;
332 /* Iterate over faces, and over each face's dots, generating edges as we
333 * go. As we find each new edge, we can immediately fill in the edge's
334 * dots, but only one of the edge's faces. Later on in the iteration, we
335 * will find the same edge again (unless it's on the border), but we will
336 * know the other face.
337 * For efficiency, maintain a list of the incomplete edges, sorted by
339 incomplete_edges
= newtree234(grid_edge_bydots_cmpfn
);
340 for (i
= 0; i
< g
->num_faces
; i
++) {
341 grid_face
*f
= g
->faces
+ i
;
343 for (j
= 0; j
< f
->order
; j
++) {
344 grid_edge e
; /* fake edge for searching */
345 grid_edge
*edge_found
;
350 e
.dot2
= f
->dots
[j2
];
351 /* Use del234 instead of find234, because we always want to
352 * remove the edge if found */
353 edge_found
= del234(incomplete_edges
, &e
);
355 /* This edge already added, so fill out missing face.
356 * Edge is already removed from incomplete_edges. */
357 edge_found
->face2
= f
;
359 assert(next_new_edge
- g
->edges
< g
->num_edges
);
360 next_new_edge
->dot1
= e
.dot1
;
361 next_new_edge
->dot2
= e
.dot2
;
362 next_new_edge
->face1
= f
;
363 next_new_edge
->face2
= NULL
; /* potentially infinite face */
364 add234(incomplete_edges
, next_new_edge
);
369 freetree234(incomplete_edges
);
371 /* ====== Stage 2 ======
372 * For each face, build its edge list.
375 /* Allocate space for each edge list. Can do this, because each face's
376 * edge-list is the same size as its dot-list. */
377 for (i
= 0; i
< g
->num_faces
; i
++) {
378 grid_face
*f
= g
->faces
+ i
;
380 f
->edges
= snewn(f
->order
, grid_edge
*);
381 /* Preload with NULLs, to help detect potential bugs. */
382 for (j
= 0; j
< f
->order
; j
++)
386 /* Iterate over each edge, and over both its faces. Add this edge to
387 * the face's edge-list, after finding where it should go in the
389 for (i
= 0; i
< g
->num_edges
; i
++) {
390 grid_edge
*e
= g
->edges
+ i
;
392 for (j
= 0; j
< 2; j
++) {
393 grid_face
*f
= j ? e
->face2
: e
->face1
;
395 if (f
== NULL
) continue;
396 /* Find one of the dots around the face */
397 for (k
= 0; k
< f
->order
; k
++) {
398 if (f
->dots
[k
] == e
->dot1
)
399 break; /* found dot1 */
401 assert(k
!= f
->order
); /* Must find the dot around this face */
403 /* Labelling scheme: as we walk clockwise around the face,
404 * starting at dot0 (f->dots[0]), we hit:
405 * (dot0), edge0, dot1, edge1, dot2,...
415 * Therefore, edgeK joins dotK and dot{K+1}
418 /* Around this face, either the next dot or the previous dot
419 * must be e->dot2. Otherwise the edge is wrong. */
423 if (f
->dots
[k2
] == e
->dot2
) {
424 /* dot1(k) and dot2(k2) go clockwise around this face, so add
425 * this edge at position k (see diagram). */
426 assert(f
->edges
[k
] == NULL
);
430 /* Try previous dot */
434 if (f
->dots
[k2
] == e
->dot2
) {
435 /* dot1(k) and dot2(k2) go anticlockwise around this face. */
436 assert(f
->edges
[k2
] == NULL
);
440 assert(!"Grid broken: bad edge-face relationship");
444 /* ====== Stage 3 ======
445 * For each dot, build its edge-list and face-list.
448 /* We don't know how many edges/faces go around each dot, so we can't
449 * allocate the right space for these lists. Pre-compute the sizes by
450 * iterating over each edge and recording a tally against each dot. */
451 for (i
= 0; i
< g
->num_dots
; i
++) {
452 g
->dots
[i
].order
= 0;
454 for (i
= 0; i
< g
->num_edges
; i
++) {
455 grid_edge
*e
= g
->edges
+ i
;
459 /* Now we have the sizes, pre-allocate the edge and face lists. */
460 for (i
= 0; i
< g
->num_dots
; i
++) {
461 grid_dot
*d
= g
->dots
+ i
;
463 assert(d
->order
>= 2); /* sanity check */
464 d
->edges
= snewn(d
->order
, grid_edge
*);
465 d
->faces
= snewn(d
->order
, grid_face
*);
466 for (j
= 0; j
< d
->order
; j
++) {
471 /* For each dot, need to find a face that touches it, so we can seed
472 * the edge-face-edge-face process around each dot. */
473 for (i
= 0; i
< g
->num_faces
; i
++) {
474 grid_face
*f
= g
->faces
+ i
;
476 for (j
= 0; j
< f
->order
; j
++) {
477 grid_dot
*d
= f
->dots
[j
];
481 /* Each dot now has a face in its first slot. Generate the remaining
482 * faces and edges around the dot, by searching both clockwise and
483 * anticlockwise from the first face. Need to do both directions,
484 * because of the possibility of hitting the infinite face, which
485 * blocks progress. But there's only one such face, so we will
486 * succeed in finding every edge and face this way. */
487 for (i
= 0; i
< g
->num_dots
; i
++) {
488 grid_dot
*d
= g
->dots
+ i
;
489 int current_face1
= 0; /* ascends clockwise */
490 int current_face2
= 0; /* descends anticlockwise */
492 /* Labelling scheme: as we walk clockwise around the dot, starting
493 * at face0 (d->faces[0]), we hit:
494 * (face0), edge0, face1, edge1, face2,...
506 * So, for example, face1 should be joined to edge0 and edge1,
507 * and those edges should appear in an anticlockwise sense around
508 * that face (see diagram). */
510 /* clockwise search */
512 grid_face
*f
= d
->faces
[current_face1
];
516 /* find dot around this face */
517 for (j
= 0; j
< f
->order
; j
++) {
521 assert(j
!= f
->order
); /* must find dot */
523 /* Around f, required edge is anticlockwise from the dot. See
524 * the other labelling scheme higher up, for why we subtract 1
530 d
->edges
[current_face1
] = e
; /* set edge */
532 if (current_face1
== d
->order
)
536 d
->faces
[current_face1
] =
537 (e
->face1
== f
) ? e
->face2
: e
->face1
;
538 if (d
->faces
[current_face1
] == NULL
)
539 break; /* cannot progress beyond infinite face */
542 /* If the clockwise search made it all the way round, don't need to
543 * bother with the anticlockwise search. */
544 if (current_face1
== d
->order
)
545 continue; /* this dot is complete, move on to next dot */
547 /* anticlockwise search */
549 grid_face
*f
= d
->faces
[current_face2
];
553 /* find dot around this face */
554 for (j
= 0; j
< f
->order
; j
++) {
558 assert(j
!= f
->order
); /* must find dot */
560 /* Around f, required edge is clockwise from the dot. */
564 if (current_face2
== -1)
565 current_face2
= d
->order
- 1;
566 d
->edges
[current_face2
] = e
; /* set edge */
569 if (current_face2
== current_face1
)
571 d
->faces
[current_face2
] =
572 (e
->face1
== f
) ? e
->face2
: e
->face1
;
573 /* There's only 1 infinite face, so we must get all the way
574 * to current_face1 before we hit it. */
575 assert(d
->faces
[current_face2
]);
579 /* ====== Stage 4 ======
580 * Compute other grid settings
583 /* Bounding rectangle */
584 for (i
= 0; i
< g
->num_dots
; i
++) {
585 grid_dot
*d
= g
->dots
+ i
;
587 g
->lowest_x
= g
->highest_x
= d
->x
;
588 g
->lowest_y
= g
->highest_y
= d
->y
;
590 g
->lowest_x
= min(g
->lowest_x
, d
->x
);
591 g
->highest_x
= max(g
->highest_x
, d
->x
);
592 g
->lowest_y
= min(g
->lowest_y
, d
->y
);
593 g
->highest_y
= max(g
->highest_y
, d
->y
);
598 grid_print_derived(g
);
602 /* Helpers for making grid-generation easier. These functions are only
603 * intended for use during grid generation. */
605 /* Comparison function for the (tree234) sorted dot list */
606 static int grid_point_cmp_fn(void *v1
, void *v2
)
611 return p2
->y
- p1
->y
;
613 return p2
->x
- p1
->x
;
615 /* Add a new face to the grid, with its dot list allocated.
616 * Assumes there's enough space allocated for the new face in grid->faces */
617 static void grid_face_add_new(grid
*g
, int face_size
)
620 grid_face
*new_face
= g
->faces
+ g
->num_faces
;
621 new_face
->order
= face_size
;
622 new_face
->dots
= snewn(face_size
, grid_dot
*);
623 for (i
= 0; i
< face_size
; i
++)
624 new_face
->dots
[i
] = NULL
;
625 new_face
->edges
= NULL
;
628 /* Assumes dot list has enough space */
629 static grid_dot
*grid_dot_add_new(grid
*g
, int x
, int y
)
631 grid_dot
*new_dot
= g
->dots
+ g
->num_dots
;
633 new_dot
->edges
= NULL
;
634 new_dot
->faces
= NULL
;
640 /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
641 * in the dot_list, or add a new dot to the grid (and the dot_list) and
643 * Assumes g->dots has enough capacity allocated */
644 static grid_dot
*grid_get_dot(grid
*g
, tree234
*dot_list
, int x
, int y
)
646 grid_dot test
= {0, NULL
, NULL
, x
, y
};
647 grid_dot
*ret
= find234(dot_list
, &test
, NULL
);
651 ret
= grid_dot_add_new(g
, x
, y
);
652 add234(dot_list
, ret
);
656 /* Sets the last face of the grid to include this dot, at this position
657 * around the face. Assumes num_faces is at least 1 (a new face has
658 * previously been added, with the required number of dots allocated) */
659 static void grid_face_set_dot(grid
*g
, grid_dot
*d
, int position
)
661 grid_face
*last_face
= g
->faces
+ g
->num_faces
- 1;
662 last_face
->dots
[position
] = d
;
665 /* ------ Generate various types of grid ------ */
667 /* General method is to generate faces, by calculating their dot coordinates.
668 * As new faces are added, we keep track of all the dots so we can tell when
669 * a new face reuses an existing dot. For example, two squares touching at an
670 * edge would generate six unique dots: four dots from the first face, then
671 * two additional dots for the second face, because we detect the other two
672 * dots have already been taken up. This list is stored in a tree234
673 * called "points". No extra memory-allocation needed here - we store the
674 * actual grid_dot* pointers, which all point into the g->dots list.
675 * For this reason, we have to calculate coordinates in such a way as to
676 * eliminate any rounding errors, so we can detect when a dot on one
677 * face precisely lands on a dot of a different face. No floating-point
681 grid
*grid_new_square(int width
, int height
)
687 /* Upper bounds - don't have to be exact */
688 int max_faces
= width
* height
;
689 int max_dots
= (width
+ 1) * (height
+ 1);
693 grid
*g
= grid_new();
695 g
->faces
= snewn(max_faces
, grid_face
);
696 g
->dots
= snewn(max_dots
, grid_dot
);
698 points
= newtree234(grid_point_cmp_fn
);
700 /* generate square faces */
701 for (y
= 0; y
< height
; y
++) {
702 for (x
= 0; x
< width
; x
++) {
708 grid_face_add_new(g
, 4);
709 d
= grid_get_dot(g
, points
, px
, py
);
710 grid_face_set_dot(g
, d
, 0);
711 d
= grid_get_dot(g
, points
, px
+ a
, py
);
712 grid_face_set_dot(g
, d
, 1);
713 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
);
714 grid_face_set_dot(g
, d
, 2);
715 d
= grid_get_dot(g
, points
, px
, py
+ a
);
716 grid_face_set_dot(g
, d
, 3);
721 assert(g
->num_faces
<= max_faces
);
722 assert(g
->num_dots
<= max_dots
);
723 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
725 grid_make_consistent(g
);
729 grid
*grid_new_honeycomb(int width
, int height
)
732 /* Vector for side of hexagon - ratio is close to sqrt(3) */
736 /* Upper bounds - don't have to be exact */
737 int max_faces
= width
* height
;
738 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
742 grid
*g
= grid_new();
744 g
->faces
= snewn(max_faces
, grid_face
);
745 g
->dots
= snewn(max_dots
, grid_dot
);
747 points
= newtree234(grid_point_cmp_fn
);
749 /* generate hexagonal faces */
750 for (y
= 0; y
< height
; y
++) {
751 for (x
= 0; x
< width
; x
++) {
758 grid_face_add_new(g
, 6);
760 d
= grid_get_dot(g
, points
, cx
- a
, cy
- b
);
761 grid_face_set_dot(g
, d
, 0);
762 d
= grid_get_dot(g
, points
, cx
+ a
, cy
- b
);
763 grid_face_set_dot(g
, d
, 1);
764 d
= grid_get_dot(g
, points
, cx
+ 2*a
, cy
);
765 grid_face_set_dot(g
, d
, 2);
766 d
= grid_get_dot(g
, points
, cx
+ a
, cy
+ b
);
767 grid_face_set_dot(g
, d
, 3);
768 d
= grid_get_dot(g
, points
, cx
- a
, cy
+ b
);
769 grid_face_set_dot(g
, d
, 4);
770 d
= grid_get_dot(g
, points
, cx
- 2*a
, cy
);
771 grid_face_set_dot(g
, d
, 5);
776 assert(g
->num_faces
<= max_faces
);
777 assert(g
->num_dots
<= max_dots
);
778 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
780 grid_make_consistent(g
);
784 /* Doesn't use the previous method of generation, it pre-dates it!
785 * A triangular grid is just about simple enough to do by "brute force" */
786 grid
*grid_new_triangular(int width
, int height
)
790 /* Vector for side of triangle - ratio is close to sqrt(3) */
796 /* convenient alias */
799 grid
*g
= grid_new();
800 g
->tilesize
= 18; /* adjust to your taste */
802 g
->num_faces
= width
* height
* 2;
803 g
->num_dots
= (width
+ 1) * (height
+ 1);
804 g
->faces
= snewn(g
->num_faces
, grid_face
);
805 g
->dots
= snewn(g
->num_dots
, grid_dot
);
809 for (y
= 0; y
<= height
; y
++) {
810 for (x
= 0; x
<= width
; x
++) {
811 grid_dot
*d
= g
->dots
+ index
;
812 /* odd rows are offset to the right */
816 d
->x
= x
* 2 * vec_x
+ ((y
% 2) ? vec_x
: 0);
824 for (y
= 0; y
< height
; y
++) {
825 for (x
= 0; x
< width
; x
++) {
826 /* initialise two faces for this (x,y) */
827 grid_face
*f1
= g
->faces
+ index
;
828 grid_face
*f2
= f1
+ 1;
831 f1
->dots
= snewn(f1
->order
, grid_dot
*);
834 f2
->dots
= snewn(f2
->order
, grid_dot
*);
836 /* face descriptions depend on whether the row-number is
839 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
840 f1
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
841 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
842 f2
->dots
[0] = g
->dots
+ y
* w
+ x
;
843 f2
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
844 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
846 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
847 f1
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
848 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
849 f2
->dots
[0] = g
->dots
+ y
* w
+ x
+ 1;
850 f2
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
851 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
857 /* "+ width" takes us to the middle of the row, because each row has
858 * (2*width) faces. */
859 g
->middle_face
= g
->faces
+ (height
/ 2) * 2 * width
+ width
;
861 grid_make_consistent(g
);
865 grid
*grid_new_snubsquare(int width
, int height
)
868 /* Vector for side of triangle - ratio is close to sqrt(3) */
872 /* Upper bounds - don't have to be exact */
873 int max_faces
= 3 * width
* height
;
874 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
878 grid
*g
= grid_new();
880 g
->faces
= snewn(max_faces
, grid_face
);
881 g
->dots
= snewn(max_dots
, grid_dot
);
883 points
= newtree234(grid_point_cmp_fn
);
885 for (y
= 0; y
< height
; y
++) {
886 for (x
= 0; x
< width
; x
++) {
889 int px
= (a
+ b
) * x
;
890 int py
= (a
+ b
) * y
;
892 /* generate square faces */
893 grid_face_add_new(g
, 4);
895 d
= grid_get_dot(g
, points
, px
+ a
, py
);
896 grid_face_set_dot(g
, d
, 0);
897 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
898 grid_face_set_dot(g
, d
, 1);
899 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
+ b
);
900 grid_face_set_dot(g
, d
, 2);
901 d
= grid_get_dot(g
, points
, px
, py
+ b
);
902 grid_face_set_dot(g
, d
, 3);
904 d
= grid_get_dot(g
, points
, px
+ b
, py
);
905 grid_face_set_dot(g
, d
, 0);
906 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ b
);
907 grid_face_set_dot(g
, d
, 1);
908 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
909 grid_face_set_dot(g
, d
, 2);
910 d
= grid_get_dot(g
, points
, px
, py
+ a
);
911 grid_face_set_dot(g
, d
, 3);
914 /* generate up/down triangles */
916 grid_face_add_new(g
, 3);
918 d
= grid_get_dot(g
, points
, px
+ a
, py
);
919 grid_face_set_dot(g
, d
, 0);
920 d
= grid_get_dot(g
, points
, px
, py
+ b
);
921 grid_face_set_dot(g
, d
, 1);
922 d
= grid_get_dot(g
, points
, px
- a
, py
);
923 grid_face_set_dot(g
, d
, 2);
925 d
= grid_get_dot(g
, points
, px
, py
+ a
);
926 grid_face_set_dot(g
, d
, 0);
927 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
928 grid_face_set_dot(g
, d
, 1);
929 d
= grid_get_dot(g
, points
, px
- a
, py
+ a
+ b
);
930 grid_face_set_dot(g
, d
, 2);
934 /* generate left/right triangles */
936 grid_face_add_new(g
, 3);
938 d
= grid_get_dot(g
, points
, px
+ a
, py
);
939 grid_face_set_dot(g
, d
, 0);
940 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
- a
);
941 grid_face_set_dot(g
, d
, 1);
942 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
943 grid_face_set_dot(g
, d
, 2);
945 d
= grid_get_dot(g
, points
, px
, py
- a
);
946 grid_face_set_dot(g
, d
, 0);
947 d
= grid_get_dot(g
, points
, px
+ b
, py
);
948 grid_face_set_dot(g
, d
, 1);
949 d
= grid_get_dot(g
, points
, px
, py
+ a
);
950 grid_face_set_dot(g
, d
, 2);
957 assert(g
->num_faces
<= max_faces
);
958 assert(g
->num_dots
<= max_dots
);
959 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
961 grid_make_consistent(g
);
965 grid
*grid_new_cairo(int width
, int height
)
968 /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
972 /* Upper bounds - don't have to be exact */
973 int max_faces
= 2 * width
* height
;
974 int max_dots
= 3 * (width
+ 1) * (height
+ 1);
978 grid
*g
= grid_new();
980 g
->faces
= snewn(max_faces
, grid_face
);
981 g
->dots
= snewn(max_dots
, grid_dot
);
983 points
= newtree234(grid_point_cmp_fn
);
985 for (y
= 0; y
< height
; y
++) {
986 for (x
= 0; x
< width
; x
++) {
992 /* horizontal pentagons */
994 grid_face_add_new(g
, 5);
996 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
997 grid_face_set_dot(g
, d
, 0);
998 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
- b
);
999 grid_face_set_dot(g
, d
, 1);
1000 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1001 grid_face_set_dot(g
, d
, 2);
1002 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1003 grid_face_set_dot(g
, d
, 3);
1004 d
= grid_get_dot(g
, points
, px
, py
);
1005 grid_face_set_dot(g
, d
, 4);
1007 d
= grid_get_dot(g
, points
, px
, py
);
1008 grid_face_set_dot(g
, d
, 0);
1009 d
= grid_get_dot(g
, points
, px
+ b
, py
- a
);
1010 grid_face_set_dot(g
, d
, 1);
1011 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1012 grid_face_set_dot(g
, d
, 2);
1013 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
+ b
);
1014 grid_face_set_dot(g
, d
, 3);
1015 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1016 grid_face_set_dot(g
, d
, 4);
1019 /* vertical pentagons */
1021 grid_face_add_new(g
, 5);
1023 d
= grid_get_dot(g
, points
, px
, py
);
1024 grid_face_set_dot(g
, d
, 0);
1025 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1026 grid_face_set_dot(g
, d
, 1);
1027 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 2*b
- a
);
1028 grid_face_set_dot(g
, d
, 2);
1029 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1030 grid_face_set_dot(g
, d
, 3);
1031 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1032 grid_face_set_dot(g
, d
, 4);
1034 d
= grid_get_dot(g
, points
, px
, py
);
1035 grid_face_set_dot(g
, d
, 0);
1036 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1037 grid_face_set_dot(g
, d
, 1);
1038 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1039 grid_face_set_dot(g
, d
, 2);
1040 d
= grid_get_dot(g
, points
, px
- b
, py
+ 2*b
- a
);
1041 grid_face_set_dot(g
, d
, 3);
1042 d
= grid_get_dot(g
, points
, px
- b
, py
+ a
);
1043 grid_face_set_dot(g
, d
, 4);
1049 freetree234(points
);
1050 assert(g
->num_faces
<= max_faces
);
1051 assert(g
->num_dots
<= max_dots
);
1052 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
1054 grid_make_consistent(g
);
1058 grid
*grid_new_greathexagonal(int width
, int height
)
1061 /* Vector for side of triangle - ratio is close to sqrt(3) */
1065 /* Upper bounds - don't have to be exact */
1066 int max_faces
= 6 * (width
+ 1) * (height
+ 1);
1067 int max_dots
= 6 * width
* height
;
1071 grid
*g
= grid_new();
1073 g
->faces
= snewn(max_faces
, grid_face
);
1074 g
->dots
= snewn(max_dots
, grid_dot
);
1076 points
= newtree234(grid_point_cmp_fn
);
1078 for (y
= 0; y
< height
; y
++) {
1079 for (x
= 0; x
< width
; x
++) {
1081 /* centre of hexagon */
1082 int px
= (3*a
+ b
) * x
;
1083 int py
= (2*a
+ 2*b
) * y
;
1088 grid_face_add_new(g
, 6);
1089 d
= grid_get_dot(g
, points
, px
- a
, py
- b
);
1090 grid_face_set_dot(g
, d
, 0);
1091 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
1092 grid_face_set_dot(g
, d
, 1);
1093 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1094 grid_face_set_dot(g
, d
, 2);
1095 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1096 grid_face_set_dot(g
, d
, 3);
1097 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1098 grid_face_set_dot(g
, d
, 4);
1099 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1100 grid_face_set_dot(g
, d
, 5);
1102 /* square below hexagon */
1103 if (y
< height
- 1) {
1104 grid_face_add_new(g
, 4);
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
+ b
);
1108 grid_face_set_dot(g
, d
, 1);
1109 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1110 grid_face_set_dot(g
, d
, 2);
1111 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1112 grid_face_set_dot(g
, d
, 3);
1115 /* square below right */
1116 if ((x
< width
- 1) && (((x
% 2) == 0) || (y
< height
- 1))) {
1117 grid_face_add_new(g
, 4);
1118 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1119 grid_face_set_dot(g
, d
, 0);
1120 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1121 grid_face_set_dot(g
, d
, 1);
1122 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1123 grid_face_set_dot(g
, d
, 2);
1124 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1125 grid_face_set_dot(g
, d
, 3);
1128 /* square below left */
1129 if ((x
> 0) && (((x
% 2) == 0) || (y
< height
- 1))) {
1130 grid_face_add_new(g
, 4);
1131 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1132 grid_face_set_dot(g
, d
, 0);
1133 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1134 grid_face_set_dot(g
, d
, 1);
1135 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1136 grid_face_set_dot(g
, d
, 2);
1137 d
= grid_get_dot(g
, points
, px
- 2*a
- b
, py
+ a
);
1138 grid_face_set_dot(g
, d
, 3);
1141 /* Triangle below right */
1142 if ((x
< width
- 1) && (y
< height
- 1)) {
1143 grid_face_add_new(g
, 3);
1144 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1145 grid_face_set_dot(g
, d
, 0);
1146 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1147 grid_face_set_dot(g
, d
, 1);
1148 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1149 grid_face_set_dot(g
, d
, 2);
1152 /* Triangle below left */
1153 if ((x
> 0) && (y
< height
- 1)) {
1154 grid_face_add_new(g
, 3);
1155 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1156 grid_face_set_dot(g
, d
, 0);
1157 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1158 grid_face_set_dot(g
, d
, 1);
1159 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1160 grid_face_set_dot(g
, d
, 2);
1165 freetree234(points
);
1166 assert(g
->num_faces
<= max_faces
);
1167 assert(g
->num_dots
<= max_dots
);
1168 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
1170 grid_make_consistent(g
);
1174 grid
*grid_new_octagonal(int width
, int height
)
1177 /* b/a approx sqrt(2) */
1181 /* Upper bounds - don't have to be exact */
1182 int max_faces
= 2 * width
* height
;
1183 int max_dots
= 4 * (width
+ 1) * (height
+ 1);
1187 grid
*g
= grid_new();
1189 g
->faces
= snewn(max_faces
, grid_face
);
1190 g
->dots
= snewn(max_dots
, grid_dot
);
1192 points
= newtree234(grid_point_cmp_fn
);
1194 for (y
= 0; y
< height
; y
++) {
1195 for (x
= 0; x
< width
; x
++) {
1198 int px
= (2*a
+ b
) * x
;
1199 int py
= (2*a
+ b
) * y
;
1201 grid_face_add_new(g
, 8);
1202 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1203 grid_face_set_dot(g
, d
, 0);
1204 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
);
1205 grid_face_set_dot(g
, d
, 1);
1206 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1207 grid_face_set_dot(g
, d
, 2);
1208 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
+ b
);
1209 grid_face_set_dot(g
, d
, 3);
1210 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ 2*a
+ b
);
1211 grid_face_set_dot(g
, d
, 4);
1212 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1213 grid_face_set_dot(g
, d
, 5);
1214 d
= grid_get_dot(g
, points
, px
, py
+ a
+ b
);
1215 grid_face_set_dot(g
, d
, 6);
1216 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1217 grid_face_set_dot(g
, d
, 7);
1220 if ((x
> 0) && (y
> 0)) {
1221 grid_face_add_new(g
, 4);
1222 d
= grid_get_dot(g
, points
, px
, py
- a
);
1223 grid_face_set_dot(g
, d
, 0);
1224 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1225 grid_face_set_dot(g
, d
, 1);
1226 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1227 grid_face_set_dot(g
, d
, 2);
1228 d
= grid_get_dot(g
, points
, px
- a
, py
);
1229 grid_face_set_dot(g
, d
, 3);
1234 freetree234(points
);
1235 assert(g
->num_faces
<= max_faces
);
1236 assert(g
->num_dots
<= max_dots
);
1237 g
->middle_face
= g
->faces
+ (height
/2) * width
+ (width
/2);
1239 grid_make_consistent(g
);
1243 grid
*grid_new_kites(int width
, int height
)
1246 /* b/a approx sqrt(3) */
1250 /* Upper bounds - don't have to be exact */
1251 int max_faces
= 6 * width
* height
;
1252 int max_dots
= 6 * (width
+ 1) * (height
+ 1);
1256 grid
*g
= grid_new();
1258 g
->faces
= snewn(max_faces
, grid_face
);
1259 g
->dots
= snewn(max_dots
, grid_dot
);
1261 points
= newtree234(grid_point_cmp_fn
);
1263 for (y
= 0; y
< height
; y
++) {
1264 for (x
= 0; x
< width
; x
++) {
1266 /* position of order-6 dot */
1272 /* kite pointing up-left */
1273 grid_face_add_new(g
, 4);
1274 d
= grid_get_dot(g
, points
, px
, py
);
1275 grid_face_set_dot(g
, d
, 0);
1276 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1277 grid_face_set_dot(g
, d
, 1);
1278 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
+ 2*a
);
1279 grid_face_set_dot(g
, d
, 2);
1280 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1281 grid_face_set_dot(g
, d
, 3);
1283 /* kite pointing up */
1284 grid_face_add_new(g
, 4);
1285 d
= grid_get_dot(g
, points
, px
, py
);
1286 grid_face_set_dot(g
, d
, 0);
1287 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1288 grid_face_set_dot(g
, d
, 1);
1289 d
= grid_get_dot(g
, points
, px
, py
+ 4*a
);
1290 grid_face_set_dot(g
, d
, 2);
1291 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1292 grid_face_set_dot(g
, d
, 3);
1294 /* kite pointing up-right */
1295 grid_face_add_new(g
, 4);
1296 d
= grid_get_dot(g
, points
, px
, py
);
1297 grid_face_set_dot(g
, d
, 0);
1298 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1299 grid_face_set_dot(g
, d
, 1);
1300 d
= grid_get_dot(g
, points
, px
- 2*b
, py
+ 2*a
);
1301 grid_face_set_dot(g
, d
, 2);
1302 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1303 grid_face_set_dot(g
, d
, 3);
1305 /* kite pointing down-right */
1306 grid_face_add_new(g
, 4);
1307 d
= grid_get_dot(g
, points
, px
, py
);
1308 grid_face_set_dot(g
, d
, 0);
1309 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1310 grid_face_set_dot(g
, d
, 1);
1311 d
= grid_get_dot(g
, points
, px
- 2*b
, py
- 2*a
);
1312 grid_face_set_dot(g
, d
, 2);
1313 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1314 grid_face_set_dot(g
, d
, 3);
1316 /* kite pointing down */
1317 grid_face_add_new(g
, 4);
1318 d
= grid_get_dot(g
, points
, px
, py
);
1319 grid_face_set_dot(g
, d
, 0);
1320 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1321 grid_face_set_dot(g
, d
, 1);
1322 d
= grid_get_dot(g
, points
, px
, py
- 4*a
);
1323 grid_face_set_dot(g
, d
, 2);
1324 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1325 grid_face_set_dot(g
, d
, 3);
1327 /* kite pointing down-left */
1328 grid_face_add_new(g
, 4);
1329 d
= grid_get_dot(g
, points
, px
, py
);
1330 grid_face_set_dot(g
, d
, 0);
1331 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1332 grid_face_set_dot(g
, d
, 1);
1333 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
- 2*a
);
1334 grid_face_set_dot(g
, d
, 2);
1335 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1336 grid_face_set_dot(g
, d
, 3);
1340 freetree234(points
);
1341 assert(g
->num_faces
<= max_faces
);
1342 assert(g
->num_dots
<= max_dots
);
1343 g
->middle_face
= g
->faces
+ 6 * ((height
/2) * width
+ (width
/2));
1345 grid_make_consistent(g
);
1349 /* ----------- End of grid generators ------------- */