DIRECTORY
ImagerManhattan USING [Polygon, Visibility],
SF USING [Box, BoxAction, BoxGenerator, Vec],
SFInline USING [Add, Empty, Intersect, Nonempty];
ImagerManhattanImpl: CEDAR MONITOR
IMPORTS SFInline
EXPORTS ImagerManhattan
~ BEGIN

Polygon: TYPE ~ ImagerManhattan.Polygon;
Visibility: TYPE ~ ImagerManhattan.Visibility;
InvalidManhattanPolygon: PUBLIC ERROR ~ CODE;

Validate: PUBLIC PROC [polygon: Polygon] RETURNS [Polygon] ~ {
IF polygon # NIL THEN {
a: Polygon ¬ polygon;
amins: INTEGER ¬ a.first.min.s;
aminf: INTEGER ¬ a.first.min.f;
amaxs: INTEGER ¬ a.first.max.s;
amaxf: INTEGER ¬ a.first.max.f;
DO
b: Polygon = a.rest;
IF amins >= amaxs OR aminf >= amaxf THEN ERROR InvalidManhattanPolygon;
IF b = NIL THEN EXIT ELSE {
bmins: INTEGER = b.first.min.s;
bminf: INTEGER = b.first.min.f;
bmaxs: INTEGER = b.first.max.s;
bmaxf: INTEGER = b.first.max.f;
SELECT TRUE FROM
amaxs <= bmins => {};
(amins = bmins AND amaxs = bmaxs AND amaxf <= bminf) => {};
ENDCASE => ERROR InvalidManhattanPolygon;
a ¬ b;
amins ¬ bmins;
aminf ¬ bminf;
amaxs ¬ bmaxs;
amaxf ¬ bmaxf;
};
ENDLOOP;
};
RETURN [polygon]
};

CreateFromRuns: PUBLIC PROC [
runs: PROC[run: PROC[sMin, fMin: INTEGER, fSize: NAT],
repeat: PROC[timesToRepeatScanline: NAT]]]
RETURNS [polygon: Polygon] ~ {
scratch: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ scratch;
secondLastRowStart: LIST OF SF.Box ¬ NIL;
lastRowStart: LIST OF SF.Box ¬ last;
secondLastRowCount: INTEGER ¬ -1;
lastRowCount: INTEGER ¬ 0;
Run: PROC[sMin, fMin: INTEGER, fSize: NAT] ~ {
fMaxCurrent: INTEGER ~ last.first.max.f;
IF lastRowCount > 0 AND sMin = last.first.min.s
THEN {
IF last.first.max.s-last.first.min.s # 1 THEN ERROR;
SELECT fMin FROM
= fMaxCurrent => {last.first.max.f ¬ last.first.max.f + fSize};
> fMaxCurrent => {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
last.first ¬ [min: [s: sMin, f: fMin], max: [s: sMin+1, f: fMin+fSize]];
lastRowCount ¬ lastRowCount + 1;
};
ENDCASE => ERROR;
}
ELSE {
IF secondLastRowCount = lastRowCount AND secondLastRowStart.first.max.s = lastRowStart.first.min.s AND TryToMergeRows[secondLastRowStart, lastRowCount]
THEN {
last ¬ lastRowStart;
lastRowStart ¬ secondLastRowStart;
secondLastRowCount ¬ -1;
}
ELSE {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
};
secondLastRowStart ¬ lastRowStart;
secondLastRowCount ¬ lastRowCount;
last.first ¬ [min: [s: sMin, f: fMin], max: [s: sMin+1, f: fMin+fSize]];
lastRowStart ¬ last;
lastRowCount ¬ 1;
IF secondLastRowStart.first.max.s > sMin THEN ERROR;
};
};
Repeat: PROC[timesToRepeatScanline: NAT] ~ {
t: LIST OF SF.Box ¬ lastRowStart;
THROUGH [0..lastRowCount) DO
t.first.max.s ¬ t.first.max.s + timesToRepeatScanline;
t ¬ t.rest;
ENDLOOP;
};
last.first ¬ [[FIRST[INTEGER], FIRST[INTEGER]], [FIRST[INTEGER], FIRST[INTEGER]]];
runs[Run, Repeat];
IF secondLastRowCount = lastRowCount AND secondLastRowStart.first.max.s = lastRowStart.first.min.s AND TryToMergeRows[secondLastRowStart, lastRowCount] THEN {
last ¬ secondLastRowStart;
THROUGH [0..lastRowCount-1) DO
last ¬ last.rest;
ENDLOOP;
};
SELECT TRUE FROM
scratch.first.max.f > scratch.first.min.f => {
polygon ¬ scratch;
scratch ¬ last.rest;
last.rest ¬ NIL;
};
last = scratch => {
polygon ¬ NIL
};
ENDCASE => {
polygon ¬ scratch.rest;
scratch.rest ¬ last.rest;
last.rest ¬ NIL;
};
FreeScratch[scratch];
};

TryToMergeRows: PROC [secondLastRowStart: LIST OF SF.Box, boxesPerRow: INT]
RETURNS [success: BOOLEAN] ~ {
max: INTEGER;
s: LIST OF SF.Box ¬ secondLastRowStart;
t: LIST OF SF.Box ¬ secondLastRowStart;
FOR i: INT IN [0..boxesPerRow) DO t ¬ t.rest ENDLOOP;
IF boxesPerRow = 0 THEN RETURN [TRUE];
FOR i: INT IN [0..boxesPerRow) DO
IF s.first.min.f # t.first.min.f OR s.first.max.f # t.first.max.f THEN RETURN [FALSE];
s ¬ s.rest; t ¬ t.rest;
ENDLOOP;
t ¬ s; s ¬ secondLastRowStart;
max ¬ t.first.max.s;
FOR i: INT IN [0..boxesPerRow) DO
s.first.max.s ¬ max;
s ¬ s.rest;
ENDLOOP;
RETURN [TRUE];
};

Destroy: PUBLIC PROC [rectangleList: LIST OF SF.Box] ~ {
FreeScratch[rectangleList];
};

Copy: PUBLIC PROC [polygon: Polygon] RETURNS [copy: Polygon] ~ {
scratch: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ scratch;
WHILE polygon # NIL DO
IF last.rest = NIL THEN {last.rest ¬ GetScratch[]};
last ¬ last.rest;
last.first ¬ polygon.first;
polygon ¬ polygon.rest;
ENDLOOP;
IF last = scratch
THEN copy ¬ NIL
ELSE {
copy ¬ scratch.rest;
scratch.rest ¬ last.rest;
last.rest ¬ NIL;
};
FreeScratch[scratch];
};

Reader: TYPE ~ RECORD [
s, fMin, fMax: INTEGER,
repeatCount: CARDINAL,
done: BOOLEAN,
currentRow, currentBox: LIST OF SF.Box
];

NewReader: PROC [polygon: Polygon] RETURNS [Reader] ~ INLINE {
IF polygon = NIL
THEN RETURN [[LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]]
ELSE RETURN [[
s: polygon.first.min.s,
fMin: polygon.first.min.f,
fMax: polygon.first.max.f,
repeatCount: polygon.first.max.s-polygon.first.min.s,
done: FALSE,
currentRow: polygon,
currentBox: polygon
]]
};

Advance: UNSAFE PROC [r: POINTER TO Reader] ~ UNCHECKED {
next: Polygon ¬ r.currentBox.rest;
IF next = NIL OR next.first.min.s # r.currentRow.first.min.s THEN {
IF r.repeatCount > 1
THEN {
r.repeatCount ¬ r.repeatCount - 1;
r.s ¬ r.s + 1;
next ¬ r.currentRow;
}
ELSE IF next # NIL THEN {
r.currentRow ¬ next;
r.repeatCount ¬ next.first.max.s-next.first.min.s;
r.s ¬ next.first.min.s;
};
};
IF next = NIL
THEN r­ ¬ [LAST[INTEGER], 0, 0, 0, TRUE, NIL, NIL]
ELSE {
r.fMin ¬ next.first.min.f;
r.fMax ¬ next.first.max.f;
r.currentBox ¬ next;
IF r.repeatCount = 0 THEN Advance[r];
};
};

SkipTo: UNSAFE PROC [r: POINTER TO Reader, s: INTEGER] ~ UNCHECKED {
WHILE r.s < s DO
IF r.currentRow = r.currentBox AND r.repeatCount > 1
THEN {
delta: INTEGER ¬ MIN[INTEGER[r.repeatCount]-1, s-r.s];
r.s ¬ r.s + delta;
r.repeatCount ¬ INTEGER[r.repeatCount] - delta;
}
ELSE Advance[r];
ENDLOOP;
};

TestReader: PROC [polygon: Polygon] ~ {
reader: Reader ¬ NewReader[polygon];
Run: PROC [box: SF.Box] ~ {
IF reader.done THEN ERROR;
IF box.min.s # reader.s THEN ERROR;
IF (box.max.s-box.min.s)#1 THEN ERROR;
IF box.min.f # reader.fMin THEN ERROR;
IF box.max.f # reader.fMax THEN ERROR;
TRUSTED {Advance[@reader]};
};
Map[polygon, Run, TRUE];
IF NOT reader.done THEN ERROR;
};

Union: PUBLIC PROC [a, b: Polygon] RETURNS [Polygon] ~ {
Runs: PROC[run: PROC[sMin, fMin: INTEGER, fSize: NAT], repeat: PROC[timesToRepeatScanline: NAT]] ~ TRUSTED {
aReader: Reader ¬ NewReader[a];
bReader: Reader ¬ NewReader[b];
UNTIL aReader.done AND bReader.done DO
as: INTEGER ¬ aReader.s;
bs: INTEGER ¬ bReader.s;
s: INTEGER ¬ MIN[as, bs];
duplicates: NAT ¬ MIN[aReader.repeatCount, bReader.repeatCount];
somethingInScanline: BOOLEAN ¬ FALSE;
WHILE s = aReader.s OR s = bReader.s DO
fStart: INTEGER ¬ LAST[INTEGER];
fEnd: INTEGER;
IF s = aReader.s THEN {fStart ¬ aReader.fMin};
IF s = bReader.s THEN {fStart ¬ MIN[fStart, bReader.fMin]};
fEnd ¬ fStart;
DO
SELECT TRUE FROM
s = aReader.s AND aReader.fMin <= fEnd => {
fEnd ¬ MAX[fEnd, aReader.fMax];
Advance[@aReader];
};
s = bReader.s AND bReader.fMin <= fEnd => {
fEnd ¬ MAX[fEnd, bReader.fMax];
Advance[@bReader];
};
ENDCASE => EXIT;
ENDLOOP;
IF fEnd > fStart THEN {run[s, fStart, fEnd - fStart]; somethingInScanline ¬ TRUE};
ENDLOOP;
IF as = s AND bs = s AND duplicates > 1 THEN {
IF somethingInScanline THEN repeat[duplicates-1];
SkipTo[@aReader, s+duplicates];
SkipTo[@bReader, s+duplicates];
};
ENDLOOP;
};
RETURN[CreateFromRuns[Runs]];
};

Intersection: PUBLIC PROC [a, b: Polygon] RETURNS [Polygon] ~ {
Runs: PROC[run: PROC[sMin, fMin: INTEGER, fSize: NAT], repeat: PROC[timesToRepeatScanline: NAT]] ~ TRUSTED {
aReader: Reader ¬ NewReader[a];
bReader: Reader ¬ NewReader[b];
DO
duplicates: NAT;
s: INTEGER;
somethingInScanline: BOOLEAN ¬ FALSE;
IF aReader.s < bReader.s THEN SkipTo[@aReader, bReader.s]; IF aReader.done THEN EXIT;
IF aReader.s > bReader.s THEN SkipTo[@bReader, aReader.s]; IF bReader.done THEN EXIT;
s ¬ aReader.s;
duplicates ¬ MIN[aReader.repeatCount, bReader.repeatCount] - 1;
WHILE s = aReader.s AND s = bReader.s DO
fMin: INTEGER ¬ MAX[aReader.fMin, bReader.fMin];
fMax: INTEGER ¬ MIN[aReader.fMax, bReader.fMax];
IF fMin < fMax THEN {run[s, fMin, fMax - fMin]; somethingInScanline ¬ TRUE};
SELECT fMax FROM
aReader.fMax => {Advance[@aReader]};
bReader.fMax => {Advance[@bReader]};
ENDCASE => ERROR;
ENDLOOP;
IF somethingInScanline AND duplicates > 0 THEN {
repeat[duplicates];
SkipTo[@aReader, s+1+duplicates];
SkipTo[@bReader, s+1+duplicates];
};
ENDLOOP;
};
RETURN[CreateFromRuns[Runs]];
};

Invert: PROC [b: Polygon, universe: SF.Box] RETURNS [inverse: Polygon] ~ {
c: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ c;
bb: SF.Box ¬ BoundingBox[b];
sMin: INTEGER ¬ MIN[universe.min.s, bb.min.s];
fMin: INTEGER ¬ MIN[universe.min.f, bb.min.f];
sMax: INTEGER ¬ MAX[universe.max.s, bb.max.s];
fMax: INTEGER ¬ MAX[universe.max.f, bb.max.f];
Emit: PROC [s0, f0, s1, f1: INTEGER] ~ {
s0 ¬ MAX[s0, universe.min.s];
s1 ¬ MIN[s1, universe.max.s];
f0 ¬ MAX[f0, universe.min.f];
f1 ¬ MIN[f1, universe.max.f];
IF s0 < s1 AND f0 < f1 THEN {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
last.first ¬ [[s0, f0], [s1, f1]];
};
};
s: INTEGER ¬ sMin;
f: INTEGER ¬ fMax;
FOR p: LIST OF SF.Box ¬ b, p.rest UNTIL p=NIL DO
r: SF.Box ~ p.first;
IF r.min.s > sMin OR p=b THEN {
Emit[sMin, f, s, fMax];
f ¬ fMin;
sMin ¬ s;
s ¬ r.min.s;
Emit[sMin, f, s, fMax];
sMin ¬ s;
s ¬ r.max.s;
};
IF sMin # r.min.s OR s # r.max.s THEN ERROR;
Emit[sMin, f, s, r.min.f];
f ¬ r.max.f;
ENDLOOP;
Emit[sMin, f, s, fMax];
Emit[s, fMin, sMax, fMax];
IF c = last
THEN inverse ¬ NIL
ELSE {
inverse ¬ c.rest;
c.rest ¬ last.rest;
last.rest ¬ NIL;
};
FreeScratch[c];
};

Difference: PUBLIC PROC [a, b: Polygon] RETURNS [diff: Polygon] ~ {
bb: SF.Box ¬ BoundingBox[a];
bInverse: Polygon ¬ Invert[b, bb];
IF a # NIL AND a.rest = NIL
THEN { diff ¬ bInverse }
ELSE { diff ¬ Intersection[a, bInverse]; FreeScratch[bInverse] };
};

Shift: PUBLIC PROC [polygon: Polygon, sShift, fShift: INTEGER] ~ {
shift: SF.Vec ~ [s: sShift, f: fShift];
WHILE polygon # NIL DO
polygon.first.min ¬ SFInline.Add[polygon.first.min, shift];
polygon.first.max ¬ SFInline.Add[polygon.first.max, shift];
polygon ¬ polygon.rest;
ENDLOOP;
};

FullyDestructiveUnion: PROC [a, b: Polygon] RETURNS [u: Polygon] ~ {
u ¬ Union[a, b];
FreeScratch[a];
FreeScratch[b];
};

DestructiveUnion: PUBLIC PROC [a, b: Polygon] RETURNS [u: Polygon] ~ {
u ¬ Union[a, b];
FreeScratch[a];
};

DestructiveIntersection: PUBLIC PROC [a, b: Polygon] RETURNS [i: Polygon ¬ NIL] ~ {
IF a = NIL OR b = NIL THEN RETURN [NIL];
IF b.rest = NIL
THEN { i ¬ DestructiveClip[a, b.first] }
ELSE { i ¬ Intersection[a, b]; FreeScratch[a] };
};

DestructiveClip: PUBLIC PROC [a: Polygon, b: SF.Box] RETURNS [i: Polygon ¬ NIL] ~ {
last: Polygon ¬ NIL;
junk: Polygon ¬ NIL;
UNTIL a = NIL DO
p: Polygon ¬ a;
sMin: INTEGER ¬ MAX[p.first.min.s, b.min.s];
fMin: INTEGER ¬ MAX[p.first.min.f, b.min.f];
sMax: INTEGER ¬ MIN[p.first.max.s, b.max.s];
fMax: INTEGER ¬ MIN[p.first.max.f, b.max.f];
a ¬ a.rest;
IF sMax <= sMin OR fMax <= fMin
THEN {p.rest ¬ junk; junk ¬ p}
ELSE {
p.first ¬ [[sMin, fMin], [sMax, fMax]];
IF last = NIL THEN i ¬ last ¬ p ELSE {last.rest ¬ p; last ¬ p};
}
ENDLOOP;
IF last # NIL THEN last.rest ¬ NIL;
FreeScratch[junk];
};

DestructiveDifference: PUBLIC PROC [a, b: Polygon] RETURNS [d: Polygon] ~ {
d ¬ Difference[a, b];
FreeScratch[a];
};

SplitOffSecondHalf: PROC [a: LIST OF SF.Box] RETURNS [r: LIST OF SF.Box] ~ {
b: LIST OF SF.Box ¬ a;
n: INT ¬ 0;
WHILE a#NIL DO
a ¬ a.rest; n ¬ n + 1;
b ¬ b.rest;
IF a = NIL THEN EXIT; a ¬ a.rest; n ¬ n + 1;
ENDLOOP;
IF n < 8 THEN r ¬ NIL
ELSE {r ¬ b.rest; b.rest ¬ NIL};
};

Canonicalize: PUBLIC PROC [rectangleList: LIST OF SF.Box] RETURNS [Polygon] ~ {
b: LIST OF SF.Box ¬ SplitOffSecondHalf[rectangleList];
a: LIST OF SF.Box ¬ rectangleList;
IF b = NIL
THEN {
WHILE a # NIL DO
a1: LIST OF SF.Box ¬ a;
a ¬ a1.rest;
a1.rest ¬ NIL;
IF SFInline.Nonempty[a1.first] THEN b ¬ FullyDestructiveUnion[b, a1];
ENDLOOP;
RETURN [b]
}
ELSE RETURN [FullyDestructiveUnion[Canonicalize[a], Canonicalize[b]]];
};

CreateFromBoxes: PUBLIC PROC [boxes: SF.BoxGenerator] RETURNS [Polygon] ~ {
head: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ head;
new: LIST OF SF.Box ¬ NIL;
AddBox: PROC [box: SF.Box] ~ {
IF SFInline.Nonempty[box] THEN {
IF last.rest = NIL THEN last.rest ¬ GetScratch[];
last ¬ last.rest;
last.first ¬ box;
};
};
boxes[AddBox];
{t: LIST OF SF.Box ¬ last.rest; last.rest ¬ NIL; new ¬ head.rest; head.rest ¬ t};
FreeScratch[head]; head ¬ last ¬ NIL;
RETURN [Validate[new ! InvalidManhattanPolygon => CONTINUE]];
RETURN [Canonicalize[new]];
};

BoundingBox: PUBLIC PROC [polygon: Polygon] RETURNS [SF.Box] ~ {
IF polygon # NIL THEN {
bmins: INTEGER ¬ polygon.first.min.s;
bminf: INTEGER ¬ polygon.first.min.f;
bmaxs: INTEGER ¬ polygon.first.max.s;
bmaxf: INTEGER ¬ polygon.first.max.f;
FOR each: Polygon ¬ polygon.rest, each.rest UNTIL each=NIL DO
emins: INTEGER = each.first.min.s;
eminf: INTEGER = each.first.min.f;
emaxs: INTEGER = each.first.max.s;
emaxf: INTEGER = each.first.max.f;
IF emins < bmins THEN bmins ¬ emins;
IF eminf < bminf THEN bminf ¬ eminf;
IF emaxs > bmaxs THEN bmaxs ¬ emaxs;
IF emaxf > bmaxf THEN bmaxf ¬ emaxf;
ENDLOOP;
RETURN [[min: [s: bmins, f: bminf], max: [s: bmaxs, f: bmaxf]]];
};
RETURN [[min: [s: 0, f: 0], max: [s: 0, f: 0]]];
};

CountBoxes: PUBLIC PROC [polygon: Polygon] RETURNS [boxes: INT ¬ 0] ~ {
WHILE polygon # NIL DO
boxes ¬ boxes + 1;
polygon ¬ polygon.rest;
ENDLOOP;
};

CountRuns: PUBLIC PROC [polygon: Polygon] RETURNS [runs: INT ¬ 0] ~ {
WHILE polygon # NIL DO
runs ¬ runs + NAT[polygon.first.max.s-polygon.first.min.s];
polygon ¬ polygon.rest;
ENDLOOP;
};

TestCreate: PROC [polygon: Polygon] RETURNS [Polygon] ~ {
Runs: PROC [run: PROC[sMin, fMin: INTEGER, fSize: NAT], repeat: PROC[timesToRepeatScanline: NAT]] ~ {
boxAction: SF.BoxAction ~ {
run[sMin: box.min.s, fMin: box.min.f, fSize: box.max.f-box.min.f]
};
Map[polygon: polygon, boxAction: boxAction, runs: TRUE];
};
RETURN [CreateFromRuns[Runs]]
};

Map: PUBLIC PROC [polygon: Polygon, boxAction: SF.BoxAction, runs: BOOL ¬ FALSE] ~ {
IF runs
THEN {
WHILE polygon # NIL DO
sMinRow: INTEGER ~ polygon.first.min.s;
sMaxRow: INTEGER ~ polygon.first.max.s;
FOR s: INTEGER IN [sMinRow..sMaxRow) DO
FOR t: Polygon ¬ polygon, t.rest UNTIL (t = NIL OR t.first.min.s # sMinRow) DO
boxAction[[min: [s: s, f: t.first.min.f], max: [s: s+1, f: t.first.max.f]]];
ENDLOOP;
ENDLOOP;
UNTIL (polygon = NIL OR polygon.first.min.s # sMinRow) DO
polygon ¬ polygon.rest;
ENDLOOP;
ENDLOOP;
}
ELSE {
FOR each: Polygon ¬ polygon, each.rest UNTIL each=NIL DO
boxAction[each.first];
ENDLOOP;
};
};

Clip: PUBLIC PROC [polygon: Polygon, box: SF.Box, boxAction: SF.BoxAction, runs: BOOL] ~ {
IF runs
THEN {
row: Polygon ¬ polygon;
WHILE row#NIL DO
smin: INTEGER ~ row.first.min.s;
smax: INTEGER ~ row.first.max.s;
IF smax<=box.min.s THEN NULL
ELSE IF smin>=box.max.s THEN EXIT
ELSE FOR s: INTEGER IN [MAX[smin, box.min.s]..MIN[smax, box.max.s]) DO
run: SF.Box ¬ [min: [s: s, f: 0], max: [s: s+1, f: 0]];
FOR t: Polygon ¬ row, t.rest UNTIL t=NIL OR t.first.min.s#smin DO
fmin: INTEGER ~ t.first.min.f;
fmax: INTEGER ~ t.first.max.f;
IF fmax<=box.min.f THEN NULL
ELSE IF fmin>=box.max.f THEN EXIT
ELSE {
run.min.f ¬ MAX[fmin, box.min.f];
run.max.f ¬ MIN[fmax, box.max.f];
boxAction[run];
};
ENDLOOP;
ENDLOOP;
UNTIL row=NIL OR row.first.min.s#smin DO row ¬ row.rest ENDLOOP;
ENDLOOP;
}
ELSE {
FOR each: Polygon ¬ polygon, each.rest UNTIL each=NIL DO
IF each.first.max.s<=box.min.s THEN NULL
ELSE IF each.first.min.s>=box.max.s THEN EXIT
ELSE {
clippedBox: SF.Box ~ SFInline.Intersect[each.first, box];
IF SFInline.Nonempty[clippedBox] THEN boxAction[clippedBox];
};
ENDLOOP;
};
};

IsVisible: PUBLIC PROC [mask, clipper: Polygon] RETURNS [visibility: Visibility] ~ {
IF mask = NIL OR clipper = NIL THEN RETURN [invisible];
IF mask.rest = NIL AND clipper.rest = NIL
THEN {
sMin: INTEGER ~ MAX[mask.first.min.s, clipper.first.min.s];
sMax: INTEGER ~ MIN[mask.first.max.s, clipper.first.max.s];
fMin: INTEGER ~ MAX[mask.first.min.f, clipper.first.min.f];
fMax: INTEGER ~ MIN[mask.first.max.f, clipper.first.max.f];
IF sMax <= sMin OR fMax <= fMin THEN RETURN [invisible];
IF mask.first = [min: [s: sMin, f: fMin], max: [s: sMax, f: fMax]] THEN
RETURN [visible];
RETURN [partlyVisible];
}
ELSE {
intersection: Polygon ¬ Intersection[mask, clipper];
visibility ¬
IF intersection = NIL THEN invisible
ELSE IF Equal[intersection, mask] THEN visible
ELSE partlyVisible;
Destroy[intersection];
intersection ¬ NIL;
};
};

ClipBoxToMask: PUBLIC PROC [box: SF.Box, mask: Polygon, action: PROC [SF.Box]] ~ {
bmins: INTEGER = box.min.s;
bminf: INTEGER = box.min.f;
bmaxs: INTEGER = box.max.s;
bmaxf: INTEGER = box.max.f;
IF bmins < bmaxs AND bminf < bmaxf THEN
FOR list: LIST OF SF.Box ¬ mask, list.rest UNTIL list=NIL DO
mins: INTEGER ¬ list.first.min.s;
maxs: INTEGER ¬ list.first.max.s;
IF bmins > mins THEN mins ¬ bmins;
IF bmaxs < maxs THEN maxs ¬ bmaxs;
IF mins < maxs THEN {
minf: INTEGER ¬ list.first.min.f;
maxf: INTEGER ¬ list.first.max.f;
IF bminf > minf THEN minf ¬ bminf;
IF bmaxf < maxf THEN maxf ¬ bmaxf;
IF minf < maxf THEN action[[min: [s: mins, f: minf], max: [s: maxs, f: maxf]]];
};
ENDLOOP;
};

Equal: PUBLIC PROC [a, b: Polygon] RETURNS [BOOLEAN] ~ {
WHILE a#NIL AND b#NIL AND a#b DO
IF a.first # b.first THEN RETURN [FALSE];
a ¬ a.rest;
b ¬ b.rest;
ENDLOOP;
RETURN [a = b];
};

FromList: PROC [numbers: LIST OF REF] RETURNS [new: LIST OF SF.Box] ~ {
scratch: LIST OF SF.Box ¬ GetScratch[];
last: LIST OF SF.Box ¬ scratch;
WHILE numbers # NIL DO
sMin: REF INT ¬ NARROW[numbers.first];
fMin: REF INT ¬ NARROW[numbers.rest.first];
sMax: REF INT ¬ NARROW[numbers.rest.rest.first];
fMax: REF INT ¬ NARROW[numbers.rest.rest.rest.first];
IF last.rest = NIL THEN {last.rest ¬ GetScratch[]};
last ¬ last.rest;
last.first ¬ [[sMin­, fMin­], [sMax­, fMax­]];
numbers ¬ numbers.rest.rest.rest.rest;
ENDLOOP;
IF last = scratch
THEN { new ¬ NIL }
ELSE {
new ¬ scratch.rest;
scratch.rest ¬ last.rest;
last.rest ¬ NIL;
};
};
globalAvail: LIST OF SF.Box ¬ NIL;
availCount: INT ¬ 0;
availLimit: INT ¬ 1000;
scratchChunkSize: NAT ¬ 8;

CreateFromBox: PUBLIC ENTRY PROC [box: SF.Box] RETURNS [polygon: Polygon] ~ {
IF SFInline.Empty[box] THEN RETURN [NIL];
IF availCount = 0 THEN RETURN [LIST[box]];
polygon ¬ globalAvail;
polygon.first ¬ box;
globalAvail ¬ polygon.rest;
polygon.rest ¬ NIL;
availCount ¬ availCount - 1;
};

GetScratch: ENTRY PROC RETURNS [scratch: LIST OF SF.Box] ~ {
empty: SF.Box ~ [[0, 0], [0, 0]];
t: LIST OF SF.Box;
WHILE availCount < scratchChunkSize DO
globalAvail ¬ CONS[empty, globalAvail];
availCount ¬ availCount + 1;
ENDLOOP;
scratch ¬ t ¬ globalAvail;
THROUGH [0..scratchChunkSize-1) DO t ¬ t.rest ENDLOOP;
globalAvail ¬ t.rest;
availCount ¬ availCount - scratchChunkSize;
t.rest ¬ NIL;
};

FreeScratch: ENTRY PROC [scratch: LIST OF SF.Box] ~ {
limit: INT ¬ MAX[availLimit, 0];
IF scratch # NIL THEN {
t: LIST OF SF.Box ¬ scratch;
UNTIL t.rest = NIL DO
t ¬ t.rest;
availCount ¬ availCount + 1;
ENDLOOP;
availCount ¬ availCount + 1;
t.rest ¬ globalAvail;
globalAvail ¬ scratch;
};
WHILE availCount > limit DO
t: LIST OF SF.Box ¬ globalAvail;
globalAvail ¬ globalAvail.rest;
t.rest ¬ NIL;
availCount ¬ availCount - 1;
ENDLOOP;
};

END.

˜
ImagerManhattanImpl.mesa
Copyright Σ 1984, 1985, 1986, 1987, 1989, 1990, 1991 by Xerox Corporation.  All rights reserved.
Michael Plass, August 2, 1989 12:51:53 pm PDT
Doug Wyatt, March 7, 1986 4:36:43 pm PST
Russ Atkinson (RRA) December 18, 1990 11:44 am PST

Assume
the secondLast row and the last row have the same number of boxes,
boxes in the secondLast row all have the same sSize,
boxes in the last row all have the same sSize.
[] _ Validate[inverse];
IF Intersection[b, inverse] # NIL THEN ERROR;
IF NOT Equal[Union[a, b], Union[diff, b]] THEN ERROR;
For creating a new list via the debugger.
Free list management
ENABLE UNWIND => NULL; -- RRA: no reasonable errors in here
ENABLE UNWIND => NULL; -- RRA: no reasonable errors in here
Consistency check:
t _ globalAvail; FOR i: INT IN [0..availCount) DO t _ t.rest ENDLOOP; IF t#NIL THEN ERROR;
ENABLE UNWIND => NULL; -- RRA: no reasonable errors in here
ΚX–
(cedarcode) style•NewlineDelimiter

™
headš
œ™Icodešœ
Οe
œU™`Lš
œ-™-Lš
œ(™(L™2L™š
Οk	˜	Lšœžœ˜,Lšžœ
žœ%˜-Lšœ	žœ#˜1——šΟnœžœ
ž˜"Lšžœ	˜Lšžœ˜Lšœž˜—˜Lšœ	žœ˜(Lšœžœ˜.LšŸœžœ
žœžœ
˜-L˜šŸœžœ
žœžœ˜>šžœžœ
žœ˜Lš
œ˜Lšœžœ˜Lšœžœ˜Lšœžœ˜Lšœžœ˜š
ž˜L˜Lšžœžœžœ
žœ˜Gš
žœžœ
žœ
žœ
žœ˜Lšœžœ˜Lšœžœ˜Lšœžœ˜Lšœžœ˜šžœ
žœ
ž˜Lš
œ˜Lšœžœžœ˜;Lšžœžœ˜)—Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜L˜—Lšžœ
˜—L˜—Lšžœ
˜L˜L˜—šŸœžœ
žœ	žœžœ
žœ	žœžœžœžœ˜ž
Lšœ	žœ
žœ
žœ˜'Lšœžœ
žœ
žœ˜Lš	œžœ
žœ
žœžœ
˜)Lšœžœ
žœ
žœ˜$Lšœžœ˜!Lšœžœ˜šŸœžœ
žœ	žœ˜.Lšœ
žœ˜(šžœžœ˜/šžœ˜Lšžœ'žœ
žœ
˜4šžœž˜L˜?˜Lšžœ
žœ
žœ˜1L˜L˜HL˜ L˜—Lšžœžœ
˜—L˜
—šžœ˜šžœ#žœ;žœ1˜—
šžœ˜Lš
œ˜Lš
œ"˜"Lš
œ˜Lš
œ
˜
—šžœ˜Lšžœ
žœ
žœ˜1Lš
œ˜Lš
œ˜——L˜"L˜"L˜HL˜L˜Lšžœ'žœ
žœ
˜4L˜——L˜—šŸœžœžœ˜,Lšœžœ
žœ
žœ˜!šžœž˜L˜6L˜Lšžœ
˜—L˜—Lšœžœ
žœžœ
žœžœ
žœžœ
žœ˜RL˜šžœ#žœ;žœ2žœ˜ž
L˜šžœž˜L˜Lšžœ
˜—L˜—šžœ
žœ
ž˜˜.L˜L˜Lšœžœ
˜L˜—˜šœ
ž˜
L˜——Lšžœ˜L˜L˜Lšœžœ
˜L˜—L˜L˜L˜—šŸœžœžœ
žœ
žœžœžœžœ˜jš
œ™Lš
œB™BLš
œ4™4Lš
œ.™.—Lšœžœ
˜
Lšœžœ
žœ
žœ˜'Lšœžœ
žœ
žœ˜'Lš
žœžœ
žœžœžœ
˜5Lšžœžœ
žœžœ˜&šžœžœ
žœž˜!Lš
žœžœžœ
žœžœ˜VL˜Lšžœ
˜—L˜L˜šžœžœ
žœž˜!L˜L˜Lšžœ
˜—Lšžœžœ˜L˜—L˜šŸœžœ
žœžœ
žœ
žœ	˜8L˜L˜—L˜šŸœžœ
žœžœ˜@Lšœ	žœ
žœ
žœ˜'Lšœžœ
žœ
žœ˜šžœžœ
ž˜Lšžœ
žœ
žœ˜3L˜L˜L˜Lšžœ
˜—šžœ˜Lšžœž˜šžœ˜L˜L˜Lšœžœ
˜L˜——L˜L˜—L˜šœžœžœ˜Lšœžœ
˜Lšœ
žœ
˜Lšœžœ
˜Lšœžœ
žœ
žœ˜&L˜—L˜šŸ	œžœžœžœ˜>šžœž˜Lšžœ
žœžœ
žœžœžœžœ˜6šžœ
žœ˜L˜L˜L˜L˜5Lšœžœ
˜L˜L˜L˜——L˜—L˜šŸœžœ
žœžœ
žœž	œ˜9L˜"šžœžœ
žœ-žœ˜Cšžœ˜šžœ˜L˜"L˜L˜L˜
—šžœ
žœžœ
žœ˜L˜L˜2L˜L˜——L˜—šžœž˜
Lšžœžœ
žœžœžœžœ
˜2šžœ˜L˜L˜L˜Lšžœžœ˜%L˜——L˜—L˜šŸœžœ
žœžœ
žœžœž	œ˜Dšžœ	ž˜Lšžœžœ˜4šžœ˜Lšœžœžœ
žœ˜6L˜Lšœžœ˜/L˜
—Lšžœ˜Lšžœ
˜—L˜—L˜šŸ
œžœ˜'L˜$šŸœžœžœ	˜Lšžœ
žœ
žœ
˜Lšžœžœ
žœ
˜#Lšžœžœ
žœ
˜&Lšžœžœ
žœ
˜&Lšžœžœ
žœ
˜&Lšžœ˜L˜—Lšœžœ˜Lšžœ
žœ
žœ
žœ
˜L˜—L˜šŸœžœ
žœžœ˜8šŸœžœžœ
žœ	žœžœžœžœ˜lL˜L˜šžœžœž˜&Lšœžœ
˜Lšœžœ
˜Lšœžœžœ	˜Lšœžœžœ+˜@Lšœžœžœ
˜%šžœžœž˜'Lšœžœžœ
žœ˜ Lšœžœ
˜Lšžœžœ˜.Lšžœžœžœ˜;L˜š
ž˜šžœ
žœ
ž˜šœžœ˜+Lšœžœ˜L˜L˜—šœžœ˜+Lšœžœ˜L˜L˜—Lšžœžœ
˜—Lšžœ
˜—Lšžœžœ7žœ˜RLšžœ
˜—šžœžœžœžœ˜.Lšžœžœ˜1L˜L˜L˜—Lšžœ
˜—L˜—Lšžœ˜L˜—L˜šŸœžœ
žœžœ˜?šŸœžœžœ
žœ	žœžœžœžœ˜lL˜L˜š
ž˜Lšœžœ
˜Lšœžœ
˜Lšœžœžœ
˜%Lš
žœžœžœžœ
žœ
˜ULš
žœžœžœžœ
žœ
˜UL˜Lšœ
žœ/˜?šžœžœž˜(Lšœžœžœ˜0Lšœžœžœ˜0Lšžœ
žœ3žœ˜Lšžœž˜L˜$L˜$Lšžœžœ
˜—Lšžœ
˜—šžœžœžœ˜0L˜L˜!L˜!L˜—Lšžœ
˜—L˜—Lšžœ˜L˜—L˜šŸœžœžœžœ˜JLšœžœ
žœ
žœ˜!Lšœžœ
žœ
žœ	˜Lšœžœ˜Lšœžœžœ˜.Lšœžœžœ˜.Lšœžœžœ˜.Lšœžœžœ˜.šŸœžœžœ˜(Lšœžœ˜Lšœžœ˜Lšœžœ˜Lšœžœ˜šžœ	žœ	žœ˜Lšžœ
žœ
žœ˜1L˜L˜"L˜—L˜—Lšœžœ˜Lšœžœ˜š
žœžœ
žœ
žœžœžœ
ž˜0Lšœžœ˜šžœžœžœ˜L˜L˜	L˜	L˜L˜L˜	L˜L˜—Lšžœžœ
žœ
žœ
˜,L˜L˜Lšžœ
˜—L˜L˜šžœ	˜Lšžœž˜šžœ˜L˜L˜Lšœžœ
˜L˜——L˜Lš
œ™Lš
œ-™-L˜—L˜šŸ
œžœ
žœžœ˜CLšœžœ˜L˜"šžœžœ
žœ
ž˜Lšžœ˜Lšžœ=˜A—Lš
œ5™5L˜—L˜šŸœžœ
žœ$žœ˜BLšœžœ˜'šžœžœ
ž˜Lš
œ;˜;Lš
œ;˜;L˜Lšžœ
˜—L˜—L˜šŸœžœžœ˜DL˜L˜L˜L˜—L˜šŸœžœ
žœžœ˜FL˜L˜L˜—L˜š
Ÿœžœ
žœžœžœ˜SLšžœžœ
žœžœ
žœ
žœžœ˜(šžœ
ž˜Lšžœ$˜(Lšžœ,˜0—L˜—L˜šŸœžœ
žœžœžœžœ˜SLšœžœ
˜Lšœžœ
˜šžœžœ
ž˜L˜Lšœžœžœ˜,Lšœžœžœ˜,Lšœžœžœ˜,Lšœžœžœ˜,L˜Lšžœžœ
˜Lšžœ˜šžœ˜L˜'Lšžœžœ
žœžœ˜?L˜
—Lšžœ
˜—Lšžœžœ
žœ
žœ
˜#L˜L˜—L˜šŸœžœ
žœžœ˜KL˜L˜L˜—L˜šŸœžœžœ
žœ
žœžœžœ
žœ
žœ	˜LLšœžœ
žœ
žœ	˜Lšœžœ˜šžœžœ
ž˜L˜L˜Lšžœžœ
žœ
žœ˜,Lšžœ
˜—šžœžœž˜Lšžœžœ˜ —L˜—L˜šŸœžœ
žœžœ
žœ
žœžœ˜OLšœžœ
žœ
žœ)˜6Lšœžœ
žœ
žœ˜"šžœž˜
šžœ˜šžœžœ
ž˜Lšœžœ
žœ
žœ	˜L˜Lšœ
žœ
˜Lšžœžœ"˜ELšžœ
˜—Lšžœ˜
L˜
—Lšžœ
žœ;˜F—L˜—L˜š
Ÿœžœ
žœ	žœžœ˜KLšœžœ
žœ
žœ˜$Lšœžœ
žœ
žœ˜Lš	œžœ
žœ
žœžœ
˜šŸœžœžœ	˜šžœžœ˜ Lšžœ
žœ
žœ˜1L˜L˜L˜—L˜—L˜Lš	œžœ
žœ
žœžœ"˜QLšœ!žœ
˜%Lšžœ,žœ˜=Lšžœ˜L˜—L˜š
Ÿœžœ
žœžœžœ	˜@šžœžœ
žœ˜Lšœžœ˜%Lšœžœ˜%Lšœžœ˜%Lšœžœ˜%šžœ)žœžœ
ž˜=Lšœžœ˜"Lšœžœ˜"Lšœžœ˜"Lšœžœ˜"Lšžœžœ˜$Lšžœžœ˜$Lšžœžœ˜$Lšžœžœ˜$Lšžœ
˜—Lšžœ:˜@L˜—Lšžœ*˜0L˜—L˜š
Ÿ
œžœ
žœžœ	žœ	˜Gšžœžœ
ž˜L˜L˜Lšžœ
˜—L˜—L˜š
Ÿ	œžœ
žœžœžœ	˜Ešžœžœ
ž˜Lšœžœ*˜;L˜Lšžœ
˜—L˜—L˜šŸ
œžœžœ˜9šŸœžœžœ
žœ	žœžœžœ˜ešœžœ˜Lš
œA˜ALš
œ˜—Lšœ2žœ˜8L˜—Lšžœ˜L˜—L˜šŸœžœ
žœžœžœžœ˜Tšžœ˜šžœ˜šžœžœ
ž˜Lšœ	žœ˜'Lšœ	žœ˜'šžœžœ
žœž˜'š	žœžœžœ
žœž˜NL˜LLšžœ
˜—Lšžœ
˜—šžœžœ
žœ ž˜9L˜Lšžœ
˜—Lšžœ
˜—L˜
—šžœ˜šžœ$žœžœ
ž˜8L˜Lšžœ
˜—L˜——L˜—L˜šŸœžœ
žœžœžœžœ˜Zšžœ˜šžœ˜L˜šžœžœ
ž˜Lšœžœ˜ Lšœžœ˜ Lšžœžœ
ž˜Lšžœ
žœžœ
ž˜!š
žœ
žœžœ
žœžœžœž˜FLšœžœ0˜7š	žœžœžœ
žœž˜ALšœžœ˜Lšœžœ˜Lšžœžœ
ž˜Lšžœ
žœžœ
ž˜!šžœ˜Lšœžœ˜!Lšœžœ˜!L˜L˜—Lšžœ
˜—Lšžœ
˜—Lš
žœžœ
žœžœžœ
˜@Lšžœ
˜—L˜
—šžœ˜šžœ$žœžœ
ž˜8šžœžœ
ž˜(Lšžœ
žœžœ
ž˜-šžœ˜Lšœžœ+˜9Lšžœžœ˜<L˜——Lšžœ
˜—L˜——L˜—L˜šŸ	œžœ
žœžœ˜TLšžœžœ
žœžœ
žœ
žœ
˜7šžœ
žœ
žœž˜)šžœ˜Lšœžœžœ(˜;Lšœžœžœ(˜;Lšœžœžœ(˜;Lšœžœžœ(˜;Lšžœžœžœ
žœ
˜8šžœAž˜GLšžœ˜—Lšžœ˜L˜
—šžœ˜L˜4˜šžœžœ
žœ
˜$Lšžœ
žœžœ˜.Lšžœ˜——L˜Lšœžœ
˜L˜——L˜—L˜šŸ
œžœ
žœžœžœžœ
˜RLšœžœ
˜Lšœžœ
˜Lšœžœ
˜Lšœžœ
˜šžœžœž˜'š
žœžœ
žœ
žœžœžœ
ž˜<Lšœžœ˜!Lšœžœ˜!Lšžœžœ˜"Lšžœžœ˜"šžœ
žœ˜Lšœžœ˜!Lšœžœ˜!Lšžœžœ˜"Lšžœžœ˜"Lšžœ
žœ<˜OL˜—Lšžœ
˜——L˜—L˜š
Ÿœžœ
žœžœžœ˜8šžœžœ
žœžœ
žœž˜ Lšžœžœ
žœžœ˜)L˜L˜Lšžœ
˜—Lšžœ	˜L˜—L˜šŸœžœžœ
žœ
žœžœžœ
žœ
žœ	˜GLš
œ)™)Lšœ	žœ
žœ
žœ˜'Lšœžœ
žœ
žœ˜šžœžœ
ž˜Lšœžœ
žœžœ˜&Lšœžœ
žœžœ˜+Lšœžœ
žœžœ˜0Lšœžœ
žœžœ˜5Lšžœ
žœ
žœ˜3L˜L˜.L˜&Lšžœ
˜—šžœ˜Lšžœ	žœ˜šžœ˜L˜L˜Lšœžœ
˜L˜——L˜——š
œ™Lš	œ
žœ
žœ
žœžœ
˜"Lšœžœ˜Lšœžœ˜Lšœžœ˜L˜šŸ
œžœ
žœ
žœžœžœ˜MLšžœ
žœžœ&™;Lšžœžœ
žœžœ˜)Lšžœžœ
žœžœ˜*L˜L˜L˜Lšœžœ
˜L˜L˜—L˜šŸ
œžœ
žœ
žœžœ
žœ
žœ	˜<Lšžœ
žœžœ&™;Lšœžœ˜!Lšœžœ
žœ
žœ˜Lš
œ™Lš
œZ™Zšžœž˜&Lšœžœ˜'L˜Lšžœ
˜—L˜Lšžœžœžœ
˜6L˜L˜+Lšœ	žœ
˜
L˜—L˜šŸœžœ
žœžœ
žœ
žœ	˜5Lšžœ
žœžœ&™;Lšœžœžœ˜ šžœžœ
žœ˜Lšœžœ
žœ
žœ˜šžœ
žœ
ž˜L˜L˜Lšžœ
˜—L˜L˜L˜L˜—šžœž˜Lšœžœ
žœ
žœ˜ L˜Lšœ	žœ
˜
L˜Lšžœ
˜—L˜—L˜—Lšžœ
˜L˜—…—KPl@