DIRECTORY Real USING [SqRt], COGRandom USING [Toss]; COGCart: CEDAR DEFINITIONS IMPORTS Real, COGRandom = BEGIN OPEN Real, Rand: COGRandom; Point: TYPE = RECORD [x, y: REAL]; Vector: TYPE = Point; Line: TYPE = RECORD [a, b, c: REAL]; Box: TYPE = RECORD [min, max: Point]; Add: PROC [a, b: Vector] RETURNS [Vector] = INLINE {RETURN [[a.x+b.x, a.y+b.y]]}; Sub: PROC [a, b: Vector] RETURNS [Vector] = INLINE {RETURN [[a.x-b.x, a.y-b.y]]}; Mul: PROC [a: REAL, u: Vector] RETURNS [w: Vector] = INLINE {RETURN [[u.x*a, u.y*a]]}; Way: PROC [alpha: REAL, a, b: Point] RETURNS [Point] = INLINE {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 {RETURN [u.x*v.x+u.y*v.y]}; Rot: PROC [u: Vector, c, s: REAL] RETURNS [ur: Vector] = INLINE {RETURN [[c*u.x-s*u.y, c*u.y+s*u.x]]}; Length: PROC [v: Vector] RETURNS [REAL] = TRUSTED INLINE {RETURN [SqRt[v.x*v.x+v.y*v.y]]}; LengthSq: PROC [v: Vector] RETURNS [REAL] = INLINE {RETURN [v.x*v.x+v.y*v.y]}; Dist: PROC [a, b: Point] RETURNS [REAL] = INLINE {RETURN [Length[Sub[a, b]]]}; DistSq: PROC [a, b: Point] RETURNS [REAL] = INLINE {RETURN [LengthSq[Sub[a, b]]]}; Bisector: PROC [a, b: Point] RETURNS [Line]; Intercept: PROC [r, s: Line] RETURNS [Point]; AddAngles: PROC [u, v: Vector] RETURNS [Vector] = INLINE {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 {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 {RETURN [u.x*v.y-v.x*u.y > 0.0]}; Convex: PROC [a, b, c: Point] RETURNS [BOOLEAN]; CircumCenter: PROC [a, b, c: Point] RETURNS [Vector] = INLINE {RETURN [Intercept[Bisector[a, b], Bisector[b, c]]]}; ScaleFactors: TYPE = RECORD [sx, sy: REAL, -- stretching tx, ty: REAL -- translation (after stretching) ]; ScalePoint: PROC [p: Point, sf: ScaleFactors] RETURNS [q: Point] = INLINE {RETURN [[p.x*sf.sx + sf.tx, p.y*sf.sy + sf.ty]]}; ScaleVector: PROC [v: Vector, sf: ScaleFactors] RETURNS [q: Point] = INLINE {RETURN [[v.x*sf.sx, v.y*sf.sy]]}; UnScalePoint: PROC [q: Point, sf: ScaleFactors] RETURNS [p: Point] = INLINE {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]; Random: PROC [box: Box] RETURNS [v: Vector] = INLINE {RETURN [[Rand.Toss [box.min.x, box.max.x], Rand.Toss [box.min.y, box.max.y]]]}; END. Z-- COGCart.mesa: Basic geometrical operations in the Cartesian plane -- last modified by Stolfi - September 20, 1982 7:27 pm -- BASIC DATA TYPES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- 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. -- PROCEDURES FOR POINTS AND VECTORS - - - - - - - - - - - - - - - - - - - - - - - - - - -- Adds two vectors (or points). -- Subtracts two vectors (or points). -- Multiplies the vector u by a real number a. -- Computes the point alpha the way from a to b.. -- Dot product of u and v. -- Rotates the vector u by an angle whose cosine is c and whose sine is s. -- Length of vector v. -- Length of vector v, squared (saves a square root extraction). -- Distance between points p and q. -- Distance between points p and q, squared (saves a square root extraction). -- PROCEDURES FOR LINES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- 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. -- 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. -- The result will make with the x-axis an angle equal to angle(u, x-axis)+angle(v, x-axis). -- The result will make with the x-axis an angle equal to angle(u, v). -- TRUE iff the angle from u to v is between 0 and pi (exclusive both). -- 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. -- Computes the circumcenter of the points p, q and r. Assumes they are given in counterclockwise order around the triangle pqr. -- POINT TRANSFORMATIONS FOR PLOTTING - - - - - - - - - - - - - - - - - - - - - - - - - - -- Transforms point p according to the scale factors sf. -- Transforms the vector v according to the scale factors sf (will not translate the origin). -- Transforms point q according to the inverse of the scale factors sf. -- 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 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -- Returns a random vector strictly inside the given box. ΚΪ– "Mesa" style˜IprocšΟcΠbc 5™DKš7™7KšΟk œŸœŸœ˜8KšΟbœŸœŸ œŸœ˜6KšŸœŸœ˜!K˜KšR™RKš œŸœŸœŸœ˜"Kš œŸœ ˜š œŸœŸœ Ÿœ˜$Kšœί™βKšœŒ™—K˜Kš œŸœŸœ˜%K˜KšY™YšΟnœŸœŸœ Ÿ˜2Kš ™ KšœŸœ˜—K˜š‘œŸœŸœ Ÿ˜2Kš%™%KšœŸœ˜—K˜š ‘œŸœŸœ ŸœŸ˜;Kš.™.KšœŸœ˜—K˜š ‘œŸœ ŸœŸœ Ÿ˜=Kš1™1KšœŸœŸœ-˜O—K˜š ‘œŸœŸœŸœŸ˜0Kš™KšœŸœ˜—K˜š‘œŸœŸœŸ˜?KšK™KKšœŸœ˜&—K˜š ‘œŸœ ŸœŸœŸœŸ˜8Kš™KšœŸœ˜!—K˜š ‘œŸœ ŸœŸœŸ˜2Kš@™@KšœŸœ˜—K˜š ‘œŸœŸœŸœŸ˜0Kš#™#KšœŸœ˜—K˜š ‘œŸœŸœŸœŸ˜2KšM™MKšœŸœ˜—K˜KšW™Wš‘œŸœŸœ˜-Kš™™™—K˜š‘ œŸœŸœ ˜-Kš.™.—K˜šX™XKšΈ™Έ—K˜š‘ œŸœŸœ Ÿ˜9Kš]™]KšœŸœ'˜.—K˜š‘ œŸœŸœ Ÿ˜8KšG™GKšœŸœ)˜0—K˜š ‘ œŸœŸœŸœŸ˜=KšH™HKšœŸœ˜!—K˜š‘œŸœŸœŸœ˜0Kš™—K˜š‘ œŸœŸœ Ÿ˜=Kš€™€KšœŸœ.˜5—K˜KšZ™ZKš  œŸœŸœ Ÿœœ Ÿœ"œ˜rK˜š‘ œŸœŸœŸ˜IKš8™8KšœŸœ+˜2—K˜š‘ œŸœŸœŸ˜KKš]™]KšœŸœ˜"—K˜š‘ œŸœŸœŸ˜KKšG™GKšœŸœ/˜6—K˜š‘ œŸœŸœŸœ˜MKš Qžžž9ž™Ο—K˜Kšc™cš‘œŸœ ŸœŸ˜4Kš9™9KšœŸœI˜P—KšŸœ˜—…— ¬ΰ