.TH GEOMETRY 3
.UC 4
.SH NAME
geometry \- primitive geometric structures and procedures in libmagicutils.a

.SH SYNOPSIS
.nf
.B #include "geometry.h"
.PP
.B typedef struct { int p_x, p_y; } Point;
.PP
.B typedef struct { Point r_ll, r_ur; } Rect;
.B #define r_xbot r_ll.p_x
.B #define r_ybot r_ll.p_y
.B #define r_xtop r_ur.p_x
.B #define r_ytop r_ur.p_y
.PP
.B typedef struct G1 { Rect r_r; struct G1 *r_next; } LinkedRect;
.PP
.B typedef struct { int t_a, t_b, t_c, t_d, t_e, t_f; } Transform;
.PP
.ta 1.5i
.B #define GEO_CENTER	0
.B #define GEO_NORTH	1
.B #define GEO_NORTHEAST	2
.B #define GEO_EAST	3
.B #define GEO_SOUTHEAST	4
.B #define GEO_SOUTH	5
.B #define GEO_SOUTHWEST	6
.B #define GEO_WEST	7
.B #define GEO_NORTHWEST	8
.PP
.B bool GEO_OVERLAP(r1, r2)
.B Rect *r1;
.B Rect *r2;
.PP
.B bool GEO_TOUCH(r1, r2)
.B Rect *r1;
.B Rect *r2;
.PP
.B bool GEO_SURROUND(r1, r2)
.B Rect *r1;
.B Rect *r2;
.PP
.B bool GEO_SURROUND_STRONG(r1, r2)
.B Rect *r1;
.B Rect *r2;
.PP
.B bool GEO_ENCLOSE(p, r)
.B Point *p;
.B Rect *r;
.PP
.B bool GEO_RECTNULL(r)
.B Rect *r;
.PP
.B GEO_EXPAND(src, amount, dst)
.B Rect *src, *dst;
.B int amount;
.PP
.B Transform GeoIdentityTransform;
.B Transform GeoUpsideDownTransform;
.B Transform GeoSidewaysTransform;
.B Transform Geo90Transform;
.B Transform Geo180Transform;
.B Transform Geo270Transform;
.PP
.B Rect GeoNullRect;
.PP
.B GeoTransPoint(t, psrc, pdst)
.B Transform *t;
.B Point *psrc, *pdst;
.PP
.B GeoTransRect(t, rsrc, rdst)
.B Transform *t;
.B Rect *rsrc, *rdst;
.PP
.B GeoTranslateTrans(tsrc, x, y, tdst)
.B Transform *tsrc, *tdst;
.B int x, y;
.PP
.B GeoTransTranslate(x, y, tsrc, tdst)
.B Transform *tsrc, *tdst;
.B int x, y;
.PP
.B GeoTransTrans(t1, t2, tdst)
.B Transform *t1, *t2, *tdst;
.PP
.B GeoInvertTrans(tsrc, tinv)
.B Transform *tsrc, *tinv;
.PP
.B int GeoScale(t)
.B Transform *t;
.PP
.B GeoDecomposeTransform(t, upsidedown, angle)
.B Transform *t;
.B bool *upsidedown;
.B int *angle;
.PP
.B int GeoNameToPos(name, manhattan, printerrors)
.B char *name;
.B bool manhattan, printerrors;
.PP
.B char *GeoPosToName(pos)
.B int pos;
.PP
.B int GeoTransPos(t, pos);
.B Transform *t;
.B int pos;
.PP
.B bool GeoInclude(src, dst);
.B Rect *src, *dst;
.PP
.B bool GeoIncludeAll(src, dst);
.B Rect *src, *dst;
.PP
.B bool GeoIncludePoint(src, dst);
.B Point *src;
.B Rect *dst;
.PP
.B GeoClip(r, cliparea)
.B Rect *r, *cliparea;
.PP
.B GeoClipPoint(p, cliparea)
.B Point *p;
.B Rect *cliparea;
.PP
.B bool GeoDisjoint(area, cliparea, func, cdata)
.B Rect *area, *cliparea;
.B bool (*func)(rect, cdata);
.B ClientData cdata;
.PP
.B bool GeoDummyFunc(rect, cdata)
.B Rect *rect;
.B ClientData cdata;
.PP
.B GeoCanonicalRect(rsrc, rdst)
.B Rect *rsrc, *rdst;
.PP
.B int GeoRectPointSide(r, p)
.B Rect *r;
.B Point *p;
.PP
.B int GeoRectRectSide(r1, r2)
.B Rect *r1, *r2;
.PP
.B bool GetRect(f, nskip, r)
.B FILE *f;
.B int nskip;
.B Rect *r;

.SH DESCRIPTION
These procedures implement a number of useful geometric primitives:
a \fIPoint\fR, which consists of an integer \fIx\fR and \fIy\fR coordinate,
and a \fIRect\fR, which describes a rectangle by its lower-left and upper-right
\fIPoint\fRs.
An important predefined \fIRect\fR is \fIGeoNullRect\fR, the rectangle
with both its lower-left and upper-right at the origin (0, 0).
If linked lists of \fIRect\fRs are needed, the \fILinkedRect\fR primitive
can be used.
.PP
Another primitive is
a position relative to a point (\fIGEO_NORTH\fR, \fIGEO_EAST\fR, etc).
There are a total of nine positions, corresponding to the eight
points around a single point in a grid plus the point itself (\fIGEO_CENTER\fR).
.PP
The final primitive is a \fITransform\fR, which represents some combination of
rotation by a multiple of 90 degrees, mirroring across the \fIx\fR or
\fIy\fR axis, scaling by an integer scale factor,
and translation by an integer \fIx\fR and \fIy\fR displacement.
A \fITransform\fR can be thought of as representing a simple linear
transformation on two-dimensional points, or as a matrix of the
form:
.sp
.in +2i
.nf
.ta +0.3i +0.3i +0.3i +0.3i +0.3i +0.3i +0.3i +0.3i +0.3i
\fIa\fR	\fId\fR	0
\fIb\fR	\fIe\fR	0
\fIc\fR	\fIf\fR	1
.fi
.in -2i
.sp
Multiplying a point vector of the form \fI(x,\ y, 0)\fR by this
transform gives a transformed point \fI(x',\ y',\ 0)\fR.
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
(\fIa\fR, \fIb\fR, \fId\fR, \fIe\fR)
and two for the translation (\fIc\fR, \fIf\fR).
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 \fIS\fR is the
integer scale factor:
.sp
.in +1i
.nf
.ta +0.3i +0.6i +0.3i +0.6i +0.3i +0.6i +0.3i
\fIS	0	0	-S	-S	0	0	S\fR
\fI0	S	S	0	0	-S	-S	0\fR
.sp
\fIS	0	0	S	-S	0	0	-S\fR
\fI0	-S	S	0	0	S	-S	0\fR
.fi
.in -1i
.sp
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 \fIx\fR-axis
after rotating).
.PP
The above rotations or mirrorings with a scale factor of 1
exist as predefined transforms.
\fIGeoIdentityTransform\fR is the identity transformation, i.e,
no transformation at all, or the first transform listed above.
\fIGeo90Transform\fR,
\fIGeo180Transform\fR, and
\fIGeo270Transform\fR correspond to the next three transformations,
or clockwise rotations of 90, 180, and 270 degrees respectively.
\fIGeoUpsideDownTransform\fR is the next transform, mirroring
across the \fIx\fR-axis.
\fIGeoSidewaysTransform\fR is the seventh transform, corresponding
to mirroring across the \fIy\fR-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 \fIGeoTransTrans\fR (see below).
.PP
A number of macros exist for determining relationships between
\fIPoint\fRs and \fIRect\fRs.
\fIGEO_OVERLAP\fR is TRUE if two rectangles share some area in common.
\fIGEO_TOUCH\fR is TRUE if two rectangles share some area or any part
of their perimeters (including touching only at a corner).
\fIGEO_SURROUND\fR is TRUE if \fIr1\fR completely surrounds \fIr2\fR,
where the boundaries of \fIr1\fR and \fIr2\fR are allowed to touch.
\fIGEO_SURROUND_STRONG\fR is like \fIGEO_SURROUND\fR, but is only TRUE
if \fIr1\fR completely surrounds \fIr2\fR without their borders
touching.
\fIGEO_ENCLOSE\fR is TRUE if a point \fIp\fR lies inside or on the
border of the rectangle \fIr\fR.
\fIGEO_RECTNULL\fR is TRUE if \fIr\fR has zero area, which can result
if the \fIx\fR-coordinate of its upper-right is less than or equal
to the \fIx\fR-coordinate of its lower-left, or similarly for the
\fIy\fR-coordinates.
Finally, \fIGEO_EXPAND\fR is used to grow (or shrink) a rectangle \fIsrc\fR
by an integer distance \fIamount\fR, leaving the new rectangle in
\fIdst\fR (which may be the same as \fIsrc\fR).
.PP
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).
\fIGeoTransPoint\fR applies the Transform \fI*t\fR to the
Point \fI*psrc\fR and leaves its result in the Point \fI*pdst\fR.
\fIGeoTransRect\fR is identical, but for Rects; it applies \fIt\fR
to \fI*rsrc\fR and leaves its result in \fI*rdst\fR.
\fIGeoTransRect\fR guarantees that \fIrdst->r_ur\fR is really above
and to the right of \fIrdst->r_ll\fR, 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, \fIGeoUpsideDownTransform\fR).
.PP
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.
\fIGeoTranslateTrans\fR composes first the Transform \fI*tsrc\fR
and then a simple translation by \fIx\fR and \fIy\fR, storing
its result in \fI*tdst\fR.
\fIGeoTransTranslate\fR composes first a simple translation by
\fIx\fR and \fIy\fR, followed by the Transform \fI*tsrc\fR,
also storing its result in \fI*tdst\fR.
Finally, \fIGeoTransTrans\fR composes two arbitrary transforms
\fI*t1\fR and \fI*t2\fR, leaving its result in \fI*tdst\fR.
.PP
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 \fIGeoInvertTrans\fR,
which leaves the inverse of \fI*tsrc\fR in \fI*tinv\fR.
.PP
Two procedures extract useful information from Transforms.
.I GeoScale
returns the scale factor associated with the Transform \fI*t\fR.
.I 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 \fI*upsidedown\fR to \fBTRUE\fR if the transform requires
flipping upside down before rotation, and sets \fI*angle\fR to
the degrees of rotation: 0, 90, 180, or 270.
.PP
Three procedures manipulate positions such as \fIGEO_NORTH\fR.
.I GeoNameToPos
maps the ASCII \fIname\fR for a position (e.g, ``north'', ``top'', or
``left'', ``west'', etc) into the internal position number.
If \fIname\fR is ambiguous, -1 is returned; if \fIname\fR is
unrecognized, -2 is returned.
If \fImanhattan\fR is TRUE, only the directions corresponding to
\fIGEO_NORTH\fR, \fIGEO_SOUTH\fR, \fIGEO_WEST\fR, or \fIGEO_EAST\fR
are accepted.
If \fIprinterrors\fR is TRUE, \fIGeoNameToPos\fR will print an error
message on the standard output in addition to returning -1 or -2.
The inverse of \fIGeoNameToPos\fR is \fIGeoPosToName\fR, which
returns the ASCII string for a given position \fIpos\fR.
.I GeoTransPos
applies the Transfor \fI*t\fR to the position \fIpos\fR and
returns the new position.  Only the rotational part of
\fI*t\fR is relevant; the translation is ignored.
.PP
The next collection of procedures manipulate Points and Rects.
.I GeoInclude
and
.I GeoIncludeAll
extend whichever sides of the Rect \fI*dst\fR that are necessary
to include the area of the Rect \fI*src\fR.
Both return TRUE if \fI*dst\fR was enlarged.
If \fI*src\fR is considered to be zero-size (see below),
\fI*dst\fR is unchanged.
If \fI*dst\fR is zero-size, it is set to \fI*src\fR if \fI*src\fR
is not also zero-size.
The two procedures differ in that \fIGeoInclude\fR considers
zero-area rectangles to be zero-size, while \fIGeoIncludeAll\fR
only considers rectangles whose bottom is actually above their
top or whose LHS is to the right of their RHS to be zero-size.
.I
GeoIncludePoint
is like
.I GeoInclude
except \fI*src\fR is a Point instead of a Rect.
.PP
Three procedures are provided for clipping.
.I GeoClip
determines the portion of the Rect \fI*r\fR that overlaps
the Rect \fI*cliparea\fR and replaces \fI*r\fR with the new
Rect.  If \fI*r\fR and \fI*cliparea\fR don't overlap at all,
\fI*r\fR is turned inside out (\fIr_xbot\fR\ >\ \fIr_xtop\fR
or \fIr_ybot\fR\ >\ \fIr_ytop\fR).
.I GeoClipPoint
moves the Point \fI*p\fR
to the closest point on the boundary of the
Rect \fI*cliparea\fR
if it isn't already contained in \fI*cliparea\fR or on its border.
Finally,
.I GeoDisjoint
is used to clip a Rect against another, but to apply a procedure
to each region in \fI*area\fR that lies outside \fI*cliparea\fR,
instead of modifying \fI*area\fR.  The procedure \fI(*proc)()\fR it applies
should be like the library procedure \fIGeoDummyFunc\fR,
which accepts a Rect and the \fIcdata\fR argument passed to
\fIGeoDisjoint\fR and returns TRUE always.  If \fI(*proc)()\fR
returns FALSE, \fIGeoDisjoint\fR aborts and returns FALSE itself;
otherwise, it returns TRUE.
.I GeoDisjoint
works in ``tile'' space, so each rectangle is considered to
contain its lower \fIx\fR- and \fIy\fR-coordinates, but
not its upper coordinates.
.PP
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.
.I GeoCanonicalRect
can remedy this situation;
it flips the top and bottom or left and right (or both) of the
Rect \fI*rsrc\fR as necessary to ensure that the upper right is
above and to the right of the lower left, leaving the canonical
Rect in \fI*rdst\fR.
.PP
Two procedures compute the relative positions of Points and Rects.
.I GeoRectPointSide
gives the side (\fIGEO_NORTH\fR, etc) of the Rect \fI*r\fR on
which the Point \fI*p\fR lies (\fI*p\fR must lie on the boundary
of \fI*r\fR; otherwise, \fIGEO_CENTER\fR is returned).
Similarly,
.I GeoRectRectSide
gives the side of \fI*r1\fR on which \fI*r2\fR lies, or \fIGEO_CENTER\fR
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).
.PP
A final procedure is provided for high-speed reading of ascii files
containing descriptions of rectangles, \fIGetRect\fR.
This procedure reads from a stdio-opened FILE \fI*f\fR, which should
be positioned so that after skipping \fInskip\fR characters, it
will be at the start of a line containing four ascii numbers that
will be stored in \fIr->r_xbot\fR, \fIr->r_ybot\fR, \fIr->r_xtop\fR,
and \fIr->r_ytop\fR.  It returns TRUE if it successfully recognized
a rectangle, FALSE on error or end-of-file.
\fIGetRect\fR is considerably faster than either \fIfscanf\fR\|(3s) or even
\fIfgets\fR\|(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).
.SH "MACROS FOR SPEED"
If speed is essential, macros are defined in \fBgeofast.h\fR
to take the place of the several procedures for special cases.
.I GEOCLIP
is identical to the procedure \fIGeoClip\fR, but it returns no value.
Four macros for manipulating Transforms, \fIGEOTRANSRECT\fR,
\fIGEOTRANSTRANS\fR, \fIGEOINVERTTRANS\fR, and
\fIGEOTRANSTRANSLATE\fR,
are similar to their procedural counterparts
\fIGeoTransRect\fR,
\fIGeoTransTrans\fR,
\fIGeoInvertTrans\fR, and \fIGeoTransTranslate\fR,
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.

.SH SEE ALSO
magicutils\|(3)