#ifndef pz_r3_chain_match_H
#define pz_r3_chain_match_H

/* Matching two {pz_r3_chain_t}s by dynamic programming. */
/* Last edited on 2015-01-20 16:49:51 by stolfilocal */

#include <r3.h>
#include <pz_r3_chain.h>
#include <pz_segment.h>
#include <pz_match.h>
#include <pz_types.h>

/* CHAIN MATCHING BY DYNAMIC PROGRAMMING */

/*
  The procedures "pz_r3_chain_match_find_best" and "pz_r3_chain_match_refine" look for a monotone
  pairing "mt" (a "pz_match_t") between two chains that minimizes some
  measure of the distance between corresponding samples.

  See "pz_mismatch" for the relevant concepts.  These procedures take
  the sample distance "d(a[r], b[s])" to be the Euclidean distance
  between the points "a[r] and "b[s]".

  The procedures return in "length" the total length "Len(mt)" of the
  pairing (average of the lengths of the two chain segments spanned
  by "mt").  They also return in "lengthMatched" the total length of
  the pairing steps whose mean chain distance "dist(S)" was strictly less than
  "maxDist".

  The procedures use internally a working array with "(a.ne)" rows
  and "(b.ne)" columns.  The client may optionally provide an array
  "rCost", at least this big, which will be automatically (re) allocated
  if omitted or too small. */

void pz_r3_chain_match_find_best(
    pz_r3_chain_t *a,
    pz_r3_chain_t *b,
    double maxDistSqr,
    bool_t removeUnmatchedEnds,
    pz_match_t *mt, /* (OUT) */
    double *avgDist, /* (OUT) */
    double *length, /* (OUT) */
    double *matchedLength,  /* (OUT) */
    pz_match_cost_matrix_t *rCost /* (WORK) */
  ) ;
  /*
    Computes (by dynamic programming) a complete monotone pairing
    "mt" between two open chains "a" and "b" that minimizes the
    integrated squared chain distance "IntgDistSqr(mt)".

    This procedure allows the chains to be sampled at arbitrary intervals,
    and takes the metric "h(a,i1,i2)" to be the Euclidean distance
    of the points "a[i1]" and "a[i2]".

    If "removeUnmatchedEnds" is true, the procedure removes any
    initial or final steps "s" whose distance "dist(s)" is equal to
    "maxDist".  Otherwise the pairing "mt" will completely cover the
    two chains. */

void pz_r3_chain_match_refine(
    pz_r3_chain_t *a,
    pz_r3_chain_t *b,
    double step,
    pz_match_t *mtOld,
    unsigned maxAdjust,
    double critDistSqr,
    double maxDistSqr,
    pz_match_t *mt, /* (OUT) */
    double *mismatch, /* (OUT) */
    double *length, /* (OUT) */
    double *matchedLength,  /* (OUT) */
    double_vec_t *minAvgDist, /* (OUT) */
    pz_match_cost_matrix_t *rCost /* (WORK) */
  ) ;
  /*
    Finds (by bidirectional dynamic programming) a partial monotone
    pairing "mt" between the polygonal chains "a" and "b", that is
    a refinement of an `input pairing' "mtOld", and minimizes
    the mismatch "Mis(mt)".

    See "pz_match_refine" for an explanation of the refinement concept,
    and the meaning of "mtOld" and "maxAdjust".  See "pz_mismatch.i3"
    for the definition of the mismatch "Mis(mt)" and the meaning of the parameters
    "critDistSqr" and "maxDistSqr".

    This procedure assumes that the two chains are smooth chains that
    were sampled at uniform intervals of given size "step".
    Therefore, the metric "h(a,i1,i2)" is assumed to be
    "step*(i2-i1)".

    The procedure returns in "minAvgDist[K]", for "K" in
    "[0..na+nb-2]", the root mean square chain distance "dist(s)" of the
    optimum match among all matches with total step count "K".  (Note
    that, if the step count is fixed, the "critDist" term does not
    affect the optimality of the match.)  */

/*
  Copyright © 2001 Universidade Estadual de Campinas (UNICAMP).
  Authors: Helena C. G. Leitão and Jorge Stolfi.

  This file can be freely distributed, used, and modified, provided
  that this copyright and authorship notice is preserved, and that any
  modified versions are clearly marked as such.

  This software has NO WARRANTY of correctness or applicability for
  any purpose. Neither the authors nor their employers chall be held
  responsible for any losses or damages that may result from its use.
*/

#endif