<<-- COGCart.mesa: Basic geometrical operations in the Cartesian plane>> <<-- last modified by Stolfi - September 20, 1982 7:27 pm>> DIRECTORY Real USING [SqRt], COGRandom USING [Toss]; COGCart: CEDAR DEFINITIONS IMPORTS Real, COGRandom = BEGIN OPEN Real, Rand: COGRandom; <<-- BASIC DATA TYPES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> Point: TYPE = RECORD [x, y: REAL]; Vector: TYPE = Point; Line: TYPE = RECORD [a, b, c: REAL]; << -- The line [a, b, c] consists of the points [x, y] for which a*x+b*y+c = 0 in Cartesian coordinates. A line with a=b=0, c#0 is said to be at empty (no point belongs to it); a line with a=b=c=0 is indeterminate (any point is in it). A line with c=0 and a#0 or b#0 is a line through the origin. The vector [a, b] is perpendicular to the line [a, b, c].>> << -- The lines r=[a, b, c] and r'=[d*a, d*b, d*c] are essentially equivalent for any d>0. If d<0, the two lines have the same points but are considered to have opposite orientations, so that, for example, the distances from a point to those two lines will have opposite signs. The orientation of line r is by definition such that the vector [a, b] points to the left of r. The empty line [0, 0, c] may be thought as a circle of infinite radius centerd at the origin; by definition, its orientation is counterclockwise iff c>0.>> Box: TYPE = RECORD [min, max: Point]; <<-- PROCEDURES FOR POINTS AND VECTORS - - - - - - - - - - - - - - - - - - - - - - - - - - >> Add: PROC [a, b: Vector] RETURNS [Vector] = INLINE <<-- Adds two vectors (or points).>> {RETURN [[a.x+b.x, a.y+b.y]]}; Sub: PROC [a, b: Vector] RETURNS [Vector] = INLINE <<-- Subtracts two vectors (or points).>> {RETURN [[a.x-b.x, a.y-b.y]]}; Mul: PROC [a: REAL, u: Vector] RETURNS [w: Vector] = INLINE <<-- Multiplies the vector u by a real number a.>> {RETURN [[u.x*a, u.y*a]]}; Way: PROC [alpha: REAL, a, b: Point] RETURNS [Point] = INLINE <<-- Computes the point alpha the way from a to b..>> {beta: REAL = (1.0-alpha); RETURN [[beta*a.x+alpha*b.x, beta*a.y+alpha*b.y]]}; Dot: PROC [u, v: Vector] RETURNS [REAL] = INLINE <<-- Dot product of u and v. >> {RETURN [u.x*v.x+u.y*v.y]}; Rot: PROC [u: Vector, c, s: REAL] RETURNS [ur: Vector] = INLINE <<-- Rotates the vector u by an angle whose cosine is c and whose sine is s. >> {RETURN [[c*u.x-s*u.y, c*u.y+s*u.x]]}; Length: PROC [v: Vector] RETURNS [REAL] = TRUSTED INLINE <<-- Length of vector v. >> {RETURN [SqRt[v.x*v.x+v.y*v.y]]}; LengthSq: PROC [v: Vector] RETURNS [REAL] = INLINE <<-- Length of vector v, squared (saves a square root extraction).>> {RETURN [v.x*v.x+v.y*v.y]}; Dist: PROC [a, b: Point] RETURNS [REAL] = INLINE <<-- Distance between points p and q.>> {RETURN [Length[Sub[a, b]]]}; DistSq: PROC [a, b: Point] RETURNS [REAL] = INLINE <<-- Distance between points p and q, squared (saves a square root extraction).>> {RETURN [LengthSq[Sub[a, b]]]}; <<-- PROCEDURES FOR LINES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - ->> Bisector: PROC [a, b: Point] RETURNS [Line]; <<-- Finds the bisector of points a and b. If both points are coincident, the line is indeterminate. The bisector is oriented 90 counterclockwise from q-p.>> Intercept: PROC [r, s: Line] RETURNS [Point]; <<-- Computes the intersection of lines r and s.>> <<-- PROCEDURES FOR DIRECTIONS AND ANGLES - - - - - - - - - - - - - - - - - - - - - - - - >> <<-- An angle between vectors, lines or points can be measured and compared by converting it to a vector that makes the same angle with the x-axis. This is done by the procedures below. >> AddAngles: PROC [u, v: Vector] RETURNS [Vector] = INLINE <<-- The result will make with the x-axis an angle equal to angle(u, x-axis)+angle(v, x-axis). >> {RETURN [[u.x*v.x-u.y*v.y, u.x*v.y+u.y*v.x]]}; SubAngles: PROC [u, v: Vector] RETURNS [Vector] = INLINE <<-- The result will make with the x-axis an angle equal to angle(u, v). >> {RETURN [[-u.x*v.x+u.y*v.y, -u.x*v.y-u.y*v.x]]}; PositiveAngle: PROC [u, v: Vector] RETURNS [BOOLEAN] = INLINE <<-- TRUE iff the angle from u to v is between 0 and pi (exclusive both). >> {RETURN [u.x*v.y-v.x*u.y > 0.0]}; Convex: PROC [a, b, c: Point] RETURNS [BOOLEAN]; <<-- Returns TRUE iff the angle pqr is strictly convex, i.e. iff from some point o the points p, q and r are seen counterclockwise in that order.>> CircumCenter: PROC [a, b, c: Point] RETURNS [Vector] = INLINE <<-- Computes the circumcenter of the points p, q and r. Assumes they are given in counterclockwise order around the triangle pqr.>> {RETURN [Intercept[Bisector[a, b], Bisector[b, c]]]}; <<-- POINT TRANSFORMATIONS FOR PLOTTING - - - - - - - - - - - - - - - - - - - - - - - - - - >> ScaleFactors: TYPE = RECORD [sx, sy: REAL, -- stretching tx, ty: REAL -- translation (after stretching) ]; ScalePoint: PROC [p: Point, sf: ScaleFactors] RETURNS [q: Point] = INLINE <<-- Transforms point p according to the scale factors sf.>> {RETURN [[p.x*sf.sx + sf.tx, p.y*sf.sy + sf.ty]]}; ScaleVector: PROC [v: Vector, sf: ScaleFactors] RETURNS [q: Point] = INLINE <<-- Transforms the vector v according to the scale factors sf (will not translate the origin).>> {RETURN [[v.x*sf.sx, v.y*sf.sy]]}; UnScalePoint: PROC [q: Point, sf: ScaleFactors] RETURNS [p: Point] = INLINE <<-- Transforms point q according to the inverse of the scale factors sf.>> {RETURN [[(q.x - sf.tx)/sf.sx, (q.y - sf.ty)/sf.sy]]}; BoxToBoxScale: PROC [bo, bd: Box, mf: REAL _ 0.1] RETURNS [sf: ScaleFactors]; <<-- Computes the scale factors (with same stretching in x and y) that map the box bo so that it fits into the box bd with the given extra margin mf around it (expressed as a fraction of the dimensions of bd).>> <<-- MISCELLANEOUS - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> Random: PROC [box: Box] RETURNS [v: Vector] = INLINE <<-- Returns a random vector strictly inside the given box.>> {RETURN [[Rand.Toss [box.min.x, box.max.x], Rand.Toss [box.min.y, box.max.y]]]}; END.