G2dBasicImpl.mesa
Copyright Ó 1988, 1992 by Xerox Corporation. All rights reserved.
Bloomenthal, July 1, 1992 7:03 pm PDT
DIRECTORY G2dBasic, Real, RealFns;
G2dBasicImpl: CEDAR PROGRAM
IMPORTS Real, RealFns
EXPORTS G2dBasic
~ BEGIN
Border:      TYPE ~ G2dBasic.Border;
Box2d:      TYPE ~ G2dBasic.Box;
Card3:       TYPE ~ G2dBasic.Card3;
Integer3:      TYPE ~ G2dBasic.Integer3;
IntegerPair:     TYPE ~ G2dBasic.IntegerPair;
IntegerPairSequence:  TYPE ~ G2dBasic.IntegerPairSequence;
IntegerPairSequenceRep: TYPE ~ G2dBasic.IntegerPairSequenceRep;
IntegerSequence:    TYPE ~ G2dBasic.IntegerSequence;
IntegerSequenceRep:   TYPE ~ G2dBasic.IntegerSequenceRep;
IntPair:      TYPE ~ G2dBasic.IntPair;
IntPairSequence:    TYPE ~ G2dBasic.IntPairSequence;
IntPairSequenceRep:   TYPE ~ G2dBasic.IntPairSequenceRep;
IntSequence:     TYPE ~ G2dBasic.IntSequence;
IntSequenceRep:    TYPE ~ G2dBasic.IntSequenceRep;
Nat3:       TYPE ~ G2dBasic.Nat3;
NatPair:      TYPE ~ G2dBasic.NatPair;
NatPairSequence:   TYPE ~ G2dBasic.NatPairSequence;
NatPairSequenceRep:  TYPE ~ G2dBasic.NatPairSequenceRep;
NatSequence:     TYPE ~ G2dBasic.NatSequence;
NatSequenceRep:    TYPE ~ G2dBasic.NatSequenceRep;
Pair:       TYPE ~ G2dBasic.Pair;
PairSequence:    TYPE ~ G2dBasic.PairSequence;
PairSequenceRep:   TYPE ~ G2dBasic.PairSequenceRep;
RealSequence:    TYPE ~ G2dBasic.RealSequence;
RealSequenceRep:   TYPE ~ G2dBasic.RealSequenceRep;
Sign:       TYPE ~ G2dBasic.Sign;
Triple:      TYPE ~ G2dBasic.Triple;
PI:        REAL ~ 3.1415926535;
Basic Operations
ArcCos: PUBLIC PROC [cos: REAL] RETURNS [a: REAL] ~ {
x: REAL ~ MIN[1.0, MAX[-1.0, cos]];
a ¬ IF x < 0.95
THEN     -- Method 1 --
RealFns.ArcTan[RealFns.SqRt[1.0-x*x], x] -- save a divide
ELSE IF x = -1.0  -- Method 2 --
THEN PI
ELSE 2.0*RealFns.ArcTan[RealFns.SqRt[(1.0-x)/(1.0+x)], 1.0];
};
ArcCosDeg: PUBLIC PROC [cos: REAL] RETURNS [REAL] ~ {
RETURN[ArcCos[cos]*180.0/PI];
};
David Goldberg notes regarding the accuracy of the two methods:
When x ~ y, then x-y is dangerous if x and/or y have suffered roundoff error, because you might cancel all the significant digits, leaving only roundoff error. That's the trouble with 1-x*x; there will be roundoff error in x*x, and if x ~ 1, then 1-x*x can have a large relative error. However, if x ~ 1, (in fact, if 1/2 < x < 2), then 1-x is exact because there is no roundoff error. Thus 1/(1-x) is very accurate. That's the theory according to floating point experts.
Method 1 is worse when x = 1-n*2^(-24), n = sqrt(2^(23)), i.e., x = 0.9998274. The correct value is 1.857983e-02; Method 1 gives 1.858144e-2 (error .000161e-2) while Method 2 gives 1.858064e-2 (error .000081e-2). So, in this case, Method 2 has half the error of Method 1.
[Artwork node; type 'Artwork on' to command tool]
The ArcCos Geometry for Method 2
Sequence Copying
CopyNatSequence: PUBLIC PROC [nats: NatSequence]
RETURNS [NatSequence] ~ {
copy: NatSequence ¬ NIL;
IF nats # NIL THEN {
copy ¬ NEW[NatSequenceRep[nats.length]];
copy.length ¬ nats.length;
FOR n: NAT IN [0..nats.length) DO copy[n] ¬ nats[n]; ENDLOOP;
};
RETURN[copy];
};
CopyIntegerSequence: PUBLIC PROC [integers: IntegerSequence]
RETURNS [IntegerSequence] ~ {
copy: IntegerSequence ¬ NIL;
IF integers # NIL THEN {
copy ¬ NEW[IntegerSequenceRep[integers.length]];
copy.length ¬ integers.length;
FOR n: NAT IN [0..integers.length) DO copy[n] ¬ integers[n]; ENDLOOP;
};
RETURN[copy];
};
CopyIntSequence: PUBLIC PROC [ints: IntSequence] RETURNS [IntSequence] ~ {
copy: IntSequence ¬ NIL;
IF ints # NIL THEN {
copy ¬ NEW[IntSequenceRep[ints.length]];
copy.length ¬ ints.length;
FOR n: NAT IN [0..ints.length) DO copy[n] ¬ ints[n]; ENDLOOP;
};
RETURN[copy];
};
CopyRealSequence: PUBLIC PROC [reals: RealSequence]
RETURNS [RealSequence] ~ {
copy: RealSequence ¬ NIL;
IF reals # NIL THEN {
copy ¬ NEW[RealSequenceRep[reals.length]];
copy.length ¬ reals.length;
FOR n: NAT IN [0..reals.length) DO copy[n] ¬ reals[n]; ENDLOOP;
};
RETURN[copy];
};
CopyPairSequence: PUBLIC PROC [pairs: PairSequence]
RETURNS [PairSequence] ~ {
copy: PairSequence ¬ NIL;
IF pairs # NIL THEN {
copy ¬ NEW[PairSequenceRep[pairs.length]];
copy.length ¬ pairs.length;
FOR n: NAT IN [0..pairs.length) DO copy[n] ¬ pairs[n]; ENDLOOP;
};
RETURN[copy];
};
CopyIntPairSequence: PUBLIC PROC [intPairs: IntPairSequence]
RETURNS [IntPairSequence]
~ {
copy: IntPairSequence ¬ NIL;
IF intPairs # NIL THEN {
copy ¬ NEW[IntPairSequenceRep[intPairs.length]];
copy.length ¬ intPairs.length;
FOR n: NAT IN [0..intPairs.length) DO copy[n] ¬ intPairs[n]; ENDLOOP;
};
RETURN[copy];
};
CopyIntegerPairSequence: PUBLIC PROC [integerPairs: IntegerPairSequence]
RETURNS [IntegerPairSequence]
~ {
copy: IntegerPairSequence ¬ NIL;
IF integerPairs # NIL THEN {
copy ¬ NEW[IntegerPairSequenceRep[integerPairs.length]];
copy.length ¬ integerPairs.length;
FOR n: NAT IN [0..integerPairs.length) DO copy[n] ¬ integerPairs[n]; ENDLOOP;
};
RETURN[copy];
};
CopyNatPairSequence: PUBLIC PROC [natPairs: NatPairSequence]
RETURNS [NatPairSequence]
~ {
copy: NatPairSequence ¬ NIL;
IF natPairs # NIL THEN {
copy ¬ NEW[NatPairSequenceRep[natPairs.length]];
copy.length ¬ natPairs.length;
FOR n: NAT IN [0..natPairs.length) DO copy[n] ¬ natPairs[n]; ENDLOOP;
};
RETURN[copy];
};
Adding to a Sequence
AddToNatSequence: PUBLIC PROC [nats: NatSequence, nat: NAT]
RETURNS [NatSequence]
~ {
IF nats = NIL THEN nats ¬ NEW[NatSequenceRep[1]];
IF nats.length = nats.maxLength THEN nats ¬ LengthenNatSequence[nats];
nats[nats.length] ¬ nat;
nats.length ¬ nats.length+1;
RETURN[nats];
};
AddToIntegerSequence: PUBLIC PROC [integers: IntegerSequence, integer: INTEGER]
RETURNS [IntegerSequence]
~ {
IF integers = NIL THEN integers ¬ NEW[IntegerSequenceRep[1]];
IF integers.length = integers.maxLength THEN integers ¬ LengthenIntegerSequence[integers];
integers[integers.length] ¬ integer;
integers.length ¬ integers.length+1;
RETURN[integers];
};
AddToIntSequence: PUBLIC PROC [ints: IntSequence, int: INT]
RETURNS [IntSequence]
~ {
IF ints = NIL THEN ints ¬ NEW[IntSequenceRep[1]];
IF ints.length = ints.maxLength THEN ints ¬ LengthenIntSequence[ints];
ints[ints.length] ¬ int;
ints.length ¬ ints.length+1;
RETURN[ints];
};
AddToRealSequence: PUBLIC PROC [reals: RealSequence, real: REAL]
RETURNS [RealSequence]
~ {
IF reals = NIL THEN reals ¬ NEW[RealSequenceRep[1]];
IF reals.length = reals.maxLength THEN reals ¬ LengthenRealSequence[reals];
reals[reals.length] ¬ real;
reals.length ¬ reals.length+1;
RETURN[reals];
};
AddToPairSequence: PUBLIC PROC [pairs: PairSequence, pair: Pair]
RETURNS [PairSequence]
~ {
IF pairs = NIL THEN pairs ¬ NEW[PairSequenceRep[1]];
IF pairs.length = pairs.maxLength THEN pairs ¬ LengthenPairSequence[pairs];
pairs[pairs.length] ¬ pair;
pairs.length ¬ pairs.length+1;
RETURN[pairs];
};
AddToNatPairSequence: PUBLIC PROC [natPairs: NatPairSequence, natPair: NatPair]
RETURNS [NatPairSequence]
~ {
IF natPairs = NIL THEN natPairs ¬ NEW[NatPairSequenceRep[1]];
IF natPairs.length = natPairs.maxLength THEN natPairs ¬ LengthenNatPairSequence[natPairs];
natPairs[natPairs.length] ¬ natPair;
natPairs.length ¬ natPairs.length+1;
RETURN[natPairs];
};
AddToIntPairSequence: PUBLIC PROC [intPairs: IntPairSequence, intPair: IntPair]
RETURNS [IntPairSequence]
~ {
IF intPairs = NIL THEN intPairs ¬ NEW[IntPairSequenceRep[1]];
IF intPairs.length = intPairs.maxLength THEN intPairs ¬ LengthenIntPairSequence[intPairs];
intPairs[intPairs.length] ¬ intPair;
intPairs.length ¬ intPairs.length+1;
RETURN[intPairs];
};
AddToIntegerPairSequence: PUBLIC PROC [
integerPairs: IntegerPairSequence, integerPair: IntegerPair]
RETURNS [IntegerPairSequence]
~ {
IF integerPairs = NIL THEN integerPairs ¬ NEW[IntegerPairSequenceRep[1]];
IF integerPairs.length = integerPairs.maxLength
THEN integerPairs ¬ LengthenIntegerPairSequence[integerPairs];
integerPairs[integerPairs.length] ¬ integerPair;
integerPairs.length ¬ integerPairs.length+1;
RETURN[integerPairs];
};
Lengthening a Sequence
LengthenNatSequence: PUBLIC PROC [nats: NatSequence, amount: REAL ¬ 1.3]
RETURNS [new: NatSequence] ~ {
newLength: CARDINAL ¬ Real.Ceiling[amount*nats.maxLength];
newLength ¬ MAX[newLength, 3];
new ¬ NEW[NatSequenceRep[newLength]];
FOR i: NAT IN [0..nats.length) DO new[i] ¬ nats[i]; ENDLOOP;
new.length ¬ nats.length;
};
LengthenIntegerSequence: PUBLIC PROC [integers: IntegerSequence, amount: REAL ¬ 1.3]
RETURNS [new: IntegerSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*integers.maxLength], 3];
new ¬ NEW[IntegerSequenceRep[newLength]];
FOR i: NAT IN [0..integers.length) DO new[i] ¬ integers[i]; ENDLOOP;
new.length ¬ integers.length;
};
LengthenIntSequence: PUBLIC PROC [ints: IntSequence, amount: REAL ¬ 1.3]
RETURNS [new: IntSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*ints.maxLength], 3];
new ¬ NEW[IntSequenceRep[newLength]];
FOR i: NAT IN [0..ints.length) DO new[i] ¬ ints[i]; ENDLOOP;
new.length ¬ ints.length;
};
LengthenRealSequence: PUBLIC PROC [reals: RealSequence, amount: REAL ¬ 1.3]
RETURNS [new: RealSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*reals.maxLength], 3];
new ¬ NEW[RealSequenceRep[newLength]];
FOR i: NAT IN [0..reals.length) DO new[i] ¬ reals[i]; ENDLOOP;
new.length ¬ reals.length;
};
LengthenPairSequence: PUBLIC PROC [pairs: PairSequence, amount: REAL ¬ 1.3]
RETURNS [new: PairSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*pairs.maxLength], 3];
new ¬ NEW[PairSequenceRep[newLength]];
FOR i: NAT IN [0..pairs.length) DO new[i] ¬ pairs[i]; ENDLOOP;
new.length ¬ pairs.length;
};
LengthenNatPairSequence: PUBLIC PROC [natPairs: NatPairSequence, amount: REAL ¬ 1.3]
RETURNS [new: NatPairSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*natPairs.maxLength], 3];
new ¬ NEW[NatPairSequenceRep[newLength]];
FOR i: NAT IN [0..natPairs.length) DO new[i] ¬ natPairs[i]; ENDLOOP;
new.length ¬ natPairs.length;
};
LengthenIntPairSequence: PUBLIC PROC [intPairs: IntPairSequence, amount: REAL ¬ 1.3]
RETURNS [new: IntPairSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*intPairs.maxLength], 3];
new ¬ NEW[IntPairSequenceRep[newLength]];
FOR i: NAT IN [0..intPairs.length) DO new[i] ¬ intPairs[i]; ENDLOOP;
new.length ¬ intPairs.length;
};
LengthenIntegerPairSequence: PUBLIC PROC [
integerPairs: IntegerPairSequence, amount: REAL ¬ 1.3]
RETURNS [new: IntegerPairSequence] ~ {
newLength: NAT ¬ MAX[Real.Ceiling[amount*integerPairs.maxLength], 3];
new ¬ NEW[IntegerPairSequenceRep[newLength]];
FOR i: NAT IN [0..integerPairs.length) DO new[i] ¬ integerPairs[i]; ENDLOOP;
new.length ¬ integerPairs.length;
};
END.