Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
structure.h
Go to the documentation of this file.
1 #ifndef STRUCTURE_H
2 #define STRUCTURE_H
3 
4 #include <boundary.h>
5 #include <freespace.h>
6 #include <tbb/tbb.h>
7 
8 namespace frechet {
9 using namespace fs;
10 
11 namespace reach {
12 
13 class StructureIterator;
14 
32 class Structure {
33 
34 private:
38  BoundaryList _boundary[2][2];
42  volatile bool* cancelFlag;
43 
44  friend class StructureIterator;
45  friend class GraphModel;
46  friend class CalculateTask;
47  friend class MergeTask;
48 public:
50  typedef boost::shared_ptr<Structure> ptr;
51 
57  Structure(int concurrency=1, volatile bool* cancelFlag=nullptr);
64  Structure(const FreeSpace::ptr fs, int concurrency=1, volatile bool* cancelFlag=nullptr);
65 
70  Structure(const Structure& that);
75  Structure(Structure&& that);
76 
82  Structure& operator= (const Structure& that);
88  Structure& operator= (Structure&& that);
89 
94  void copy(const Structure& that);
99  void swap(Structure& that);
103  virtual ~Structure();
104 
106  const FreeSpace::ptr freeSpace() const { return fs; }
107 
114  return _boundary[ori][dir];
115  }
116 
122  const BoundaryList& boundary(Orientation ori, Direction dir) const {
123  return _boundary[ori][dir];
124  }
129  BoundaryList& first(Orientation ori) { return _boundary[ori][FIRST]; }
134  BoundaryList& second(Orientation ori) { return _boundary[ori][SECOND]; }
135 
140  const BoundaryList& first(Orientation ori) const { return _boundary[ori][FIRST]; }
145  const BoundaryList& second(Orientation ori) const { return _boundary[ori][SECOND]; }
146 
152  BoundaryList& horizontal(Direction dir) { return _boundary[HORIZONTAL][dir]; }
158  BoundaryList& vertical(Direction dir) { return _boundary[VERTICAL][dir]; }
159 
161  BoundaryList& left() { return _boundary[VERTICAL][FIRST]; }
163  BoundaryList& right() { return _boundary[VERTICAL][SECOND]; }
165  BoundaryList& bottom() { return _boundary[HORIZONTAL][FIRST]; }
167  BoundaryList& top() { return _boundary[HORIZONTAL][SECOND]; }
168 
170  const BoundaryList& left() const { return _boundary[VERTICAL][FIRST]; }
172  const BoundaryList& right() const { return _boundary[VERTICAL][SECOND]; }
174  const BoundaryList& bottom() const { return _boundary[HORIZONTAL][FIRST]; }
176  const BoundaryList& top() const { return _boundary[HORIZONTAL][SECOND]; }
177 
186  Pointer calculate();
187 
193  Pointer calculateDouble();
194 
200  Pointer calculateSingle();
201 
208  void calculateColumns(int i, int j);
209 
210  //
216  void singleCell(int i, int j);
217 
224  void calculateDouble(Orientation fringe);
225 
234  Pointer findStartingPoint(Orientation edge);
235 
241  void shift(Point offset);
242 
249  Pointer next(Pointer p) const;
256  Pointer prev(Pointer p) const;
264  void synchIntervals(Orientation fringe, Structure& that);
265 
266 private:
272  Pointer prevReachable(Pointer p);
278  Pointer nextReachable(Pointer p);
279 
285  void calcRecursive(const Rect& r);
291  void doCalcRecursive(const Rect& r);
292 
293  // Structure Merging
302  void merge(Orientation fringe, Structure& that,
303  const Rect& r1, const Rect& r2);
304  // buildings blocks of the merge process:
314  Pointer split(Pointer seg, double y, Pointer twin);
321  void split2(Pointer& a, double x, Pointer& b);
330  void crossLink(Pointer i1, Pointer i2, Pointer j1, Pointer j2);
337  void merge(BoundaryList& list, Pointer a, Pointer b);
345  void mergeConsecutive(Orientation ori);
351  void scanAndMerge (Pointer K, Orientation fringe);
357  void markNonAccesible(Orientation fringe, Structure& that);
363  void markNonAccesible(Pointer p, Pointer p2);
371  void updatePointers(Pointer K, Pointer l, Pointer h, Pointer K1);
372 
373 
377  data::Interval F[2][2]; // [Orientation][Direction]
379  int arr[2]; // [Orientation]
381  Pointer seg[2][2][5]; // [Orientation][Direction][0..4]
383  PointerInterval P[2][2]; // [Orientation][Direction]
384  };
385 
386 public:
393  static int freeSpaceArrangement(data::Interval LF, data::Interval RF);
394 private:
401  static int freeSpaceArrangement(SingleCellAuxData& aux, Orientation ori);
408  void createSingleCellSegments(SingleCellAuxData& aux, Orientation ori, double y0);
414  void linkSingleCellSegments(SingleCellAuxData& aux, Orientation ori);
420  void clipSeeThroughPointer(Pointer p);
426  PointerInterval reachableInterval(Pointer seg[5]);
437  void create2Segments(Pointer& first, Pointer& second, data::Interval ival, Orientation ori, Type t1, Type t2);
443  void copySegments(BoundaryList& list, Pointer seg[5]);
452  void testCancelFlag();
453 
458  static bool assertSynchedIntervals(Pointer i1, Pointer i2, Pointer i3, Pointer i4);
459 
460 public:
465  static bool assertPointerInterval(Pointer p, const PointerInterval& ival);
466 
468  typedef void (*assert_hook) (
469  Structure*, const Rect*,
470  Structure*, const Rect*,
471  Orientation);
472 
473  static assert_hook after_single_cell, before_merge, after_merge;
475  void takeOwnership();
476 };
477 
489 {
490 private:
492  const Structure& str;
497 
498 public:
505  StructureIterator(const Structure& str, Pointer first, Pointer last);
514  const PointerInterval& ival, Pointer ifnull=nullptr);
515 
520  operator bool() const { return current; }
524  bool operator!() const { return !current; }
525 
529  explicit operator Pointer() { return current; }
534  BoundarySegment& operator *() { return *current; }
538  BoundarySegment* operator ->() { return current; }
544 };
545 
554 {
555 public:
560  StructureTask(Structure* owner);
564  virtual ~StructureTask();
565 
569  virtual void start()=0;
578  static StructureTask* createTask(Structure* owner, const frechet::Rect& r, tbb::flow::graph& graph, int concurrency);
579 
581  typedef tbb::flow::continue_msg msg_t;
583  typedef tbb::flow::continue_node<msg_t> node_t;
584 
589 };
590 
595 public:
602  CalculateTask(Structure* owner, frechet::Rect r, tbb::flow::graph& graph);
606  virtual void start() override;
607 };
608 
612 class MergeTask: public StructureTask {
613 private:
620 public:
628  MergeTask(Structure* owner, frechet::Rect r, tbb::flow::graph& graph, int concurrency);
632  virtual ~MergeTask();
636  virtual void start() override;
637 };
638 
646 std::ostream& operator<< (std::ostream& out, const Structure& str);
647 
648 } } // namespace frechet::reach
649 #endif // STRUCTURE_H
const BoundaryList & right() const
Definition: structure.h:172
BoundaryList & first(Orientation ori)
Definition: structure.h:129
BoundaryList & left()
Definition: structure.h:161
void swap(gpuword **A, gpuword **B)
const BoundaryList & left() const
Definition: structure.h:170
BoundaryList & second(Orientation ori)
Definition: structure.h:134
a sub-task, computing a region of the reachability structure
Definition: structure.h:594
model the mapping of free-space intervals to nodes in a frechet::reach::Graph.
Definition: graph_boost.h:109
task object for parallel execution. When the reachability structur is computed in parallel threads,...
Definition: structure.h:553
boost::shared_ptr< Structure > ptr
smart pointer to a Structure object
Definition: structure.h:50
BoundarySegment & operator *()
Definition: structure.h:534
const FreeSpace::ptr freeSpace() const
Definition: structure.h:106
global definitions for all algorithms.
StructureTask * child2
prerquisite task; only after child1 and child2 are finished, start the merging task
Definition: structure.h:619
tbb::flow::continue_msg msg_t
used to connect nodes in the dependency graph
Definition: structure.h:581
const BoundaryList & second(Orientation ori) const
Definition: structure.h:145
static assert_hook before_merge
Definition: structure.h:473
Direction
direction of a Pointer inside the reachability structure.
Definition: boundary.h:115
Pointer current
current location of the iterator
Definition: structure.h:494
The StructureIterator class.
Definition: structure.h:488
BoundaryList & horizontal(Direction dir)
first or second part of the reachability structure
Definition: structure.h:152
BoundaryList & vertical(Direction dir)
first or second part of the reachability structure
Definition: structure.h:158
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
Definition: boundary.h:285
describes l,h pointers. Both pointers are assumed to point into the same rectangle section (right-top...
Definition: boundary.h:160
Structure * owner
the underlying reachability structure
Definition: structure.h:586
BoundaryList & right()
Definition: structure.h:163
BoundaryList & boundary(Orientation ori, Direction dir)
Definition: structure.h:113
const BoundaryList & top() const
Definition: structure.h:176
aux. data structure that is used to construct an initial reachability cell
Definition: structure.h:375
BoundarySegment * operator ->()
Definition: structure.h:538
volatile bool * cancelFlag
used when running ia a background thread to indicate cancellation by the user
Definition: structure.h:42
BoundarySegment * Pointer
(dumb) pointer to a BoundarySegment object
Definition: boundary.h:55
BoundaryList & top()
Definition: structure.h:167
Pointer last
last segment
Definition: structure.h:496
QPointF Point
a point in the plane; with double floating point precision. This type is heavily used throughout all ...
Definition: types.h:14
a very simple Rectangle structure, with integer boundaries.
Definition: types.h:35
const BoundaryList & first(Orientation ori) const
Definition: structure.h:140
Type
Segment Types.
Definition: boundary.h:17
Orientation
Segment Orientation.
Definition: boundary.h:31
tbb::flow::continue_node< msg_t > node_t
a node in the dependency graph
Definition: structure.h:583
const FreeSpace::ptr fs
the underlying free-space; may be nullptr
Definition: structure.h:36
second segment = right and top edge
Definition: boundary.h:118
const BoundaryList & boundary(Orientation ori, Direction dir) const
Definition: structure.h:122
const Structure & str
the associated reachability structure
Definition: structure.h:492
StructureTask * child1
prerquisite task; only after child1 and child2 are finished, start the merging task
Definition: structure.h:617
#define str(S)
Orientation & operator++(Orientation &ori)
pre-increment an orientation variable. Note that an orientation variable can only be incremented once...
Definition: boundary.h:50
int concurrency
number of parallel threads to use
Definition: structure.h:40
const BoundaryList & bottom() const
Definition: structure.h:174
Structure buddy
structure to merge with
Definition: structure.h:615
The Reachability Structure; maintains a list of intervals on the border of Free Space,...
Definition: structure.h:32
first segment = bottom and left edge
Definition: boundary.h:117
std::ostream & operator<<(std::ostream &out, const Structure &str)
print operator used for debugging; prints diagnostic info about a reachability structure
Definition: structure.cpp:1051
an interval of two double values.
Definition: interval.h:31
node_t * node
a node in the dependency graph
Definition: structure.h:588
BoundaryList & bottom()
Definition: structure.h:165
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
Definition: freespace.h:92
a sub-taks, performing the merging of two reachability structures
Definition: structure.h:612