Shinya Kitaoka 810553
#pragma once
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef TCG_POLYLINE_OPS_HPP
Toshihiro Shimizu 890ddd
#define TCG_POLYLINE_OPS_HPP
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// tcg includes
Toshihiro Shimizu 890ddd
#include "../polyline_ops.h"
Toshihiro Shimizu 890ddd
#include "../iterator_ops.h"
Toshihiro Shimizu 890ddd
#include "../sequence_ops.h"
Toshihiro Shimizu 890ddd
#include "../point_ops.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// STD includes
Toshihiro Shimizu 890ddd
#include <assert.h></assert.h>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace tcg {
Shinya Kitaoka 120a6e
namespace polyline_ops {
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
using tcg::point_ops::operator/;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//***********************************************************************************
Toshihiro Shimizu 890ddd
//    Standard Deviation Evaluator
Toshihiro Shimizu 890ddd
//***********************************************************************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename ranit=""></typename>
Shinya Kitaoka 120a6e
StandardDeviationEvaluator<ranit>::StandardDeviationEvaluator(</ranit>
Shinya Kitaoka 120a6e
    const RanIt &begin, const RanIt &end)
Shinya Kitaoka 120a6e
    : m_begin(begin), m_end(end) {
Shinya Kitaoka 120a6e
  // Let m_sum[i] and m_sum2[i] be respectively the sums of vertex coordinates
Shinya Kitaoka 120a6e
  //(relative to begin is sufficient) from 0 to i, and the sums of their
Shinya Kitaoka 38fd86
  // squares;
Shinya Kitaoka 120a6e
  // m_sumsMix contain sums of xy terms.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  diff_type i, n = m_end - m_begin;
Shinya Kitaoka 120a6e
  diff_type n2 = n * 2;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  m_sums_x.resize(n);
Shinya Kitaoka 120a6e
  m_sums_y.resize(n);
Shinya Kitaoka 120a6e
  m_sums2_x.resize(n);
Shinya Kitaoka 120a6e
  m_sums2_y.resize(n);
Shinya Kitaoka 120a6e
  m_sums_xy.resize(n);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  m_sums_x[0] = m_sums_y[0] = m_sums2_x[0] = m_sums2_y[0] = m_sums_xy[0] = 0.0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build sums following the path
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  point_type posToBegin;
Shinya Kitaoka 120a6e
  i = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  iterator_type a = m_begin;
Shinya Kitaoka 120a6e
  for (a = m_begin, ++a; a != m_end; ++a, ++i) {
Shinya Kitaoka 120a6e
    posToBegin = point_type(a->x - m_begin->x, a->y - m_begin->y);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    m_sums_x[i + 1]  = m_sums_x[i] + posToBegin.x;
Shinya Kitaoka 120a6e
    m_sums_y[i + 1]  = m_sums_y[i] + posToBegin.y;
Shinya Kitaoka 120a6e
    m_sums2_x[i + 1] = m_sums2_x[i] + sq(posToBegin.x);
Shinya Kitaoka 120a6e
    m_sums2_y[i + 1] = m_sums2_y[i] + sq(posToBegin.y);
Shinya Kitaoka 120a6e
    m_sums_xy[i + 1] = m_sums_xy[i] + posToBegin.x * posToBegin.y;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename ranit=""></typename>
Toshihiro Shimizu 890ddd
typename StandardDeviationEvaluator<ranit>::penalty_type</ranit>
Shinya Kitaoka 120a6e
StandardDeviationEvaluator<ranit>::penalty(const iterator_type &a,</ranit>
Shinya Kitaoka 120a6e
                                           const iterator_type &b) {
Shinya Kitaoka 120a6e
  diff_type aIdx = a - m_begin, bIdx = b - m_begin;
Shinya Kitaoka 120a6e
  point_type v(b->x - a->x, b->y - a->y),
Shinya Kitaoka 120a6e
      a_(a->x - m_begin->x, a->y - m_begin->y);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double n      = b - a;  // Needs to be of higher precision than diff_type
Shinya Kitaoka 120a6e
  double sumX   = m_sums_x[bIdx] - m_sums_x[aIdx];
Shinya Kitaoka 120a6e
  double sumY   = m_sums_y[bIdx] - m_sums_y[aIdx];
Shinya Kitaoka 120a6e
  double sum2X  = m_sums2_x[bIdx] - m_sums2_x[aIdx];
Shinya Kitaoka 120a6e
  double sum2Y  = m_sums2_y[bIdx] - m_sums2_y[aIdx];
Shinya Kitaoka 120a6e
  double sumMix = m_sums_xy[bIdx] - m_sums_xy[aIdx];
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (bIdx < aIdx) {
Shinya Kitaoka 120a6e
    int count = m_end - m_begin, count_1 = count - 1;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    n += count;
Shinya Kitaoka 120a6e
    sumX += m_sums_x[count_1];
Shinya Kitaoka 120a6e
    sumY += m_sums_y[count_1];
Shinya Kitaoka 120a6e
    sum2X += m_sums2_x[count_1];
Shinya Kitaoka 120a6e
    sum2Y += m_sums2_y[count_1];
Shinya Kitaoka 120a6e
    sumMix += m_sums_xy[count_1];
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double A = sum2Y - 2.0 * sumY * a_.y + n * sq(a_.y);
Shinya Kitaoka 120a6e
  double B = sum2X - 2.0 * sumX * a_.x + n * sq(a_.x);
Shinya Kitaoka 120a6e
  double C = sumMix - sumX * a_.y - sumY * a_.x + n * a_.x * a_.y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return sqrt((v.x * v.x * A + v.y * v.y * B - 2 * v.x * v.y * C) / n);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//***********************************************************************************
Toshihiro Shimizu 890ddd
//    Quadratics approximation Evaluator
Toshihiro Shimizu 890ddd
//***********************************************************************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename point=""></typename>
Shinya Kitaoka 120a6e
class _QuadraticsEdgeEvaluator {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  typedef Point point_type;
Shinya Kitaoka 120a6e
  typedef typename tcg::point_traits<point_type>::value_type value_type;</point_type>
Shinya Kitaoka 120a6e
  typedef typename std::vector<point>::iterator cp_iterator;</point>
Shinya Kitaoka 120a6e
  typedef typename tcg::step_iterator<cp_iterator> quad_iterator;</cp_iterator>
Shinya Kitaoka 120a6e
  typedef double penalty_type;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
private:
Shinya Kitaoka 120a6e
  quad_iterator m_begin, m_end;
Shinya Kitaoka 120a6e
  penalty_type m_tol;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  _QuadraticsEdgeEvaluator(const quad_iterator &begin, const quad_iterator &end,
Shinya Kitaoka 120a6e
                           penalty_type tol);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  quad_iterator furthestFrom(const quad_iterator &a);
Shinya Kitaoka 120a6e
  penalty_type penalty(const quad_iterator &a, const quad_iterator &b);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename point=""></typename>
Toshihiro Shimizu 890ddd
_QuadraticsEdgeEvaluator<point>::_QuadraticsEdgeEvaluator(</point>
Shinya Kitaoka 120a6e
    const quad_iterator &begin, const quad_iterator &end, penalty_type tol)
Shinya Kitaoka 120a6e
    : m_begin(begin), m_end(end), m_tol(tol) {}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename point=""></typename>
Toshihiro Shimizu 890ddd
typename _QuadraticsEdgeEvaluator<point>::quad_iterator</point>
Shinya Kitaoka 120a6e
_QuadraticsEdgeEvaluator<point>::furthestFrom(const quad_iterator &at) {</point>
Shinya Kitaoka 120a6e
  const point_type &A  = *at;
Shinya Kitaoka 120a6e
  const point_type &A1 = *(at.it() + 1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build at (opposite) side
Shinya Kitaoka 120a6e
  int atSide_        = -tcg::numeric_ops::sign(cross(A - A1, *(at + 1) - A1));
Shinya Kitaoka 120a6e
  bool atSideNotZero = (atSide_ != 0);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  quad_iterator bt,
Shinya Kitaoka 120a6e
      last = this->m_end - 1;          // Don't do the last (it's a dummy quad)
Shinya Kitaoka 120a6e
  for (bt = at + 1; bt != last; ++bt)  // Always allow 1 step
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    // Trying to reach (bt + 1) from at
Shinya Kitaoka 120a6e
    const point_type &C  = *(bt + 1);
Shinya Kitaoka 120a6e
    const point_type &C1 = *(bt.it() + 1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Ensure that bt is not a corner
Shinya Kitaoka 120a6e
    if (abs(tcg::point_ops::cross(*(bt.it() - 1) - *bt, *(bt.it() + 1) - *bt)) >
Shinya Kitaoka 120a6e
        1e-3)
Shinya Kitaoka 120a6e
      break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Ensure there is no sign inversion
Shinya Kitaoka 120a6e
    int btSide =
Shinya Kitaoka 120a6e
        tcg::numeric_ops::sign(tcg::point_ops::cross(*bt - C1, C - C1));
Shinya Kitaoka 120a6e
    if (atSideNotZero && btSide != 0 && btSide == atSide_) break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Build the approximating new quad if any
Shinya Kitaoka 120a6e
    value_type s, t;
Shinya Kitaoka 120a6e
    tcg::point_ops::intersectionSegCoords(A, A1, C, C1, s, t, 1e-4);
Shinya Kitaoka 120a6e
    if (s == tcg::numeric_ops::NaN<value_type>()) {</value_type>
Shinya Kitaoka 120a6e
      // A-A1 and C1-C are parallel. There are 2 cases:
Shinya Kitaoka 120a6e
      if ((A1 - A) * (C - C1) >= 0)
Shinya Kitaoka 120a6e
        // Either we're still on a straight line
Shinya Kitaoka 120a6e
        continue;
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        // Or, we just can't build the new quad
Shinya Kitaoka 120a6e
        break;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    point_type B(A + s * (A1 - A));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    point_type A_B(A - B);
Shinya Kitaoka 120a6e
    point_type AC_2B(A_B + C - B);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Now, for each quadratic between at and bt, build the 'distance' from our
Shinya Kitaoka 120a6e
    // new
Shinya Kitaoka 120a6e
    // approximating quad (ABC)
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    quad_iterator qt, end = bt + 1;
Shinya Kitaoka 120a6e
    for (qt = at; qt != end; ++qt) {
Shinya Kitaoka 120a6e
      const point_type &Q_A(*qt);
Shinya Kitaoka 120a6e
      const point_type &Q_B(*(qt.it() + 1));
Shinya Kitaoka 120a6e
      const point_type &Q_C(*(qt + 1));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Check the distance of Q_B from the ABC tangent whose direction
Shinya Kitaoka 120a6e
      // is the same as Q'_B - ie, Q_A -> Q_C.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      point_type dir(Q_C - Q_A);
Shinya Kitaoka 120a6e
      value_type dirNorm = tcg::point_ops::norm(dir);
Shinya Kitaoka 120a6e
      if (dirNorm < 1e-4) break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      dir = dir / dirNorm;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      value_type den = tcg::point_ops::cross(AC_2B, dir);
Shinya Kitaoka 120a6e
      if (den < 1e-4 && den > -1e-4) break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      value_type t = tcg::point_ops::cross(A_B, dir) / den;
Shinya Kitaoka 120a6e
      if (t < 0.0 || t > 1.0) break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      value_type t1 = 1.0 - t;
Shinya Kitaoka 120a6e
      point_type P(sq(t1) * A + 2.0 * t * t1 * B + sq(t) * C);
Shinya Kitaoka 120a6e
      point_type Q(0.25 * Q_A + 0.5 * Q_B + 0.25 * Q_C);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (tcg::point_ops::lineDist(Q, P, dir) > m_tol) break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      value_type pos = ((P - Q_A) * dir);
Shinya Kitaoka 120a6e
      if (pos < 0.0 || pos > dirNorm) break;
Shinya Kitaoka 120a6e
      /*if(pos < -m_tol || pos > dirNorm + m_tol)     //Should this be relaxed
Shinya Kitaoka 120a6e
too?
Shinya Kitaoka 120a6e
break;*/
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (qt == bt) continue;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Check the distance of Q_C from the ABC tangent whose direction
Shinya Kitaoka 120a6e
      // is the same as Q'_C.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      dir = tcg::point_ops::direction(Q_B, Q_C);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      den = tcg::point_ops::cross(AC_2B, dir);
Shinya Kitaoka 120a6e
      if (den < 1e-4 && den > -1e-4) break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      t = tcg::point_ops::cross(A_B, dir) / den;
Shinya Kitaoka 120a6e
      if (t < 0.0 || t > 1.0) break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      t1 = 1.0 - t;
Shinya Kitaoka 120a6e
      P  = sq(t1) * A + 2.0 * t * t1 * B + sq(t) * C;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (tcg::point_ops::lineDist(Q_C, P, dir) > m_tol) break;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (qt != end) break;  // Constraints were violated
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return std::min(bt, this->m_end - 1);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename point=""></typename>
Toshihiro Shimizu 890ddd
typename _QuadraticsEdgeEvaluator<point>::penalty_type</point>
Shinya Kitaoka 120a6e
_QuadraticsEdgeEvaluator<point>::penalty(const quad_iterator &at,</point>
Shinya Kitaoka 120a6e
                                         const quad_iterator &bt) {
Shinya Kitaoka 120a6e
  if (bt == at + 1) return 0.0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  penalty_type penalty = 0.0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  const point_type &A(*at);
Shinya Kitaoka 120a6e
  const point_type &A1(*(at.it() + 1));
Shinya Kitaoka 120a6e
  const point_type &C(*bt);
Shinya Kitaoka 120a6e
  const point_type &C1(*(bt.it() - 1));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Build B
Shinya Kitaoka 120a6e
  value_type s, t;
Shinya Kitaoka 120a6e
  tcg::point_ops::intersectionSegCoords(A, A1, C, C1, s, t, 1e-4);
Shinya Kitaoka 120a6e
  if (s == tcg::numeric_ops::NaN<value_type>()) return 0.0;</value_type>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  point_type B(A + s * (A1 - A));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Iterate and build penalties
Shinya Kitaoka 120a6e
  point_type A_B(A - B);
Shinya Kitaoka 120a6e
  point_type AC_2B(A_B + C - B);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  quad_iterator qt, bt_1 = bt - 1;
Shinya Kitaoka 120a6e
  for (qt = at; qt != bt; ++qt) {
Shinya Kitaoka 120a6e
    const point_type &Q_A(*qt);
Shinya Kitaoka 120a6e
    const point_type &Q_B(*(qt.it() + 1));
Shinya Kitaoka 120a6e
    const point_type &Q_C(*(qt + 1));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // point_type dir(tcg::point_ops::direction(Q_A, Q_C));
Shinya Kitaoka 120a6e
    point_type dir(Q_C - Q_A);
Shinya Kitaoka 120a6e
    dir = dir / tcg::point_ops::norm(dir);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    value_type t =
Shinya Kitaoka 120a6e
        tcg::point_ops::cross(A_B, dir) / tcg::point_ops::cross(AC_2B, dir);
Shinya Kitaoka 120a6e
    assert(t >= 0.0 && t <= 1.0);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    value_type t1 = 1.0 - t;
Shinya Kitaoka 120a6e
    point_type P(sq(t1) * A + 2.0 * t * t1 * B + sq(t) * C);
Shinya Kitaoka 120a6e
    point_type Q(0.25 * Q_A + 0.5 * Q_B + 0.25 * Q_C);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    penalty += tcg::point_ops::lineDist(Q, P, dir);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    if (qt == bt_1) continue;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    dir = tcg::point_ops::direction(Q_B, Q_C);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    t = tcg::point_ops::cross(A_B, dir) / tcg::point_ops::cross(AC_2B, dir);
Shinya Kitaoka 120a6e
    assert(t >= 0.0 && t <= 1.0);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    t1 = 1.0 - t;
Shinya Kitaoka 120a6e
    P  = sq(t1) * A + 2.0 * t * t1 * B + sq(t) * C;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    penalty += tcg::point_ops::lineDist(Q_C, P, dir);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return penalty;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//***********************************************************************************
Toshihiro Shimizu 890ddd
//    Conversion to Quadratics functions
Toshihiro Shimizu 890ddd
//***********************************************************************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename cps_reader=""></typename>
Shinya Kitaoka 120a6e
class _QuadReader {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  typedef typename cps_reader::value_type point_type;
Shinya Kitaoka 120a6e
  typedef typename tcg::point_traits<point_type>::value_type value_type;</point_type>
Shinya Kitaoka 120a6e
  typedef typename std::vector<point_type>::iterator cps_iterator;</point_type>
Shinya Kitaoka 120a6e
  typedef typename tcg::step_iterator<cps_iterator> quad_iterator;</cps_iterator>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
private:
Shinya Kitaoka 120a6e
  cps_reader &m_reader;
Shinya Kitaoka 120a6e
  quad_iterator m_it;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  _QuadReader(cps_reader &reader) : m_reader(reader) {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void openContainer(const quad_iterator &it) {
Shinya Kitaoka 120a6e
    m_reader.openContainer(*it);
Shinya Kitaoka 120a6e
    m_it = it;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void addElement(const quad_iterator &it) {
Shinya Kitaoka 120a6e
    if (it == m_it + 1) {
Shinya Kitaoka 120a6e
      m_reader.addElement(*(it.it() - 1));
Shinya Kitaoka 120a6e
      m_reader.addElement(*it);
Shinya Kitaoka 120a6e
    } else {
Shinya Kitaoka 120a6e
      const point_type &A(*m_it);
Shinya Kitaoka 120a6e
      const point_type &A1(*(m_it.it() + 1));
Shinya Kitaoka 120a6e
      const point_type &C(*it);
Shinya Kitaoka 120a6e
      const point_type &C1(*(it.it() - 1));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Build B
Shinya Kitaoka 120a6e
      value_type s, t;
Shinya Kitaoka 120a6e
      tcg::point_ops::intersectionSegCoords(A, A1, C, C1, s, t, 1e-4);
Shinya Kitaoka 120a6e
      point_type B((s == tcg::numeric_ops::NaN<value_type>())</value_type>
Shinya Kitaoka 120a6e
                       ? 0.5 * (A + C)
Shinya Kitaoka 120a6e
                       : A + s * (A1 - A));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      m_reader.addElement(B);
Shinya Kitaoka 120a6e
      m_reader.addElement(C);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    m_it = it;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void closeContainer() { m_reader.closeContainer(); }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename iter_type,="" reader,="" tripletoquadsfunc="" typename=""></typename>
Toshihiro Shimizu 890ddd
void _naiveQuadraticConversion(const iter_type &begin, const iter_type &end,
Shinya Kitaoka 120a6e
                               Reader &reader,
Shinya Kitaoka 120a6e
                               tripleToQuadsFunc &tripleToQuadsF) {
Shinya Kitaoka 120a6e
  typedef typename std::iterator_traits<iter_type>::value_type point_type;</iter_type>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  point_type a, c;
Shinya Kitaoka 120a6e
  iter_type it, jt;
Shinya Kitaoka 120a6e
  iter_type last(end);
Shinya Kitaoka 120a6e
  --last;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (*begin != *last) {
Shinya Kitaoka 120a6e
    reader.openContainer();
Shinya Kitaoka 120a6e
    reader.addElement(*begin);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    ++(it = begin);
Shinya Kitaoka 120a6e
    a = 0.5 * (*begin + *it);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    reader.addElement(0.5 * (*begin + a));
Shinya Kitaoka 120a6e
    reader.addElement(a);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Work out each quadratic
Shinya Kitaoka 120a6e
    for (++(jt = it); jt != end; it = jt, ++jt) {
Shinya Kitaoka 120a6e
      c = 0.5 * (*it + *jt);
Shinya Kitaoka 120a6e
      tripleToQuadsF(a, it, c, reader);
Shinya Kitaoka 120a6e
      a = c;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    reader.addElement(0.5 * (a + *it));
Shinya Kitaoka 120a6e
    reader.addElement(*it);
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    ++(it = begin);
Shinya Kitaoka 120a6e
    point_type first = a = 0.5 * (*begin + *it);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    reader.openContainer();
Shinya Kitaoka 120a6e
    reader.addElement(a);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    for (++(jt = it); jt != end; it = jt, ++jt) {
Shinya Kitaoka 120a6e
      c = 0.5 * (*it + *jt);
Shinya Kitaoka 120a6e
      tripleToQuadsF(a, it, c, reader);
Shinya Kitaoka 120a6e
      a = c;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    tripleToQuadsF(a, last, first, reader);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  reader.closeContainer();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename containers_reader,="" iter_type,="" toquadsfunc="" typename=""></typename>
Toshihiro Shimizu 890ddd
void toQuadratics(iter_type begin, iter_type end, containers_reader &output,
Shinya Kitaoka 120a6e
                  toQuadsFunc &toQuadsF, double reductionTol) {
Shinya Kitaoka 120a6e
  typedef typename std::iterator_traits<iter_type>::difference_type diff_type;</iter_type>
Shinya Kitaoka 120a6e
  typedef typename std::iterator_traits<iter_type>::value_type point_type;</iter_type>
Shinya Kitaoka 120a6e
  typedef typename tcg::point_traits<point_type>::value_type value_type;</point_type>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (begin == end) return;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  diff_type count = std::distance(begin, end);
Shinya Kitaoka 120a6e
  if (count < 2) {
Shinya Kitaoka 120a6e
    // Single point - add 2 points on top of it and quit.
Shinya Kitaoka 120a6e
    output.openContainer(*begin);
Shinya Kitaoka 120a6e
    output.addElement(*begin), output.addElement(*begin);
Shinya Kitaoka 120a6e
    output.closeContainer();
Shinya Kitaoka 120a6e
    return;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (count == 2) {
Shinya Kitaoka 120a6e
    // Segment case
Shinya Kitaoka 120a6e
    iter_type it = begin;
Shinya Kitaoka 120a6e
    ++it;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    output.openContainer(*begin);
Shinya Kitaoka 120a6e
    output.addElement(0.5 * (*begin + *it)), output.addElement(*it);
Shinya Kitaoka 120a6e
    output.closeContainer();
Shinya Kitaoka 120a6e
    return;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build an intermediate vector of points containing the naive quadratic
Shinya Kitaoka 120a6e
  // conversion.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  std::vector<point_type> cps;</point_type>
Shinya Kitaoka 120a6e
  tcg::sequential_reader<std::vector<point_type>> cpsReader(&cps);</std::vector<point_type>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _naiveQuadraticConversion(begin, end, cpsReader, toQuadsF);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (reductionTol <= 0) {
Shinya Kitaoka 120a6e
    output.openContainer(*cps.begin());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Directly output the naive conversion
Shinya Kitaoka 120a6e
    typename std::vector<point_type>::iterator it, end = cps.end();</point_type>
Shinya Kitaoka 120a6e
    for (it = ++cps.begin(); it != end; ++it) output.addElement(*it);
Shinya Kitaoka 120a6e
    output.closeContainer();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    return;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Resize the cps to cover a multiple of 2
Shinya Kitaoka 120a6e
  cps.resize(cps.size() + 2 - (cps.size() % 2));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, launch the quadratics reduction procedure
Shinya Kitaoka 120a6e
  tcg::step_iterator<typename std::vector<point_type="">::iterator> bt(cps.begin(),</typename>
Shinya Kitaoka 120a6e
                                                                    2),
Shinya Kitaoka 120a6e
      et(cps.end(), 2);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _QuadraticsEdgeEvaluator<point_type> eval(bt, et, reductionTol);</point_type>
Shinya Kitaoka 120a6e
  _QuadReader<containers_reader> quadReader(output);</containers_reader>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bool ret = tcg::sequence_ops::minimalPath(bt, et, eval, quadReader);
Shinya Kitaoka 120a6e
  assert(ret);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
}
Shinya Kitaoka 120a6e
}  // namespace tcg::polyline_ops
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
#endif  // TCG_POLYLINE_OPS_HPP