GEOMETRY(3)

NAME
geometry - primitive geometric structures and procedures in libmagicutils.a

SYNOPSIS
#include geometry.h

typedef struct { int p_x, p_y; } Point;

typedef struct { Point r_ll, r_ur; } Rect;
#define r_xbot r_ll.p_x
#define r_ybot r_ll.p_y
#define r_xtop r_ur.p_x
#define r_ytop r_ur.p_y

typedef struct G1 { Rect r_r; struct G1 *r_next; } LinkedRect;

typedef struct { int t_a, t_b, t_c, t_d, t_e, t_f; } Transform;

#define GEO_CENTER 0
#define GEO_NORTH 1
#define GEO_NORTHEAST 2
#define GEO_EAST 3
#define GEO_SOUTHEAST 4
#define GEO_SOUTH 5
#define GEO_SOUTHWEST 6
#define GEO_WEST 7
#define GEO_NORTHWEST 8

bool GEO_OVERLAP(r1, r2)
Rect *r1;
Rect *r2;

bool GEO_TOUCH(r1, r2)
Rect *r1;
Rect *r2;

bool GEO_SURROUND(r1, r2)
Rect *r1;
Rect *r2;

bool GEO_SURROUND_STRONG(r1, r2)
Rect *r1;
Rect *r2;

bool GEO_ENCLOSE(p, r)
Point *p;
Rect *r;

bool GEO_RECTNULL(r)
Rect *r;

GEO_EXPAND(src, amount, dst)
Rect *src, *dst;
int amount;

Transform GeoIdentityTransform;
Transform GeoUpsideDownTransform;
Transform GeoSidewaysTransform;
Transform Geo90Transform;
Transform Geo180Transform;
Transform Geo270Transform;

Rect GeoNullRect;

GeoTransPoint(t, psrc, pdst)
Transform *t;
Point *psrc, *pdst;

GeoTransRect(t, rsrc, rdst)
Transform *t;
Rect *rsrc, *rdst;

GeoTranslateTrans(tsrc, x, y, tdst)
Transform *tsrc, *tdst;
int x, y;

GeoTransTranslate(x, y, tsrc, tdst)
Transform *tsrc, *tdst;
int x, y;

GeoTransTrans(t1, t2, tdst)
Transform *t1, *t2, *tdst;

GeoInvertTrans(tsrc, tinv)
Transform *tsrc, *tinv;

int GeoScale(t)
Transform *t;

GeoDecomposeTransform(t, upsidedown, angle)
Transform *t;
bool *upsidedown;
int *angle;

int GeoNameToPos(name, manhattan, printerrors)
char *name;
bool manhattan, printerrors;

char *GeoPosToName(pos)
int pos;

int GeoTransPos(t, pos);
Transform *t;
int pos;

bool GeoInclude(src, dst);
Rect *src, *dst;

bool GeoIncludeAll(src, dst);
Rect *src, *dst;

bool GeoIncludePoint(src, dst);
Point *src;
Rect *dst;

GeoClip(r, cliparea)
Rect *r, *cliparea;

GeoClipPoint(p, cliparea)
Point *p;
Rect *cliparea;

bool GeoDisjoint(area, cliparea, func, cdata)
Rect *area, *cliparea;
bool (*func)(rect, cdata);
ClientData cdata;

bool GeoDummyFunc(rect, cdata)
Rect *rect;
ClientData cdata;

GeoCanonicalRect(rsrc, rdst)
Rect *rsrc, *rdst;

int GeoRectPointSide(r, p)
Rect *r;
Point *p;

int GeoRectRectSide(r1, r2)
Rect *r1, *r2;

bool GetRect(f, nskip, r)
FILE *f;
int nskip;
Rect *r;

DESCRIPTION
These procedures implement a number of useful geometric primitives: a Point, which consists of an integer x and y coordinate, and a Rect, which describes a rectangle by its lower-left and upper-right Points. An important predefined Rect is GeoNullRect, the rectangle with both its lower-left and upper-right at the origin (0, 0). If linked lists of Rects are needed, the LinkedRect primitive can be used.

Another primitive is a position relative to a point (GEO_NORTH, GEO_EAST, etc). There are a total of nine positions, corresponding to the eight points around a single point in a grid plus the point itself (GEO_CENTER).

The final primitive is a Transform, which represents some combination of rotation by a multiple of 90 degrees, mirroring across the x or y axis, scaling by an integer scale factor, and translation by an integer x and y displacement. A Transform can be thought of as representing a simple linear transformation on two-dimensional points, or as a matrix of the form:

a	d	0
b	e	0
c	f	1

Multiplying a point vector of the form (x, y, 0) by this transform gives a transformed point (x', y', 0). Although the transform matrix has nine elements, the three on the right-hand are always constant, so only six numbers are needed to describe a transform: four for the rotation (a, b, d, e) and two for the translation (c, f). Because the only rotations are multiples of 90 degrees, transforms will always be of one of the following even more specific forms (only the four rotation numbers are shown), where S is the integer scale factor:

S	0	0	-S	-S	0	0	S
0	S	S	0	0	-S	-S	0

S	0	0	S	-S	0	0	-S
0	-S	S	0	0	S	-S	0

The first four forms correspond to clockwise rotations of 0, 90, 180, and 270 degrees, and the second four correspond to the same four orientations flipped upside down (mirror across the x-axis after rotating).

The above rotations or mirrorings with a scale factor of 1 exist as predefined transforms. GeoIdentityTransform is the identity transformation, i.e, no transformation at all, or the first transform listed above. Geo90Transform, Geo180Transform, and Geo270Transform correspond to the next three transformations, or clockwise rotations of 90, 180, and 270 degrees respectively. GeoUpsideDownTransform is the next transform, mirroring across the x-axis. GeoSidewaysTransform is the seventh transform, corresponding to mirroring across the y-axis. The remaining two transforms above (the sixth and eighth) don't have any predefined transforms, but can be built by composing predefined transforms using GeoTransTrans (see below).

A number of macros exist for determining relationships between Points and Rects. GEO_OVERLAP is TRUE if two rectangles share some area in common. GEO_TOUCH is TRUE if two rectangles share some area or any part of their perimeters (including touching only at a corner). GEO_SURROUND is TRUE if r1 completely surrounds r2, where the boundaries of r1 and r2 are allowed to touch. GEO_SURROUND_STRONG is like GEO_SURROUND, but is only TRUE if r1 completely surrounds r2 without their borders touching. GEO_ENCLOSE is TRUE if a point p lies inside or on the border of the rectangle r. GEO_RECTNULL is TRUE if r has zero area, which can result if the x-coordinate of its upper-right is less than or equal to the x-coordinate of its lower-left, or similarly for the y-coordinates. Finally, GEO_EXPAND is used to grow (or shrink) a rectangle src by an integer distance amount, leaving the new rectangle in dst (which may be the same as src).

Many procedures exist to manipulate transformations. In general, when they accept more than one Point or Rect as arguments, the Points or Rects must be distinct from each other (i.e, no aliasing is allowed). GeoTransPoint applies the Transform *t to the Point *psrc and leaves its result in the Point *pdst. GeoTransRect is identical, but for Rects; it applies t to *rsrc and leaves its result in *rdst. GeoTransRect guarantees that rdst->r_ur is really above and to the right of rdst->r_ll, by interchanging upper and lower coordinates if necessary after the transform. Note that this is NOT the same as transforming the upper-right and lower-left Points separately, since separate transformations can result in a rectangle whose upper right is below its lower left (e.g, GeoUpsideDownTransform).

Three procedures compose transforms, producing the transform that is equivalent to applying first one, then the second of the two transforms. There are two special-case procedures. GeoTranslateTrans composes first the Transform *tsrc and then a simple translation by x and y, storing its result in *tdst. GeoTransTranslate composes first a simple translation by x and y, followed by the Transform *tsrc, also storing its result in *tdst. Finally, GeoTransTrans composes two arbitrary transforms *t1 and *t2, leaving its result in *tdst.

Transforms that adhere to one of the eight rotation formats described above are always invertible. The inverse of such a transform can be computed by GeoInvertTrans, which leaves the inverse of *tsrc in *tinv.

Two procedures extract useful information from Transforms. GeoScale returns the scale factor associated with the Transform *t. GeoDecomposeTransform breaks up a transform into an optional mirror about the x-axis (i.e., flipping upside down), followed by an optional counterclockwise rotation. It sets *upsidedown to TRUE if the transform requires flipping upside down before rotation, and sets *angle to the degrees of rotation: 0, 90, 180, or 270.

Three procedures manipulate positions such as GEO_NORTH. GeoNameToPos maps the ASCII name for a position (e.g, ``north'', ``top'', or ``left'', ``west'', etc) into the internal position number. If name is ambiguous, -1 is returned; if name is unrecognized, -2 is returned. If manhattan is TRUE, only the directions corresponding to GEO_NORTH, GEO_SOUTH, GEO_WEST, or GEO_EAST are accepted. If printerrors is TRUE, GeoNameToPos will print an error message on the standard output in addition to returning -1 or -2. The inverse of GeoNameToPos is GeoPosToName, which returns the ASCII string for a given position pos. GeoTransPos applies the Transfor *t to the position pos and returns the new position. Only the rotational part of *t is relevant; the translation is ignored.

The next collection of procedures manipulate Points and Rects. GeoInclude and GeoIncludeAll extend whichever sides of the Rect *dst that are necessary to include the area of the Rect *src. Both return TRUE if *dst was enlarged. If *src is considered to be zero-size (see below), *dst is unchanged. If *dst is zero-size, it is set to *src if *src is not also zero-size. The two procedures differ in that GeoInclude considers zero-area rectangles to be zero-size, while GeoIncludeAll only considers rectangles whose bottom is actually above their top or whose LHS is to the right of their RHS to be zero-size. GeoIncludePoint is like GeoInclude except *src is a Point instead of a Rect.

Three procedures are provided for clipping. GeoClip determines the portion of the Rect *r that overlaps the Rect *cliparea and replaces *r with the new Rect. If *r and *cliparea don't overlap at all, *r is turned inside out (r_xbot > r_xtop or r_ybot > r_ytop). GeoClipPoint moves the Point *p to the closest point on the boundary of the Rect *cliparea if it isn't already contained in *cliparea or on its border. Finally, GeoDisjoint is used to clip a Rect against another, but to apply a procedure to each region in *area that lies outside *cliparea, instead of modifying *area. The procedure (*proc)() it applies should be like the library procedure GeoDummyFunc, which accepts a Rect and the cdata argument passed to GeoDisjoint and returns TRUE always. If (*proc)() returns FALSE, GeoDisjoint aborts and returns FALSE itself; otherwise, it returns TRUE. GeoDisjoint works in ``tile'' space, so each rectangle is considered to contain its lower x- and y-coordinates, but not its upper coordinates.

The discussion earlier on transformation mentioned that transforming the two corner points of a Rect independently could result in a Rect whose lower left was above or to the right of its upper right. GeoCanonicalRect can remedy this situation; it flips the top and bottom or left and right (or both) of the Rect *rsrc as necessary to ensure that the upper right is above and to the right of the lower left, leaving the canonical Rect in *rdst.

Two procedures compute the relative positions of Points and Rects. GeoRectPointSide gives the side (GEO_NORTH, etc) of the Rect *r on which the Point *p lies (*p must lie on the boundary of *r; otherwise, GEO_CENTER is returned). Similarly, GeoRectRectSide gives the side of *r1 on which *r2 lies, or GEO_CENTER if they don't share any side. Unfortunately this procedure doesn't detect the case where the Rects share a coordinate without sharing a side (e.g, the LHS of one is equal to the RHS of the other, but they don't come even close in the vertical dimension).

A final procedure is provided for high-speed reading of ascii files containing descriptions of rectangles, GetRect. This procedure reads from a stdio-opened FILE *f, which should be positioned so that after skipping nskip characters, it will be at the start of a line containing four ascii numbers that will be stored in r->r_xbot, r->r_ybot, r->r_xtop, and r->r_ytop. It returns TRUE if it successfully recognized a rectangle, FALSE on error or end-of-file. GetRect is considerably faster than either fscanf(3s) or even fgets(3s) followed by manual decoding of the line, because it reads data directly from the stdio buffer in its input file. As such, it depends on the structure of a FILE, and may fail to work properly on machines with wildly different implementations of the stdio library from the standard Berkeley distribution (those in which certain fields are nonexistent or renamed).

MACROS FOR SPEED
If speed is essential, macros are defined in geofast.h to take the place of the several procedures for special cases. GEOCLIP is identical to the procedure GeoClip, but it returns no value. Four macros for manipulating Transforms, GEOTRANSRECT, GEOTRANSTRANS, GEOINVERTTRANS, and GEOTRANSTRANSLATE, are similar to their procedural counterparts GeoTransRect, GeoTransTrans, GeoInvertTrans, and GeoTransTranslate, but only work with Transforms whose scale factor is unity (1). These macros are several times faster than their procedural counterparts; on a Sun-2 the speed difference is close to a factor of 10, but on other machines the difference is less extreme.

SEE ALSO
magicutils(3)