Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
freespace_impl.h
Go to the documentation of this file.
1 
2 namespace frechet { namespace fs {
3 
4 using namespace data;
5 using namespace numeric;
6 
7 template<typename Float>
9  const Point& p, const Point& q, const Point& r,
10  double epsilon,
11  data::Interval& result)
12 {
13  // solve a quadratic equation
14  Float a,b,c,d;
15 
16  a = euclidean_distance_sq<Float>(q,r);
17  if (a==0.0) {
18  /* q==r indicates a duplicate point
19  it would create various problems later (e.g. in Feasible Paths finding).
20  therefore, identical points must be removed on input.
21  */
22  Q_ASSERT(false);
23  result = Interval::INVALID; // invalid
24  return;
25  }
26 
27  Float px = p.x();
28  Float py = p.y();
29  Float qx = q.x();
30  Float qy = q.y();
31  Float rx = r.x();
32  Float ry = r.y();
33 
34  b = 2.0 * ((qx - px) * (rx - qx) + (qy - py) * (ry - qy));
35  c = euclidean_distance_sq<Float>(p,q) - sq<Float>(epsilon);
36 
37  d = sq(b) - 4.0 * a * c;
38 
39  if (d < 0.0 || a==0.0) {
40  result = Interval::INVALID; // invalid
41  return;
42  }
43 
44  Float sqrtd = sqrt<Float>(d);
45  result.lower() = (double)((-b - sqrtd) / (2.0*a));
46  result.upper() = (double)((-b + sqrtd) / (2.0*a));
47 
48  result &= Interval::UNIT;
49  if (result.empty())
50  result = Interval::INVALID; // invalid
51 }
52 
53 } } // namespace
static const Interval INVALID
an invalid interval (contains NAN values)
Definition: interval.h:39
global definitions for all algorithms.
static void calculateFreeSpaceSegment(const Point &p, const Point &q, const Point &r, double epsilon, data::Interval &result)
compute intervals for one point and segment. As parameters we expect a point on one curve (P,...
Definition: freespace_impl.h:8
bool empty() const
empty test
Definition: interval.h:79
double upper() const
Definition: interval.h:96
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
Definition: types.h:14
double lower() const
Definition: interval.h:92
static const Interval UNIT
the unit interval [0,1]
Definition: interval.h:37
Number sq(const Number &x)
square function template for arbitrary number types
Definition: numeric.h:61
an interval of two double values.
Definition: interval.h:31