/*
* (c) Lambros Lambrou 2008
*
* Code for working with general grids, which can be any planar graph
* with faces, edges and vertices (dots). Includes generators for a few
* types of grid, including square, hexagonal, triangular and others.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>
#include "puzzles.h"
#include "tree234.h"
#include "grid.h"
/* Debugging options */
/*
#define DEBUG_GRID
*/
/* ----------------------------------------------------------------------
* Deallocate or dereference a grid
*/
void grid_free(grid *g)
{
assert(g->refcount);
g->refcount--;
if (g->refcount == 0) {
int i;
for (i = 0; i < g->num_faces; i++) {
sfree(g->faces[i].dots);
sfree(g->faces[i].edges);
}
for (i = 0; i < g->num_dots; i++) {
sfree(g->dots[i].faces);
sfree(g->dots[i].edges);
}
sfree(g->faces);
sfree(g->edges);
sfree(g->dots);
sfree(g);
}
}
/* Used by the other grid generators. Create a brand new grid with nothing
* initialised (all lists are NULL) */
static grid *grid_new(void)
{
grid *g = snew(grid);
g->faces = NULL;
g->edges = NULL;
g->dots = NULL;
g->num_faces = g->num_edges = g->num_dots = 0;
g->refcount = 1;
g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0;
return g;
}
/* Helper function to calculate perpendicular distance from
* a point P to a line AB. A and B mustn't be equal here.
*
* Well-known formula for area A of a triangle:
* / 1 1 1 \
* 2A = determinant of matrix | px ax bx |
* \ py ay by /
*
* Also well-known: 2A = base * height
* = perpendicular distance * line-length.
*
* Combining gives: distance = determinant / line-length(a,b)
*/
static double point_line_distance(long px, long py,
long ax, long ay,
long bx, long by)
{
long det = ax*by - bx*ay + bx*py - px*by + px*ay - ax*py;
double len;
det = max(det, -det);
len = sqrt(SQ(ax - bx) + SQ(ay - by));
return det / len;
}
/* Determine nearest edge to where the user clicked.
* (x, y) is the clicked location, converted to grid coordinates.
* Returns the nearest edge, or NULL if no edge is reasonably
* near the position.
*
* Just judging edges by perpendicular distance is not quite right -
* the edge might be "off to one side". So we insist that the triangle
* with (x,y) has acute angles at the edge's dots.
*
* edge1
* *---------*------
* |
* | *(x,y)
* edge2 |
* | edge2 is OK, but edge1 is not, even though
* | edge1 is perpendicularly closer to (x,y)
* *
*
*/
grid_edge *grid_nearest_edge(grid *g, int x, int y)
{
grid_edge *best_edge;
double best_distance = 0;
int i;
best_edge = NULL;
for (i = 0; i < g->num_edges; i++) {
grid_edge *e = &g->edges[i];
long e2; /* squared length of edge */
long a2, b2; /* squared lengths of other sides */
double dist;
/* See if edge e is eligible - the triangle must have acute angles
* at the edge's dots.
* Pythagoras formula h^2 = a^2 + b^2 detects right-angles,
* so detect acute angles by testing for h^2 < a^2 + b^2 */
e2 = SQ((long)e->dot1->x - (long)e->dot2->x) + SQ((long)e->dot1->y - (long)e->dot2->y);
a2 = SQ((long)e->dot1->x - (long)x) + SQ((long)e->dot1->y - (long)y);
b2 = SQ((long)e->dot2->x - (long)x) + SQ((long)e->dot2->y - (long)y);
if (a2 >= e2 + b2) continue;
if (b2 >= e2 + a2) continue;
/* e is eligible so far. Now check the edge is reasonably close
* to where the user clicked. Don't want to toggle an edge if the
* click was way off the grid.
* There is room for experimentation here. We could check the
* perpendicular distance is within a certain fraction of the length
* of the edge. That amounts to testing a rectangular region around
* the edge.
* Alternatively, we could check that the angle at the point is obtuse.
* That would amount to testing a circular region with the edge as
* diameter. */
dist = point_line_distance((long)x, (long)y,
(long)e->dot1->x, (long)e->dot1->y,
(long)e->dot2->x, (long)e->dot2->y);
/* Is dist more than half edge length ? */
if (4 * SQ(dist) > e2)
continue;
if (best_edge == NULL || dist < best_distance) {
best_edge = e;
best_distance = dist;
}
}
return best_edge;
}
/* ----------------------------------------------------------------------
* Grid generation
*/
#ifdef DEBUG_GRID
/* Show the basic grid information, before doing grid_make_consistent */
static void grid_print_basic(grid *g)
{
/* TODO: Maybe we should generate an SVG image of the dots and lines
* of the grid here, before grid_make_consistent.
* Would help with debugging grid generation. */
int i;
printf("--- Basic Grid Data ---\n");
for (i = 0; i < g->num_faces; i++) {
grid_face *f = g->faces + i;
printf("Face %d: dots[", i);
int j;
for (j = 0; j < f->order; j++) {
grid_dot *d = f->dots[j];
printf("%s%d", j ? "," : "", (int)(d - g->dots));
}
printf("]\n");
}
}
/* Show the derived grid information, computed by grid_make_consistent */
static void grid_print_derived(grid *g)
{
/* edges */
int i;
printf("--- Derived Grid Data ---\n");
for (i = 0; i < g->num_edges; i++) {
grid_edge *e = g->edges + i;
printf("Edge %d: dots[%d,%d] faces[%d,%d]\n",
i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots),
e->face1 ? (int)(e->face1 - g->faces) : -1,
e->face2 ? (int)(e->face2 - g->faces) : -1);
}
/* faces */
for (i = 0; i < g->num_faces; i++) {
grid_face *f = g->faces + i;
int j;
printf("Face %d: faces[", i);
for (j = 0; j < f->order; j++) {
grid_edge *e = f->edges[j];
grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1;
printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1);
}
printf("]\n");
}
/* dots */
for (i = 0; i < g->num_dots; i++) {
grid_dot *d = g->dots + i;
int j;
printf("Dot %d: dots[", i);
for (j = 0; j < d->order; j++) {
grid_edge *e = d->edges[j];
grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1;
printf("%s%d", j ? "," : "", (int)(d2 - g->dots));
}
printf("] faces[");
for (j = 0; j < d->order; j++) {
grid_face *f = d->faces[j];
printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1);
}
printf("]\n");
}
}
#endif /* DEBUG_GRID */
/* Helper function for building incomplete-edges list in
* grid_make_consistent() */
static int grid_edge_bydots_cmpfn(void *v1, void *v2)
{
grid_edge *a = v1;
grid_edge *b = v2;
grid_dot *da, *db;
/* Pointer subtraction is valid here, because all dots point into the
* same dot-list (g->dots).
* Edges are not "normalised" - the 2 dots could be stored in any order,
* so we need to take this into account when comparing edges. */
/* Compare first dots */
da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2;
db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2;
if (da != db)
return db - da;
/* Compare last dots */
da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1;
db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1;
if (da != db)
return db - da;
return 0;
}
/* Input: grid has its dots and faces initialised:
* - dots have (optionally) x and y coordinates, but no edges or faces
* (pointers are NULL).
|