PROCEDURE ReadCodedChain(rd: Rd.T): REF CodedChain; (* Reads a CodedChain from file "fname". The format is where is an integer, and is a string of "0" (move straight), "1" (turn right), "2" (turn left). Embedded blanks are ignored. ???CHECK!!! *) PROCEDURE DecodeChain(READONLY V: CodedChain): REF IntChain; (* Converts a "CodedChain" to a list of vertex coordinates, assuming each step has length 1. The chain is assumed to start from point "(0,0)" heading towards "+X" *) PROCEDURE ExtractCodedChainBoundary(READONLY M: Image): REF CodedChain; (* Gets a PGM image "M" of a single 4-connected puzzle piece, and returns the piece's outline as a coded chain. Assumes that "M[y,x]=0" if and only if pixel "(x,y)" is outside the piece. Also assumes that the piece does not touch the boundary of "M". *) PROCEDURE TrimCodedChain(READONLY c: CodedChain; i, n: CARDINAL): REF CodedChain; <* FATAL Wr.Failure, Alerted , Rd.EndOfFile, Rd.Failure, OSError.E *> CONST CodedChainFmtVersion = "96-04-11"; PROCEDURE ReadCharacter(r: Rd.T): CHAR = BEGIN RETURN(Rd.GetChar(r)) END ReadCharacter; PROCEDURE ReadCodedChain(rd: Rd.T): REF CodedChain = VAR length: CARDINAL; charact: CHAR; BEGIN ReadFileHeader(rd, "coded chain", CodedChainFmtVersion); length := ReadCardinalParam(rd, "length ="); WITH rcd = NEW(REF CodedChain, length), cd = rcd^ DO FOR i := 0 TO length-1 DO charact := ReadCharacter(rd); WHILE charact IN Lex.Blanks DO charact := ReadCharacter(rd) END; CASE charact OF | '0' => cd[i] := 0; | '1' => cd[i] := 1; | '2' => cd[i] := 2; ELSE Wr.PutText(stderr, "invalid character in coded string at position "); Wr.PutText(stderr, Fmt.Int(i)); Wr.PutText(stderr, " = "); Wr.PutChar(stderr, charact); Wr.PutChar(stderr, '\n') END END; ReadFileFooter(rd, "coded chain"); RETURN rcd END; END ReadCodedChain; (***************************************************) PROCEDURE ExtractCodedChainBoundary(READONLY M: Image): REF CodedChain = VAR x, y: CARDINAL; Ok: BOOLEAN := FALSE; length: CARDINAL; BEGIN WITH NY = NUMBER(M), NX = NUMBER(M[0]) DO y := 0; WHILE y < NY AND NOT Ok DO x := 0; WHILE x < NX AND NOT Ok DO Ok := M[y,x] # 0; IF NOT Ok THEN INC(x) END END; IF NOT Ok THEN INC(y) END END; <* ASSERT Ok *> length := 0; WITH rChain = NEW(REF CodedChain, NX*NY), chain = rChain^ DO FollowCodedChainBoundary(M, chain, length, x, y); RETURN TrimCodedChain(chain, 0, length) END; END END ExtractCodedChainBoundary; PROCEDURE FollowCodedChainBoundary( READONLY M: Image; VAR c: CodedChain; VAR nSteps: CARDINAL; x, y: CARDINAL; ) = (* Given the image "M" of an isolated piece, and a pixel "(x,y)" on the boundary of the piece (such that pixel "(x-1,y)" is outside), follows the piece's boundary counterclockwise. The coded steps are stored in "c", and their number is stored in "nSteps". *) VAR po : PZTypes.IntPos; (* The "outside" foot *) pi : PZTypes.IntPos; (* The "inside" foot *) PROCEDURE Inside(x, y: CARDINAL): BOOLEAN = BEGIN RETURN M[y,x] # 0 END Inside; PROCEDURE Outside(x, y: CARDINAL): BOOLEAN = BEGIN RETURN M[y,x] = 0 END Outside; BEGIN pi := IntPos{x, y}; po := IntPos{x, y-1}; REPEAT WITH xo = po[0], yo = po[1], xi = pi[0], yi = pi[1] DO IF yo = yi-1 THEN IF Inside(xi+1, yi) THEN IF Outside(xo+1, yo) THEN pi[0] := xi+1; po[0] := xo+1; c[nSteps] := 0; ELSE pi[0] := xi+1; pi[1] := yi-1; c[nSteps] := 1; END; ELSE po[0] := xo+1; po[1] := yo+1; c[nSteps] := 2; END; ELSIF yo = yi+1 THEN IF Inside(xi-1, yi) THEN IF Outside(xo-1, yo) THEN pi[0] := xi-1; po[0] := xo-1; c[nSteps] := 0; ELSE pi[0] := xi-1; pi[1] := yi+1; c[nSteps] := 1; END; ELSE po[0] := xo-1; po[1] := yo-1; c[nSteps] := 2; END; ELSIF xo = xi+1 THEN IF Inside(xi, yi+1) THEN IF Outside(xo, yo+1) THEN pi[1] := yi+1; po[1] := yo+1; c[nSteps] := 0; ELSE pi[0] := xi+1; pi[1]:= yi+1; c[nSteps] := 1; END; ELSE po[0] := xo-1; po[1] := yo+1; c[nSteps] := 2; END; ELSIF xo = xi-1 THEN IF Inside(xi, yi-1) THEN IF Outside(xo, yo-1) THEN pi[1] := yi-1; po[1] := yo-1; c[nSteps] := 0; ELSE pi[0] := xi-1; pi[1] := yi-1; c[nSteps] := 1; END; ELSE po[0] := xo+1; po[1] := yo-1; c[nSteps] := 2; END; END; nSteps := nSteps+1; END; UNTIL ( pi[0] = x AND pi[1] = y ) AND nSteps > 1 ; END FollowCodedChainBoundary; PROCEDURE TrimCodedChain(READONLY c: CodedChain; i, n: CARDINAL): REF CodedChain = BEGIN WITH rAuxChain = NEW(REF CodedChain, n) DO rAuxChain^ := SUBARRAY(c, i, n); RETURN rAuxChain END END TrimCodedChain; PROCEDURE DecodeChain(READONLY V: CodedChain): REF IntChain = CONST start = IntPos{0, 0}; VAR pi, po: IntPos; BEGIN WITH N = NUMBER(V), RU = NEW(REF IntChain, N), U = RU^ DO pi:= start; po:= IntPos{start[0], start[1]-1}; FOR i := 0 TO N-1 DO IF po[1] = pi[1]-1 THEN U[i] := pi; CASE V[i] OF | 0 => pi[0]:= pi[0]+1; po[0]:= po[0]+1; | 1 => pi[0] := pi[0]+1; pi[1]:= pi[1]-1; | 2 => po[0] := po[0]+1; po[1] := po[1]+1 END; ELSIF po[1] = pi[1]+1 THEN U[i] := IntPos{pi[0]+1, pi[1]+1}; CASE V[i] OF | 0 => pi[0]:= pi[0]-1; po[0]:= po[0]-1; | 1 => pi[0] := pi[0]-1; pi[1]:= pi[1]+1; | 2 => po[0] := po[0]-1; po[1] := po[1]-1 END; ELSIF po[0] = pi[0]+1 THEN U[i] := IntPos{pi[0]+1, pi[1]}; CASE V[i] OF | 0 => pi[1]:= pi[1]+1; po[1]:= po[1]+1; | 1 => pi[0] := pi[0]+1; pi[1]:= pi[1]+1; | 2 => po[0] := po[0]-1; po[1] := po[1]+1 END; ELSIF po[0] = pi[0]-1 THEN U[i] := IntPos{pi[0], pi[1]+1}; CASE V[i] OF | 0 => pi[1]:= pi[1]-1; po[1]:= po[1]-1; | 1 => pi[0] := pi[0]-1; pi[1]:= pi[1]-1; | 2 => po[0] := po[0]+1; po[1] := po[1]-1 END ELSE <* ASSERT FALSE *> END; END; RETURN RU END END DecodeChain; CodedChain = ARRAY OF [0..2]; (* A fragment outline coded as a sequence of unit steps parallel to the coordinate axes. The steps are coded as "0" (move straight), "1" (turn right), "2" (turn left). *)