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.
10 #define PUZZLES_GRID_H
13 #define SQ(x) ( (x) * (x) )
15 /* ----------------------------------------------------------------------
17 * A grid is made up of faces, edges and dots. These structures hold
18 * the incidence relationships between these types. For example, an
19 * edge always joins two dots, and is adjacent to two faces.
20 * The "grid_xxx **" members are lists of pointers which are dynamically
21 * allocated during grid generation.
22 * A pointer to a face/edge/dot will always point somewhere inside one of the
23 * three lists of the main "grid" structure: faces, edges, dots.
24 * Could have used integer offsets into these lists, but using actual
25 * pointers instead gives us type-safety.
28 /* Need forward declarations */
29 typedef struct grid_face grid_face
;
30 typedef struct grid_edge grid_edge
;
31 typedef struct grid_dot grid_dot
;
34 int order
; /* Number of edges, also the number of dots */
35 grid_edge
**edges
; /* edges around this face */
36 grid_dot
**dots
; /* corners of this face */
38 * For each face, we optionally compute and store its 'incentre'.
39 * The incentre of a triangle is the centre of a circle tangent to
40 * all three edges; I generalise the concept to arbitrary polygons
41 * by defining it to be the centre of the largest circle you can fit
42 * anywhere in the polygon. It's a useful thing to know because if
43 * you want to draw any symbol or text in the face (e.g. clue
44 * numbers in Loopy), that's the place it will most easily fit.
46 * When a grid is first generated, no face has this information
47 * computed, because it's fiddly to do. You can call
48 * grid_find_incentre() on a face, and it will fill in ix,iy below
49 * and set has_incentre to indicate that it's done so.
52 int ix
, iy
; /* incentre (centre of largest inscribed circle) */
55 grid_dot
*dot1
, *dot2
;
56 grid_face
*face1
, *face2
; /* Use NULL for the infinite outside face */
61 grid_face
**faces
; /* A NULL grid_face* means infinite outside face */
63 /* Position in some fairly arbitrary (Cartesian) coordinate system.
64 * Use large enough values such that we can get away with
65 * integer arithmetic, but small enough such that arithmetic
70 /* These are (dynamically allocated) arrays of all the
71 * faces, edges, dots that are in the grid. */
72 int num_faces
; grid_face
*faces
;
73 int num_edges
; grid_edge
*edges
;
74 int num_dots
; grid_dot
*dots
;
76 /* Cache the bounding-box of the grid, so the drawing-code can quickly
77 * figure out the proper scaling to draw onto a given area. */
78 int lowest_x
, lowest_y
, highest_x
, highest_y
;
80 /* A measure of tile size for this grid (in grid coordinates), to help
81 * the renderer decide how large to draw the grid.
82 * Roughly the size of a single tile - for example the side-length
83 * of a square cell. */
86 /* We really don't want to copy this monstrosity!
87 * A grid is immutable once generated.
92 grid
*grid_new_square(int width
, int height
);
93 grid
*grid_new_honeycomb(int width
, int height
);
94 grid
*grid_new_triangular(int width
, int height
);
95 grid
*grid_new_snubsquare(int width
, int height
);
96 grid
*grid_new_cairo(int width
, int height
);
97 grid
*grid_new_greathexagonal(int width
, int height
);
98 grid
*grid_new_octagonal(int width
, int height
);
99 grid
*grid_new_kites(int width
, int height
);
100 grid
*grid_new_floret(int width
, int height
);
101 grid
*grid_new_dodecagonal(int width
, int height
);
102 grid
*grid_new_greatdodecagonal(int width
, int height
);
104 void grid_free(grid
*g
);
106 grid_edge
*grid_nearest_edge(grid
*g
, int x
, int y
);
108 void grid_find_incentre(grid_face
*f
);
110 #endif /* PUZZLES_GRID_H */