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 /* Useful macros */
  13 #define SQ(x) ( (x) * (x) )
  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 */
  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) */
  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
  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);
 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);
 103
 104 void grid_free(grid *g);
 105
 106 grid_edge *grid_nearest_edge(grid *g, int x, int y);
 107
 108 void grid_find_incentre(grid_face *f);
 109
 110 #endif /* PUZZLES_GRID_H */