Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
fs_path.h
Go to the documentation of this file.
1 #ifndef REACHABILITY_H
2 #define REACHABILITY_H
3 
4 #include <freespace.h>
5 #include <boundary.h>
6 #include <poly/types.h>
7 
8 
9 namespace frechet { namespace reach {
10 
11 using namespace data;
12 using namespace fs;
13 using namespace poly;
14 
44 class FSPath {
45 
46 protected:
50  bool wrapTop;
52  bool wrapRight;
58  Curve path[2];
59 public:
61  static const double PRECISION;
62 
63 public:
65  typedef boost::shared_ptr<FSPath> ptr;
66 
75  virtual ~FSPath() {}
76 
80  bool empty() const {
81  return path[0].empty() && path[1].empty();
82  }
89  Curve getPath(int i) const;
90 
98  void mapFromP(Segment pseg, Curve result[2]) const;
99  void mapFromQ(Segment pseg, Curve result[2]) const;
100 
101  void mapToP(Curve path[2]) const;
102  void mapToQ(Curve path[2]) const;
103 
104  Point mapFromP(int p) const;
105  Point mapFromQ(int q) const;
106 
107  double mapFromPToQ(int p) const;
108  double mapFromQToP(int q) const;
109 
110  const frechet::data::Interval& left(int i, int j) const {
111  return LR.at(i,j);
112  }
113 
114  const frechet::data::Interval& bottom(int i, int j) const {
115  return BR.at(i,j);
116  }
117 
118  const Curve& fixPoints() const { return fix; }
119 
120  void clearReachability();
121 
122  virtual void clear();
123 
131  void calculateReachability(Point start, Point end, bool allow_wrap, double prec=PRECISION);
132 
139  void update(Point start, double epsilon);
140 
146  Point toPoint(Pointer segment);
147 
156  bool isReachable(int i, int j, double prec=PRECISION) const;
164  bool isReachable(Point a, double prec=PRECISION) const;
168  Point startPoint() const { return fix.first(); }
169 
178  static Interval opposite(const Interval& LR, const Interval& RF);
179 
180 public:
191  static void propagate(const Interval& RF, const Interval& TF,
192  const Interval& LR, const Interval& BR,
193  Interval& RR, Interval& TR);
194 protected:
196  FSPath();
197 
199  void calculatePath();
200 
209  void findPathSegment(Point a, Point b, Curve curve[2], int& cc);
217  bool propagateHorizontalEdge(Point a, double bx, double prec=PRECISION);
225  bool propagateVerticalEdge(Point a, double by, double prec=PRECISION);
234  void propagateInner(int i, int j, double bx, double by);
243  void propagateBottom(int i, int j, double bx, double by);
247  int next_hor(int i);
251  int next_vert(int j);
260  bool left_contains(int i, int j, double y, double prec=PRECISION) const;
269  bool bottom_contains(int i, int j, double x, double prec=PRECISION) const;
270 
279  void propagateColumn(int i, int j0, double bx, double by, bool allow_wrap);
288  void propagateBottom(int i, int j0, double bx, double by, bool allow_wrap);
298  static double mapToSegment(double a, Point p1, Point p2);
304  static void append(std::vector<double>& map, double x);
305 
312  static int binSearchX(const Curve& curve, int x);
319  static int binSearchY(const Curve& curve, int y);
327  static void copy(Curve& dest, const Curve& source, int i, int j);
339  static bool are_consistent(Curve path0, Curve path1, int n, int m);
340  //void copy2Sections(Curve dest[2], int i1, int j1, int i2, int j2) const;
341 };
342 
343 
344 } } // namespace frechet::reach
345 
346 #endif // REACHABILITY_H
Represents a polygon line segment from node i to j.
Definition: types.h:39
bool wrapTop
free-space wraps at top, Q is closed
Definition: fs_path.h:50
global definitions for all algorithms.
Point startPoint() const
Definition: fs_path.h:168
const frechet::data::Interval & left(int i, int j) const
Definition: fs_path.h:110
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
Definition: boundary.h:285
bool empty() const
Definition: fs_path.h:80
bool wrapRight
free-space wraps right, P is closed
Definition: fs_path.h:52
const frechet::data::Interval & bottom(int i, int j) const
Definition: fs_path.h:114
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
QPolygonF Curve
a polygonal curve in the plane; with double floating point precision. This type is heavily used throu...
Definition: types.h:20
virtual ~FSPath()
destructor
Definition: fs_path.h:75
A simple two-dimensional array of fixed size.
Definition: array2d.h:19
Curve fix
fix points
Definition: fs_path.h:56
static const double PRECISION
floating point precision
Definition: fs_path.h:61
Array2D< Interval > LR
reachable intervals
Definition: fs_path.h:54
Orientation opposite(Orientation ori)
Definition: boundary.h:39
const Curve & fixPoints() const
Definition: fs_path.h:118
an interval of two double values.
Definition: interval.h:31
T & at(int i, int j)
array accessor
Definition: array2d.h:54
FreeSpace::ptr fs
underlying free-space
Definition: fs_path.h:48
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
Definition: freespace.h:92
Calculates a feasible path in the Free-Space given a start point (0,0) and an end point (n-1,...
Definition: fs_path.h:44