ref: 6d347772d007e854bfcbdaecbb38abd7ef56ac6f
dir: /penrose-internal.h/
#include "penrose.h"
static inline unsigned num_subtriangles(char t)
{
return (t == 'A' || t == 'B' || t == 'X' || t == 'Y') ? 3 : 2;
}
static inline unsigned sibling_edge(char t)
{
switch (t) {
case 'A': case 'U': return 2;
case 'B': case 'V': return 1;
default: return 0;
}
}
/*
* Coordinate system for tracking Penrose-tile half-triangles.
* PenroseCoords simply stores an array of triangle types.
*/
typedef struct PenroseCoords {
char *c;
size_t nc, csize;
} PenroseCoords;
PenroseCoords *penrose_coords_new(void);
void penrose_coords_free(PenroseCoords *pc);
void penrose_coords_make_space(PenroseCoords *pc, size_t size);
PenroseCoords *penrose_coords_copy(PenroseCoords *pc_in);
/*
* Coordinate system for locating Penrose tiles in the plane.
*
* The 'Point' structure represents a single point by means of an
* integer linear combination of {1, t, t^2, t^3}, where t is the
* complex number exp(i pi/5) representing 1/10 of a turn about the
* origin.
*
* The 'PenroseTriangle' structure represents a half-tile triangle,
* giving both the locations of its vertices and its combinatorial
* coordinates. It also contains a linked-list pointer and a boolean
* flag, used during breadth-first search to generate all the tiles in
* an area and report them exactly once.
*/
typedef struct Point {
int coeffs[4];
} Point;
typedef struct PenroseTriangle PenroseTriangle;
struct PenroseTriangle {
Point vertices[3];
PenroseCoords *pc;
PenroseTriangle *next; /* used in breadth-first search */
bool reported;
};
/* Fill in all the coordinates of a triangle starting from any single edge.
* Requires tri->pc to have been filled in, so that we know which shape of
* triangle we're placing. */
void penrose_place(PenroseTriangle *tri, Point u, Point v, int index_of_u);
/* Free a PenroseHalf and its contained coordinates, or a whole PenroseTile */
void penrose_free(PenroseTriangle *tri);
/*
* A Point is really a complex number, so we can add, subtract and
* multiply them.
*/
static inline Point point_add(Point a, Point b)
{
Point r;
size_t i;
for (i = 0; i < 4; i++)
r.coeffs[i] = a.coeffs[i] + b.coeffs[i];
return r;
}
static inline Point point_sub(Point a, Point b)
{
Point r;
size_t i;
for (i = 0; i < 4; i++)
r.coeffs[i] = a.coeffs[i] - b.coeffs[i];
return r;
}
static inline Point point_mul_by_t(Point x)
{
Point r;
/* Multiply by t by using the identity t^4 - t^3 + t^2 - t + 1 = 0,
* so t^4 = t^3 - t^2 + t - 1 */
r.coeffs[0] = -x.coeffs[3];
r.coeffs[1] = x.coeffs[0] + x.coeffs[3];
r.coeffs[2] = x.coeffs[1] - x.coeffs[3];
r.coeffs[3] = x.coeffs[2] + x.coeffs[3];
return r;
}
static inline Point point_mul(Point a, Point b)
{
size_t i, j;
Point r;
/* Initialise r to be a, scaled by b's t^3 term */
for (j = 0; j < 4; j++)
r.coeffs[j] = a.coeffs[j] * b.coeffs[3];
/* Now iterate r = t*r + (next coefficient down), by Horner's rule */
for (i = 3; i-- > 0 ;) {
r = point_mul_by_t(r);
for (j = 0; j < 4; j++)
r.coeffs[j] += a.coeffs[j] * b.coeffs[i];
}
return r;
}
static inline bool point_equal(Point a, Point b)
{
size_t i;
for (i = 0; i < 4; i++)
if (a.coeffs[i] != b.coeffs[i])
return false;
return true;
}
/*
* Return the Point corresponding to a rotation of s steps around the
* origin, i.e. a rotation by 36*s degrees or s*pi/5 radians.
*/
static inline Point point_rot(int s)
{
Point r = {{ 1, 0, 0, 0 }};
Point tpower = {{ 0, 1, 0, 0 }};
/* Reduce to a sensible range */
s = s % 10;
if (s < 0)
s += 10;
while (true) {
if (s & 1)
r = point_mul(r, tpower);
s >>= 1;
if (!s)
break;
tpower = point_mul(tpower, tpower);
}
return r;
}
/*
* PenroseContext is the shared context of a whole run of the
* algorithm. Its 'prototype' PenroseCoords object represents the
* coordinates of the starting triangle, and is extended as necessary;
* any other PenroseCoord that needs extending will copy the
* higher-order values from ctx->prototype as needed, so that once
* each choice has been made, it remains consistent.
*
* When we're inventing a random piece of tiling in the first place,
* we append to ctx->prototype by choosing a random (but legal)
* higher-level metatile for the current topmost one to turn out to be
* part of. When we're replaying a generation whose parameters are
* already stored, we don't have a random_state, and we make fixed
* decisions if not enough coordinates were provided, as in the
* corresponding hat.c system.
*
* For a normal (non-testing) caller, penrosectx_generate() is the
* main useful function. It breadth-first searches a whole area to
* generate all the triangles in it, starting from a (typically
* central) one with the coordinates of ctx->prototype. It takes two
* callback function: one that checks whether a triangle is within the
* bounds of the target area (and therefore the search should continue
* exploring its neighbours), and another that reports a full Penrose
* tile once both of its halves have been found and determined to be
* in bounds.
*/
typedef struct PenroseContext {
random_state *rs;
bool must_free_rs;
unsigned start_vertex; /* which vertex of 'prototype' is at the origin? */
int orientation; /* orientation to put in PenrosePatchParams */
PenroseCoords *prototype;
} PenroseContext;
void penrosectx_init_random(PenroseContext *ctx, random_state *rs, int which);
void penrosectx_init_from_params(
PenroseContext *ctx, const struct PenrosePatchParams *ps);
void penrosectx_cleanup(PenroseContext *ctx);
PenroseCoords *penrosectx_initial_coords(PenroseContext *ctx);
void penrosectx_extend_coords(PenroseContext *ctx, PenroseCoords *pc,
size_t n);
void penrosectx_step(PenroseContext *ctx, PenroseCoords *pc,
unsigned edge, unsigned *outedge);
void penrosectx_generate(
PenroseContext *ctx,
bool (*inbounds)(void *inboundsctx,
const PenroseTriangle *tri), void *inboundsctx,
void (*tile)(void *tilectx, const Point *vertices), void *tilectx);
/* Subroutines that step around the tiling specified by a PenroseCtx,
* delivering both plane and combinatorial coordinates as they go */
PenroseTriangle *penrose_initial(PenroseContext *ctx);
PenroseTriangle *penrose_adjacent(PenroseContext *ctx,
const PenroseTriangle *src_spec,
unsigned src_edge, unsigned *dst_edge);
/* For extracting the point coordinates */
typedef struct Coord {
int c1, cr5; /* coefficients of 1 and sqrt(5) respectively */
} Coord;
static inline Coord point_x(Point p)
{
Coord x = {
4 * p.coeffs[0] + p.coeffs[1] - p.coeffs[2] + p.coeffs[3],
p.coeffs[1] + p.coeffs[2] - p.coeffs[3],
};
return x;
}
static inline Coord point_y(Point p)
{
Coord y = {
2 * p.coeffs[1] + p.coeffs[2] + p.coeffs[3],
p.coeffs[2] + p.coeffs[3],
};
return y;
}
static inline int coord_sign(Coord x)
{
if (x.c1 == 0 && x.cr5 == 0)
return 0;
if (x.c1 >= 0 && x.cr5 >= 0)
return +1;
if (x.c1 <= 0 && x.cr5 <= 0)
return -1;
if (x.c1 * x.c1 > 5 * x.cr5 * x.cr5)
return x.c1 < 0 ? -1 : +1;
else
return x.cr5 < 0 ? -1 : +1;
}
static inline Coord coord_construct(int c1, int cr5)
{
Coord c = { c1, cr5 };
return c;
}
static inline Coord coord_integer(int c1)
{
return coord_construct(c1, 0);
}
static inline Coord coord_add(Coord a, Coord b)
{
Coord sum;
sum.c1 = a.c1 + b.c1;
sum.cr5 = a.cr5 + b.cr5;
return sum;
}
static inline Coord coord_sub(Coord a, Coord b)
{
Coord diff;
diff.c1 = a.c1 - b.c1;
diff.cr5 = a.cr5 - b.cr5;
return diff;
}
static inline Coord coord_mul(Coord a, Coord b)
{
Coord prod;
prod.c1 = a.c1 * b.c1 + 5 * a.cr5 * b.cr5;
prod.cr5 = a.c1 * b.cr5 + a.cr5 * b.c1;
return prod;
}
static inline Coord coord_abs(Coord a)
{
int sign = coord_sign(a);
Coord abs;
abs.c1 = a.c1 * sign;
abs.cr5 = a.cr5 * sign;
return abs;
}
static inline int coord_cmp(Coord a, Coord b)
{
return coord_sign(coord_sub(a, b));
}