Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
boundary.cpp
Go to the documentation of this file.
1 
2 #include <boundary.h>
3 
4 
5 using namespace frechet;
6 using namespace reach;
7 using namespace data;
8 
9 BoundarySegment::BoundarySegment(const Interval &ival, Orientation anori, Direction adir, Type t, void* owner)
11  Interval(ival),
13  ori(anori), dir(adir),
14  type(t)
15 {
16  temp.clone=nullptr;
17 #ifdef QT_DEBUG
18  temp.owner=owner;
19 #endif
20 }
21 
23 
26 {
27  Q_ASSERT(!a && !b || a && b && (a->dir==b->dir));
28 }
29 
31  return !l || !h;
32 }
33 
35  l = h = p;
36  return *this;
37 }
38 
40  if (doit) std::swap(l,h);
41  return *this;
42 }
43 
45  return {h,l};
46 }
47 
48 
50 {
51  if(!a) return b;
52  if(!b) return a;
53 
54  if ((a->lower() < b->lower()) || (a->upper() < b->upper()))
55  return a;
56  else
57  return b;
58 }
59 
61 {
62  return min(a.l, a.h);
63 }
64 
66 {
68 }
69 
71 {
72  if(!a) return b;
73  if(!b) return a;
74 
75  if ((a->lower() > b->lower()) || (a->upper() > b->upper()))
76  return a;
77  else
78  return b;
79 }
80 
82 {
83  return frechet::reach::max(a.l,a.h);
84 }
85 
87 {
89 }
90 
93 {
94  if (!*this) return *this;
95 
96  Q_ASSERT(l->ori==h->ori);
97 
98  if (l->ori==VERTICAL)
99  return { frechet::reach::min(*this), frechet::reach::max(*this) }; // vertical UP
100  else
101  return { frechet::reach::max(*this), frechet::reach::min(*this) }; // horizontal REVERSED
102 }
103 
106 {
107  if(!*this) return b.normalized();
108  if(!b) return this->normalized();
109 
110  Q_ASSERT(l->ori==h->ori);
111  Q_ASSERT(b.l->ori==b.h->ori);
112 
113  Q_ASSERT(l->dir==b.l->dir);
114 
115  if (l->ori == b.l->ori) {
116  if (l->ori==VERTICAL)
117  return { frechet::reach::min(*this,b), frechet::reach::max(*this,b) }; // vertical + vertical
118  else
119  return { frechet::reach::max(*this,b),frechet::reach:: min(*this,b) }; // horizonzal + horizontal
120  }
121  else
122  {
123  Q_ASSERT(l->ori != b.l->ori);
124  if (l->dir==CLOCKWISE)
125  {
126  // clockwise: horizontal + vertical
127  if (l->ori==HORIZONTAL)
128  return { frechet::reach::max(*this), frechet::reach::max(b) };
129  else
130  return { frechet::reach::max(b), frechet::reach::max(*this) };
131  }
132  else
133  {
134  // counter-clockwise: vertical + horizontal
135  if (l->ori==VERTICAL)
136  return { frechet::reach::min(*this), frechet::reach::min(b) };
137  else
138  return { frechet::reach::min(b), frechet::reach::min(*this) };
139  }
140  }
141 }
142 
143 frechet::reach::PointerInterval::operator bool() const {
144  return l && h;
145 }
146 
149 {
150  if (p==q) return 0;
151 
152  Q_ASSERT(p->dir==q->dir);
153  int c1,c2;
154 
155  // dir==SECOND (right-top) --> VERTICAL < HORIZONTAL
156  // dir==FIRST (bottom-left) --> VERTICAL > HORIZONTAL
157 
158  switch(p->ori) {
159  case HORIZONTAL:
160  switch(q->ori) {
161  case HORIZONTAL:
162  c1 = numeric::compare(p->lower(),q->lower());
163  c2 = numeric::compare(p->upper(),q->upper());
164  return - (c1 ? c1 : c2);
165  case VERTICAL:
166  return (p->dir==FIRST) ? -1 : +1; // HORIZONTAL < VERTICAL
167  }
168  break;
169 
170  case VERTICAL:
171  switch(q->ori) {
172  case HORIZONTAL:
173  return (p->dir==FIRST) ? +1 : -1; // VERTICAL > HORIZONTAL
174  case VERTICAL:
175  c1 = numeric::compare(p->lower(),q->lower());
176  c2 = numeric::compare(p->upper(),q->upper());
177  return c1 ? c1 : c2;
178  }
179  break;
180  }
181  Q_ASSERT(false);
182 }
183 
184 
185 
187 {
188  return compare_interval(i.l,i.h);
189 }
190 
192 {
193  Q_ASSERT(a && b);
194  return compare_interval(a,b) > 0;
195 }
196 
198 {
199  return empty_interval(i.l,i.h);
200 }
201 
204 {
205  Q_ASSERT(p->type==SEE_THROUGH);
206  Q_ASSERT(!p->l || !p->h);
207  if (p->l)
208  return (p->dir==FIRST) ? (compare_pointers(p,p->l) > 0) : (compare_pointers(p,p->l) < 0);
209  else
210  return (p->dir==FIRST) ? (compare_pointers(p,p->h) > 0) : (compare_pointers(p,p->h) < 0);
211 }
212 
215 {
216  if (p==q) return 0;
217 
218  Q_ASSERT(p->dir != q->dir);
219  int c1,c2;
220 
221  switch(p->ori) {
222  case HORIZONTAL:
223  switch(q->ori) {
224  case HORIZONTAL:
225  c1 = numeric::compare(p->lower(),q->lower());
226  c2 = numeric::compare(p->upper(),q->upper());
227  return c1 ? c1 : c2;
228  case VERTICAL:
229  return (p->dir==FIRST) ? -1 : +1;
230  }
231  break;
232 
233  case VERTICAL:
234  switch(q->ori) {
235  case HORIZONTAL:
236  return (p->dir==FIRST) ? -1 : +1;
237  case VERTICAL:
238  c1 = numeric::compare(p->lower(),q->lower());
239  c2 = numeric::compare(p->upper(),q->upper());
240  return c1 ? c1 : c2;
241  }
242  break;
243  }
244  Q_ASSERT(false);
245 }
246 
247 
249 {
250  if (p==l || p==h) return true;
251 
252  return (compare_interval(p,l) >= 0) && (compare_interval(p,h) <= 0);
253 }
254 
256 {
257  l = h = nullptr;
258 }
259 
260 static std::string DIRECTION[2][2] = {
261  { "B", "T" }, { "L","R" }
262 };
263 
264 const std::string direction(Pointer p) {
265  return DIRECTION[p->ori][p->dir];
266 }
267 
268 static std::string TYPE[3] = {
269  "n","r","s"
270 };
271 
272 std::ostream& frechet::reach::operator<<(std::ostream &out, const BoundaryList &list)
273 {
274  if (list.empty()) {
275  out << "[]";
276  return out;
277  }
278 
279  Pointer p=list.first();
280  out << "[" << direction(p) << ": ";
281 
282  int i=0; int imax=10;
283  for( ; p && i < imax; p=p->next(), ++i)
284  {
285  if (i > 0) out << ",";
286  out << "("<< TYPE[p->type];
287  if (i==0) out<<" "<<p->lower();
288  out << ".."<< p->upper();
289 
290  if (p->l) out << " l="<<direction(p->l)<<".."<<p->l->upper();
291  if (p->h) out << " h="<<direction(p->h)<<".."<<p->h->upper();
292  out << ")";
293  }
294  if (i >= imax && list.size() > imax)
295  out << "...(" << (list.size()-imax)<<")";
296  out << "]";
297  return out;
298 }
bool empty_see_through_interval(Pointer p)
test intersection of intervals. Assumes a SEE_THROUGH segment.
Definition: boundary.cpp:203
Pointer max(const Pointer a, const Pointer b)
maximum of two reachability intervals; compare lower bound, then upper bound
Definition: boundary.cpp:70
void swap(gpuword **A, gpuword **B)
Pointer min(const Pointer a, const Pointer b)
minimum of two reachability intervals; compare lower bound, then upper bound
Definition: boundary.cpp:49
PointerInterval operator+(const PointerInterval &that) const
merge operator
Definition: boundary.cpp:105
clockwise interval (bottom-then-left)
Definition: boundary.h:132
void clear()
clear both pointer (assgin nullptr)
Definition: boundary.cpp:255
Point normalized(Point p)
normalize a vector to unit length
Definition: numeric.h:265
PointerInterval & swap(bool doit=true)
conditional swap
Definition: boundary.cpp:39
see-through: other interals are visible with a straight line
Definition: boundary.h:23
global definitions for all algorithms.
PointerInterval swapped() const
Definition: boundary.cpp:44
const Orientation ori
horizontal or vertical
Definition: boundary.h:318
Direction
direction of a Pointer inside the reachability structure.
Definition: boundary.h:115
static std::string DIRECTION[2][2]
Definition: boundary.cpp:260
struct frechet::reach::BoundarySegment::@4 temp
temporary data used during merge and split operations
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
PointerInterval()
empty constructor; constructs an invalid interval, with both pointers being nullptr
Definition: boundary.cpp:22
double upper() const
Definition: interval.h:96
int compare_pointers(Pointer a, Pointer b)
compare two pointers on opposite parts of a reachability structure (eitehr left->right-top,...
Definition: boundary.cpp:214
int compare(double a, double b)
comparator function
Definition: numeric.h:254
BoundarySegment * Pointer
(dumb) pointer to a BoundarySegment object
Definition: boundary.h:55
Type type
reachability label
Definition: boundary.h:317
PointerInterval normalized() const
assumes identical orientation !!
Definition: boundary.cpp:92
std::ostream & operator<<(std::ostream &out, const BoundaryList &list)
print operator for debugging
Definition: boundary.cpp:272
Type
Segment Types.
Definition: boundary.h:17
PointerInterval & operator=(const Pointer &p)
assigment
Definition: boundary.cpp:34
Orientation
Segment Orientation.
Definition: boundary.h:31
double lower() const
Definition: interval.h:92
const Direction dir
left/right or bottom/top
Definition: boundary.h:319
Pointer l
points to the lowest segment of the interval
Definition: boundary.h:161
int compare_interval(Pointer a, Pointer b)
compare two pointers in the same part of a reachability structure (either right-top,...
Definition: boundary.cpp:148
bool contains(Pointer p) const
containment test
Definition: boundary.cpp:248
BoundarySegment(const Interval &ival, Orientation ori, Direction dir, Type t, void *owner=nullptr)
default constructor
Definition: boundary.cpp:9
Pointer h
points to the highest segment of the interval
Definition: boundary.h:162
first segment = bottom and left edge
Definition: boundary.h:117
base template for elements of a LinkedList
Definition: linkedlist.h:54
an interval of two double values.
Definition: interval.h:31
static std::string TYPE[3]
Definition: boundary.cpp:268
const std::string direction(Pointer p)
Definition: boundary.cpp:264
bool empty_interval(Pointer a, Pointer b)
test intersection of intervals
Definition: boundary.cpp:191