OnionArcImpl.mesa 
Copyright © 1985 by Xerox Corporation. All rights reversed.
Created by Bertrand Serlet, February 10, 1986 9:13:25 pm PST
Last Edited by: Serlet, July 3, 1985 2:05:09 pm PDT
DIRECTORY
CD, CDBasics, OnionArc, Rope;
OnionArcImpl: CEDAR PROGRAM
IMPORTS CDBasics
EXPORTS OnionArc =
BEGIN
OPEN OnionArc;
-- The projection of the point according to side is assumed to intersect the "ring" defined by the segment
PointInSeg: PROC [point: INT, thisSide: Side, seg: Seg, rect: CD.Rect] RETURNS [in: BOOLFALSE] = {
IsInThisBit: EachSegBitProc = {in ← in OR (side=thisSide AND min<=point AND point<=max)};
SegEnumerateSegBits[seg, rect, IsInThisBit];
};
SegLength: PROC [seg: Seg, rect: CD.Rect] RETURNS [length: INT 𡤀] = {
LengthSegBit: EachSegBitProc = {IF min>max THEN ERROR; length ← length + max - min};
SegEnumerateSegBits[seg, rect, LengthSegBit];
};
SegIntersect: PROC [seg1, seg2: Seg, rect: CD.Rect] RETURNS [intersect: BOOL] = {
intersect ← PointInSeg[seg1.point1, seg1.side1, seg2, rect] OR PointInSeg[seg2.point1, seg2.side1, seg1, rect];
};
Extends the segment after point2
SegExtent: PROC [seg: Seg, rect: CD.Rect, dist: INT] RETURNS [newSeg: Seg] = {
newPoint2: INT ← seg.point2;
newSide2: Side ← seg.side2;
SELECT seg.side2 FROM
bottom => IF newPoint2+dist<=rect.x2
THEN newPoint2 ← newPoint2+dist
ELSE {newPoint2 ← rect.y1+dist; newSide2 ← right};
right  => IF newPoint2+dist<=rect.y2
THEN newPoint2 ← newPoint2+dist
ELSE {newPoint2 ← rect.x2-dist; newSide2 ← top};
top  => IF newPoint2-dist>=rect.x1
THEN newPoint2 ← newPoint2-dist
ELSE {newPoint2 ← rect.y2-dist; newSide2 ← left};
left  => IF newPoint2-dist>=rect.y1
THEN newPoint2 ← newPoint2-dist
ELSE {newPoint2 ← rect.x1+dist; newSide2 ← bottom};
ENDCASE => ERROR;
newSeg ← NEW[SegRec ← [point1: seg.point1, side1: seg.side1, point2: newPoint2, side2: newSide2]];
};
SegEnumerateSegBits: PROC [seg: Seg, rect: CD.Rect, eachSegBit: EachSegBitProc] = {
point: INT ← seg.point1; side: Side ← seg.side1;
WHILE side#seg.side2 OR (SELECT side FROM bottom, right => seg.point2<point, top, left => seg.point2>point, ENDCASE => ERROR) DO
SELECT side FROM
bottom => {eachSegBit[point, rect.x2, bottom]; point ← rect.y1; side ← right};
right   => {eachSegBit[point, rect.y2, right]; point ← rect.x2; side ← top};
top  => {eachSegBit[rect.x1, point, top]; point ← rect.y2; side ← left};
left   => {eachSegBit[rect.y1, point, left]; point ← rect.x1; side ← bottom};
ENDCASE => ERROR;
ENDLOOP;
eachSegBit[MIN[point, seg.point2], MAX[point, seg.point2], side];
};
EmptyArc: PUBLIC PROC [rect: CD.Rect] RETURNS [arc: Arc] = {
arc ← NEW [ArcRec ← [rect: rect, segs: NIL]];
};
Length: PUBLIC PROC [arc: Arc] RETURNS [length: INT ← 0] = {
FOR segs: LIST OF Seg ← arc.segs, segs.rest WHILE segs#NIL DO
length ← length + SegLength[segs.first, arc.rect];
ENDLOOP;
};
Positive: PROC [side: Side] RETURNS [positive: BOOL] = {
positive ← SELECT side FROM
bottom, right  => TRUE,
left, top    => FALSE,
ENDCASE   => ERROR;
};
ConnectSegBitToArc: PUBLIC PROC [min, max: INT, side: Side, arc: Arc] RETURNS [connection: Arc] = {
rect: CD.Rect ← arc.rect;
segs: LIST OF Seg ← NIL;
seg: Seg;
Extend rect according to point
SELECT side FROM
bottom, top => {rect.x1 ← MIN[rect.x1, min]; rect.x2 ← MAX[rect.x2, max]};
right, left => {rect.y1 ← MIN[rect.y1, min]; rect.y2 ← MAX[rect.y2, max]};
ENDCASE  => ERROR;
IF ~Positive[side] THEN {w: INT ← min; min ← max; max ← w};
Test whether segs is empty
IF arc.segs=NIL THEN
seg ← NEW [SegRec ← [point1: min, point2: max, side1: side, side2: side]]
ELSE {
IF arc.segs.rest#NIL THEN ERROR;
seg ← arc.segs.first;
SELECT TRUE FROM
PointInSeg[min, side, seg, rect] AND PointInSeg[max, side, seg, rect]  => {};
PointInSeg[min, side, seg, rect]            =>
seg ← NEW[SegRec ← [point1: seg.point1, side1: seg.side1, point2: max, side2: side]];
PointInSeg[max, side, seg, rect]            =>
seg ← NEW[SegRec ← [point1: min, side1: side, point2: seg.point2, side2: seg.side2]];
ENDCASE                   => {
Estimates for each seg the price of extending the seg to point in both directions
possibleSeg1: Seg ← NEW[SegRec ← [point1: seg.point1, point2: max, side1: seg.side1, side2: side]];
possibleSeg2: Seg ← NEW[SegRec ← [point1: min, point2: seg.point2, side1: side, side2: seg.side2]];
seg ← IF SegLength[possibleSeg1, rect] < SegLength[possibleSeg2, rect] THEN possibleSeg1 ELSE possibleSeg2;
};
};
connection ← NEW [ArcRec ← [rect: rect, segs: LIST [seg]]];
RETURN;
};
The 2 arcs can be of different sizes
NotOverlinsting: PUBLIC PROC [arc1, arc2: Arc, minDist: INT] RETURNS [notOverlinsting: BOOLTRUE] = {
rect: CD.Rect ← CDBasics.Surround[arc1.rect, arc2.rect];
FOR segs1: LIST OF Seg ← arc1.segs, segs1.rest WHILE segs1#NIL DO
extSeg1: Seg ← SegExtent[segs1.first, rect, minDist];
FOR segs2: LIST OF Seg ← arc2.segs, segs2.rest WHILE segs2#NIL DO
IF SegIntersect[extSeg1, SegExtent[segs2.first, rect, minDist], rect] THEN {
RETURN[FALSE];
};
ENDLOOP;
ENDLOOP;
};
The union is positionned to fit on the largest rect.
Union: PUBLIC PROC [arc1, arc2: Arc] RETURNS [union: Arc] = {
rect: CD.Rect ← CDBasics.Surround[arc1.rect, arc2.rect];
segs: LIST OF Seg ← arc2.segs;
FOR segs1: LIST OF Seg ← arc1.segs, segs1.rest WHILE segs1#NIL DO
segs ← CONS[segs1.first, segs];
ENDLOOP;
union ← NEW[ArcRec ← [rect: rect, segs: segs]];
};
EnumerateSegBits: PUBLIC PROC [arc: Arc, eachSegBit: EachSegBitProc] = {
FOR segs: LIST OF Seg ← arc.segs, segs.rest WHILE segs#NIL DO
SegEnumerateSegBits[segs.first, arc.rect, eachSegBit];
ENDLOOP;
};
END.