3 template<
typename R>
int Algorithm::binarySearch(
4 const std::vector<double>& values,
int lo,
int hi,
15 Q_ASSERT(mid >=0 && mid < values.size());
16 double epsilon = values[mid];
18 local_fs->calculateFreeSpace(epsilon);
19 R mresult = (this->*decideFunction) (local_fs,no_path,epsilon,
false);
32 template<
typename R>
double Algorithm::intervalSearch(
33 double lower_bound,
double upper_bound,
double precision,
43 while((upper_bound-lower_bound) > precision)
45 mepsilon = (lower_bound+upper_bound)/2;
47 local_fs->calculateFreeSpace(mepsilon);
48 mresult = (this->*decideFunction)(local_fs, no_path, mepsilon,
false);
55 lower_bound = mepsilon;
61 template<
typename Float>
62 Float Algorithm::segment_distance(
const QLineF& segment,
const Point& q1)
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);
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)
84 Float t_denom = 2*((p1x-p2x)*(q1x-q2x) + (p1y-p2y)*(q1y-q2y));
85 if (t_denom==0.0)
return -1;
87 Float t_nom = (q2x + q1x - 2 * p1x)*(q2x - q1x) + (q2y + q1y - 2 * p1y)*(q2y - q1y);
88 Float t = t_nom/t_denom;
90 if (t < -tolerance || t > 1+tolerance)
93 Q_ASSERT(t>=-tolerance && t<=1+tolerance);
95 Float rx = p1x + t*(p2x-p1x);
96 Float ry = p1y + t*(p2y-p1y);
98 euclidean_distance<Float>(rx,ry, q1x,q1y)-
99 euclidean_distance<Float>(rx,ry, q2x,q2y))
101 return euclidean_distance<Float>(rx,ry, q1x,q1y);
104 template<
typename Float>
105 Float Algorithm::bisector_distance(
107 const QLineF& segment,
113 const Point& p1 = segment.p1();
114 const Point& p2 = segment.p2();
116 return bisector_distance<Float> (
117 p1.x(),p1.y(), p2.x(),p2.y(),
118 q1.x(),q1.y(), q2.x(),q2.y(), tolerance);
base class for algorithm for simple polygons.
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
boost::shared_ptr< FSPath > ptr
smart pointer to an FSPath object
double min(double a, double b)
minimum function with checks for NAN
Number abs(const Number &x)
abs() function template for arbitrary numerical types
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object