Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
optimise_impl.h
Go to the documentation of this file.
1 
2 
3 template<typename R> int Algorithm::binarySearch(
4  const std::vector<double>& values, int lo, int hi,
5  R (Algorithm::* decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool),
6  R& result)
7 {
8  // (2) binsearch on critical points
9  // operate on private free-space
10  Q_ASSERT(local_fs);
11  reach::FSPath::ptr no_path;
12 
13  while(lo < hi) {
14  int mid = (lo+hi)/2;
15  Q_ASSERT(mid >=0 && mid < values.size());
16  double epsilon = values[mid];
17 
18  local_fs->calculateFreeSpace(epsilon);
19  R mresult = (this->*decideFunction) (local_fs,no_path,epsilon,false);
20 
21  if ((bool)mresult) {
22  hi = mid;
23  result = mresult;
24  }
25  else {
26  lo = mid+1;
27  }
28  }
29  return hi;
30 }
31 
32 template<typename R> double Algorithm::intervalSearch(
33  double lower_bound, double upper_bound, double precision,
34  R (Algorithm::* decideFunction) (FreeSpace::ptr, reach::FSPath::ptr, double, bool),
35  R& result)
36 {
37  Q_ASSERT(local_fs);
38  reach::FSPath::ptr no_path;
39 
40  double mepsilon;
41  R mresult;
42 
43  while((upper_bound-lower_bound) > precision)
44  {
45  mepsilon = (lower_bound+upper_bound)/2;
46 
47  local_fs->calculateFreeSpace(mepsilon);
48  mresult = (this->*decideFunction)(local_fs, no_path, mepsilon, false);
49 
50  if ((bool)mresult) {
51  upper_bound=mepsilon;
52  result=mresult;
53  }
54  else {
55  lower_bound = mepsilon;
56  }
57  }
58  return upper_bound;
59 }
60 
61 template<typename Float>
62 Float Algorithm::segment_distance(const QLineF& segment, const Point& q1)
63 {
64  // distance from a point to a segment
65  Float d1 = euclidean_segment_distance<Float>(segment,q1);
66  Float d2 = euclidean_distance<Float>(segment.p1(),q1);
67  Float d3 = euclidean_distance<Float>(segment.p2(),q1);
68  return min(min(d1,d2),d3);
69  // right ??
70 }
71 
72 template<typename Float>
73 Float Algorithm::bisector_distance(
74  const Float& p1x, const Float& p1y,
75  const Float& p2x, const Float& p2y,
76  const Float& q1x, const Float& q1y,
77  const Float& q2x, const Float& q2y,
78  const Float& tolerance)
79 {
80  // bisector between q1, q2
81  // intersect with segment p1..p2
82  // distance of intersection to q1,q2 (which is equal)
83 
84  Float t_denom = 2*((p1x-p2x)*(q1x-q2x) + (p1y-p2y)*(q1y-q2y));
85  if (t_denom==0.0) return -1;
86 
87  Float t_nom = (q2x + q1x - 2 * p1x)*(q2x - q1x) + (q2y + q1y - 2 * p1y)*(q2y - q1y);
88  Float t = t_nom/t_denom;
89 
90  if (t < -tolerance || t > 1+tolerance)
91  return -1; // bisector does not hit [p1..p2]
92 
93  Q_ASSERT(t>=-tolerance && t<=1+tolerance);
94 
95  Float rx = p1x + t*(p2x-p1x);
96  Float ry = p1y + t*(p2y-p1y);
97  Q_ASSERT(abs(
98  euclidean_distance<Float>(rx,ry, q1x,q1y)-
99  euclidean_distance<Float>(rx,ry, q2x,q2y))
100  <= 1e-9);
101  return euclidean_distance<Float>(rx,ry, q1x,q1y);
102 }
103 
104 template<typename Float>
105 Float Algorithm::bisector_distance(
106  const Point& q1, const Point& q2,
107  const QLineF& segment,
108  Float tolerance)
109 {
110  // bisector between q1, q2
111  // intersect with segment
112  // distance of intersection to q1,q2 (which is equal)
113  const Point& p1 = segment.p1();
114  const Point& p2 = segment.p2();
115 
116  return bisector_distance<Float> (
117  p1.x(),p1.y(), p2.x(),p2.y(),
118  q1.x(),q1.y(), q2.x(),q2.y(), tolerance);
119 }
120 
base class for algorithm for simple polygons.
Definition: algorithm.h:51
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
Definition: types.h:14
boost::shared_ptr< FSPath > ptr
smart pointer to an FSPath object
Definition: fs_path.h:65
double min(double a, double b)
minimum function with checks for NAN
Definition: numeric.h:222
Number abs(const Number &x)
abs() function template for arbitrary numerical types
Definition: numeric.h:91
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
Definition: freespace.h:92