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
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 𡤀] = {
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:
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;
};
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.