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 struct grid_edge {
  39   grid_dot *dot1, *dot2;
  40   grid_face *face1, *face2; /* Use NULL for the infinite outside face */
  41 };
  42 struct grid_dot {
  43   int order;
  44   grid_edge **edges;
  45   grid_face **faces; /* A NULL grid_face* means infinite outside face */
  46
  47   /* Position in some fairly arbitrary (Cartesian) coordinate system.
  48    * Use large enough values such that we can get away with
  49    * integer arithmetic, but small enough such that arithmetic
  50    * won't overflow. */
  51   int x, y;
  52 };
  53 typedef struct grid {
  54   /* These are (dynamically allocated) arrays of all the
  55    * faces, edges, dots that are in the grid. */
  56   int num_faces; grid_face *faces;
  57   int num_edges; grid_edge *edges;
  58   int num_dots;  grid_dot *dots;
  59
  60   /* Cache the bounding-box of the grid, so the drawing-code can quickly
  61    * figure out the proper scaling to draw onto a given area. */
  62   int lowest_x, lowest_y, highest_x, highest_y;
  63
  64   /* A measure of tile size for this grid (in grid coordinates), to help
  65    * the renderer decide how large to draw the grid.
  66    * Roughly the size of a single tile - for example the side-length
  67    * of a square cell. */
  68   int tilesize;
  69
  70   /* We really don't want to copy this monstrosity!
  71    * A grid is immutable once generated.
  72    */
  73   int refcount;
  74 } grid;
  75
  76 grid *grid_new_square(int width, int height);
  77 grid *grid_new_honeycomb(int width, int height);
  78 grid *grid_new_triangular(int width, int height);
  79 grid *grid_new_snubsquare(int width, int height);
  80 grid *grid_new_cairo(int width, int height);
  81 grid *grid_new_greathexagonal(int width, int height);
  82 grid *grid_new_octagonal(int width, int height);
  83 grid *grid_new_floret(int width, int height);
  84 grid *grid_new_kites(int width, int height);
  85
  86 void grid_free(grid *g);
  87
  88 grid_edge *grid_nearest_edge(grid *g, int x, int y);
  89
  90 #endif /* PUZZLES_GRID_H */