INTERFACE PZPose;

(* A "PZPose.T" is a placement of a fragment in a specified position. *)
(* Last edited on 2001-11-16 22:52:06 by stolfi *)

IMPORT Wr, Rd;
IMPORT LR4x4, LR2;
IMPORT PZLR3Chain, PZSegment;
FROM PZTypes IMPORT NAT, LONG, BOOL, BOOLS;

TYPE
  T = RECORD
      cvx: CurvePair;  (* Two curve indices. *)
      m: LR4x4.T;      (* Matrix that maps "cvx[0]" so as to fit "cvx[1]". *)
    END;
    (*
      The curve "cvx[1]" may be LAST(NAT), to denote an absolute pose,
      i.e. a transformation to apply to "cvx[0]". *)

  CurvePair = ARRAY [0..1] OF NAT;

  List = ARRAY OF T;
  
PROCEDURE Native(f: NAT): T;
  (*
    An absolute pose for "f" with the identity matrix. *)

PROCEDURE Indeterminate(f: NAT): T;
  (*
    A pose that relates "f" to itself through the identity matrix. *)
  
PROCEDURE Inverse(READONLY P: T): T;
  (* 
    Returns the inverse of "p"'s pose, that is, swaps the two 
    curves and the two matrices. *)

PROCEDURE Compose(READONLY P, Q: T): T;
  (* 
    Given the pose "P" that makes curve "a" fit curve "b", and the pose 
    "Q" that makes "b" fit "c", returns a pose that makes "a" fit "c". *)

PROCEDURE MakeAbsolute(VAR pos: List);
  (*
    Tries to change all relative poses in "pos" to 
    absolute ones. More precisely, after this call,
    every pose "P = pos[k]" is either absolute ("P.cvx[1] = LAST(NAT)"),
    indeterminate ("P.cvx[1] = P.cvx[0]"), or relative to some
    curve for which there is no pose in "pos". 
    
    Fails if "pos" contains two or more poses for the same curve, or
    a non-trivial loop of relative poses. *)

TYPE
  EdgeKind = { Ignored, Tree, Ok, Bad };
  (*
    "Ignored" = not considered (out of range).
    "Tree" = edge belongs to the spanning tree.
    "Ok" = edge is not in the spanning tree but is consistent with it.
    "Bad" = edge is not in the spanning tree and is inconsistent with it.
  *)

PROCEDURE FindClusters(
    READONLY candPose: ARRAY OF T;
    firstPose, lastPose: NAT;
    angTol: LONG;                (* Angular discrepancy tolerance, in radians. *)
    linTol: LONG;                (* Linear discrepancy tolerance. *)
    VAR kind: ARRAY OF EdgeKind; (* Classification of each edge. *)
    VAR joinPose: ARRAY OF T;
    VAR clusterId: ARRAY OF NAT;
  ): REF ARRAY OF REF ARRAY OF NAT;
  (* 
    
    Identifies clusters of connected fragments among a set of
    fragments that are connected by a given list of pairwise relative
    poses "candPose[firstPose..lastPose]".
    
    The procedure also computes a pose "joinPose[f]" for each fragment
    "f" within its cluster, that is consistent with the given relative
    poses. These can be seen as edges of a graph, whose vertices are
    the fragments. The procedure chooses arbitrarily a `root' fragment
    in each conected component of the forest; then, for every fragment
    "f" in that component, it sets "joinPose[f]" to the correct
    placement of fragment "f" with respect to that root. (In
    particular, if "f" is a root fragment, then "joinPose[f]" is an
    absolute pose for "f", with the identity matrix.)
    
    To compute the cluster-relative poses, the procedure computes a
    maximum-confidence spanning forest of the graph, assuming that the
    relative poses are sorted in order of decreasing confidence. Then
    the matrix "joinPose[f].m" is simply the product of the matrices
    "candPose[i].m" (or their inverses, as appropriate), along the
    path in this forest that connects "f" to the root node.
    
    The procedure sets "kind[i]" depending on whether "candPose[i]" was
    part of the spanning forest used to define the absolute poses,
    and, if not, on whether it is consistent with it. here consistent
    means that its matrix is not too different from the previously
    computed absolute poses --- i.e., if the product of all matrices
    along the cycle created by "candPose[i]" has rotation component
    greater tham "angTol", or linear displacement component greater
    than "linTol".
    
    The procedure returns a ragged two-dimensional array "cluster" of
    fragment indices, where each row is a connected component of the
    graph. I..e., "cluster[k][j]" is the "j"th fragment in the "k"th
    component, and NUMBER(cluster[k]^) is the size of that component.
    particular, "cluster[k][0]" is the root fragment. The rows
    are sorted by their root node, and within each row the
    fragments are in increasing order. The procedue also sets
    "clusterId[f] := k" if fragment "f" is part of "cluster[k]". *)

PROCEDURE PlaceSegment(
    READONLY seg: PZSegment.T;
    READONLY chain: PZLR3Chain.T;
    tilt: LONG := 0.0d0;
    shift: LR2.T := LR2.T{0.0d0, 0.0d0};
    flip: BOOL := FALSE;
  ): LR4x4.T;
  (*
    Computes a matrix that, when applied to the given "chain",
    causes its segment "seg" to become horizontal, with midpoint at
    the origin. *)

PROCEDURE ChainsPlaced(READONLY pos: List): REF BOOLS;
  (*
    Returns a vector "used" such that "used[k]" is TRUE 
    iff chain "k" is placed by some pose "pos[i]". *)
    
TYPE
  ReadData = RECORD
      cmt: TEXT;      (* File comments. *)
      pos: REF List;  (* Poses for each fragment. *)
    END;

PROCEDURE Read(rd: Rd.T): ReadData;

PROCEDURE Write(wr: Wr.T; READONLY pos: List; cmt: TEXT);

END PZPose.