<> <> <> <> 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: BOOL _ FALSE] = { 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 _0] = { 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]; }; <> 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 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; <> 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}; <> 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 => { <> 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; }; <> NotOverlinsting: PUBLIC PROC [arc1, arc2: Arc, minDist: INT] RETURNS [notOverlinsting: BOOL _ TRUE] = { 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; }; <<>> <> 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.