Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
str_singlecell.cpp
Go to the documentation of this file.
1 
2 #include <structure.h>
3 #include <numeric.h>
4 
5 using namespace frechet;
6 using namespace data;
7 using namespace reach;
8 using namespace numeric;
9 
10 void Structure::singleCell(int i, int j)
11 {
12  // Free-Space intervals:
13  SingleCellAuxData aux;
14  aux.F[VERTICAL][FIRST] = fs->cell(i,j).L + (double)j; // left
15  aux.F[HORIZONTAL][FIRST] = fs->cell(i,j).B + (double)i; // bottom
16  aux.F[VERTICAL][SECOND] = fs->cell(i+1,j).L + (double)j; // right
17  aux.F[HORIZONTAL][SECOND] = fs->cell(i,j+1).B + (double)i; // top
18 
19  // create segments
20  for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
21  aux.arr[ori] = freeSpaceArrangement(aux, ori);
22 
29  // create segments, store in *seg
30  memset(aux.seg, 0, 2*2*5*sizeof(Pointer));
31 
32  createSingleCellSegments(aux, HORIZONTAL, i);
33  createSingleCellSegments(aux, VERTICAL, j);
34 
35  // calculate lowest,highest segment on each edge
36  for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
37  for(Direction dir=FIRST; dir <= SECOND; ++dir)
38  aux.P[ori][dir] = reachableInterval(aux.seg[ori][dir]);
39 
40  // link l,h pointers
41  for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
42  linkSingleCellSegments(aux, ori);
43 
44  // copy arrays to linked list
45  for(Orientation ori=HORIZONTAL; ori <= VERTICAL; ++ori)
46  for(Direction dir=FIRST; dir <= SECOND; ++dir)
47  copySegments(boundary(ori,dir), aux.seg[ori][dir]);
48 
49 #ifdef QT_DEBUG
50  frechet::Rect r (i,j, i+1,j+1);
51  Q_ASSERT(!after_single_cell || (after_single_cell(this, &r,
52  nullptr, nullptr, HORIZONTAL),true));
53 #endif
54 }
55 
56 int Structure::freeSpaceArrangement(SingleCellAuxData& aux, Orientation ori)
57 {
58  Interval LF = aux.F[ori][FIRST];
59  Interval RF = aux.F[ori][SECOND];
60 
61  return freeSpaceArrangement(LF,RF);
62 }
63 
64 int Structure::freeSpaceArrangement(Interval LF, Interval RF)
65 {
66  if (!LF && !RF) // (0) completely empty
67  return 0;
68 
69  if (LF && !RF) // (1) left reachable, right not
70  return 1;
71 
72  if (!LF && RF) // (2) right reachable
73  return 2;
74 
75  Q_ASSERT(LF && RF);
76 
77  if (LF.lower() < RF.lower())
78  {
79  // (I)
80  // |
81  // | ---
82  // ---
83 
84  if (LF.upper() < RF.lower())
85  // ---
86  // |
87  // ---
88  //
89  // ---
90  // |
91  // ---
92  return 3;
93 
94  if (LF.upper() == RF.lower())
95  // ---
96  // |
97  // --- ---
98  // |
99  // ---
100  return (RF.upper() > LF.upper()) ? 4:6;
101 
102  Q_ASSERT(LF.upper() > RF.lower());
103  // --- |
104  // | ---
105  // ---
106 
107  if (RF.upper() < LF.upper())
108  // ---
109  // | ---
110  // | |
111  // | ---
112  // ---
113  return 5;
114 
115  if (RF.upper() == LF.upper())
116  // --- ---
117  // | |
118  // | ---
119  // |
120  // ---
121  return 6;
122 
123  Q_ASSERT(RF.upper() > LF.upper());
124  // ---
125  // |
126  // --- |
127  // | |
128  // | ---
129  // |
130  // ---
131  return 7;
132  }
133  if (LF.lower() == RF.lower())
134  {
135  // (II)
136  // | |
137  // --- ---
138 
139  if (LF.upper() < RF.upper())
140  // ---
141  // |
142  // --- |
143  // | |
144  // --- ---
145  return 8;
146 
147  if (LF.upper() == RF.upper())
148  // --- ---
149  // | |
150  // --- ---
151  return 9;
152 
153  Q_ASSERT(LF.upper() > RF.upper());
154  // ---
155  // |
156  // | ---
157  // | |
158  // --- ---
159  return 10;
160  }
161  Q_ASSERT(LF.lower() > RF.lower());
162  // (III)
163  // | |
164  // --- |
165  // ---
166  {
167  if (RF.upper() < LF.lower())
168  // ---
169  // |
170  // ---
171  //
172  // ---
173  // |
174  // ---
175  return 11;
176 
177  if (RF.upper() == LF.lower())
178  // ---
179  // |
180  // --- ---
181  // |
182  // ---
183  return 12;
184 
185  Q_ASSERT(RF.upper() > LF.lower());
186  // | ---
187  // --- |
188  // |
189  // ---
190  {
191  if (LF.upper() < RF.upper())
192  // ---
193  // |
194  // --- |
195  // | |
196  // --- |
197  // |
198  // ---
199  return 13;
200  if (LF.upper() == RF.upper())
201  // --- ---
202  // | |
203  // --- |
204  // |
205  // ---
206  return 14;
207 
208  Q_ASSERT(LF.upper() > RF.upper());
209  // ---
210  // |
211  // | ---
212  // | |
213  // --- |
214  // |
215  // ---
216  return 15;
217  }
218  }
219 
220  Q_ASSERT(false); // never come here
221 }
222 
223 
224 void Structure::createSingleCellSegments(SingleCellAuxData& aux, Orientation ori, double y0)
225 {
226  Interval LF = aux.F[ori][FIRST];
227  Interval RF = aux.F[ori][SECOND];
228  bool BF = aux.F[opposite(ori)][FIRST];
229  bool TF = aux.F[opposite(ori)][SECOND];
230 
231  Pointer *left = aux.seg[ori][FIRST];
232  Pointer *right = aux.seg[ori][SECOND];
233 
234  Interval all (y0, y0+1);
235  Interval set ( // LF u RF
236  numeric::min(LF.lower(),RF.lower()),
237  numeric::max(LF.upper(),RF.upper()) );
238 
239  // handle all cases of overlapping intervals
240  switch(aux.arr[ori])
241  {
242  case 0: // (0) completely empty
243  set.clear();
244  break;
245  case 1: // (1) left reachable, right not
246  if (TF)
247  create2Segments(left[2],right[2], LF, ori, REACHABLE, NON_ACCESSIBLE);
248  else
249  set.clear();
250  break;
251  case 2: // (2) right reachable
252  if (BF)
253  create2Segments(left[2],right[2], RF, ori, NON_ACCESSIBLE, REACHABLE);
254  else
255  set.clear();
256  break;
257  case 3:
258  create2Segments(left[2],right[2], {LF.upper(),RF.lower()}, ori, NON_ACCESSIBLE, NON_ACCESSIBLE);
259  // fall-through intended
260  case 4:
261  // ---
262  // | [3] = RP
263  // ---
264  // ([2] = n)
265  // ---
266  // | [1] = LP
267  // ---
268  create2Segments(left[3],right[3], RF, ori, NON_ACCESSIBLE, REACHABLE);
269  create2Segments(left[1],right[1], LF, ori, REACHABLE, NON_ACCESSIBLE);
270  break;
271  case 5:
272  // ---
273  // | [3] = LP
274  // | ---
275  // | | [2] = RP
276  // | ---
277  // | [1] = LP
278  // ---
279  if (TF)
280  create2Segments(left[3],right[3], {RF.upper(),LF.upper()}, ori, REACHABLE, NON_ACCESSIBLE);
281  else
282  set.upper() = RF.upper();
283  create2Segments(left[2],right[2], RF, ori, SEE_THROUGH,SEE_THROUGH);
284  create2Segments(left[1],right[1], {LF.lower(),RF.lower()}, ori, REACHABLE, NON_ACCESSIBLE);
285  break;
286  case 6:
287  // --- ---
288  // | | [2] = LP,RP
289  // | ---
290  // | [1] = LP
291  // ---
292  create2Segments(left[2],right[2], RF, ori, SEE_THROUGH,SEE_THROUGH);
293  create2Segments(left[1],right[1], {LF.lower(),RF.lower()}, ori, REACHABLE, NON_ACCESSIBLE);
294  break;
295  case 7:
296  // ---
297  // | [3] = RP
298  // --- |
299  // | | [2] = LP,RP
300  // | ---
301  // | [1] = LP
302  // ---
303  create2Segments(left[3],right[3], {LF.upper(),RF.upper()}, ori, NON_ACCESSIBLE, REACHABLE);
304  create2Segments(left[2],right[2], {RF.lower(),LF.upper()}, ori, SEE_THROUGH, SEE_THROUGH);
305  create2Segments(left[1],right[1], {LF.lower(),RF.lower()}, ori, REACHABLE, NON_ACCESSIBLE);
306  break;
307  case 8:
308  // ---
309  // | [3] = RP
310  // --- |
311  // | | [2] = RP,LP
312  // --- ---
313  create2Segments(left[3],right[3], {LF.upper(),RF.upper()}, ori, NON_ACCESSIBLE, REACHABLE);
314  create2Segments(left[2],right[2], LF, ori, SEE_THROUGH,SEE_THROUGH);
315  break;
316  case 9:
317  Q_ASSERT(LF==RF);
318  // --- ---
319  // | | [2]
320  // --- ---
321  create2Segments(left[2],right[2], LF, ori, SEE_THROUGH,SEE_THROUGH);
322  break;
323  case 10:
324  // ---
325  // | [3]
326  // | ---
327  // | | [2]
328  // --- ---
329  if (TF)
330  create2Segments(left[3],right[3], {RF.upper(),LF.upper()}, ori, REACHABLE, NON_ACCESSIBLE);
331  else
332  set.upper() = RF.upper();
333  create2Segments(left[2],right[2], RF, ori, SEE_THROUGH,SEE_THROUGH);
334  break;
335  case 11:
336  if (TF && BF)
337  create2Segments(left[2],right[2], {RF.upper(),LF.lower()}, ori, NON_ACCESSIBLE,NON_ACCESSIBLE);
338  // fall-through intended
339  case 12:
340  // ---
341  // | [3] = LP
342  // ---
343  // ([2] = n)
344  // ---
345  // | [1] = RP
346  // ---
347  // the right edge can only be seen from the bottom edge
348  if (!TF && !BF)
349  set.clear();
350  else {
351  if (TF)
352  create2Segments(left[3],right[3], LF, ori, REACHABLE, NON_ACCESSIBLE);
353  else
354  set.upper() = RF.upper();
355  if (BF)
356  create2Segments(left[1],right[1], RF, ori, NON_ACCESSIBLE, REACHABLE);
357  else
358  set.lower() = LF.lower();
359  }
360  break;
361  case 13:
362  // ---
363  // | [3] = RP
364  // --- |
365  // | | [2] = LP
366  // --- |
367  // | [1] = RP
368  // ---
369  create2Segments(left[3],right[3], {LF.upper(),RF.upper()}, ori, NON_ACCESSIBLE, REACHABLE);
370  create2Segments(left[2],right[2], LF, ori, SEE_THROUGH,SEE_THROUGH);
371  if (BF)
372  create2Segments(left[1],right[1], {RF.lower(),LF.lower()}, ori, NON_ACCESSIBLE, REACHABLE);
373  else
374  set.lower() = LF.lower();
375  break;
376  case 14:
377  // --- ---
378  // | | [2]
379  // --- |
380  // | [1]
381  // ---
382  create2Segments(left[2],right[2], LF, ori, SEE_THROUGH,SEE_THROUGH);
383  if (BF)
384  create2Segments(left[1],right[1], {RF.lower(),LF.lower()}, ori, NON_ACCESSIBLE, REACHABLE);
385  else
386  set.lower() = LF.lower();
387  break;
388  case 15:
389  // ---
390  // | [3] = LP
391  // | ---
392  // | | [2] = LP,RP
393  // --- |
394  // | [1] = LP
395  // ---
396  if (TF)
397  create2Segments(left[3],right[3], {RF.upper(),LF.upper()}, ori, REACHABLE, NON_ACCESSIBLE);
398  else
399  set.upper() = RF.upper();
400  if (BF)
401  create2Segments(left[1],right[1], {RF.lower(),LF.lower()}, ori, NON_ACCESSIBLE, REACHABLE);
402  else
403  set.lower() = LF.lower();
404  create2Segments(left[2],right[2], {LF.lower(),RF.upper()}, ori, SEE_THROUGH,SEE_THROUGH);
405  break;
406  default:
407  Q_ASSERT(false); // don't come here
408  }
409 
410  // *seg[0] and *seg[4] are the empty segments below and above
411  if (set)
412  {
413  if (set.lower() > all.lower())
414  create2Segments(left[0],right[0], {all.lower(),set.lower()}, ori, NON_ACCESSIBLE,NON_ACCESSIBLE);
415  if (set.upper() < all.upper())
416  create2Segments(left[4],right[4], {set.upper(),all.upper()}, ori, NON_ACCESSIBLE,NON_ACCESSIBLE);
417  }
418  else
419  { // completely empty
420  create2Segments(left[0],right[0], all, ori, NON_ACCESSIBLE,NON_ACCESSIBLE);
421  }
422 }
423 
424 void Structure::linkSingleCellSegments(
425  SingleCellAuxData& aux, Orientation ori)
426 {
427  PointerInterval LP = aux.P[ori][FIRST];
428  PointerInterval RP = aux.P[ori][SECOND];
429  PointerInterval BP = aux.P[opposite(ori)][FIRST].normalized();
430  PointerInterval TP = aux.P[opposite(ori)][SECOND].normalized();
431 
432  Pointer *left = aux.seg[ori][FIRST];
433  Pointer *right = aux.seg[ori][SECOND];
434 
435  // LP,RP may be reversed. We make NO assumption about the correct orientation of PointerIntervals.
436  // adjust() and combine() must take care of it!
437 
438  // handle all cases of overlapping intervals
439  switch(aux.arr[ori])
440  {
441  case 0: // (0) completely empty
442  // nothing to see, nothing to be seen
443  break;
444  case 1: // (1) left reachable, right not
445  // we can see the top edge
446  if (left[2]) *left[2] = TP;
447  break;
448  case 2: // (2) right reachable
449  // can be seen from bottom edge
450  if (right[2]) *right[2] = BP;
451  break;
452  case 3:
453  case 4:
454  // ---
455  // | [3]
456  // ---
457  //
458  // ---
459  // | [1]
460  // ---
461  *left[1] = RP+TP;
462  *right[3] = BP+LP;
463  break;
464  case 5:
465  // ---
466  // | [3]
467  // | ---
468  // ...
469  LP = {left[1],left[2]};
470  if (left[3]) {
471  *left[3] = TP;
472  // the right edge can not be seen from uppermost left interval (*seg[3])
473  Q_ASSERT(! LP.contains(left[3])); // *seg[3] can not see *seg[2]
474  }
475  // fall-through intended
476  case 6:
477  // --- ---
478  // | | [2]
479  // | ---
480  // | [1]
481  // ---
482  *left[1] = RP+TP;
483  // see-through: only one pointer is needed
484  *left[2] = RP+TP;
485  *right[2] = BP+LP;
486  break;
487  case 7:
488  // ---
489  // | [3]
490  // --- |
491  // | | [2]
492  // | ---
493  // | [1]
494  // ---
495  // right and top are visible from bottom and left
496  *left[1] = RP+TP;
497  *left[2] = RP+TP;
498  *right[2] = BP+LP;
499  *right[3] = BP+LP;
500  break;
501  case 8:
502  // ---
503  // | [3]
504  // --- |
505  // | | [2]
506  // --- ---
507  *left[2] = RP+TP;
508  *right[2] = BP+LP;
509  *right[3] = BP+LP;
510  break;
511  case 9:
512  // --- ---
513  // | | [2]
514  // --- ---
515  *left[2] = RP+TP;
516  *right[2] = BP+LP;
517  break;
518  case 10:
519  // ---
520  // | [3]
521  // | ---
522  // | | [2]
523  // --- ---
524  // right[2] can not be seen from left[3]
525  LP = left[2];
526  if (left[3]) {
527  *left[3] = TP;
528  Q_ASSERT(! LP.contains(left[3]));
529  }
530  *left[2] = RP+TP;
531  *right[2] = BP+LP;
532  break;
533  case 11:
534  case 12:
535  // ---
536  // | [3]
537  // ---
538  //
539  // ---
540  // | [1]
541  // ---
542  // the right edge can only be seen from the bottom edge
543  if (right[1])
544  *right[1] = BP;
545  // we can only see the top edge
546  if (left[3])
547  *left[3] = TP;
548  break;
549  case 13:
550  // ---
551  // | [3]
552  // --- |
553  // | | [2]
554  // --- |
555  // | [1]
556  // ---
557  RP = {right[2],right[3]};
558  if (right[1]) {
559  *right[1] = BP;
560  Q_ASSERT(!RP.contains(right[1])); // right[1] can not be seen
561  }
562  *left[2] = RP+TP;
563  *right[2] = BP+LP;
564  *right[3] = BP+LP;
565  break;
566  case 15:
567  // ---
568  // | ([3])
569  // | ---
570  // | |
571  // ...
572  LP = left[2];
573  if (left[3]) {
574  *left[3] = TP;
575  Q_ASSERT(! LP.contains(left[3])); // *seg[3] can not be seen
576  }
577  // fall-through intended
578  case 14:
579  // --- ---
580  // | | [2]
581  // --- |
582  // | [1]
583  // ---
584  // this interval can not be seen from the left edge, only from the bottom edge
585  RP = right[2]; // right[1] can not be seen
586  if (right[1]) {
587  *right[1] = BP;
588  Q_ASSERT(! RP.contains(right[1]));
589  }
590  *left[2] = RP+TP;
591  // the right edge can not be seen from the upper left interval
592  *right[2] = BP+LP;
593  break;
594  default:
595  Q_ASSERT(false); // don't come here
596  }
597 
598  // SEE-THROUGH: one pointer is actually redundant
599  clipSeeThroughPointer(left[2]);
600  clipSeeThroughPointer(right[2]);
601 }
602 
603 void Structure::clipSeeThroughPointer(Pointer p)
604 {
605  if (p && p->type==SEE_THROUGH)
606  {
607  if ((p->ori==VERTICAL && p->dir==SECOND)
608  || (p->ori==HORIZONTAL && p->dir==FIRST))
609  p->h = nullptr;
610  else
611  p->l = nullptr;
612  }
613 }
614 
615 PointerInterval Structure::reachableInterval(Pointer seg[5])
616 {
617  PointerInterval result;
618  for(int i=0; i < 5; ++i)
619  if (seg[i] && seg[i]->type!=NON_ACCESSIBLE) {
620  result.h = seg[i];
621  if (!result.l)
622  result.l = seg[i];
623  }
624  return result;
625 }
626 
627 void Structure::create2Segments(Pointer& first, Pointer& second, Interval ival, Orientation ori, Type t1, Type t2)
628 {
629  first = new BoundarySegment(ival,ori,FIRST,t1,this);
630  second = new BoundarySegment(ival,ori,SECOND,t2,this);
631 }
632 
633 
634 void Structure::copySegments(BoundaryList& list, Pointer seg[5])
635 {
636  for(int i=0; i < 5; ++i)
637  if (seg[i])
638  {
639  Pointer p = seg[i];
640  Q_ASSERT(p);
641  Q_ASSERT(p->type!=NON_ACCESSIBLE || (p->l==NULL && p->h==NULL));
642 
643  list.insert_last(p);
644  }
645 }
646 
647 
648 
frechet::reach::Structure::SingleCellAuxData::F
data::Interval F[2][2]
Free-Space edges.
Definition: structure.h:377
frechet::data::BLinkedList::insert_last
void insert_last(BLinkedListElement *el)
insert a new element at the end of the list; the list takes ownership of the element....
Definition: linkedlist.cpp:52
frechet::reach::REACHABLE
reachable: other intervals are reachable
Definition: boundary.h:21
frechet::reach::SEE_THROUGH
see-through: other interals are visible with a straight line
Definition: boundary.h:23
frechet
global definitions for all algorithms.
frechet::reach::Structure::SingleCellAuxData::seg
Pointer seg[2][2][5]
reachability rectangle segments
Definition: structure.h:381
frechet::reach::BoundarySegment::ori
const Orientation ori
horizontal or vertical
Definition: boundary.h:318
frechet::reach::NON_ACCESSIBLE
non-accesible. no interval is reachable from this one
Definition: boundary.h:19
frechet::reach::Direction
Direction
direction of a Pointer inside the reachability structure.
Definition: boundary.h:115
frechet::reach::BoundarySegment
boundary interval in the reachability structure. Represents an interval on the boundary of the FreeSp...
Definition: boundary.h:285
frechet::reach::PointerInterval
describes l,h pointers. Both pointers are assumed to point into the same rectangle section (right-top...
Definition: boundary.h:160
frechet::data::Interval::clear
Interval & clear()
make this an invalid interval
Definition: interval.h:197
frechet::data::Interval::upper
double upper() const
Definition: interval.h:96
frechet::reach::Structure::SingleCellAuxData
aux. data structure that is used to construct an initial reachability cell
Definition: structure.h:375
frechet::reach::BoundarySegment::type
Type type
reachability label
Definition: boundary.h:317
frechet::data::Rect
a very simple Rectangle structure, with integer boundaries.
Definition: types.h:35
frechet::reach::PointerInterval::normalized
PointerInterval normalized() const
assumes identical orientation !!
Definition: boundary.cpp:92
frechet::reach::Type
Type
Segment Types.
Definition: boundary.h:17
frechet::reach::Orientation
Orientation
Segment Orientation.
Definition: boundary.h:31
frechet::data::Interval::lower
double lower() const
Definition: interval.h:92
frechet::numeric::min
double min(double a, double b)
minimum function with checks for NAN
Definition: numeric.h:222
frechet::reach::SECOND
second segment = right and top edge
Definition: boundary.h:118
frechet::reach::BoundarySegment::dir
const Direction dir
left/right or bottom/top
Definition: boundary.h:319
frechet::reach::PointerInterval::l
Pointer l
points to the lowest segment of the interval
Definition: boundary.h:161
frechet::reach::PointerInterval::contains
bool contains(Pointer p) const
containment test
Definition: boundary.cpp:248
frechet::reach::opposite
Orientation opposite(Orientation ori)
Definition: boundary.h:39
frechet::reach::PointerInterval::h
Pointer h
points to the highest segment of the interval
Definition: boundary.h:162
frechet::reach::FIRST
first segment = bottom and left edge
Definition: boundary.h:117
frechet::data::Interval
an interval of two double values.
Definition: interval.h:31
frechet::reach::Structure::SingleCellAuxData::P
PointerInterval P[2][2]
min/max for each rectangle edge
Definition: structure.h:383
frechet::numeric::max
double max(double a, double b)
maximum function with checks for NAN
Definition: numeric.h:233