DIRECTORY COGHomo, Real USING [SqRt, TrappingNaN, LargestNumber], RealFns USING [AlmostZero], COGCart USING [Point, PositiveAngle, Vector, ScaleFactors, Add]; COGHomoImpl: CEDAR PROGRAM IMPORTS Real, RealFns, COGHomo, COGCart EXPORTS COGHomo = BEGIN OPEN Real, RealFns, Homo: COGHomo, Cart: COGCart; Way: PUBLIC PROC [alpha: REAL, p, q: Homo.Point] RETURNS [Homo.Point] = BEGIN IF alpha = 0.0 THEN RETURN [p] ELSE IF alpha = 1.0 THEN RETURN [q] ELSE {u: REAL = (1.0-alpha)*q.w; v: REAL = alpha*p.w; RETURN [[u*p.x+v*q.x, u*p.y+v*q.y, p.w*q.w]]} END; Length: PUBLIC PROC [v: Homo.Vector] RETURNS [REAL] = TRUSTED BEGIN IF v.w=0 THEN IF v.x=0 AND v.y = 0 THEN RETURN [Real.TrappingNaN] -- I am guessing here ELSE RETURN [Real.LargestNumber] ELSE RETURN [SqRt[v.x*v.x+v.y*v.y]/ABS[v.w]] END; LengthSq: PUBLIC PROC [v: Homo.Vector] RETURNS [REAL] = BEGIN IF v.w=0 THEN IF v.x=0 AND v.y = 0 THEN RETURN [Real.TrappingNaN] -- I am guessing here ELSE RETURN [Real.LargestNumber] ELSE RETURN [(v.x*v.x+v.y*v.y)/(v.w*v.w)] END; Dist: PUBLIC PROC [p, q: Homo.Point] RETURNS [REAL] = {RETURN [Length[Homo.Sub[p,q]]]}; Incident: PUBLIC PROC [p: Homo.Point, r: Homo.Line] RETURNS [R: BOOLEAN] = BEGIN R _ AlmostZero[r.x*p.x+r.y*p.y+r.w*p.w, -20] END; DistToLine: PUBLIC PROC [p: Homo.Point, r: Homo.Line] RETURNS [REAL] = TRUSTED BEGIN prod: REAL = p.x*r.x+p.y*r.y+p.w*r.w; mod: REAL = r.x*r.x+r.y*r.y; RETURN [IF mod=0 OR p.w=0 THEN IF prod>0 THEN Real.LargestNumber ELSE IF prod<0 THEN -Real.LargestNumber ELSE Real.TrappingNaN ELSE prod/(p.w*SqRt[mod])] END; SameSide: PUBLIC PROC [p, q: Homo.Point, r: Homo.Line] RETURNS [R: BOOLEAN] = {RETURN[(r.x*p.x+r.y*p.y+r.w*p.w)*(r.x*q.x+r.y*q.y+r.w*q.w) >= 0]}; Intercept: PUBLIC PROC [r, s: Homo.Line] RETURNS [Homo.Point] = BEGIN RETURN [[r.y*s.w-r.w*s.y, -r.x*s.w+r.w*s.x, r.x*s.y-r.y*s.x]] END; Bisector: PUBLIC PROC [p, q: Homo.Point] RETURNS [Homo.Line] = BEGIN v: Homo.Vector = Homo.Sub [q, p]; m: Homo.Point = Homo.Add [p, q]; RETURN [[2.0*v.w*v.x, 2.0*v.w*v.y, -m.x*v.x-m.y*v.y]] END; LineThrough: PUBLIC PROC [p, q: Homo.Point] RETURNS [Homo.Line] = BEGIN RETURN [[p.y*q.w-p.w*q.y, -p.x*q.w+p.w*q.x, p.x*q.y-p.y*q.x]] END; Cvx: PROC [p, q, r: Homo.Point] RETURNS [BOOLEAN] = BEGIN -- called by CCW - assumes q is finite RETURN [Cart.PositiveAngle[Homo.PtPtDir[p, q], Homo.PtPtDir[q, r]]] END; CCW: PUBLIC PROC [p, q, r: Homo.Point] RETURNS [BOOLEAN] = BEGIN RETURN [IF Homo.FinPt[q] THEN Cvx[p, q, r] ELSE IF Homo.FinPt[p] THEN Cvx[r, p, q] ELSE IF Homo.FinPt[r] THEN Cvx[q, r, p] ELSE Cart.PositiveAngle[Homo.VecDir[p], Homo.VecDir[q]] AND Cart.PositiveAngle[Homo.VecDir[q], Homo.VecDir[r]]] END; InfiniteCC: PROC [p, q, r: Homo.Point] RETURNS [Homo.Point] = BEGIN -- assumes p is infinite IF Homo.InfPt [q] OR Homo.InfPt [r] THEN RETURN [[0.0, 0.0, 0.0]] ELSE {t: Homo.Vector = Homo.Sub [r, q]; RETURN [[-t.y, t.x, 0.0]]} END; CircumCenter: PUBLIC PROC [p, q, r: Homo.Point] RETURNS [Homo.Vector] = BEGIN -- assumes p, q, r are in counterclockwise order IF Homo.InfPt [p] THEN RETURN [InfiniteCC[p, q, r]] ELSE IF Homo.InfPt [q] THEN RETURN [InfiniteCC[q, r, p]] ELSE IF Homo.InfPt [r] THEN RETURN [InfiniteCC[r, p, q]] ELSE RETURN [Homo.Intercept[Homo.Bisector[p, q], Homo.Bisector[q, r]]] END; Below: PUBLIC PROC [p, q: Homo.Point] RETURNS [R: BOOL] = BEGIN ydir: REAL; ydir _ IF Homo.InfPt[p] AND Homo.InfPt[q] THEN q.y - p.y ELSE Homo.PtPtDir[p, q].y; RETURN [ydir > 0.0] END; ToTheLeftOf: PUBLIC PROC [p, q: Homo.Point] RETURNS [R: BOOL] = BEGIN xdir: REAL = IF Homo.InfPt[p] AND Homo.InfPt[q] THEN q.x - p.x ELSE Homo.PtPtDir[p, q].x; RETURN [xdir > 0.0] END; Precedes: PUBLIC PROC [p, q: Homo.Point] RETURNS [R: BOOL] = BEGIN dir: Cart.Vector = IF Homo.InfPt[p] AND Homo.InfPt[q] THEN [q.x - p.x, q.y - p.y] ELSE Homo.PtPtDir[p, q]; RETURN [dir.x > 0 OR dir.x = 0 AND dir.y > 0] END; InCircle: PUBLIC PROC [p, q, r, s: Homo.Point] RETURNS [R: BOOL] = BEGIN -- used to be ShouldConnect24 -- Checks whether the diagonal qs should be connected in the convex Delaunay -- face pqrs, by intersecting the bisectors of pr and qs and checking which pair -- is closest to the intersection. a, b: Homo.Line; o: Homo.Point; IF q.w = 0.0 OR s.w = 0.0 THEN RETURN [FALSE]; IF p.w = 0.0 OR r.w = 0.0 THEN RETURN [TRUE]; a _ Homo.Bisector[p, r]; b _ Homo.Bisector[q, s]; o _ Homo.Intercept[a, b]; R _ Homo.DistSq[o, p] > Homo.DistSq [o, q] END; ScalePoint: PUBLIC PROC [p: Homo.Point, sf: Cart.ScaleFactors] RETURNS [ps: Cart.Point] = {s: REAL = IF Homo.FinPt[p] THEN 1.0/p.w ELSE 1.0e5; RETURN [[p.x*s*sf.sx + sf.tx, p.y*s*sf.sy + sf.ty]]}; ScaleVector: PUBLIC PROC [v: Homo.Vector, sf: Cart.ScaleFactors] RETURNS [vs: Cart.Point] = {s: REAL = IF Homo.FinPt[v] THEN 1.0/v.w ELSE 1.0e5; RETURN [[v.x*s*sf.sx, v.y*s*sf.sy]]}; ScaleSeg: PUBLIC PROC [p, q: Homo.Point, sf: Cart.ScaleFactors] RETURNS [ps, qs: Cart.Point] = BEGIN IF Homo.FinPt [p] THEN {ps _ Homo.ScalePoint [p, sf]; IF Homo.FinPt [q] THEN {qs _ Homo.ScalePoint [q, sf]} ELSE {qs _ Cart.Add[ps, Homo.ScaleVector [q, sf]]} } ELSE IF Homo.FinPt[q] THEN {qs _ Homo.ScalePoint [q, sf]; ps _ Cart.Add [qs, Homo.ScaleVector [p, sf]] } ELSE {ps _ qs _ [sf.tx, sf.ty]} END; END. F-- COGHomoImpl.mesa: Basic geometrical operations in homogeneous coordinates (implem.) -- last modified by Stolfi October 16, 1982 8:29 pm -- Distance between points p and q. Returns LargestNumber if one point is infinite, and TrappingNaN if both are infinite or one is indeterminate. -- Checks if point belongs to line. Returns TRUE if the line or the point are indeterminate (maybe should return FALSE, but TRUE is easier). Note that Incident[p, r] = Incident[r, p] -- Returns TRUE iff the points p and q are on the same side of the line r (or one of them is on the line). -- Transforms point p according to the scale factors sf. If p is infinite, will map it into a point in the same direction (as seen from the scaled origin) and at a very large distance. If p is indeterminate, will map it as if it were [0, 0]. -- Transforms vector v according to the scale factors sf (will not displace origin). If p is infinite, will map it into a vector in the same direction (as seen from the scaled origin) and at a very large distance. If v is indeterminate, will map it as if it were [0, 0]. Êÿ– "Mesa" style˜IprocšÏcÐbcC™VKš3™3KšÏk œŸœMŸœ3˜¦Kš Ïb œŸœŸœŸœ#Ÿœ ˜XKšŸœŸœ-˜7š ÏnœŸœŸœ ŸœŸœ˜GKšŸœŸœ ŸœŸœŸœŸœ ŸœŸœŸœŸœ!ŸœŸœ(Ÿœ˜Ë—š ¡œŸœŸœŸœŸœŸ˜=KšŸœŸœŸœŸœŸœ ŸœŸœœŸœŸœŸœŸœŸœŸœ˜¼—š ¡œŸœŸœŸœŸœ˜7KšŸœŸœŸœŸœŸœ ŸœŸœœŸœŸœŸœŸœŸœ˜»—š ¡œŸœŸœŸœŸœ˜5Kš‘™‘KšœŸœ˜!—š ¡œŸœŸœŸœŸœŸœ˜KKš¶™¶KšŸœŸœ,Ÿœ˜9—š ¡ œŸœŸœŸœŸœŸ˜NKšŸœ Ÿœ#ŸœŸœŸœŸœŸœŸœŸœ$ŸœŸœŸœ%Ÿœ ŸœŸœ˜«—š ¡œŸœŸœ"ŸœŸœŸœ˜NKšj™jKšœŸœ<˜C—š¡ œŸœŸœŸœ˜?KšŸœŸœ8Ÿœ˜J—š¡œŸœŸœŸœ˜>KšŸœJŸœ0Ÿœ˜‰—š¡ œŸœŸœŸœ˜AKšŸœŸœ8Ÿœ˜J—š¡œŸœŸœŸœ˜4KšŸœ'œŸœ>Ÿœ˜y—š ¡œŸœŸœŸœŸœ˜:KšŸœŸœŸœŸœŸœŸœŸœŸœŸœŸœŸœ4ŸœIŸœ˜²—š¡ œŸœŸœ˜>KšŸœœŸœŸœŸœŸœŸœ.ŸœŸœ˜¸—š¡ œŸœŸœŸœ˜HKš Ÿœ1œŸœŸœŸœŸœŸœŸœŸœŸœŸœŸœŸœŸœŸœ<Ÿœ˜²—š ¡œŸœŸœŸœŸœŸœ˜9KšŸœ Ÿœ ŸœŸœŸœ ŸœŸœŸœ˜„—š ¡ œŸœŸœŸœŸœŸœ˜?KšŸœ ŸœŸœŸœŸœ ŸœŸœŸœ˜|—š ¡œŸœŸœŸœŸœŸœ˜