Code-Eli  0.3.6
length.hpp
Go to the documentation of this file.
1 /*********************************************************************************
2 * Copyright (c) 2013 David D. Marshall <ddmarsha@calpoly.edu>
3 *
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
8 *
9 * Contributors:
10 * David D. Marshall - initial code and implementation
11 ********************************************************************************/
12 
13 #ifndef eli_geom_curve_length_hpp
14 #define eli_geom_curve_length_hpp
15 
16 #include "eli/code_eli.hpp"
17 
18 #include "eli/mutil/quad.hpp"
19 
21 
22 namespace eli
23 {
24  namespace geom
25  {
26  namespace curve
27  {
28  namespace internal
29  {
30  template <typename curve__>
32  {
33  const curve__ *pcurve;
34 
35  typename curve__::data_type operator()(const typename curve__::data_type &t)
36  {
37  return pcurve->fp(t).norm();
38  }
39  };
40  }
41 
42  template<template<typename, unsigned short, typename> class curve__, typename data__, unsigned short dim__, typename tol__>
46  {
47  typedef piecewise<curve__, data__, dim__, tol__> piecewise_type;
48  typedef typename piecewise_type::data_type data_type;
49 
50  typename piecewise_type::segment_collection_type::const_iterator it;
51  data_type seg_len;
52  for (len=0, it=pc.segments.begin(); it!=pc.segments.end(); ++it)
53  {
54  length(seg_len, it->second, tol);
55  len+=seg_len;
56  }
57  }
58  template<template<typename, unsigned short, typename> class curve__, typename data__, unsigned short dim__, typename tol__>
64  {
65  typedef piecewise<curve__, data__, dim__, tol__> piecewise_type;
66  typedef typename piecewise_type::data_type data_type;
67 
68  // short circuit for invalid parameters
69  if (t0>=t1)
70  {
71  len=0;
72  return;
73  }
74 
75  typename piecewise_type::segment_collection_type::const_iterator it, it0, it1;
76  data_type tt0, tt1, seg_len;
77 
78  // calculate the length of the start and end pieces
79  pc.find_segment(it0, tt0, t0);
80  pc.find_segment(it1, tt1, t1);
81  if (it0==it1)
82  {
83  length(len, it0->second, tt0, tt1, tol);
84  return;
85  }
86  length(seg_len, it0->second, tt0, 1, tol);
87  len=seg_len;
88  length(seg_len, it1->second, 0, tt1, tol);
89  len+=seg_len;
90 
91  // add the length of all of the complete segments between the start and end pieces
92  it=it0;
93  for (++it; it!=it1; ++it)
94  {
95  length(seg_len, it->second, tol);
96  len+=seg_len;
97  }
98  }
99 
100  template<typename curve__>
101  void length(typename curve__::data_type &len, const curve__ &c, const typename curve__::data_type &tol)
102  {
103  length(len, c, static_cast<typename curve__::data_type>(0.0), static_cast<typename curve__::data_type>(1.0), tol);
104  }
105  template<typename curve__>
106  void length(typename curve__::data_type &len, const curve__ &c, const typename curve__::data_type &t0, const typename curve__::data_type &t1, const typename curve__::data_type &tol)
107  {
111 
112  // short circuit for invalid parameters
113  if (t0>=t1)
114  {
115  len=0;
116  return;
117  }
118 
119  f.pcurve=&c;
120 
121  // set the specified tolerance
122  ap.tolerance=tol;
123  len=quad(f, t0, t1, ap);
124  }
125 
126 // NOTE: These are here as a reference implementation of an algorithm for bezier curves.
127 // It was written as methods to class, so will need to be rewritten to be an external
128 // function. It didn't seem to be any better than the general algorithm.
129 #if 0
130  data_type length_adaptive_subdivision() const
131  {
132  // NOTE: Implements Adaptive Subdivision method: Jens Gravesen. Adaptive Subdivision and
133  // the length and energy of Bezier curves. Computational Geometry, v8, pp. 13-31, 1997.
134  return internal_length_adaptive_subdivision(SMALL_POS_FLOAT, 0);
135  }
136 
137  data_type internal_length_adaptive_subdivision(const data_type &tol, const index_type &depth) const
138  {
139  data_type L1, Lc, Lp, err;
140  index_type i, n(this->degree()), depth_max(20);
141 
142  // find the length of the control polygon and the chord
143  Lc=dist(b[0], b[n]);
144  Lp=0;
145  for (i=0; i<n; ++i)
146  Lp+=dist(b[i], b[i+1]);
147  L1=(2*Lc+(n-1)*Lp)/(n+1);
148 
149  // calculate error
150  // NOTE: Lp-Lc is order(h^2) approximation to error, so just dividing by h^2 to get
151  // approximation to tighter error bounds
152  err=std::abs(Lp-Lc)/(1<<(2*depth));
153 
154  // if error small enough, converged
155  if ( (err>tol) && (depth<depth_max) )
156  {
157  beziern_curve bc_l, bc_r;
158 
159  // split the curve in half
160  split(bc_l, bc_r, 0.5);
161 
162  // calculate the length using the two segments and halving the tolerances
163  L1=bc_l.internal_length_adaptive_subdivision(tol/2, depth+1)+bc_r.internal_length_adaptive_subdivision(tol/2, depth+1);
164  }
165 
166  return L1;
167  }
168 #endif
169  }
170  }
171 }
172 #endif
curve__::data_type operator()(const typename curve__::data_type &t)
Definition: length.hpp:35
Definition: math.hpp:20
data__ data_type
Definition: piecewise.hpp:276
data__ tolerance
Definition: simpson.hpp:33
Definition: piecewise.hpp:244
const curve__ * pcurve
Definition: length.hpp:33
void length(typename piecewise< curve__, data__, dim__, tol__ >::data_type &len, const piecewise< curve__, data__, dim__, tol__ > &pc, const typename piecewise< curve__, data__, dim__, tol__ >::data_type &tol)
Definition: length.hpp:43
segment_collection_type segments
Definition: piecewise.hpp:1858
void find_segment(typename segment_collection_type::const_iterator &it, const index_type &index) const
Definition: piecewise.hpp:2013
Definition: simpson.hpp:27