DIRECTORY Convert, Draw2d, G2dBasic, G2dContour, G2dVector, Imager, ImagerBackdoor, ImagerPath, ImagerSample, IO, Real, RealFns, Rope, RuntimeError, Vector2; G2dContourImpl: CEDAR PROGRAM IMPORTS Convert, Draw2d, G2dBasic, G2dVector, Imager, ImagerBackdoor, ImagerSample, IO, Real, RealFns, Rope, RuntimeError, Vector2 EXPORTS G2dContour ~ BEGIN OPEN G2dContour; Error: PUBLIC SIGNAL [code: ATOM, reason: ROPE] = CODE; TestProc: TYPE ~ PROC [p0, p1, p2: Pair] RETURNS [BOOL]; NatList: TYPE ~ REF NatListRep; NatListRep: TYPE ~ RECORD [n: NAT, next: NatList ¬ NIL]; NatListSequence: TYPE ~ REF NatListSequenceRep; NatListSequenceRep: TYPE ~ RECORD [element: SEQUENCE length: NAT OF NatList]; FromPairs: PUBLIC PROC [pairs: PairSequence, closed: BOOL ¬ FALSE, t: REAL ¬ 0.0] RETURNS [contour: Contour] ~ { contour ¬ NEW[ContourRep ¬ [t: t, closed: closed]]; contour.circle ¬ FALSE; contour.pairs ¬ pairs; }; FromIntegerPairs: PUBLIC PROC [ integerPairs: IntegerPairSequence, closed: BOOL ¬ FALSE, t: REAL ¬ 0.0] RETURNS [Contour] ~ { pairs: PairSequence ¬ NEW[PairSequenceRep[integerPairs.length]]; pairs.length ¬ integerPairs.length; FOR n: NAT IN [0..integerPairs.length) DO ip: IntegerPair ¬ integerPairs[n]; pairs[n] ¬ [ip.x, ip.y]; ENDLOOP; RETURN[FromPairs[pairs, closed, t]]; }; IntegerPairsFromPairs: PUBLIC PROC [pairs: PairSequence] RETURNS [ints: IntegerPairSequence] ~ { ints ¬ NEW[G2dBasic.IntegerPairSequenceRep[pairs.length]]; ints.length ¬ pairs.length; FOR n: NAT IN [0..ints.length) DO p: Pair ¬ pairs[n]; ints[n] ¬ [Real.Round[p.x], Real.Round[p.y]]; ENDLOOP; }; PairsFromIntegerPairs: PUBLIC PROC [integerPairs: IntegerPairSequence] RETURNS [pairs: PairSequence] ~ { pairs ¬ NEW[PairSequenceRep[integerPairs.length]]; pairs.length ¬ integerPairs.length; FOR n: NAT IN [0..pairs.length) DO ip: IntegerPair ¬ integerPairs[n]; pairs[n] ¬ [ip.x, ip.y]; ENDLOOP; }; ShiftPairs: PUBLIC PROC [pairs: PairSequence, shift: INTEGER] ~ { leftShift: NAT ¬ IF shift < 0 THEN pairs.length+shift+1 ELSE shift; save: PairSequence ¬ NEW[PairSequenceRep[leftShift]]; stop: INTEGER ¬ pairs.length-leftShift; FOR n: NAT IN [0..leftShift) DO save[n] ¬ pairs[n]; ENDLOOP; FOR n: NAT IN [0..stop) DO pairs[n] ¬ pairs[n+leftShift]; ENDLOOP; FOR n: NAT IN [0..leftShift) DO pairs[n+stop] ¬ save[n]; ENDLOOP; }; Scale: PUBLIC PROC [contour: Contour, scale: Pair] RETURNS [Contour] ~ { IF contour # NIL AND contour.pairs # NIL THEN FOR n: NAT IN [0..contour.pairs.length) DO contour.pairs[n] ¬ Vector2.MulC[contour.pairs[n], scale]; ENDLOOP; RETURN[contour]; }; Offset: PUBLIC PROC [contour: Contour, offset: Pair] RETURNS [Contour] ~ { IF contour # NIL AND contour.pairs # NIL THEN FOR n: NAT IN [0..contour.pairs.length) DO contour.pairs[n] ¬ Vector2.Add[contour.pairs[n], offset]; ENDLOOP; RETURN[contour]; }; Center: PUBLIC PROC [contour: Contour] RETURNS [Contour] ~ { RETURN[Offset[contour, Vector2.Neg[Centroid[contour]]]]; }; Orient: PUBLIC PROC [contour: Contour] RETURNS [Contour] ~ { IF contour # NIL AND contour.pairs # NIL THEN { shift: NAT ¬ 0; min, max: Pair; [min, max] ¬ MinMax[contour]; DO IF contour.pairs[shift].y = min.y THEN EXIT; shift ¬ shift+1; ENDLOOP; ShiftPairs[contour.pairs, shift]; IF contour.normals # NIL THEN ShiftPairs[contour.normals, shift]; }; RETURN[contour]; }; ContourOK: PUBLIC PROC [contour: Contour] RETURNS [BOOL] ~ { RETURN[contour # NIL AND contour.pairs # NIL AND contour.pairs.length > 0]; }; MinMax: PUBLIC PROC [contour: Contour] RETURNS [min, max: Pair] ~ { IF contour # NIL AND contour.pairs # NIL AND contour.pairs.length > 0 THEN { min ¬ [10000.0, 10000.0]; max ¬ [-10000.0, -10000.0]; FOR n: NAT IN [0..contour.pairs.length) DO p: Pair ¬ contour.pairs[n]; min ¬ [MIN[min.x, p.x], MIN[min.y, p.y]]; max ¬ [MAX[max.x, p.x], MAX[max.y, p.y]]; ENDLOOP; }; }; Centroid: PUBLIC PROC [contour: Contour] RETURNS [Pair] ~ { min, max, centroid: Pair ¬ [0.0, 0.0]; IF contour # NIL AND contour.pairs # NIL AND contour.pairs.length > 0 THEN { [min, max] ¬ MinMax[contour]; centroid ¬ [0.5*(min.x+max.x), 0.5*(min.y+max.y)]; }; RETURN[centroid]; }; Area: PUBLIC PROC [contour: Contour] RETURNS [REAL] ~ { area: REAL ¬ 0.0; IF contour # NIL AND contour.pairs # NIL AND contour.closed THEN { p0: Pair ¬ contour.pairs[contour.pairs.length-1]; FOR n: NAT IN [0..contour.pairs.length) DO p1: Pair ¬ contour.pairs[n]; area ¬ area+(p1.x-p0.x)*(p0.y+p1.y); p0 ¬ p1; ENDLOOP; }; RETURN[0.5*area]; }; SmoothPairs: PUBLIC PROC [src: PairSequence, dst: PairSequence ¬ NIL] RETURNS [PairSequence] ~ { IF src = NIL THEN RETURN[NIL]; IF dst = NIL OR dst.maxLength < src.length THEN dst ¬ NEW[PairSequenceRep[src.length]]; dst.length ¬ src.length; { p1: Pair ¬ dst[0] ¬ src[0]; p2: Pair ¬ src[1]; FOR n: NAT IN [2..src.length) DO p0: Pair ¬ p1; p1 ¬ p2; p2 ¬ src[n]; dst[n-1] ¬ [0.25*(p0.x+p1.x+p1.x+p2.x), 0.25*(p0.y+p1.y+p1.y+p2.y)]; ENDLOOP; }; RETURN[dst]; }; Smooth: PUBLIC PROC [contour: Contour] RETURNS [Contour] ~ { IF contour # NIL AND contour.pairs # NIL AND contour.pairs.length > 2 THEN { nPairs: NAT ¬ contour.pairs.length; start, stop: NAT; p0, p1, p2: Pair; IF contour.closed THEN { start ¬ 0; stop ¬ nPairs-1; p1 ¬ contour.pairs[stop]; } ELSE { start ¬ 1; stop ¬ nPairs-2; p1 ¬ contour.pairs[0]; }; p2 ¬ contour.pairs[start]; FOR n: NAT IN [start..stop] DO p0 ¬ p1; p1 ¬ p2; p2 ¬ contour.pairs[(n+1) MOD nPairs]; contour.pairs[n] ¬ [0.25*(p0.x+p1.x+p1.x+p2.x), 0.25*(p0.y+p1.y+p1.y+p2.y)]; ENDLOOP; }; RETURN[contour]; }; Thin: PUBLIC PROC [contour: Contour, epsilon: REAL ¬ 3.0] RETURNS [Contour] ~ { limit: REAL ¬ ABS[RealFns.Cos[epsilon]]; ret: Contour ¬ Reduce[contour, Thinner]; nPairs0: INTEGER ¬ contour.pairs.length; nPairs1: INTEGER ¬ ret.pairs.length; Thinner: TestProc ~ {RETURN[p0 = p1 OR Dot[p0, p1, p2] > limit]}; WHILE nPairs0 # nPairs1 DO nPairs0 ¬ nPairs1; nPairs1 ¬ (ret ¬ Reduce[ret, Thinner]).pairs.length; ENDLOOP; RETURN[ret]; }; ResampleNats: PUBLIC PROC [src: NatPairSequence, dstnum: NAT, dst: PairSequence ¬ NIL] RETURNS [PairSequence] ~ { totSrcLen: REAL ¬ 0.; IF dstnum = 1 THEN RETURN[NIL]; FOR j: NAT IN [1..src.length) DO totSrcLen ¬ totSrcLen+G2dVector.NatPairDistance[src[j-1], src[j]]; ENDLOOP; { dDstLen: REAL ¬ totSrcLen/(dstnum-1); srcLen0, dstLen: REAL ¬ 0.; j: NAT ¬ 0; IF dst = NIL OR dst.maxLength < dstnum THEN dst ¬ NEW[G2dBasic.PairSequenceRep[dstnum]]; dst.length ¬ dstnum; FOR i: NAT IN [1..src.length) DO srcLen1: REAL ¬ srcLen0+G2dVector.NatPairDistance[src[i-1], src[i]]; WHILE dstLen < srcLen1 DO dst[j] ¬ G2dVector.NatPairLerp[(dstLen-srcLen0)/(srcLen1-srcLen0), src[i-1], src[i]]; j ¬ j+1; dstLen ¬ dstLen+dDstLen; ENDLOOP; srcLen0 ¬ srcLen1; ENDLOOP; dst[dstnum-1] ¬ [src[src.length-1].x, src[src.length-1].y]; }; RETURN[dst]; }; ResamplePairs: PUBLIC PROC [src: PairSequence, dstnum: NAT, dst: PairSequence ¬ NIL] RETURNS [PairSequence] ~ { totSrcLen: REAL ¬ 0.; IF dstnum = 1 THEN RETURN[NIL]; FOR j: NAT IN [1..src.length) DO totSrcLen ¬ totSrcLen+G2dVector.Distance[src[j-1], src[j]]; ENDLOOP; { dDstLen: REAL ¬ totSrcLen/(dstnum-1); srcLen0, dstLen: REAL ¬ 0.; j: NAT ¬ 0; IF dst = NIL OR dst.maxLength < dstnum THEN dst ¬ NEW[G2dBasic.PairSequenceRep[dstnum]]; dst.length ¬ dstnum; FOR i: NAT IN [1..src.length) DO srcLen1: REAL ¬ srcLen0+G2dVector.Distance[src[i-1], src[i]]; WHILE dstLen < srcLen1 DO dst[j] ¬ G2dVector.Interp[(dstLen-srcLen0)/(srcLen1-srcLen0), src[i-1], src[i]]; j ¬ j+1; dstLen ¬ dstLen+dDstLen; ENDLOOP; srcLen0 ¬ srcLen1; ENDLOOP; dst[dstnum-1] ¬ [src[src.length-1].x, src[src.length-1].y]; }; RETURN[dst]; }; Interpolate: PUBLIC PROC [contour0, contour1: Contour, alpha: REAL] RETURNS [Contour] ~ { IF contour1 = NIL THEN RETURN[contour0]; IF contour0 = NIL THEN RETURN[contour1]; IF alpha = 0.0 THEN RETURN[contour0]; IF alpha = 1.0 THEN RETURN[contour1]; IF contour0.pairs.length < 3 OR contour1.pairs.length < 3 THEN RETURN[NIL] ELSE { nPairs0: NAT ¬ contour0.pairs.length; nPairs1: NAT ¬ contour1.pairs.length; contour: Contour ¬ NEW[ContourRep]; contour.t ¬ contour0.t+alpha*(contour1.t-contour0.t); contour.closed ¬ contour0.closed AND contour1.closed; contour.circle ¬ contour0.circle AND contour1.circle; IF contour.circle THEN { nPairs: INTEGER ¬ Real.Round[nPairs0+alpha*(nPairs1-nPairs0)]; contour.pairs ¬ contour.normals ¬ CirclePairs[nPairs]; contour.pairs.length ¬ contour.pairs.maxLength; } ELSE { n0, n1, nPairs: NAT ¬ 0; pcs, pcs0, pcs1: RealSequence ¬ NIL; IF contour0.percents = NIL THEN contour0.percents ¬ Percents[contour0]; IF contour1.percents = NIL THEN contour1.percents ¬ Percents[contour1]; pcs ¬ contour.percents ¬ NEW[RealSequenceRep[nPairs0+nPairs1]]; pcs0 ¬ contour0.percents; pcs1 ¬ contour1.percents; DO IF n0 = nPairs0 THEN { FOR n: NAT IN [n1..nPairs1) DO pcs[nPairs] ¬ pcs1[n]; nPairs ¬ nPairs+1; ENDLOOP; EXIT; }; IF n1 = nPairs1 THEN { FOR n: NAT IN [n0..nPairs0) DO pcs[nPairs] ¬ pcs0[n]; nPairs ¬ nPairs+1; ENDLOOP; EXIT; }; SELECT TRUE FROM pcs0[n0] < pcs1[n1] => {pcs[nPairs] ¬ pcs0[n0]; n0 ¬ n0+1}; pcs0[n0] > pcs1[n1] => {pcs[nPairs] ¬ pcs1[n1]; n1 ¬ n1+1}; ENDCASE => {pcs[nPairs] ¬ pcs0[n0]; n0 ¬ n0+1; n1 ¬ n1+1}; nPairs ¬ nPairs+1; ENDLOOP; contour.pairs ¬ NEW[PairSequenceRep[nPairs]]; contour.pairs.length ¬ contour.percents.length ¬ nPairs; FOR n: NAT IN [0..nPairs) DO p0: Pair ¬ PercentPair[contour0, pcs[n]]; p1: Pair ¬ PercentPair[contour1, pcs[n]]; contour.pairs[n] ¬ [p0.x+alpha*(p1.x-p0.x), p0.y+alpha*(p1.y-p0.y)]; ENDLOOP; [] ¬ Thin[contour]; }; RETURN[contour]; }; }; Sample: PUBLIC PROC [contour: Contour, nPairs: INTEGER] RETURNS [Contour] ~ { new: Contour ¬ NEW[ContourRep ¬ contour­]; IF ContourOK[contour] THEN { IF contour.percents = NIL THEN contour.percents ¬ Percents[contour]; new.pairs ¬ NEW[PairSequenceRep[nPairs]]; new.pairs.length ¬ nPairs; FOR n: NAT IN [0..nPairs) DO fraction: REAL ¬ REAL[n]/REAL[nPairs]; nContour: INTEGER ¬ Real.Round[fraction]; alpha: REAL ¬ fraction-nContour; percent0: REAL ¬ contour.percents[nContour]; percent1: REAL ¬ contour.percents[(nContour+1) MOD contour.pairs.length]; new.pairs[n] ¬ PercentPair[contour, percent0+alpha*(percent1-percent0)]; ENDLOOP; }; RETURN[new]; }; Similar: PUBLIC PROC [contour0, contour1: Contour] RETURNS [REAL] ~ { IF NOT ContourOK[contour0] OR NOT ContourOK[contour1] THEN RETURN[1.0]; IF contour0.pairs.length > contour1.pairs.length THEN {c: Contour ¬ contour0; contour0 ¬ contour1; contour1 ¬ c}; IF contour0.circle AND contour1.circle THEN RETURN[ 1.0-REAL[contour1.pairs.length-contour0.pairs.length]/REAL[contour1.pairs.length]] ELSE { min: REAL ¬ 1000.0; IF contour0.pairs.length > contour1.pairs.length THEN {c: Contour ¬ contour0; contour0 ¬ contour1; contour1 ¬ c}; CheckPercentsAndNormals[contour0]; CheckPercentsAndNormals[contour1]; FOR n: NAT IN [0..contour0.pairs.length) DO n0: Pair ¬ contour0.normals[n]; n1: Pair ¬ PercentNormal[contour1, contour0.percents[n] ! NullNormal => GOTO bad]; IF n0 # [0.0, 0.0] AND n1 # [0.0, 0.0] THEN min ¬ MIN[min, Vector2.Dot[n0, n1]]; REPEAT bad => NULL; ENDLOOP; RETURN[0.5*(min+1.0)]; }; }; InsideContour: PUBLIC PROC [p: Pair, pairs: PairSequence] RETURNS [Border] ~ { zcross: REAL; odd: BOOL ¬ FALSE; d2: Pair ¬ [pairs[pairs.length-1].x-p.x, pairs[pairs.length-1].y-p.y]; FOR n: NAT IN [0..pairs.length) DO d1: Pair ¬ d2; d2 ¬ [pairs[n].x-p.x, pairs[n].y-p.y]; IF (d1.y > 0 AND d2.y > 0) OR (d1.y < 0 AND d2.y < 0) OR (d1.x < 0 AND d2.x < 0) THEN LOOP; -- no chance to cross IF (zcross ¬ d2.y*d1.x-d1.y*d2.x) = 0.0 THEN RETURN[edge]; IF (d1.y > 0 OR d2.y > 0) AND (zcross < 0) # (d1.y-d2.y < 0) THEN odd ¬ NOT odd; ENDLOOP; RETURN[IF odd THEN inside ELSE outside]; }; CirclePairs: PUBLIC PROC [nPairs: INTEGER] RETURNS [PairSequence] ~ { RETURN[G2dBasic.CopyPairSequence[IF nPairs <= 0 THEN NIL ELSE IF nPairs > nCircles THEN NewCircle[nPairs] ELSE IF circles[nPairs] = NIL THEN (circles[nPairs] ¬ NewCircle[nPairs]) ELSE circles[nPairs] ]]; }; Circle: PUBLIC PROC [nPairs: INTEGER] RETURNS [Contour] ~ { IF nPairs <= 0 THEN RETURN[NIL] ELSE { contour: Contour ¬ NEW[ContourRep]; contour.closed ¬ contour.circle ¬ TRUE; contour.pairs ¬ contour.normals ¬ CirclePairs[nPairs]; RETURN[contour]; }; }; Normals: PUBLIC PROC [contour: Contour] RETURNS [PairSequence] ~ { SELECT TRUE FROM NOT ContourOK[contour] OR contour.pairs.length < 2 => RETURN[NIL]; contour.circle => RETURN[G2dBasic.CopyPairSequence[contour.pairs]]; ENDCASE => { MakeNormal3: PROC [p0, p1, p2: Pair] RETURNS [Pair] ~ { v: Pair ¬ Vector2.Add[MakeNormal2[p0, p1], MakeNormal2[p1, p2]]; m: REAL ~ RealFns.SqRt[v.x*v.x+v.y*v.y]; RETURN[IF m # 0.0 THEN [v.x/m, v.y/m] ELSE [0.0, 0.0]]; }; MakeNormal2: PROC [p0, p1: Pair] RETURNS [Pair] ~ { v: Pair ¬ Vector2.Sub[p1, p0]; m: REAL ~ RealFns.SqRt[v.x*v.x+v.y*v.y]; RETURN[IF m # 0.0 THEN [-v.y/m, v.x/m] ELSE [0.0, 0.0]]; }; nPairs: INTEGER ¬ contour.pairs.length; normals: PairSequence ¬ NEW[PairSequenceRep[nPairs]]; normals.length ¬ nPairs; FOR n: INT IN [0..nPairs) DO p: Pair ¬ contour.pairs[n]; SELECT n FROM 0 => normals[n] ¬ IF contour.closed THEN MakeNormal3[contour.pairs[nPairs-1], p, contour.pairs[n+1]] ELSE MakeNormal2[p, contour.pairs[n+1]]; nPairs-1 => normals[n] ¬ IF contour.closed THEN MakeNormal3[contour.pairs[n-1], p, contour.pairs[0]] ELSE MakeNormal2[contour.pairs[n-1], p]; ENDCASE => normals[n] ¬ MakeNormal3[contour.pairs[n-1], contour.pairs[n], contour.pairs[n+1]]; ENDLOOP; RETURN[normals]; }; }; Percents: PUBLIC PROC [contour: Contour] RETURNS [RealSequence] ~ { percents: RealSequence ¬ NIL; IF contour # NIL AND contour.pairs # NIL THEN { pairs: PairSequence ¬ contour.pairs; percents ¬ NEW[RealSequenceRep[pairs.length]]; percents.length ¬ pairs.length; percents[0] ¬ 0.0; IF contour.circle THEN { FOR n: NAT IN [1..pairs.length) DO percents[n] ¬ REAL[n]/REAL[pairs.length]; ENDLOOP; } ELSE { total: REAL; FOR n: NAT IN [1..pairs.length) DO percents[n] ¬ percents[n-1]+Vector2.Length[Vector2.Sub[pairs[n-1], pairs[n]]]; ENDLOOP; total ¬ percents[pairs.length-1]; IF contour.closed THEN total ¬ total+Vector2.Length[Vector2.Sub[pairs[pairs.length-1], pairs[0]]]; FOR n: NAT IN [1..pairs.length) DO percents[n] ¬ percents[n]/total; ENDLOOP; }; }; RETURN[percents]; }; AtPercent: PUBLIC PROC [contour: Contour, percent: REAL] RETURNS [RealIndex] ~ { IF NOT ContourOK[contour] THEN RETURN[[0, 0.0]] ELSE { pcs: RealSequence ¬ contour.percents; nPairs: INTEGER ¬ contour.pairs.length; IF pcs = NIL THEN pcs ¬ contour.percents ¬ Percents[contour]; FOR n: NAT IN [0..nPairs) DO SELECT TRUE FROM pcs[n] = percent => RETURN[[n, 0.0]]; pcs[n] > percent => RETURN[[n-1, (percent-pcs[n-1])/(pcs[n]-pcs[n-1])]]; ENDCASE; ENDLOOP; RETURN[[nPairs-1, (percent-pcs[nPairs-1])/(1.0-pcs[nPairs-1])]]; }; }; PercentPair: PUBLIC PROC [contour: Contour, percent: REAL] RETURNS [Pair] ~ { IF NOT ContourOK[contour] THEN RETURN[[0.0, 0.0]] ELSE RETURN[PercentOfPairSequence[contour.pairs, AtPercent[contour, percent]]]; }; NullNormal: ERROR = CODE; PercentNormal: PUBLIC PROC [contour: Contour, percent: REAL] RETURNS [Pair] ~ { IF NOT ContourOK[contour] THEN RETURN[[0.0, 0.0]] ELSE { n: Pair ¬ PercentOfPairSequence[contour.normals, AtPercent[contour, percent]]; m: REAL ~ RealFns.SqRt[n.x*n.x+n.y*n.y]; IF m = 0.0 THEN ERROR NullNormal; RETURN[[n.x/m, n.y/m]]; }; }; Spans: PUBLIC PROC [contour: Contour, rectangle: Rectangle] RETURNS [SpanSequence] ~ { spans: SpanSequence ¬ NIL; IF contour # NIL AND contour.pairs # NIL AND contour.closed THEN { MinY: PROC RETURNS [y: NAT ¬ LAST[NAT]] ~ { FOR i: NAT IN [0..nIntegerPairs) DO y ¬ MIN[integerPairs[i].y, y]; ENDLOOP; }; MaxY:PROC RETURNS [y: NAT ¬ 0] ~ { FOR i: NAT IN [0..nIntegerPairs) DO y ¬ MAX[integerPairs[i].y, y]; ENDLOOP; }; PixelProc: Draw2d.PixelProc ~ { IF skip THEN skip ¬ FALSE ELSE { new: NatList ¬ NEW[NatListRep ¬ [n: x]]; yList: NatList ¬ yLists[y-yMin]; IF yList = NIL OR yList.n > x THEN {new.next ¬ yList; yLists[y-yMin] ¬ new} ELSE { WHILE yList.next # NIL AND yList.next.n < x DO yList ¬ yList.next; ENDLOOP; new.next ¬ yList.next; yList.next ¬ new; }; count ¬ count+1; }; }; count: NAT ¬ 0; integerPairs: IntegerPairSequence ¬ FitToRectangle[contour.pairs, rectangle]; nIntegerPairs: NAT ¬ contour.pairs.length; s0: IntegerPair ¬ integerPairs[nIntegerPairs-1]; yMin: NAT ¬ MinY[]; yListLength: NAT ¬ MaxY[]-yMin+1; yLists: NatListSequence ¬ NEW[NatListSequenceRep[yListLength]]; up0: BOOL ¬ s0.y < integerPairs[0].y; skip: BOOL; FOR n: NAT IN [0..nIntegerPairs) DO s1: IntegerPair ¬ integerPairs[n]; up1: BOOL ¬ s0.y < s1.y; skip ¬ up0 = up1; Draw2d.DoWithLine[[s0.x, s0.y], [s1.x, s1.y], PixelProc]; s0 ¬ s1; up0 ¬ up1; ENDLOOP; FOR n: NAT IN [0..yListLength) DO seg0a, seg0b, seg1a, seg1b: NatList; IF (seg0a ¬ yLists[n]) = NIL THEN LOOP; IF (seg0b ¬ seg0a.next) = NIL THEN LOOP; DO IF (seg1a ¬ seg0b.next) = NIL THEN EXIT; IF (seg1b ¬ seg1a.next) = NIL THEN EXIT; IF seg0b.n = seg1a.n THEN seg0a.next ¬ seg1b ELSE seg0a ¬ seg1a; seg0b ¬ seg1b; ENDLOOP; ENDLOOP; spans ¬ NEW[SpanSequenceRep[count]]; FOR n: NAT IN [0..yListLength) DO yList: NatList ¬ yLists[n]; WHILE yList # NIL AND yList.next # NIL DO spans[spans.length].y ¬ yMin+n; spans[spans.length].x0 ¬ yList.n; yList ¬ yList.next; spans[spans.length].x1 ¬ yList.n; yList ¬ yList.next; spans.length ¬ spans.length+1; ENDLOOP; ENDLOOP; }; RETURN[spans]; }; PutBWLine: PROC [map: SampleMap, x0, y0, x1, y1: INTEGER, value: CARDINAL] ~ { PerPixel: Draw2d.PixelProc~{ ImagerSample.Put[map, [y, x], value ! RuntimeError.BoundsFault => CONTINUE]; }; Draw2d.DoWithLine[[x0, y0], [x1, y1], PerPixel]; }; FillSpans: PUBLIC PROC [map: SampleMap, spans: SpanSequence, color: CARDINAL] ~ { IF spans # NIL THEN FOR n: NAT IN [0..spans.length) DO span: Span ¬ spans[n]; PutBWLine[map, span.x0, span.y, span.x1, span.y, color]; ENDLOOP; }; Fill: PUBLIC PROC [context: Context, contour: Contour, color: Color ¬ Imager.black] ~ { path: Imager.PathProc ~ {Path[context, contour, moveTo, lineTo]}; Imager.SetColor[context, color]; IF ContourOK[contour] THEN Imager.MaskFill[context, path]; }; Outline: PUBLIC PROC [context: Context, contour: Contour, color: Color ¬ Imager.black] ~ { path: Imager.PathProc ~ {Path[context, contour, moveTo, lineTo]}; Imager.SetColor[context, color]; IF ContourOK[contour] THEN Imager.MaskStroke[context, path]; }; OutlineMap: PUBLIC PROC [map: SampleMap, contour: Contour, color: CARDINAL] ~ { IF contour # NIL AND contour.pairs # NIL THEN { integerPairs: IntegerPairSequence ¬ FitToRectangle[contour.pairs, RectangleFromSampleMap[map]]; s0, s1, start: IntegerPair ¬ integerPairs[0]; FOR n: NAT IN [1..contour.pairs.length) DO s1 ¬ integerPairs[n]; PutBWLine[map, s0.x, s0.y, s1.x, s1.y, color]; s0 ¬ s1; ENDLOOP; IF contour.closed THEN PutBWLine[map, s0.x, s0.y, start.x, start.y, color]; }; }; FillMap: PUBLIC PROC [map: SampleMap, contour: Contour, color: CARDINAL] ~ { FillSpans[map, Spans[contour, RectangleFromSampleMap[map]], color]; }; Copy: PUBLIC PROC [contour: Contour] RETURNS [Contour] ~ { copy: Contour ¬ NIL; IF contour # NIL THEN { copy ¬ NEW[ContourRep ¬ contour­]; copy.pairs ¬ G2dBasic.CopyPairSequence[contour.pairs]; IF copy.circle THEN copy.normals ¬ copy.pairs; }; RETURN[copy]; }; CopySequence: PUBLIC PROC [contour: ContourSequence] RETURNS [ContourSequence] ~ { copy: ContourSequence ¬ NIL; IF contour # NIL THEN { copy ¬ NEW[ContourSequenceRep[contour.length]]; copy.length ¬ contour.length; FOR n: NAT IN [0..contour.length) DO copy[n] ¬ Copy[contour[n]]; ENDLOOP; }; RETURN[copy]; }; Paint: PUBLIC PROC [contour: Contour, context: Context, paintNormals: BOOL ¬ FALSE] ~ { Action: PROC ~ { IF ContourOK[contour] THEN { pairs: PairSequence ¬ contour.pairs; normals: PairSequence ¬ contour.normals; p0, p1: Pair ¬ --Xform[--pairs[0]--]--; Draw2d.Clear[context]; FOR n: NAT IN [1..pairs.length) DO p1 ¬ --Xform[--pairs[n]--]--; Draw2d.Line[context, p0, p1]; p0 ¬ p1; ENDLOOP; IF contour.closed THEN Draw2d.Line[context, p1, --Xform[--pairs[0]--]--]; IF paintNormals AND normals # NIL THEN FOR n: NAT IN [0..pairs.length) DO p: Pair ¬ --Xform[--pairs[n]--]--; Draw2d.Arrow[context, p, Vector2.Add[p, Vector2.Mul[normals[n], 30.0]]]; ENDLOOP; }; }; bounds: Imager.Rectangle ¬ ImagerBackdoor.GetBounds[context]; Draw2d.DoWithBuffer[context, Action, FALSE]; }; Write: PUBLIC PROC [stream: STREAM, contour: Contour] ~ { IO.PutRope[stream, IF contour.closed THEN "closed\n" ELSE "open\n"]; IO.PutRope[stream, IF contour.circle THEN "circle\n" ELSE "notcircle\n"]; IO.PutF1[stream, "%g\n", IO.real[contour.t]]; IO.PutF1[stream, "%g\n", IO.int[contour.pairs.length]]; FOR n: NAT IN [0..contour.pairs.length) DO IO.PutF[stream, "%g\t%g\n", IO.real[contour.pairs[n].x], IO.real[contour.pairs[n].y]]; ENDLOOP; IO.Close[stream]; }; Read: PUBLIC PROC [stream: STREAM] RETURNS [contour: Contour] ~ { GetFirstWord: PROC RETURNS [word: ROPE] ~ { line: ROPE ¬ IO.GetLineRope[stream]; pos0: INTEGER ¬ Rope.SkipOver[line, 0, " \t"]; word ¬ Rope.Substr[line, pos0, Rope.SkipTo[line, pos0, " \t"]-pos0]; }; contour: Contour ¬ NIL; IF stream # NIL THEN { ENABLE Convert.Error => GOTO Bad; contour ¬ NEW[ContourRep]; contour.closed ¬ Rope.Equal[GetFirstWord[], "closed"]; contour.circle ¬ Rope.Equal[GetFirstWord[], "circle"]; contour.t ¬ Convert.RealFromRope[GetFirstWord[]]; contour.pairs ¬ NEW[PairSequenceRep[Convert.IntFromRope[GetFirstWord[]]]]; contour.pairs.length ¬ contour.pairs.maxLength; FOR n: NAT IN[0..contour.pairs.length) DO line: ROPE ¬ IO.GetLineRope[stream]; pos0: INTEGER ¬ Rope.SkipOver[line, 0, " \t"]; pos1: INTEGER ¬ Rope.SkipTo[line, pos0, " \t"]; pos2: INTEGER ¬ Rope.SkipOver[line, pos1, " \t"]; pos3: INTEGER ¬ Rope.SkipTo[line, pos2, " \t"]; contour.pairs[n].x ¬ Convert.RealFromRope[Rope.Substr[line, pos0, pos1-pos0]]; contour.pairs[n].y ¬ Convert.RealFromRope[Rope.Substr[line, pos2, pos3-pos2]]; ENDLOOP; IO.Close[stream]; }; EXITS Bad => NULL; }; RectangleFromSampleMap: PROC [map: SampleMap] RETURNS [Rectangle] ~ { b: ImagerSample.Box ¬ ImagerSample.GetBox[map]; RETURN[[b.min.f, b.min.s, b.max.f-b.min.f, b.max.s-b.min.s]]; }; Reduce: PROC [contour: Contour, testProc: TestProc] RETURNS [Contour] ~ { IF NOT ContourOK[contour] OR contour.pairs.length < 3 THEN RETURN[contour] ELSE { n: CARDINAL ¬ 0; noMore: ERROR = CODE; Store: PROC [p: Pair] ~ { new.pairs[new.pairs.length] ¬ p; new.pairs.length ¬ new.pairs.length+1; }; NewPair: PROC RETURNS [Pair] ~ { IF (n ¬ n+1) > contour.pairs.length THEN ERROR noMore; RETURN[contour.pairs[n-1]]; }; new: Contour ¬ NEW[ContourRep ¬ contour­]; p0: Pair ¬ NewPair[]; p1: Pair ¬ NewPair[]; p2: Pair ¬ NewPair[]; new.pairs ¬ NEW[PairSequenceRep[contour.pairs.length]]; DO Store[p0]; IF testProc[p0, p1, p2] THEN { p0 ¬ p2; p1 ¬ NewPair[! noMore => {Store[p0]; EXIT}]; p2 ¬ NewPair[! noMore => {Store[p0]; Store[p1]; EXIT}]; } ELSE { p0 ¬ p1; p1 ¬ p2; p2 ¬ NewPair[! noMore => {Store[p0]; Store[p1]; EXIT}]; }; ENDLOOP; RETURN[new]; }; }; Dot: PROC [p0, p1, p2: Pair] RETURNS [REAL] ~ { RETURN[IF p0 = p1 OR p1 = p2 THEN 0.0 ELSE ABS[Vector2.Dot[ Vector2.Unit[Vector2.Sub[p1, p0]], Vector2.Unit[Vector2.Sub[p2, p1]]]]]; }; ConvertingValues: PROC [rectangle: Rectangle] RETURNS [scale, xOffset, yOffset: REAL] ~ { scale ¬ (MIN[rectangle.w, rectangle.h]-1)/2.0; xOffset ¬ rectangle.x+scale-1.0; yOffset ¬ rectangle.y+scale-1.0; }; FitToRectangle: PROC [pairs: PairSequence, rectangle: Rectangle] RETURNS [i: IntegerPairSequence] ~ { IF pairs # NIL THEN { scale, xOffset, yOffset: REAL; [scale, xOffset, yOffset] ¬ ConvertingValues[rectangle]; i ¬ NEW[IntegerPairSequenceRep[pairs.length]]; FOR n: NAT IN [0..i.length) DO i[n] ¬ [Real.Round[xOffset+scale*pairs[n].x], Real.Round[yOffset-scale*pairs[n].y]]; ENDLOOP; }; }; Path: PROC [ context: Context, contour: Contour, moveTo: ImagerPath.MoveToProc, lineTo: ImagerPath.LineToProc] ~ { IF contour # NIL AND contour.pairs # NIL THEN { start: Pair; scale, xOffset, yOffset: REAL; [scale, xOffset, yOffset] ¬ ConvertingValues[ImagerBackdoor.GetBounds[context]]; moveTo[start ¬ [xOffset+scale*contour.pairs[0].x, yOffset+scale*contour.pairs[0].y]]; FOR n: NAT IN [1..contour.pairs.length) DO lineTo[[xOffset+scale*contour.pairs[n].x, yOffset+scale*contour.pairs[n].y]]; ENDLOOP; IF contour.closed THEN lineTo[start]; }; }; CheckPercentsAndNormals: PROC [contour: Contour] ~ { IF NOT ContourOK[contour] THEN RETURN; IF contour.normals = NIL THEN contour.normals ¬ Normals[contour]; IF contour.percents = NIL THEN contour.percents ¬ Percents[contour]; }; PercentOfPairSequence: PROC [pairs: PairSequence, index: RealIndex] RETURNS [Pair] ~ { IF index.alpha = 0.0 THEN RETURN[pairs[index.n]] ELSE { p0: Pair ¬ pairs[index.n]; p1: Pair ¬ pairs[(index.n+1) MOD pairs.length]; RETURN[[p0.x+index.alpha*(p1.x-p0.x), p0.y+index.alpha*(p1.y-p0.y)]]; }; }; nCircles: INTEGER ~ 40; circles: ARRAY [1..nCircles] OF PairSequence ¬ ALL[NIL]; NewCircle: PROC [nPairs: INTEGER] RETURNS [PairSequence] ~ { rad: REAL ¬ 0.0; drad: REAL ¬ 2.0*3.1415926535/REAL[nPairs]; circle: PairSequence ¬ NEW[PairSequenceRep[nPairs]]; circle.length ¬ nPairs; FOR i: NAT IN[0..circle.length ¬ nPairs) DO circle[i] ¬ [RealFns.Cos[rad], RealFns.Sin[rad]]; rad ¬ rad-drad; -- clockwise ENDLOOP; RETURN[circle]; }; END. x G2dContourImpl.mesa Copyright Σ 1985, 1988, 1992 by Xerox Corporation. All rights reserved. Bloomenthal, July 2, 1992 5:13 pm PDT Errors Types Contour Creation General Operations Positive shift is to the left, negative to the right: Attributes Smoothing and Thinning Interpolation/Resampling/Comparing Resample src curve to have dstnum (approx) equally spaced points; nats in, reals out copy last point; sometimes roundoff will cause it to be copied above as well Resample src curve to have dstnum (approx) equally spaced points; reals in, reals out copy last point; sometimes roundoff will cause it to be copied above as well Inside/Outside Test Based on code from Pat Hanrahan: InsideContour: PUBLIC PROC [p: Pair, pairs: PairSequence] RETURNS [Border] ~ { Based on code from Pat Hanrahan: odd: BOOL _ FALSE; dx1, dy1, zcross: REAL; dx2: REAL _ pairs[pairs.length-1].x-p.x; dy2: REAL _ pairs[pairs.length-1].y-p.y; FOR n: NAT IN [0..pairs.length) DO dx1 _ dx2; dy1 _ dy2; dx2 _ pairs[n].x-p.x; dy2 _ pairs[n].y-p.y; IF (dy1>0 AND dy2>0) OR (dy1<0 AND dy2<0) OR (dx1<0 AND dx2<0) THEN LOOP; -- no chance to cross zcross _ dy2*dx1-dy1*dx2; IF zcross = 0.0 THEN RETURN[edge]; IF (dy1>0 OR dy2>0) AND (zcross<0) # (dy1-dy2<0) THEN odd _ NOT odd; ENDLOOP; RETURN[IF odd THEN inside ELSE outside]; }; Circles Normals Percents Spans This doesn't work now: need to cull out internal, duplicate horizontal pixels. Filling/Outlining Copying Painting Xform: PROC [p: Pair] RETURNS [Pair] ~ {RETURN[[bounds.w*p.x, bounds.h*p.y]]}; wScale: REAL _ 0.5*(bounds.w-1.0); hScale: REAL _ 0.5*(bounds.h-1.0); IO Support Assumes circular PairSequence: Κ!H–"cedarcode" style•NewlineDelimiter ™šœ™Jšœ Οeœ=™HJ™%—J˜JšΟk œežœ-˜J˜šΠblœžœž˜JšžœMžœ,˜‚Jšžœ ˜—J˜šœž˜Jšžœ ˜—headšΟl™Jš Οnœžœžœžœ žœžœ˜;—š ™š œ ž œžœžœžœ˜J˜6J˜/J˜—šžœ˜Jšœžœ˜Jšœ žœ˜$Jšžœžœžœ(˜GJšžœžœžœ(˜GJšœžœ#˜?J˜J˜šž˜šžœžœ˜šžœžœžœž˜J˜J˜Jšžœ˜—Jšžœ˜J˜—šžœžœ˜šžœžœžœž˜Jšœž˜J˜Jšžœ˜—Jšžœ˜J˜—šžœžœž˜J˜;J˜;Jšžœ3˜:—J˜Jšžœ˜—Jšœžœ˜-J˜8šžœžœžœ ž˜J˜)J˜)J˜DJšžœ˜—J˜J˜—Jšžœ ˜—J˜——J˜J˜—š ‘œžœžœžœžœ˜MJšœžœ˜*šžœžœ˜Jšžœžœžœ&˜DJšœ žœ˜)J˜šžœžœžœ ž˜Jšœ žœžœžœ ˜&Jšœ žœ˜)Jšœžœ˜ Jšœ žœ˜,Jšœ žœ!žœ˜IJ˜HJšžœ˜—J˜—Jšžœ˜ J˜J˜—š ‘œžœžœžœžœ˜EJš žœžœžœžœžœžœ˜Gšžœ.˜0Jšžœ<˜@—šžœžœ˜&šžœžœ˜ Jšœžœ.žœ˜R—šžœ˜Jšœžœ ˜šžœ.˜0Jšžœ<˜@—Jšœ"˜"J˜"šžœžœžœž˜+J˜JšœHžœ˜RJšžœžœžœžœ˜Pšž˜Jšœžœ˜ —Jšžœ˜—Jšžœ˜J˜——J˜——š ™š‘ œž œ žœ ˜NJ™ Jšœžœ˜ Jšœžœžœ˜J˜Fšžœžœžœž˜"J˜J˜&š žœ žœ žœ žœ žœ žœ ˜PJšžœžœΟc˜!—Jšžœ&žœžœ˜:Jš žœ žœ žœ žœžœ˜PJšžœ˜—Jšžœžœžœžœ ˜(J˜J˜—š‘ œž œ žœ ™NJ™ Jšœžœžœ™Jšœžœ™Jšœžœ™(Jšœžœ™(šžœžœžœž™"J™ J™ J™J™šžœžœž™Jšœžœž™Jšœžœžœžœ’™3—J™Jšžœžœžœ ™$Jš žœžœžœžœžœ™DJšžœ™—Jšžœžœžœžœ ™(J™——š ™š‘ œž œ žœžœ˜Ešžœžœ ˜/Jšžœž˜šžœžœ˜šžœ˜šžœžœž˜Jšžœ&˜*Jšžœ˜——J˜——J˜J˜—š ‘œžœžœ žœžœ˜;šžœ ˜Jšžœžœžœ˜šžœ˜Jšœžœ ˜#Jšœ"žœ˜'J˜6Jšžœ ˜J˜——J˜——š ™š‘œžœžœžœ˜Bšžœžœž˜Jšžœžœžœžœ˜BJšœžœ+˜Cšžœ˜ š‘ œžœžœ ˜7J˜@Jšœžœ!˜(Jšžœžœ žœžœ ˜7J˜—š‘ œžœžœ ˜3J˜Jšœžœ!˜(Jšžœžœ žœžœ ˜8J˜—Jšœžœ˜'Jšœžœ˜5J˜šžœžœžœ ž˜J˜šžœž˜ šœžœ˜#Jšžœ<˜@Jšžœ$˜(—šœžœ˜*Jšžœ5˜9Jšžœ$˜(—šžœ˜JšœF˜F——Jšžœ˜—Jšžœ ˜J˜——J˜——š  ™ š‘œžœžœžœ˜CJšœžœ˜š žœ žœžœžœžœ˜/J˜$Jšœ žœ ˜.J˜J˜šžœ˜šžœ˜šžœžœžœž˜"Jšœžœžœ˜)Jšžœ˜J˜——šžœ˜Jšœžœ˜ šžœžœžœž˜"J˜NJšžœ˜—J˜!šžœ˜JšžœM˜Q—šžœžœžœž˜"J˜ Jšžœ˜—Jšœ˜——J˜Jšžœ ˜—J˜J˜—š ‘ œžœžœžœžœ˜Pšžœžœ˜Jšžœžœ ˜šžœ˜J˜%Jšœžœ˜'Jšžœžœžœ,˜=J˜šžœžœžœ ž˜šžœžœž˜Jšœžœ ˜%Jšœžœ.˜HJšžœ˜—Jšžœ˜—Jšžœ:˜@J˜——J˜J˜—š‘ œž œžœžœ ˜Mšžœžœ˜Jšžœžœ ˜JšžœžœD˜O—J˜J˜—š‘ œžœžœ˜J˜—š‘ œž œžœžœ ˜Ošžœžœ˜Jšžœžœ ˜šžœ˜J˜NJšœžœ!˜(Jšžœ žœžœ ˜!Jšžœ˜J˜——J˜——š ™š‘œžœžœ*žœ˜VJšœžœ˜š žœ žœžœžœžœžœ˜Bš ‘œžœžœžœžœžœ˜+Jš žœžœžœžœžœžœ˜KJšœ˜—š‘œžœžœžœ ˜"Jš žœžœžœžœžœžœ˜KJšœ˜—šΟb œ˜J™Nšžœ˜Jšžœž˜šžœ˜Jšœžœ˜(J˜ Jšžœ žœžœ žœ)˜Kšžœ˜Jš žœžœžœžœžœ˜KJ˜J˜J˜—J˜J˜——J˜—Jšœžœ˜J˜MJšœžœ˜*J˜0Jšœžœ ˜Jšœ žœ˜!Jšœžœ"˜?Jšœžœ˜%Jšœžœ˜ šžœžœžœž˜#J˜"Jšœžœ˜J˜J˜9J˜J˜ Jšžœ˜—šžœžœžœž˜!J˜$Jšžœžœžœžœ˜'Jšžœžœžœžœ˜(šž˜Jšžœžœžœžœ˜(Jšžœžœžœžœ˜(šžœ˜Jšžœ˜Jšžœ˜—J˜Jšžœ˜—Jšžœ˜—Jšœžœ˜$šžœžœžœž˜!J˜š žœ žœžœžœž˜)J˜J˜!J˜J˜!J˜J˜Jšžœ˜—Jšžœ˜—J˜—Jšžœ˜J˜J˜—š‘ œžœ"žœ žœ˜Nš‘œ˜JšœAž œ˜LJšœ˜—J˜0J˜J˜—š‘ œžœžœ.žœ˜Qšžœ žœžœžœžœžœžœ˜7J˜Jšœ8˜8Jšžœ˜—J˜——š ™š‘œžœžœF˜WJ˜AJ˜ Jšžœžœ ˜:J˜J˜—š‘œžœžœF˜ZJ˜AJ˜ Jšžœžœ"˜