7c95608a |
1 | /* |
2 | * (c) Lambros Lambrou 2008 |
3 | * |
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. |
7 | */ |
8 | |
9 | #ifndef PUZZLES_GRID_H |
10 | #define PUZZLES_GRID_H |
11 | |
12 | /* Useful macros */ |
1515b973 |
13 | #define SQ(x) ( (x) * (x) ) |
7c95608a |
14 | |
15 | /* ---------------------------------------------------------------------- |
16 | * Grid structures: |
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. |
26 | */ |
27 | |
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; |
32 | |
33 | struct grid_face { |
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 */ |
e64991db |
37 | /* |
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. |
45 | * |
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. |
50 | */ |
51 | int has_incentre; |
52 | int ix, iy; /* incentre (centre of largest inscribed circle) */ |
7c95608a |
53 | }; |
54 | struct grid_edge { |
55 | grid_dot *dot1, *dot2; |
56 | grid_face *face1, *face2; /* Use NULL for the infinite outside face */ |
57 | }; |
58 | struct grid_dot { |
59 | int order; |
60 | grid_edge **edges; |
61 | grid_face **faces; /* A NULL grid_face* means infinite outside face */ |
62 | |
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 |
66 | * won't overflow. */ |
67 | int x, y; |
68 | }; |
69 | typedef struct grid { |
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; |
75 | |
7c95608a |
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; |
79 | |
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. */ |
84 | int tilesize; |
85 | |
86 | /* We really don't want to copy this monstrosity! |
87 | * A grid is immutable once generated. |
88 | */ |
89 | int refcount; |
90 | } grid; |
91 | |
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); |
918a098a |
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); |
7c95608a |
103 | |
104 | void grid_free(grid *g); |
105 | |
106 | grid_edge *grid_nearest_edge(grid *g, int x, int y); |
107 | |
e64991db |
108 | void grid_find_incentre(grid_face *f); |
109 | |
7c95608a |
110 | #endif /* PUZZLES_GRID_H */ |