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
;
578 new_face
->has_incentre
= FALSE
;
581 /* Assumes dot list has enough space */
582 static grid_dot
*grid_dot_add_new(grid
*g
, int x
, int y
)
584 grid_dot
*new_dot
= g
->dots
+ g
->num_dots
;
586 new_dot
->edges
= NULL
;
587 new_dot
->faces
= NULL
;
593 /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot
594 * in the dot_list, or add a new dot to the grid (and the dot_list) and
596 * Assumes g->dots has enough capacity allocated */
597 static grid_dot
*grid_get_dot(grid
*g
, tree234
*dot_list
, int x
, int y
)
606 ret
= find234(dot_list
, &test
, NULL
);
610 ret
= grid_dot_add_new(g
, x
, y
);
611 add234(dot_list
, ret
);
615 /* Sets the last face of the grid to include this dot, at this position
616 * around the face. Assumes num_faces is at least 1 (a new face has
617 * previously been added, with the required number of dots allocated) */
618 static void grid_face_set_dot(grid
*g
, grid_dot
*d
, int position
)
620 grid_face
*last_face
= g
->faces
+ g
->num_faces
- 1;
621 last_face
->dots
[position
] = d
;
625 * Helper routines for grid_find_incentre.
627 static int solve_2x2_matrix(double mx
[4], double vin
[2], double vout
[2])
631 det
= (mx
[0]*mx
[3] - mx
[1]*mx
[2]);
635 inv
[0] = mx
[3] / det
;
636 inv
[1] = -mx
[1] / det
;
637 inv
[2] = -mx
[2] / det
;
638 inv
[3] = mx
[0] / det
;
640 vout
[0] = inv
[0]*vin
[0] + inv
[1]*vin
[1];
641 vout
[1] = inv
[2]*vin
[0] + inv
[3]*vin
[1];
645 static int solve_3x3_matrix(double mx
[9], double vin
[3], double vout
[3])
650 det
= (mx
[0]*mx
[4]*mx
[8] + mx
[1]*mx
[5]*mx
[6] + mx
[2]*mx
[3]*mx
[7] -
651 mx
[0]*mx
[5]*mx
[7] - mx
[1]*mx
[3]*mx
[8] - mx
[2]*mx
[4]*mx
[6]);
655 inv
[0] = (mx
[4]*mx
[8] - mx
[5]*mx
[7]) / det
;
656 inv
[1] = (mx
[2]*mx
[7] - mx
[1]*mx
[8]) / det
;
657 inv
[2] = (mx
[1]*mx
[5] - mx
[2]*mx
[4]) / det
;
658 inv
[3] = (mx
[5]*mx
[6] - mx
[3]*mx
[8]) / det
;
659 inv
[4] = (mx
[0]*mx
[8] - mx
[2]*mx
[6]) / det
;
660 inv
[5] = (mx
[2]*mx
[3] - mx
[0]*mx
[5]) / det
;
661 inv
[6] = (mx
[3]*mx
[7] - mx
[4]*mx
[6]) / det
;
662 inv
[7] = (mx
[1]*mx
[6] - mx
[0]*mx
[7]) / det
;
663 inv
[8] = (mx
[0]*mx
[4] - mx
[1]*mx
[3]) / det
;
665 vout
[0] = inv
[0]*vin
[0] + inv
[1]*vin
[1] + inv
[2]*vin
[2];
666 vout
[1] = inv
[3]*vin
[0] + inv
[4]*vin
[1] + inv
[5]*vin
[2];
667 vout
[2] = inv
[6]*vin
[0] + inv
[7]*vin
[1] + inv
[8]*vin
[2];
672 void grid_find_incentre(grid_face
*f
)
674 double xbest
, ybest
, bestdist
;
676 grid_dot
*edgedot1
[3], *edgedot2
[3];
684 * Find the point in the polygon with the maximum distance to any
687 * Such a point must exist which is in contact with at least three
688 * edges and/or vertices. (Proof: if it's only in contact with two
689 * edges and/or vertices, it can't even be at a _local_ maximum -
690 * any such circle can always be expanded in some direction.) So
691 * we iterate through all 3-subsets of the combined set of edges
692 * and vertices; for each subset we generate one or two candidate
693 * points that might be the incentre, and then we vet each one to
694 * see if it's inside the polygon and what its maximum radius is.
696 * (There's one case which this algorithm will get noticeably
697 * wrong, and that's when a continuum of equally good answers
698 * exists due to parallel edges. Consider a long thin rectangle,
699 * for instance, or a parallelogram. This algorithm will pick a
700 * point near one end, and choose the end arbitrarily; obviously a
701 * nicer point to choose would be in the centre. To fix this I
702 * would have to introduce a special-case system which detected
703 * parallel edges in advance, set aside all candidate points
704 * generated using both edges in a parallel pair, and generated
705 * some additional candidate points half way between them. Also,
706 * of course, I'd have to cope with rounding error making such a
707 * point look worse than one of its endpoints. So I haven't done
708 * this for the moment, and will cross it if necessary when I come
711 * We don't actually iterate literally over _edges_, in the sense
712 * of grid_edge structures. Instead, we fill in edgedot1[] and
713 * edgedot2[] with a pair of dots adjacent in the face's list of
714 * vertices. This ensures that we get the edges in consistent
715 * orientation, which we could not do from the grid structure
716 * alone. (A moment's consideration of an order-3 vertex should
717 * make it clear that if a notional arrow was written on each
718 * edge, _at least one_ of the three faces bordering that vertex
719 * would have to have the two arrows tip-to-tip or tail-to-tail
720 * rather than tip-to-tail.)
726 for (i
= 0; i
+2 < 2*f
->order
; i
++) {
728 edgedot1
[nedges
] = f
->dots
[i
];
729 edgedot2
[nedges
++] = f
->dots
[(i
+1)%f
->order
];
731 dots
[ndots
++] = f
->dots
[i
- f
->order
];
733 for (j
= i
+1; j
+1 < 2*f
->order
; j
++) {
735 edgedot1
[nedges
] = f
->dots
[j
];
736 edgedot2
[nedges
++] = f
->dots
[(j
+1)%f
->order
];
738 dots
[ndots
++] = f
->dots
[j
- f
->order
];
740 for (k
= j
+1; k
< 2*f
->order
; k
++) {
741 double cx
[2], cy
[2]; /* candidate positions */
742 int cn
= 0; /* number of candidates */
745 edgedot1
[nedges
] = f
->dots
[k
];
746 edgedot2
[nedges
++] = f
->dots
[(k
+1)%f
->order
];
748 dots
[ndots
++] = f
->dots
[k
- f
->order
];
751 * Find a point, or pair of points, equidistant from
752 * all the specified edges and/or vertices.
756 * Three edges. This is a linear matrix equation:
757 * each row of the matrix represents the fact that
758 * the point (x,y) we seek is at distance r from
759 * that edge, and we solve three of those
760 * simultaneously to obtain x,y,r. (We ignore r.)
762 double matrix
[9], vector
[3], vector2
[3];
765 for (m
= 0; m
< 3; m
++) {
766 int x1
= edgedot1
[m
]->x
, x2
= edgedot2
[m
]->x
;
767 int y1
= edgedot1
[m
]->y
, y2
= edgedot2
[m
]->y
;
768 int dx
= x2
-x1
, dy
= y2
-y1
;
771 * ((x,y) - (x1,y1)) . (dy,-dx) = r |(dx,dy)|
773 * => x dy - y dx - r |(dx,dy)| = (x1 dy - y1 dx)
777 matrix
[3*m
+2] = -sqrt((double)dx
*dx
+(double)dy
*dy
);
778 vector
[m
] = (double)x1
*dy
- (double)y1
*dx
;
781 if (solve_3x3_matrix(matrix
, vector
, vector2
)) {
786 } else if (nedges
== 2) {
788 * Two edges and a dot. This will end up in a
789 * quadratic equation.
791 * First, look at the two edges. Having our point
792 * be some distance r from both of them gives rise
793 * to a pair of linear equations in x,y,r of the
796 * (x-x1) dy - (y-y1) dx = r sqrt(dx^2+dy^2)
798 * We eliminate r between those equations to give
799 * us a single linear equation in x,y describing
800 * the locus of points equidistant from both lines
801 * - i.e. the angle bisector.
803 * We then choose one of x,y to be a parameter t,
804 * and derive linear formulae for x,y,r in terms
805 * of t. This enables us to write down the
806 * circular equation (x-xd)^2+(y-yd)^2=r^2 as a
807 * quadratic in t; solving that and substituting
808 * in for x,y gives us two candidate points.
810 double eqs
[2][4]; /* a,b,c,d : ax+by+cr=d */
811 double eq
[3]; /* a,b,c: ax+by=c */
812 double xt
[2], yt
[2], rt
[2]; /* a,b: {x,y,r}=at+b */
813 double q
[3]; /* a,b,c: at^2+bt+c=0 */
816 /* Find equations of the two input lines. */
817 for (m
= 0; m
< 2; m
++) {
818 int x1
= edgedot1
[m
]->x
, x2
= edgedot2
[m
]->x
;
819 int y1
= edgedot1
[m
]->y
, y2
= edgedot2
[m
]->y
;
820 int dx
= x2
-x1
, dy
= y2
-y1
;
824 eqs
[m
][2] = -sqrt(dx
*dx
+dy
*dy
);
825 eqs
[m
][3] = x1
*dy
- y1
*dx
;
828 /* Derive the angle bisector by eliminating r. */
829 eq
[0] = eqs
[0][0]*eqs
[1][2] - eqs
[1][0]*eqs
[0][2];
830 eq
[1] = eqs
[0][1]*eqs
[1][2] - eqs
[1][1]*eqs
[0][2];
831 eq
[2] = eqs
[0][3]*eqs
[1][2] - eqs
[1][3]*eqs
[0][2];
833 /* Parametrise x and y in terms of some t. */
834 if (abs(eq
[0]) < abs(eq
[1])) {
835 /* Parameter is x. */
836 xt
[0] = 1; xt
[1] = 0;
837 yt
[0] = -eq
[0]/eq
[1]; yt
[1] = eq
[2]/eq
[1];
839 /* Parameter is y. */
840 yt
[0] = 1; yt
[1] = 0;
841 xt
[0] = -eq
[1]/eq
[0]; xt
[1] = eq
[2]/eq
[0];
844 /* Find a linear representation of r using eqs[0]. */
845 rt
[0] = -(eqs
[0][0]*xt
[0] + eqs
[0][1]*yt
[0])/eqs
[0][2];
846 rt
[1] = (eqs
[0][3] - eqs
[0][0]*xt
[1] -
847 eqs
[0][1]*yt
[1])/eqs
[0][2];
849 /* Construct the quadratic equation. */
851 q
[1] = -2*rt
[0]*rt
[1];
854 q
[1] += 2*xt
[0]*(xt
[1]-dots
[0]->x
);
855 q
[2] += (xt
[1]-dots
[0]->x
)*(xt
[1]-dots
[0]->x
);
857 q
[1] += 2*yt
[0]*(yt
[1]-dots
[0]->y
);
858 q
[2] += (yt
[1]-dots
[0]->y
)*(yt
[1]-dots
[0]->y
);
861 disc
= q
[1]*q
[1] - 4*q
[0]*q
[2];
867 t
= (-q
[1] + disc
) / (2*q
[0]);
868 cx
[cn
] = xt
[0]*t
+ xt
[1];
869 cy
[cn
] = yt
[0]*t
+ yt
[1];
872 t
= (-q
[1] - disc
) / (2*q
[0]);
873 cx
[cn
] = xt
[0]*t
+ xt
[1];
874 cy
[cn
] = yt
[0]*t
+ yt
[1];
877 } else if (nedges
== 1) {
879 * Two dots and an edge. This one's another
880 * quadratic equation.
882 * The point we want must lie on the perpendicular
883 * bisector of the two dots; that much is obvious.
884 * So we can construct a parametrisation of that
885 * bisecting line, giving linear formulae for x,y
886 * in terms of t. We can also express the distance
887 * from the edge as such a linear formula.
889 * Then we set that equal to the radius of the
890 * circle passing through the two points, which is
891 * a Pythagoras exercise; that gives rise to a
892 * quadratic in t, which we solve.
894 double xt
[2], yt
[2], rt
[2]; /* a,b: {x,y,r}=at+b */
895 double q
[3]; /* a,b,c: at^2+bt+c=0 */
899 /* Find parametric formulae for x,y. */
901 int x1
= dots
[0]->x
, x2
= dots
[1]->x
;
902 int y1
= dots
[0]->y
, y2
= dots
[1]->y
;
903 int dx
= x2
-x1
, dy
= y2
-y1
;
904 double d
= sqrt((double)dx
*dx
+ (double)dy
*dy
);
908 /* It's convenient if we have t at standard scale. */
912 /* Also note down half the separation between
913 * the dots, for use in computing the circle radius. */
917 /* Find a parametric formula for r. */
919 int x1
= edgedot1
[0]->x
, x2
= edgedot2
[0]->x
;
920 int y1
= edgedot1
[0]->y
, y2
= edgedot2
[0]->y
;
921 int dx
= x2
-x1
, dy
= y2
-y1
;
922 double d
= sqrt((double)dx
*dx
+ (double)dy
*dy
);
923 rt
[0] = (xt
[0]*dy
- yt
[0]*dx
) / d
;
924 rt
[1] = ((xt
[1]-x1
)*dy
- (yt
[1]-y1
)*dx
) / d
;
927 /* Construct the quadratic equation. */
929 q
[1] = 2*rt
[0]*rt
[1];
932 q
[2] -= halfsep
*halfsep
;
935 disc
= q
[1]*q
[1] - 4*q
[0]*q
[2];
941 t
= (-q
[1] + disc
) / (2*q
[0]);
942 cx
[cn
] = xt
[0]*t
+ xt
[1];
943 cy
[cn
] = yt
[0]*t
+ yt
[1];
946 t
= (-q
[1] - disc
) / (2*q
[0]);
947 cx
[cn
] = xt
[0]*t
+ xt
[1];
948 cy
[cn
] = yt
[0]*t
+ yt
[1];
951 } else if (nedges
== 0) {
953 * Three dots. This is another linear matrix
954 * equation, this time with each row of the matrix
955 * representing the perpendicular bisector between
956 * two of the points. Of course we only need two
957 * such lines to find their intersection, so we
958 * need only solve a 2x2 matrix equation.
961 double matrix
[4], vector
[2], vector2
[2];
964 for (m
= 0; m
< 2; m
++) {
965 int x1
= dots
[m
]->x
, x2
= dots
[m
+1]->x
;
966 int y1
= dots
[m
]->y
, y2
= dots
[m
+1]->y
;
967 int dx
= x2
-x1
, dy
= y2
-y1
;
970 * ((x,y) - (x1,y1)) . (dx,dy) = 1/2 |(dx,dy)|^2
972 * => 2x dx + 2y dy = dx^2+dy^2 + (2 x1 dx + 2 y1 dy)
974 matrix
[2*m
+0] = 2*dx
;
975 matrix
[2*m
+1] = 2*dy
;
976 vector
[m
] = ((double)dx
*dx
+ (double)dy
*dy
+
977 2.0*x1
*dx
+ 2.0*y1
*dy
);
980 if (solve_2x2_matrix(matrix
, vector
, vector2
)) {
988 * Now go through our candidate points and see if any
989 * of them are better than what we've got so far.
991 for (m
= 0; m
< cn
; m
++) {
992 double x
= cx
[m
], y
= cy
[m
];
995 * First, disqualify the point if it's not inside
996 * the polygon, which we work out by counting the
997 * edges to the right of the point. (For
998 * tiebreaking purposes when edges start or end on
999 * our y-coordinate or go right through it, we
1000 * consider our point to be offset by a small
1001 * _positive_ epsilon in both the x- and
1005 for (e
= 0; e
< f
->order
; e
++) {
1006 int xs
= f
->edges
[e
]->dot1
->x
;
1007 int xe
= f
->edges
[e
]->dot2
->x
;
1008 int ys
= f
->edges
[e
]->dot1
->y
;
1009 int ye
= f
->edges
[e
]->dot2
->y
;
1010 if ((y
>= ys
&& y
< ye
) || (y
>= ye
&& y
< ys
)) {
1012 * The line goes past our y-position. Now we need
1013 * to know if its x-coordinate when it does so is
1016 * The x-coordinate in question is mathematically
1017 * (y - ys) * (xe - xs) / (ye - ys), and we want
1018 * to know whether (x - xs) >= that. Of course we
1019 * avoid the division, so we can work in integers;
1020 * to do this we must multiply both sides of the
1021 * inequality by ye - ys, which means we must
1022 * first check that's not negative.
1024 int num
= xe
- xs
, denom
= ye
- ys
;
1029 if ((x
- xs
) * denom
>= (y
- ys
) * num
)
1035 double mindist
= HUGE_VAL
;
1039 * This point is inside the polygon, so now we check
1040 * its minimum distance to every edge and corner.
1041 * First the corners ...
1043 for (d
= 0; d
< f
->order
; d
++) {
1044 int xp
= f
->dots
[d
]->x
;
1045 int yp
= f
->dots
[d
]->y
;
1046 double dx
= x
- xp
, dy
= y
- yp
;
1047 double dist
= dx
*dx
+ dy
*dy
;
1053 * ... and now also check the perpendicular distance
1054 * to every edge, if the perpendicular lies between
1055 * the edge's endpoints.
1057 for (e
= 0; e
< f
->order
; e
++) {
1058 int xs
= f
->edges
[e
]->dot1
->x
;
1059 int xe
= f
->edges
[e
]->dot2
->x
;
1060 int ys
= f
->edges
[e
]->dot1
->y
;
1061 int ye
= f
->edges
[e
]->dot2
->y
;
1064 * If s and e are our endpoints, and p our
1065 * candidate circle centre, the foot of a
1066 * perpendicular from p to the line se lies
1067 * between s and e if and only if (p-s).(e-s) lies
1068 * strictly between 0 and (e-s).(e-s).
1070 int edx
= xe
- xs
, edy
= ye
- ys
;
1071 double pdx
= x
- xs
, pdy
= y
- ys
;
1072 double pde
= pdx
* edx
+ pdy
* edy
;
1073 long ede
= (long)edx
* edx
+ (long)edy
* edy
;
1074 if (0 < pde
&& pde
< ede
) {
1076 * Yes, the nearest point on this edge is
1077 * closer than either endpoint, so we must
1078 * take it into account by measuring the
1079 * perpendicular distance to the edge and
1080 * checking its square against mindist.
1083 double pdre
= pdx
* edy
- pdy
* edx
;
1084 double sqlen
= pdre
* pdre
/ ede
;
1086 if (mindist
> sqlen
)
1092 * Right. Now we know the biggest circle around this
1093 * point, so we can check it against bestdist.
1095 if (bestdist
< mindist
) {
1119 assert(bestdist
> 0);
1121 f
->has_incentre
= TRUE
;
1122 f
->ix
= xbest
+ 0.5; /* round to nearest */
1123 f
->iy
= ybest
+ 0.5;
1126 /* ------ Generate various types of grid ------ */
1128 /* General method is to generate faces, by calculating their dot coordinates.
1129 * As new faces are added, we keep track of all the dots so we can tell when
1130 * a new face reuses an existing dot. For example, two squares touching at an
1131 * edge would generate six unique dots: four dots from the first face, then
1132 * two additional dots for the second face, because we detect the other two
1133 * dots have already been taken up. This list is stored in a tree234
1134 * called "points". No extra memory-allocation needed here - we store the
1135 * actual grid_dot* pointers, which all point into the g->dots list.
1136 * For this reason, we have to calculate coordinates in such a way as to
1137 * eliminate any rounding errors, so we can detect when a dot on one
1138 * face precisely lands on a dot of a different face. No floating-point
1142 grid
*grid_new_square(int width
, int height
)
1148 /* Upper bounds - don't have to be exact */
1149 int max_faces
= width
* height
;
1150 int max_dots
= (width
+ 1) * (height
+ 1);
1154 grid
*g
= grid_new();
1156 g
->faces
= snewn(max_faces
, grid_face
);
1157 g
->dots
= snewn(max_dots
, grid_dot
);
1159 points
= newtree234(grid_point_cmp_fn
);
1161 /* generate square faces */
1162 for (y
= 0; y
< height
; y
++) {
1163 for (x
= 0; x
< width
; x
++) {
1169 grid_face_add_new(g
, 4);
1170 d
= grid_get_dot(g
, points
, px
, py
);
1171 grid_face_set_dot(g
, d
, 0);
1172 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1173 grid_face_set_dot(g
, d
, 1);
1174 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
);
1175 grid_face_set_dot(g
, d
, 2);
1176 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1177 grid_face_set_dot(g
, d
, 3);
1181 freetree234(points
);
1182 assert(g
->num_faces
<= max_faces
);
1183 assert(g
->num_dots
<= max_dots
);
1185 grid_make_consistent(g
);
1189 grid
*grid_new_honeycomb(int width
, int height
)
1192 /* Vector for side of hexagon - ratio is close to sqrt(3) */
1196 /* Upper bounds - don't have to be exact */
1197 int max_faces
= width
* height
;
1198 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
1202 grid
*g
= grid_new();
1203 g
->tilesize
= 3 * a
;
1204 g
->faces
= snewn(max_faces
, grid_face
);
1205 g
->dots
= snewn(max_dots
, grid_dot
);
1207 points
= newtree234(grid_point_cmp_fn
);
1209 /* generate hexagonal faces */
1210 for (y
= 0; y
< height
; y
++) {
1211 for (x
= 0; x
< width
; x
++) {
1218 grid_face_add_new(g
, 6);
1220 d
= grid_get_dot(g
, points
, cx
- a
, cy
- b
);
1221 grid_face_set_dot(g
, d
, 0);
1222 d
= grid_get_dot(g
, points
, cx
+ a
, cy
- b
);
1223 grid_face_set_dot(g
, d
, 1);
1224 d
= grid_get_dot(g
, points
, cx
+ 2*a
, cy
);
1225 grid_face_set_dot(g
, d
, 2);
1226 d
= grid_get_dot(g
, points
, cx
+ a
, cy
+ b
);
1227 grid_face_set_dot(g
, d
, 3);
1228 d
= grid_get_dot(g
, points
, cx
- a
, cy
+ b
);
1229 grid_face_set_dot(g
, d
, 4);
1230 d
= grid_get_dot(g
, points
, cx
- 2*a
, cy
);
1231 grid_face_set_dot(g
, d
, 5);
1235 freetree234(points
);
1236 assert(g
->num_faces
<= max_faces
);
1237 assert(g
->num_dots
<= max_dots
);
1239 grid_make_consistent(g
);
1243 /* Doesn't use the previous method of generation, it pre-dates it!
1244 * A triangular grid is just about simple enough to do by "brute force" */
1245 grid
*grid_new_triangular(int width
, int height
)
1249 /* Vector for side of triangle - ratio is close to sqrt(3) */
1255 /* convenient alias */
1258 grid
*g
= grid_new();
1259 g
->tilesize
= 18; /* adjust to your taste */
1261 g
->num_faces
= width
* height
* 2;
1262 g
->num_dots
= (width
+ 1) * (height
+ 1);
1263 g
->faces
= snewn(g
->num_faces
, grid_face
);
1264 g
->dots
= snewn(g
->num_dots
, grid_dot
);
1268 for (y
= 0; y
<= height
; y
++) {
1269 for (x
= 0; x
<= width
; x
++) {
1270 grid_dot
*d
= g
->dots
+ index
;
1271 /* odd rows are offset to the right */
1275 d
->x
= x
* 2 * vec_x
+ ((y
% 2) ? vec_x
: 0);
1281 /* generate faces */
1283 for (y
= 0; y
< height
; y
++) {
1284 for (x
= 0; x
< width
; x
++) {
1285 /* initialise two faces for this (x,y) */
1286 grid_face
*f1
= g
->faces
+ index
;
1287 grid_face
*f2
= f1
+ 1;
1290 f1
->dots
= snewn(f1
->order
, grid_dot
*);
1293 f2
->dots
= snewn(f2
->order
, grid_dot
*);
1295 /* face descriptions depend on whether the row-number is
1298 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
1299 f1
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
1300 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
1301 f2
->dots
[0] = g
->dots
+ y
* w
+ x
;
1302 f2
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
1303 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
1305 f1
->dots
[0] = g
->dots
+ y
* w
+ x
;
1306 f1
->dots
[1] = g
->dots
+ y
* w
+ x
+ 1;
1307 f1
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
1308 f2
->dots
[0] = g
->dots
+ y
* w
+ x
+ 1;
1309 f2
->dots
[1] = g
->dots
+ (y
+ 1) * w
+ x
+ 1;
1310 f2
->dots
[2] = g
->dots
+ (y
+ 1) * w
+ x
;
1316 grid_make_consistent(g
);
1320 grid
*grid_new_snubsquare(int width
, int height
)
1323 /* Vector for side of triangle - ratio is close to sqrt(3) */
1327 /* Upper bounds - don't have to be exact */
1328 int max_faces
= 3 * width
* height
;
1329 int max_dots
= 2 * (width
+ 1) * (height
+ 1);
1333 grid
*g
= grid_new();
1335 g
->faces
= snewn(max_faces
, grid_face
);
1336 g
->dots
= snewn(max_dots
, grid_dot
);
1338 points
= newtree234(grid_point_cmp_fn
);
1340 for (y
= 0; y
< height
; y
++) {
1341 for (x
= 0; x
< width
; x
++) {
1344 int px
= (a
+ b
) * x
;
1345 int py
= (a
+ b
) * y
;
1347 /* generate square faces */
1348 grid_face_add_new(g
, 4);
1350 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1351 grid_face_set_dot(g
, d
, 0);
1352 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
1353 grid_face_set_dot(g
, d
, 1);
1354 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
+ b
);
1355 grid_face_set_dot(g
, d
, 2);
1356 d
= grid_get_dot(g
, points
, px
, py
+ b
);
1357 grid_face_set_dot(g
, d
, 3);
1359 d
= grid_get_dot(g
, points
, px
+ b
, py
);
1360 grid_face_set_dot(g
, d
, 0);
1361 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ b
);
1362 grid_face_set_dot(g
, d
, 1);
1363 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
1364 grid_face_set_dot(g
, d
, 2);
1365 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1366 grid_face_set_dot(g
, d
, 3);
1369 /* generate up/down triangles */
1371 grid_face_add_new(g
, 3);
1373 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1374 grid_face_set_dot(g
, d
, 0);
1375 d
= grid_get_dot(g
, points
, px
, py
+ b
);
1376 grid_face_set_dot(g
, d
, 1);
1377 d
= grid_get_dot(g
, points
, px
- a
, py
);
1378 grid_face_set_dot(g
, d
, 2);
1380 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1381 grid_face_set_dot(g
, d
, 0);
1382 d
= grid_get_dot(g
, points
, px
+ a
, py
+ a
+ b
);
1383 grid_face_set_dot(g
, d
, 1);
1384 d
= grid_get_dot(g
, points
, px
- a
, py
+ a
+ b
);
1385 grid_face_set_dot(g
, d
, 2);
1389 /* generate left/right triangles */
1391 grid_face_add_new(g
, 3);
1393 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1394 grid_face_set_dot(g
, d
, 0);
1395 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
- a
);
1396 grid_face_set_dot(g
, d
, 1);
1397 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
);
1398 grid_face_set_dot(g
, d
, 2);
1400 d
= grid_get_dot(g
, points
, px
, py
- a
);
1401 grid_face_set_dot(g
, d
, 0);
1402 d
= grid_get_dot(g
, points
, px
+ b
, py
);
1403 grid_face_set_dot(g
, d
, 1);
1404 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1405 grid_face_set_dot(g
, d
, 2);
1411 freetree234(points
);
1412 assert(g
->num_faces
<= max_faces
);
1413 assert(g
->num_dots
<= max_dots
);
1415 grid_make_consistent(g
);
1419 grid
*grid_new_cairo(int width
, int height
)
1422 /* Vector for side of pentagon - ratio is close to (4+sqrt(7))/3 */
1426 /* Upper bounds - don't have to be exact */
1427 int max_faces
= 2 * width
* height
;
1428 int max_dots
= 3 * (width
+ 1) * (height
+ 1);
1432 grid
*g
= grid_new();
1434 g
->faces
= snewn(max_faces
, grid_face
);
1435 g
->dots
= snewn(max_dots
, grid_dot
);
1437 points
= newtree234(grid_point_cmp_fn
);
1439 for (y
= 0; y
< height
; y
++) {
1440 for (x
= 0; x
< width
; x
++) {
1446 /* horizontal pentagons */
1448 grid_face_add_new(g
, 5);
1450 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
1451 grid_face_set_dot(g
, d
, 0);
1452 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
- b
);
1453 grid_face_set_dot(g
, d
, 1);
1454 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1455 grid_face_set_dot(g
, d
, 2);
1456 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1457 grid_face_set_dot(g
, d
, 3);
1458 d
= grid_get_dot(g
, points
, px
, py
);
1459 grid_face_set_dot(g
, d
, 4);
1461 d
= grid_get_dot(g
, points
, px
, py
);
1462 grid_face_set_dot(g
, d
, 0);
1463 d
= grid_get_dot(g
, points
, px
+ b
, py
- a
);
1464 grid_face_set_dot(g
, d
, 1);
1465 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1466 grid_face_set_dot(g
, d
, 2);
1467 d
= grid_get_dot(g
, points
, px
+ 2*b
- a
, py
+ b
);
1468 grid_face_set_dot(g
, d
, 3);
1469 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1470 grid_face_set_dot(g
, d
, 4);
1473 /* vertical pentagons */
1475 grid_face_add_new(g
, 5);
1477 d
= grid_get_dot(g
, points
, px
, py
);
1478 grid_face_set_dot(g
, d
, 0);
1479 d
= grid_get_dot(g
, points
, px
+ b
, py
+ a
);
1480 grid_face_set_dot(g
, d
, 1);
1481 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 2*b
- a
);
1482 grid_face_set_dot(g
, d
, 2);
1483 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1484 grid_face_set_dot(g
, d
, 3);
1485 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1486 grid_face_set_dot(g
, d
, 4);
1488 d
= grid_get_dot(g
, points
, px
, py
);
1489 grid_face_set_dot(g
, d
, 0);
1490 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1491 grid_face_set_dot(g
, d
, 1);
1492 d
= grid_get_dot(g
, points
, px
, py
+ 2*b
);
1493 grid_face_set_dot(g
, d
, 2);
1494 d
= grid_get_dot(g
, points
, px
- b
, py
+ 2*b
- a
);
1495 grid_face_set_dot(g
, d
, 3);
1496 d
= grid_get_dot(g
, points
, px
- b
, py
+ a
);
1497 grid_face_set_dot(g
, d
, 4);
1503 freetree234(points
);
1504 assert(g
->num_faces
<= max_faces
);
1505 assert(g
->num_dots
<= max_dots
);
1507 grid_make_consistent(g
);
1511 grid
*grid_new_greathexagonal(int width
, int height
)
1514 /* Vector for side of triangle - ratio is close to sqrt(3) */
1518 /* Upper bounds - don't have to be exact */
1519 int max_faces
= 6 * (width
+ 1) * (height
+ 1);
1520 int max_dots
= 6 * width
* height
;
1524 grid
*g
= grid_new();
1526 g
->faces
= snewn(max_faces
, grid_face
);
1527 g
->dots
= snewn(max_dots
, grid_dot
);
1529 points
= newtree234(grid_point_cmp_fn
);
1531 for (y
= 0; y
< height
; y
++) {
1532 for (x
= 0; x
< width
; x
++) {
1534 /* centre of hexagon */
1535 int px
= (3*a
+ b
) * x
;
1536 int py
= (2*a
+ 2*b
) * y
;
1541 grid_face_add_new(g
, 6);
1542 d
= grid_get_dot(g
, points
, px
- a
, py
- b
);
1543 grid_face_set_dot(g
, d
, 0);
1544 d
= grid_get_dot(g
, points
, px
+ a
, py
- b
);
1545 grid_face_set_dot(g
, d
, 1);
1546 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1547 grid_face_set_dot(g
, d
, 2);
1548 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1549 grid_face_set_dot(g
, d
, 3);
1550 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1551 grid_face_set_dot(g
, d
, 4);
1552 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1553 grid_face_set_dot(g
, d
, 5);
1555 /* square below hexagon */
1556 if (y
< height
- 1) {
1557 grid_face_add_new(g
, 4);
1558 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1559 grid_face_set_dot(g
, d
, 0);
1560 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1561 grid_face_set_dot(g
, d
, 1);
1562 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1563 grid_face_set_dot(g
, d
, 2);
1564 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1565 grid_face_set_dot(g
, d
, 3);
1568 /* square below right */
1569 if ((x
< width
- 1) && (((x
% 2) == 0) || (y
< height
- 1))) {
1570 grid_face_add_new(g
, 4);
1571 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
);
1572 grid_face_set_dot(g
, d
, 0);
1573 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1574 grid_face_set_dot(g
, d
, 1);
1575 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1576 grid_face_set_dot(g
, d
, 2);
1577 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1578 grid_face_set_dot(g
, d
, 3);
1581 /* square below left */
1582 if ((x
> 0) && (((x
% 2) == 0) || (y
< height
- 1))) {
1583 grid_face_add_new(g
, 4);
1584 d
= grid_get_dot(g
, points
, px
- 2*a
, py
);
1585 grid_face_set_dot(g
, d
, 0);
1586 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1587 grid_face_set_dot(g
, d
, 1);
1588 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1589 grid_face_set_dot(g
, d
, 2);
1590 d
= grid_get_dot(g
, points
, px
- 2*a
- b
, py
+ a
);
1591 grid_face_set_dot(g
, d
, 3);
1594 /* Triangle below right */
1595 if ((x
< width
- 1) && (y
< height
- 1)) {
1596 grid_face_add_new(g
, 3);
1597 d
= grid_get_dot(g
, points
, px
+ a
, py
+ b
);
1598 grid_face_set_dot(g
, d
, 0);
1599 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ a
+ b
);
1600 grid_face_set_dot(g
, d
, 1);
1601 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1602 grid_face_set_dot(g
, d
, 2);
1605 /* Triangle below left */
1606 if ((x
> 0) && (y
< height
- 1)) {
1607 grid_face_add_new(g
, 3);
1608 d
= grid_get_dot(g
, points
, px
- a
, py
+ b
);
1609 grid_face_set_dot(g
, d
, 0);
1610 d
= grid_get_dot(g
, points
, px
- a
, py
+ 2*a
+ b
);
1611 grid_face_set_dot(g
, d
, 1);
1612 d
= grid_get_dot(g
, points
, px
- a
- b
, py
+ a
+ b
);
1613 grid_face_set_dot(g
, d
, 2);
1618 freetree234(points
);
1619 assert(g
->num_faces
<= max_faces
);
1620 assert(g
->num_dots
<= max_dots
);
1622 grid_make_consistent(g
);
1626 grid
*grid_new_octagonal(int width
, int height
)
1629 /* b/a approx sqrt(2) */
1633 /* Upper bounds - don't have to be exact */
1634 int max_faces
= 2 * width
* height
;
1635 int max_dots
= 4 * (width
+ 1) * (height
+ 1);
1639 grid
*g
= grid_new();
1641 g
->faces
= snewn(max_faces
, grid_face
);
1642 g
->dots
= snewn(max_dots
, grid_dot
);
1644 points
= newtree234(grid_point_cmp_fn
);
1646 for (y
= 0; y
< height
; y
++) {
1647 for (x
= 0; x
< width
; x
++) {
1650 int px
= (2*a
+ b
) * x
;
1651 int py
= (2*a
+ b
) * y
;
1653 grid_face_add_new(g
, 8);
1654 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1655 grid_face_set_dot(g
, d
, 0);
1656 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
);
1657 grid_face_set_dot(g
, d
, 1);
1658 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
);
1659 grid_face_set_dot(g
, d
, 2);
1660 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
+ b
);
1661 grid_face_set_dot(g
, d
, 3);
1662 d
= grid_get_dot(g
, points
, px
+ a
+ b
, py
+ 2*a
+ b
);
1663 grid_face_set_dot(g
, d
, 4);
1664 d
= grid_get_dot(g
, points
, px
+ a
, py
+ 2*a
+ b
);
1665 grid_face_set_dot(g
, d
, 5);
1666 d
= grid_get_dot(g
, points
, px
, py
+ a
+ b
);
1667 grid_face_set_dot(g
, d
, 6);
1668 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1669 grid_face_set_dot(g
, d
, 7);
1672 if ((x
> 0) && (y
> 0)) {
1673 grid_face_add_new(g
, 4);
1674 d
= grid_get_dot(g
, points
, px
, py
- a
);
1675 grid_face_set_dot(g
, d
, 0);
1676 d
= grid_get_dot(g
, points
, px
+ a
, py
);
1677 grid_face_set_dot(g
, d
, 1);
1678 d
= grid_get_dot(g
, points
, px
, py
+ a
);
1679 grid_face_set_dot(g
, d
, 2);
1680 d
= grid_get_dot(g
, points
, px
- a
, py
);
1681 grid_face_set_dot(g
, d
, 3);
1686 freetree234(points
);
1687 assert(g
->num_faces
<= max_faces
);
1688 assert(g
->num_dots
<= max_dots
);
1690 grid_make_consistent(g
);
1694 grid
*grid_new_kites(int width
, int height
)
1697 /* b/a approx sqrt(3) */
1701 /* Upper bounds - don't have to be exact */
1702 int max_faces
= 6 * width
* height
;
1703 int max_dots
= 6 * (width
+ 1) * (height
+ 1);
1707 grid
*g
= grid_new();
1709 g
->faces
= snewn(max_faces
, grid_face
);
1710 g
->dots
= snewn(max_dots
, grid_dot
);
1712 points
= newtree234(grid_point_cmp_fn
);
1714 for (y
= 0; y
< height
; y
++) {
1715 for (x
= 0; x
< width
; x
++) {
1717 /* position of order-6 dot */
1723 /* kite pointing up-left */
1724 grid_face_add_new(g
, 4);
1725 d
= grid_get_dot(g
, points
, px
, py
);
1726 grid_face_set_dot(g
, d
, 0);
1727 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1728 grid_face_set_dot(g
, d
, 1);
1729 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
+ 2*a
);
1730 grid_face_set_dot(g
, d
, 2);
1731 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1732 grid_face_set_dot(g
, d
, 3);
1734 /* kite pointing up */
1735 grid_face_add_new(g
, 4);
1736 d
= grid_get_dot(g
, points
, px
, py
);
1737 grid_face_set_dot(g
, d
, 0);
1738 d
= grid_get_dot(g
, points
, px
+ b
, py
+ 3*a
);
1739 grid_face_set_dot(g
, d
, 1);
1740 d
= grid_get_dot(g
, points
, px
, py
+ 4*a
);
1741 grid_face_set_dot(g
, d
, 2);
1742 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1743 grid_face_set_dot(g
, d
, 3);
1745 /* kite pointing up-right */
1746 grid_face_add_new(g
, 4);
1747 d
= grid_get_dot(g
, points
, px
, py
);
1748 grid_face_set_dot(g
, d
, 0);
1749 d
= grid_get_dot(g
, points
, px
- b
, py
+ 3*a
);
1750 grid_face_set_dot(g
, d
, 1);
1751 d
= grid_get_dot(g
, points
, px
- 2*b
, py
+ 2*a
);
1752 grid_face_set_dot(g
, d
, 2);
1753 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1754 grid_face_set_dot(g
, d
, 3);
1756 /* kite pointing down-right */
1757 grid_face_add_new(g
, 4);
1758 d
= grid_get_dot(g
, points
, px
, py
);
1759 grid_face_set_dot(g
, d
, 0);
1760 d
= grid_get_dot(g
, points
, px
- 2*b
, py
);
1761 grid_face_set_dot(g
, d
, 1);
1762 d
= grid_get_dot(g
, points
, px
- 2*b
, py
- 2*a
);
1763 grid_face_set_dot(g
, d
, 2);
1764 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1765 grid_face_set_dot(g
, d
, 3);
1767 /* kite pointing down */
1768 grid_face_add_new(g
, 4);
1769 d
= grid_get_dot(g
, points
, px
, py
);
1770 grid_face_set_dot(g
, d
, 0);
1771 d
= grid_get_dot(g
, points
, px
- b
, py
- 3*a
);
1772 grid_face_set_dot(g
, d
, 1);
1773 d
= grid_get_dot(g
, points
, px
, py
- 4*a
);
1774 grid_face_set_dot(g
, d
, 2);
1775 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1776 grid_face_set_dot(g
, d
, 3);
1778 /* kite pointing down-left */
1779 grid_face_add_new(g
, 4);
1780 d
= grid_get_dot(g
, points
, px
, py
);
1781 grid_face_set_dot(g
, d
, 0);
1782 d
= grid_get_dot(g
, points
, px
+ b
, py
- 3*a
);
1783 grid_face_set_dot(g
, d
, 1);
1784 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
- 2*a
);
1785 grid_face_set_dot(g
, d
, 2);
1786 d
= grid_get_dot(g
, points
, px
+ 2*b
, py
);
1787 grid_face_set_dot(g
, d
, 3);
1791 freetree234(points
);
1792 assert(g
->num_faces
<= max_faces
);
1793 assert(g
->num_dots
<= max_dots
);
1795 grid_make_consistent(g
);
1799 grid
*grid_new_floret(int width
, int height
)
1802 /* Vectors for sides; weird numbers needed to keep puzzle aligned with window
1803 * -py/px is close to tan(30 - atan(sqrt(3)/9))
1804 * using py=26 makes everything lean to the left, rather than right
1806 int px
= 75, py
= -26; /* |( 75, -26)| = 79.43 */
1807 int qx
= 4*px
/5, qy
= -py
*2; /* |( 60, 52)| = 79.40 */
1808 int rx
= qx
-px
, ry
= qy
-py
; /* |(-15, 78)| = 79.38 */
1810 /* Upper bounds - don't have to be exact */
1811 int max_faces
= 6 * width
* height
;
1812 int max_dots
= 9 * (width
+ 1) * (height
+ 1);
1816 grid
*g
= grid_new();
1817 g
->tilesize
= 2 * px
;
1818 g
->faces
= snewn(max_faces
, grid_face
);
1819 g
->dots
= snewn(max_dots
, grid_dot
);
1821 points
= newtree234(grid_point_cmp_fn
);
1823 /* generate pentagonal faces */
1824 for (y
= 0; y
< height
; y
++) {
1825 for (x
= 0; x
< width
; x
++) {
1828 int cx
= (6*px
+3*qx
)/2 * x
;
1829 int cy
= (4*py
-5*qy
) * y
;
1831 cy
-= (4*py
-5*qy
)/2;
1832 else if (y
&& y
== height
-1)
1833 continue; /* make better looking grids? try 3x3 for instance */
1835 grid_face_add_new(g
, 5);
1836 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1837 d
= grid_get_dot(g
, points
, cx
+2*rx
, cy
+2*ry
); grid_face_set_dot(g
, d
, 1);
1838 d
= grid_get_dot(g
, points
, cx
+2*rx
+qx
, cy
+2*ry
+qy
); grid_face_set_dot(g
, d
, 2);
1839 d
= grid_get_dot(g
, points
, cx
+2*qx
+rx
, cy
+2*qy
+ry
); grid_face_set_dot(g
, d
, 3);
1840 d
= grid_get_dot(g
, points
, cx
+2*qx
, cy
+2*qy
); grid_face_set_dot(g
, d
, 4);
1842 grid_face_add_new(g
, 5);
1843 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1844 d
= grid_get_dot(g
, points
, cx
+2*qx
, cy
+2*qy
); grid_face_set_dot(g
, d
, 1);
1845 d
= grid_get_dot(g
, points
, cx
+2*qx
+px
, cy
+2*qy
+py
); grid_face_set_dot(g
, d
, 2);
1846 d
= grid_get_dot(g
, points
, cx
+2*px
+qx
, cy
+2*py
+qy
); grid_face_set_dot(g
, d
, 3);
1847 d
= grid_get_dot(g
, points
, cx
+2*px
, cy
+2*py
); grid_face_set_dot(g
, d
, 4);
1849 grid_face_add_new(g
, 5);
1850 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1851 d
= grid_get_dot(g
, points
, cx
+2*px
, cy
+2*py
); grid_face_set_dot(g
, d
, 1);
1852 d
= grid_get_dot(g
, points
, cx
+2*px
-rx
, cy
+2*py
-ry
); grid_face_set_dot(g
, d
, 2);
1853 d
= grid_get_dot(g
, points
, cx
-2*rx
+px
, cy
-2*ry
+py
); grid_face_set_dot(g
, d
, 3);
1854 d
= grid_get_dot(g
, points
, cx
-2*rx
, cy
-2*ry
); grid_face_set_dot(g
, d
, 4);
1856 grid_face_add_new(g
, 5);
1857 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1858 d
= grid_get_dot(g
, points
, cx
-2*rx
, cy
-2*ry
); grid_face_set_dot(g
, d
, 1);
1859 d
= grid_get_dot(g
, points
, cx
-2*rx
-qx
, cy
-2*ry
-qy
); grid_face_set_dot(g
, d
, 2);
1860 d
= grid_get_dot(g
, points
, cx
-2*qx
-rx
, cy
-2*qy
-ry
); grid_face_set_dot(g
, d
, 3);
1861 d
= grid_get_dot(g
, points
, cx
-2*qx
, cy
-2*qy
); grid_face_set_dot(g
, d
, 4);
1863 grid_face_add_new(g
, 5);
1864 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1865 d
= grid_get_dot(g
, points
, cx
-2*qx
, cy
-2*qy
); grid_face_set_dot(g
, d
, 1);
1866 d
= grid_get_dot(g
, points
, cx
-2*qx
-px
, cy
-2*qy
-py
); grid_face_set_dot(g
, d
, 2);
1867 d
= grid_get_dot(g
, points
, cx
-2*px
-qx
, cy
-2*py
-qy
); grid_face_set_dot(g
, d
, 3);
1868 d
= grid_get_dot(g
, points
, cx
-2*px
, cy
-2*py
); grid_face_set_dot(g
, d
, 4);
1870 grid_face_add_new(g
, 5);
1871 d
= grid_get_dot(g
, points
, cx
, cy
); grid_face_set_dot(g
, d
, 0);
1872 d
= grid_get_dot(g
, points
, cx
-2*px
, cy
-2*py
); grid_face_set_dot(g
, d
, 1);
1873 d
= grid_get_dot(g
, points
, cx
-2*px
+rx
, cy
-2*py
+ry
); grid_face_set_dot(g
, d
, 2);
1874 d
= grid_get_dot(g
, points
, cx
+2*rx
-px
, cy
+2*ry
-py
); grid_face_set_dot(g
, d
, 3);
1875 d
= grid_get_dot(g
, points
, cx
+2*rx
, cy
+2*ry
); grid_face_set_dot(g
, d
, 4);
1879 freetree234(points
);
1880 assert(g
->num_faces
<= max_faces
);
1881 assert(g
->num_dots
<= max_dots
);
1883 grid_make_consistent(g
);
1887 grid
*grid_new_dodecagonal(int width
, int height
)
1890 /* Vector for side of triangle - ratio is close to sqrt(3) */
1894 /* Upper bounds - don't have to be exact */
1895 int max_faces
= 3 * width
* height
;
1896 int max_dots
= 14 * width
* height
;
1900 grid
*g
= grid_new();
1902 g
->faces
= snewn(max_faces
, grid_face
);
1903 g
->dots
= snewn(max_dots
, grid_dot
);
1905 points
= newtree234(grid_point_cmp_fn
);
1907 for (y
= 0; y
< height
; y
++) {
1908 for (x
= 0; x
< width
; x
++) {
1910 /* centre of dodecagon */
1911 int px
= (4*a
+ 2*b
) * x
;
1912 int py
= (3*a
+ 2*b
) * y
;
1917 grid_face_add_new(g
, 12);
1918 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1919 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 1);
1920 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 2);
1921 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 3);
1922 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 4);
1923 d
= grid_get_dot(g
, points
, px
+ ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
1924 d
= grid_get_dot(g
, points
, px
- ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 6);
1925 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 7);
1926 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 8);
1927 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 9);
1928 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 10);
1929 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 11);
1931 /* triangle below dodecagon */
1932 if ((y
< height
- 1 && (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2)))) {
1933 grid_face_add_new(g
, 3);
1934 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1935 d
= grid_get_dot(g
, points
, px
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1936 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 2);
1939 /* triangle above dodecagon */
1940 if ((y
&& (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2)))) {
1941 grid_face_add_new(g
, 3);
1942 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1943 d
= grid_get_dot(g
, points
, px
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
1944 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 2);
1949 freetree234(points
);
1950 assert(g
->num_faces
<= max_faces
);
1951 assert(g
->num_dots
<= max_dots
);
1953 grid_make_consistent(g
);
1957 grid
*grid_new_greatdodecagonal(int width
, int height
)
1960 /* Vector for side of triangle - ratio is close to sqrt(3) */
1964 /* Upper bounds - don't have to be exact */
1965 int max_faces
= 30 * width
* height
;
1966 int max_dots
= 200 * width
* height
;
1970 grid
*g
= grid_new();
1972 g
->faces
= snewn(max_faces
, grid_face
);
1973 g
->dots
= snewn(max_dots
, grid_dot
);
1975 points
= newtree234(grid_point_cmp_fn
);
1977 for (y
= 0; y
< height
; y
++) {
1978 for (x
= 0; x
< width
; x
++) {
1980 /* centre of dodecagon */
1981 int px
= (6*a
+ 2*b
) * x
;
1982 int py
= (3*a
+ 3*b
) * y
;
1987 grid_face_add_new(g
, 12);
1988 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
1989 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 1);
1990 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 2);
1991 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 3);
1992 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 4);
1993 d
= grid_get_dot(g
, points
, px
+ ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
1994 d
= grid_get_dot(g
, points
, px
- ( a
), py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 6);
1995 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
+ ( a
+ b
)); grid_face_set_dot(g
, d
, 7);
1996 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
+ ( a
)); grid_face_set_dot(g
, d
, 8);
1997 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
)); grid_face_set_dot(g
, d
, 9);
1998 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 10);
1999 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 11);
2001 /* hexagon below dodecagon */
2002 if (y
< height
- 1 && (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2))) {
2003 grid_face_add_new(g
, 6);
2004 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2005 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2006 d
= grid_get_dot(g
, points
, px
+ a
, py
+ (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 2);
2007 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 3);
2008 d
= grid_get_dot(g
, points
, px
- 2*a
, py
+ (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 4);
2009 d
= grid_get_dot(g
, points
, px
- a
, py
+ (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
2012 /* hexagon above dodecagon */
2013 if (y
&& (x
< width
- 1 || !(y
% 2)) && (x
> 0 || (y
% 2))) {
2014 grid_face_add_new(g
, 6);
2015 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2016 d
= grid_get_dot(g
, points
, px
- 2*a
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2017 d
= grid_get_dot(g
, points
, px
- a
, py
- (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 2);
2018 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ 3*b
)); grid_face_set_dot(g
, d
, 3);
2019 d
= grid_get_dot(g
, points
, px
+ 2*a
, py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 4);
2020 d
= grid_get_dot(g
, points
, px
+ a
, py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 5);
2023 /* square on right of dodecagon */
2024 if (x
< width
- 1) {
2025 grid_face_add_new(g
, 4);
2026 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
- a
); grid_face_set_dot(g
, d
, 0);
2027 d
= grid_get_dot(g
, points
, px
+ 4*a
+ b
, py
- a
); grid_face_set_dot(g
, d
, 1);
2028 d
= grid_get_dot(g
, points
, px
+ 4*a
+ b
, py
+ a
); grid_face_set_dot(g
, d
, 2);
2029 d
= grid_get_dot(g
, points
, px
+ 2*a
+ b
, py
+ a
); grid_face_set_dot(g
, d
, 3);
2032 /* square on top right of dodecagon */
2033 if (y
&& (x
< width
- 1 || !(y
% 2))) {
2034 grid_face_add_new(g
, 4);
2035 d
= grid_get_dot(g
, points
, px
+ ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 0);
2036 d
= grid_get_dot(g
, points
, px
+ (2*a
), py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2037 d
= grid_get_dot(g
, points
, px
+ (2*a
+ b
), py
- ( a
+ 2*b
)); grid_face_set_dot(g
, d
, 2);
2038 d
= grid_get_dot(g
, points
, px
+ ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 3);
2041 /* square on top left of dodecagon */
2042 if (y
&& (x
|| (y
% 2))) {
2043 grid_face_add_new(g
, 4);
2044 d
= grid_get_dot(g
, points
, px
- ( a
+ b
), py
- ( a
+ b
)); grid_face_set_dot(g
, d
, 0);
2045 d
= grid_get_dot(g
, points
, px
- (2*a
+ b
), py
- ( a
+ 2*b
)); grid_face_set_dot(g
, d
, 1);
2046 d
= grid_get_dot(g
, points
, px
- (2*a
), py
- (2*a
+ 2*b
)); grid_face_set_dot(g
, d
, 2);
2047 d
= grid_get_dot(g
, points
, px
- ( a
), py
- (2*a
+ b
)); grid_face_set_dot(g
, d
, 3);
2052 freetree234(points
);
2053 assert(g
->num_faces
<= max_faces
);
2054 assert(g
->num_dots
<= max_dots
);
2056 grid_make_consistent(g
);
2060 /* ----------- End of grid generators ------------- */