grid.h

   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 #include "puzzles.h" /* for random_state */
  13
  14 /* Useful macros */
  15 #define SQ(x) ( (x) * (x) )
  16
  17 /* ----------------------------------------------------------------------
  18  * Grid structures:
  19  * A grid is made up of faces, edges and dots.  These structures hold
  20  * the incidence relationships between these types.  For example, an
  21  * edge always joins two dots, and is adjacent to two faces.
  22  * The "grid_xxx **" members are lists of pointers which are dynamically
  23  * allocated during grid generation.
  24  * A pointer to a face/edge/dot will always point somewhere inside one of the
  25  * three lists of the main "grid" structure: faces, edges, dots.
  26  * Could have used integer offsets into these lists, but using actual
  27  * pointers instead gives us type-safety.
  28  */
  29
  30 /* Need forward declarations */
  31 typedef struct grid_face grid_face;
  32 typedef struct grid_edge grid_edge;
  33 typedef struct grid_dot grid_dot;
  34
  35 struct grid_face {
  36   int order; /* Number of edges, also the number of dots */
  37   grid_edge **edges; /* edges around this face */
  38   grid_dot **dots; /* corners of this face */
  39   /*
  40    * For each face, we optionally compute and store its 'incentre'.
  41    * The incentre of a triangle is the centre of a circle tangent to
  42    * all three edges; I generalise the concept to arbitrary polygons
  43    * by defining it to be the centre of the largest circle you can fit
  44    * anywhere in the polygon. It's a useful thing to know because if
  45    * you want to draw any symbol or text in the face (e.g. clue
  46    * numbers in Loopy), that's the place it will most easily fit.
  47    *
  48    * When a grid is first generated, no face has this information
  49    * computed, because it's fiddly to do. You can call
  50    * grid_find_incentre() on a face, and it will fill in ix,iy below
  51    * and set has_incentre to indicate that it's done so.
  52    */
  53   int has_incentre;
  54   int ix, iy;      /* incentre (centre of largest inscribed circle) */
  55 };
  56 struct grid_edge {
  57   grid_dot *dot1, *dot2;
  58   grid_face *face1, *face2; /* Use NULL for the infinite outside face */
  59 };
  60 struct grid_dot {
  61   int order;
  62   grid_edge **edges;
  63   grid_face **faces; /* A NULL grid_face* means infinite outside face */
  64
  65   /* Position in some fairly arbitrary (Cartesian) coordinate system.
  66    * Use large enough values such that we can get away with
  67    * integer arithmetic, but small enough such that arithmetic
  68    * won't overflow. */
  69   int x, y;
  70 };
  71 typedef struct grid {
  72   /* These are (dynamically allocated) arrays of all the
  73    * faces, edges, dots that are in the grid. */
  74   int num_faces; grid_face *faces;
  75   int num_edges; grid_edge *edges;
  76   int num_dots;  grid_dot *dots;
  77
  78   /* Cache the bounding-box of the grid, so the drawing-code can quickly
  79    * figure out the proper scaling to draw onto a given area. */
  80   int lowest_x, lowest_y, highest_x, highest_y;
  81
  82   /* A measure of tile size for this grid (in grid coordinates), to help
  83    * the renderer decide how large to draw the grid.
  84    * Roughly the size of a single tile - for example the side-length
  85    * of a square cell. */
  86   int tilesize;
  87
  88   /* We really don't want to copy this monstrosity!
  89    * A grid is immutable once generated.
  90    */
  91   int refcount;
  92 } grid;
  93
  94 /* Grids are specified by type: GRID_SQUARE, GRID_KITE, etc. */
  95
  96 #define GRIDGEN_LIST(A) \
  97   A(SQUARE,square) \
  98   A(HONEYCOMB,honeycomb) \
  99   A(TRIANGULAR,triangular) \
 100   A(SNUBSQUARE,snubsquare) \
 101   A(CAIRO,cairo) \
 102   A(GREATHEXAGONAL,greathexagonal) \
 103   A(OCTAGONAL,octagonal) \
 104   A(KITE,kites) \
 105   A(FLORET,floret) \
 106   A(DODECAGONAL,dodecagonal) \
 107   A(GREATDODECAGONAL,greatdodecagonal) \
 108   A(GREATGREATDODECAGONAL,greatgreatdodecagonal) \
 109   A(PENROSE_P2,penrose_p2_kite) \
 110   A(PENROSE_P3,penrose_p3_thick)
 111
 112 #define ENUM(upper,lower) GRID_ ## upper,
 113 typedef enum grid_type { GRIDGEN_LIST(ENUM) GRID_TYPE_MAX } grid_type;
 114 #undef ENUM
 115
 116 /* Free directly after use if non-NULL. Will never contain an underscore
 117  * (so clients can safely use that as a separator). */
 118 char *grid_new_desc(grid_type type, int width, int height, random_state *rs);
 119 char *grid_validate_desc(grid_type type, int width, int height,
 120                          const char *desc);
 121
 122 grid *grid_new(grid_type type, int width, int height, const char *desc);
 123
 124 void grid_free(grid *g);
 125
 126 grid_edge *grid_nearest_edge(grid *g, int x, int y);
 127
 128 void grid_compute_size(grid_type type, int width, int height,
 129                        int *tilesize, int *xextent, int *yextent);
 130
 131 void grid_find_incentre(grid_face *f);
 132
 133 #endif /* PUZZLES_GRID_H */