lasinterval.cpp
Go to the documentation of this file.
1 /*
2 ===============================================================================
3 
4  FILE: lasinterval.cpp
5 
6  CONTENTS:
7 
8  see corresponding header file
9 
10  PROGRAMMERS:
11 
12  martin.isenburg@gmail.com
13 
14  COPYRIGHT:
15 
16  (c) 2011, Martin Isenburg, LASSO - tools to catch reality
17 
18  This software is distributed WITHOUT ANY WARRANTY and without even the
19  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
20 
21  CHANGE HISTORY:
22 
23  see corresponding header file
24 
25 ===============================================================================
26 */
27 #include "lasinterval.hpp"
28 
29 #include "bytestreamin.hpp"
30 #include "bytestreamout.hpp"
31 
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <string.h>
35 #include <assert.h>
36 
37 #include <map>
38 #include <set>
39 using namespace std;
40 
41 //#ifdef UNORDERED
42 #include <unordered_map>
43 using namespace std;
44 typedef unordered_map<I32, LASintervalStartCell*> my_cell_hash;
45 //#else
46 
47 
48 /*#if _MSC_VER
49 #include <hash_map>
50 using namespace stdext;
51 #else
52 #include <ext/hash_map>
53 using namespace __gnu_cxx;
54 #endif
55 
56 typedef hash_map<I32, LASintervalStartCell*> my_cell_hash;
57 #endif
58 */
59 typedef multimap<U32, LASintervalCell*> my_cell_map;
60 typedef set<LASintervalStartCell*> my_cell_set;
61 
63 {
64  start = 0;
65  end = 0;
66  next = 0;
67 }
68 
70 {
71  start = p_index;
72  end = p_index;
73  next = 0;
74 }
75 
77 {
78  start = cell->start;
79  end = cell->end;
80  next = 0;
81 }
82 
84 {
85  full = 0;
86  total = 0;
87  last = 0;
88 }
89 
91 {
92  full = 1;
93  total = 1;
94  last = 0;
95 }
96 
97 BOOL LASintervalStartCell::add(const U32 p_index, const U32 threshold)
98 {
99  U32 current_end = (last ? last->end : end);
100  assert(p_index > current_end);
101  U32 diff = p_index - current_end;
102  full++;
103  if (diff > threshold)
104  {
105  if (last)
106  {
107  last->next = new LASintervalCell(p_index);
108  last = last->next;
109  }
110  else
111  {
112  next = new LASintervalCell(p_index);
113  last = next;
114  }
115  total++;
116  return TRUE; // created new interval
117  }
118  if (last)
119  {
120  last->end = p_index;
121  }
122  else
123  {
124  end = p_index;
125  }
126  total += diff;
127  return FALSE; // added to interval
128 }
129 
130 BOOL LASinterval::add(const U32 p_index, const I32 c_index)
131 {
132  if (last_cell == 0 || last_index != c_index)
133  {
134  last_index = c_index;
135  my_cell_hash::iterator hash_element = ((my_cell_hash*)cells)->find(c_index);
136  if (hash_element == ((my_cell_hash*)cells)->end())
137  {
138  last_cell = new LASintervalStartCell(p_index);
139  ((my_cell_hash*)cells)->insert(my_cell_hash::value_type(c_index, last_cell));
141  return TRUE;
142  }
143  last_cell = (*hash_element).second;
144  }
145  if (last_cell->add(p_index, threshold))
146  {
148  return TRUE;
149  }
150  return FALSE;
151 }
152 
153 // get total number of cells
155 {
156  return ((my_cell_hash*)cells)->size();
157 }
158 
159 // get total number of intervals
161 {
162  return number_intervals;
163 }
164 
165 // merge cells (and their intervals) into one cell
166 BOOL LASinterval::merge_cells(const U32 num_indices, const I32* indices, const I32 new_index)
167 {
168  U32 i;
169  if (num_indices == 1)
170  {
171  my_cell_hash::iterator hash_element = ((my_cell_hash*)cells)->find(indices[0]);
172  if (hash_element == ((my_cell_hash*)cells)->end())
173  {
174  return FALSE;
175  }
176  ((my_cell_hash*)cells)->insert(my_cell_hash::value_type(new_index, (*hash_element).second));
177  ((my_cell_hash*)cells)->erase(hash_element);
178  }
179  else
180  {
181  if (cells_to_merge) ((my_cell_set*)cells_to_merge)->clear();
182  for (i = 0; i < num_indices; i++)
183  {
184  add_cell_to_merge_cell_set(indices[i], TRUE);
185  }
186  if (!merge(TRUE)) return FALSE;
187  ((my_cell_hash*)cells)->insert(my_cell_hash::value_type(new_index, merged_cells));
188  merged_cells = 0;
189  }
190  return TRUE;
191 }
192 
193 // merge adjacent intervals with small gaps in cells to reduce total interval number to maximum
194 void LASinterval::merge_intervals(U32 maximum_intervals)
195 {
196  U32 diff;
197  LASintervalCell* cell;
198  LASintervalCell* delete_cell;
199 
200  // each cell has minimum one interval
201 
202  if (maximum_intervals < get_number_cells())
203  {
204  maximum_intervals = 0;
205  }
206  else
207  {
208  maximum_intervals -= get_number_cells();
209  }
210 
211  // order intervals by smallest gap
212 
214  my_cell_hash::iterator hash_element = ((my_cell_hash*)cells)->begin();
215  while (hash_element != ((my_cell_hash*)cells)->end())
216  {
217  cell = (*hash_element).second;
218  while (cell->next)
219  {
220  diff = cell->next->start - cell->end - 1;
221  map.insert(my_cell_map::value_type(diff, cell));
222  cell = cell->next;
223  }
224  hash_element++;
225  }
226 
227  my_cell_map::iterator map_element = map.begin();
228  diff = (*map_element).first;
229 
230  // maybe nothing to do
231  if (map.size() <= maximum_intervals)
232  {
233  fprintf(stderr,"next largest interval gap is %u\n", diff);
234  return;
235  }
236 
237  U32 size = map.size();
238  while (size > maximum_intervals)
239  {
240  map_element = map.begin();
241  diff = (*map_element).first;
242  cell = (*map_element).second;
243  map.erase(map_element);
244  if (cell->end == 0) // the (end == 0) signals that the cell is to be deleted
245  {
247  delete cell;
248  }
249  else
250  {
251  delete_cell = cell->next;
252  cell->end = delete_cell->end;
253  cell->next = delete_cell->next;
254  if (cell->next)
255  {
256  map.insert(my_cell_map::value_type(cell->next->start - cell->end - 1, cell));
257  delete_cell->end = 0; // the (end == 0) signals that the cell is to be deleted
258  }
259  else
260  {
262  delete delete_cell;
263  }
264  size--;
265  }
266  }
267  map_element = map.begin();
268  while (true)
269  {
270  if (map_element == map.end()) break;
271  cell = (*map_element).second;
272  if (cell->end == 0) // the (end == 0) signals that the cell is to be deleted
273  {
275  delete cell;
276  }
277  map_element++;
278  }
279  fprintf(stderr,"largest interval gap increased to %u\n", diff);
280 
281  // update totals
282 
283  LASintervalStartCell* start_cell;
284  hash_element = ((my_cell_hash*)cells)->begin();
285  while (hash_element != ((my_cell_hash*)cells)->end())
286  {
287  start_cell = (*hash_element).second;
288  start_cell->total = 0;
289  cell = start_cell;
290  while (cell)
291  {
292  start_cell->total += (cell->end - cell->start + 1);
293  cell = cell->next;
294  }
295  hash_element++;
296  }
297 }
298 
300 {
302  current_cell = 0;
303 }
304 
306 {
307  my_cell_hash::iterator hash_element;
308  if (last_index == I32_MIN)
309  {
310  hash_element = ((my_cell_hash*)cells)->begin();
311  }
312  else
313  {
314  hash_element = ((my_cell_hash*)cells)->find(last_index);
315  hash_element++;
316  }
317  if (hash_element == ((my_cell_hash*)cells)->end())
318  {
320  current_cell = 0;
321  return FALSE;
322  }
323  last_index = (*hash_element).first;
324  index = (*hash_element).first;
325  full = (*hash_element).second->full;
326  total = (*hash_element).second->total;
327  current_cell = (*hash_element).second;
328  return TRUE;
329 }
330 
332 {
333  my_cell_hash::iterator hash_element = ((my_cell_hash*)cells)->find(c_index);
334  if (hash_element == ((my_cell_hash*)cells)->end())
335  {
336  current_cell = 0;
337  return FALSE;
338  }
339  index = (*hash_element).first;
340  full = (*hash_element).second->full;
341  total = (*hash_element).second->total;
342  current_cell = (*hash_element).second;
343  return TRUE;
344 }
345 
347 {
348  if (current_cell == 0)
349  {
350  return FALSE;
351  }
352  if (cells_to_merge == 0)
353  {
354  cells_to_merge = (void*) new my_cell_set;
355  }
357  return TRUE;
358 }
359 
361 {
362  my_cell_hash::iterator hash_element = ((my_cell_hash*)cells)->find(c_index);
363  if (hash_element == ((my_cell_hash*)cells)->end())
364  {
365  return FALSE;
366  }
367  if (cells_to_merge == 0)
368  {
369  cells_to_merge = (void*) new my_cell_set;
370  }
371  ((my_cell_set*)cells_to_merge)->insert((*hash_element).second);
372  if (erase) ((my_cell_hash*)cells)->erase(hash_element);
373  return TRUE;
374 }
375 
377 {
378  // maybe delete temporary merge cells from the previous merge
379  if (merged_cells)
380  {
382  {
383  LASintervalCell* next_next;
385  while (next)
386  {
387  next_next = next->next;
388  delete next;
389  next = next_next;
390  }
391  delete merged_cells;
392  }
393  merged_cells = 0;
394  }
395  // are there cells to merge
396  if (cells_to_merge == 0) return FALSE;
397  if (((my_cell_set*)cells_to_merge)->size() == 0) return FALSE;
398  // is there just one cell
399  if (((my_cell_set*)cells_to_merge)->size() == 1)
400  {
402  // simply use this cell as the merge cell
403  my_cell_set::iterator set_element = ((my_cell_set*)cells_to_merge)->begin();
404  merged_cells = (*set_element);
405  }
406  else
407  {
410  // iterate over all cells and add their intervals to map
411  LASintervalCell* cell;
413  my_cell_set::iterator set_element = ((my_cell_set*)cells_to_merge)->begin();
414  while (true)
415  {
416  if (set_element == ((my_cell_set*)cells_to_merge)->end()) break;
417  cell = (*set_element);
418  merged_cells->full += ((LASintervalStartCell*)cell)->full;
419  while (cell)
420  {
421  map.insert(my_cell_map::value_type(cell->start, cell));
422  cell = cell->next;
423  }
424  set_element++;
425  }
426  // initialize merged_cells with first interval
427  my_cell_map::iterator map_element = map.begin();
428  cell = (*map_element).second;
429  map.erase(map_element);
430  merged_cells->start = cell->start;
431  merged_cells->end = cell->end;
432  merged_cells->total = cell->end - cell->start + 1;
433  if (erase) delete cell;
434  // merge intervals
436  I32 diff;
437  while (map.size())
438  {
439  map_element = map.begin();
440  cell = (*map_element).second;
441  map.erase(map_element);
442  diff = cell->start - last_cell->end;
443  if (diff > (I32)threshold)
444  {
445  last_cell->next = new LASintervalCell(cell);
447  merged_cells->total += (cell->end - cell->start + 1);
448  }
449  else
450  {
451  diff = cell->end - last_cell->end;
452  if (diff > 0)
453  {
454  last_cell->end = cell->end;
455  merged_cells->total += diff;
456  }
458  }
459  if (erase) delete cell;
460  }
461  }
465  return TRUE;
466 }
467 
469 {
470  if (cells_to_merge)
471  {
472  ((my_cell_set*)cells_to_merge)->clear();
473  }
474 }
475 
477 {
478  if (merged_cells)
479  {
483  return TRUE;
484  }
485  return FALSE;
486 }
487 
489 {
490  if (current_cell)
491  {
493  end = current_cell->end;
495  return TRUE;
496  }
497  return FALSE;
498 }
499 
501 {
502  cells = new my_cell_hash;
503  cells_to_merge = 0;
504  this->threshold = threshold;
505  number_intervals = 0;
507  last_cell = 0;
508  current_cell = 0;
509  merged_cells = 0;
511 }
512 
514 {
515  delete ((my_cell_hash*)cells);
516  if (cells_to_merge) delete ((my_cell_set*)cells_to_merge);
517 }
518 
520 {
521  char signature[4];
522  try { stream->getBytes((U8*)signature, 4); } catch (...)
523  {
524  fprintf(stderr,"ERROR (LASinterval): reading signature\n");
525  return FALSE;
526  }
527  if (strncmp(signature, "LASV", 4) != 0)
528  {
529  fprintf(stderr,"ERROR (LASinterval): wrong signature %4s instead of 'LASV'\n", signature);
530  return FALSE;
531  }
532  U32 version;
533  try { stream->get32bitsLE((U8*)&version); } catch (...)
534  {
535  fprintf(stderr,"ERROR (LASinterval): reading version\n");
536  return FALSE;
537  }
538  // read number of cells
539  U32 number_cells;
540  try { stream->get32bitsLE((U8*)&number_cells); } catch (...)
541  {
542  fprintf(stderr,"ERROR (LASinterval): reading number of cells\n");
543  return FALSE;
544  }
545  // loop over all cells
546  while (number_cells)
547  {
548  // read index of cell
549  I32 cell_index;
550  try { stream->get32bitsLE((U8*)&cell_index); } catch (...)
551  {
552  fprintf(stderr,"ERROR (LASinterval): reading cell index\n");
553  return FALSE;
554  }
555  // create cell and insert into hash
556  LASintervalStartCell* start_cell = new LASintervalStartCell();
557  ((my_cell_hash*)cells)->insert(my_cell_hash::value_type(cell_index, start_cell));
558  LASintervalCell* cell = start_cell;
559  // read number of intervals in cell
561  try { stream->get32bitsLE((U8*)&number_intervals); } catch (...)
562  {
563  fprintf(stderr,"ERROR (LASinterval): reading number of intervals in cell\n");
564  return FALSE;
565  }
566  // read number of points in cell
567  U32 number_points;
568  try { stream->get32bitsLE((U8*)&number_points); } catch (...)
569  {
570  fprintf(stderr,"ERROR (LASinterval): reading number of points in cell\n");
571  return FALSE;
572  }
573  start_cell->full = number_points;
574  start_cell->total = 0;
575  while (number_intervals)
576  {
577  // read start of interval
578  try { stream->get32bitsLE((U8*)&(cell->start)); } catch (...)
579  {
580  fprintf(stderr,"ERROR (LASinterval): reading start %d of interval\n", cell->start);
581  return FALSE;
582  }
583  // read end of interval
584  try { stream->get32bitsLE((U8*)&(cell->end)); } catch (...)
585  {
586  fprintf(stderr,"ERROR (LASinterval): reading end %d of interval\n", cell->end);
587  return FALSE;
588  }
589  start_cell->total += (cell->end - cell->start + 1);
591  if (number_intervals)
592  {
593  cell->next = new LASintervalCell();
594  cell = cell->next;
595  }
596  }
597  number_cells--;
598  }
599 
600  return TRUE;
601 }
602 
604 {
605  if (!stream->putBytes((U8*)"LASV", 4))
606  {
607  fprintf(stderr,"ERROR (LASinterval): writing signature\n");
608  return FALSE;
609  }
610  U32 version = 0;
611  if (!stream->put32bitsLE((U8*)&version))
612  {
613  fprintf(stderr,"ERROR (LASinterval): writing version\n");
614  return FALSE;
615  }
616  // write number of cells
617  U32 number_cells = ((my_cell_hash*)cells)->size();
618  if (!stream->put32bitsLE((U8*)&number_cells))
619  {
620  fprintf(stderr,"ERROR (LASinterval): writing number of cells %d\n", number_cells);
621  return FALSE;
622  }
623  // loop over all cells
624  my_cell_hash::iterator hash_element = ((my_cell_hash*)cells)->begin();
625  while (hash_element != ((my_cell_hash*)cells)->end())
626  {
627  LASintervalCell* cell = (*hash_element).second;
628  // count number of intervals and points in cell
629  U32 number_intervals = 0;
630  U32 number_points = ((LASintervalStartCell*)cell)->full;
631  while (cell)
632  {
634  cell = cell->next;
635  }
636  // write index of cell
637  I32 cell_index = (*hash_element).first;
638  if (!stream->put32bitsLE((U8*)&cell_index))
639  {
640  fprintf(stderr,"ERROR (LASinterval): writing cell index %d\n", cell_index);
641  return FALSE;
642  }
643  // write number of intervals in cell
644  if (!stream->put32bitsLE((U8*)&number_intervals))
645  {
646  fprintf(stderr,"ERROR (LASinterval): writing number of intervals %d in cell\n", number_intervals);
647  return FALSE;
648  }
649  // write number of points in cell
650  if (!stream->put32bitsLE((U8*)&number_points))
651  {
652  fprintf(stderr,"ERROR (LASinterval): writing number of points %d in cell\n", number_points);
653  return FALSE;
654  }
655  // write intervals
656  cell = (*hash_element).second;
657  while (cell)
658  {
659  // write start of interval
660  if (!stream->put32bitsLE((U8*)&(cell->start)))
661  {
662  fprintf(stderr,"ERROR (LASinterval): writing start %d of interval\n", cell->start);
663  return FALSE;
664  }
665  // write end of interval
666  if (!stream->put32bitsLE((U8*)&(cell->end)))
667  {
668  fprintf(stderr,"ERROR (LASinterval): writing end %d of interval\n", cell->end);
669  return FALSE;
670  }
671  cell = cell->next;
672  }
673  hash_element++;
674  }
675  return TRUE;
676 }
LASinterval::last_cell
LASintervalStartCell * last_cell
Definition: lasinterval.hpp:115
LASinterval::clear_merge_cell_set
void clear_merge_cell_set()
Definition: lasinterval.cpp:468
LASinterval::number_intervals
U32 number_intervals
Definition: lasinterval.hpp:113
LASinterval::current_cell
LASintervalCell * current_cell
Definition: lasinterval.hpp:116
my_cell_hash
unordered_map< I32, U32 > my_cell_hash
Definition: lasindex.cpp:44
LASinterval::add
BOOL add(const U32 p_index, const I32 c_index)
Definition: lasinterval.cpp:130
LASinterval::get_cells
void get_cells()
Definition: lasinterval.cpp:299
LASinterval::index
I32 index
Definition: lasinterval.hpp:103
I32
int I32
Definition: mydefs.hpp:35
TRUE
#define TRUE
Definition: mydefs.hpp:137
LASintervalStartCell::add
BOOL add(const U32 p_index, const U32 threshold=1000)
Definition: lasinterval.cpp:97
lasinterval.hpp
LASintervalCell
Definition: lasinterval.hpp:39
LASintervalStartCell::total
U32 total
Definition: lasinterval.hpp:54
LASinterval::start
U32 start
Definition: lasinterval.hpp:104
ByteStreamOut::put32bitsLE
virtual BOOL put32bitsLE(const U8 *bytes)=0
LASinterval::merge_intervals
void merge_intervals(U32 maximum)
Definition: lasinterval.cpp:194
LASinterval::get_number_intervals
U32 get_number_intervals() const
Definition: lasinterval.cpp:160
I32_MIN
#define I32_MIN
Definition: mydefs.hpp:88
lvr2::map
OutMapT< typename InMapT::HandleType, std::result_of_t< MapF(typename InMapT::ValueType)> > map(const InMapT &mapIn, MapF func)
Calls func for each value of the given map and save the result in the output map.
ByteStreamOut
Definition: bytestreamout.hpp:36
bytestreamin.hpp
my_cell_hash
unordered_map< I32, LASintervalStartCell * > my_cell_hash
Definition: lasinterval.cpp:44
LASinterval::merged_cells_temporary
BOOL merged_cells_temporary
Definition: lasinterval.hpp:118
LASintervalStartCell::last
LASintervalCell * last
Definition: lasinterval.hpp:55
ByteStreamIn::get32bitsLE
virtual void get32bitsLE(U8 *bytes)=0
LASinterval::threshold
U32 threshold
Definition: lasinterval.hpp:112
LASinterval::get_merged_cell
BOOL get_merged_cell()
Definition: lasinterval.cpp:476
LASinterval::end
U32 end
Definition: lasinterval.hpp:105
my_cell_map
multimap< U32, LASintervalCell * > my_cell_map
Definition: lasinterval.cpp:59
bytestreamout.hpp
ByteStreamIn
Definition: bytestreamin.hpp:36
LASinterval::has_intervals
BOOL has_intervals()
Definition: lasinterval.cpp:488
LASinterval::full
U32 full
Definition: lasinterval.hpp:106
LASinterval::LASinterval
LASinterval(const U32 threshold=1000)
Definition: lasinterval.cpp:500
LASinterval::read
BOOL read(ByteStreamIn *stream)
Definition: lasinterval.cpp:519
LASinterval::~LASinterval
~LASinterval()
Definition: lasinterval.cpp:513
LASintervalStartCell::LASintervalStartCell
LASintervalStartCell()
Definition: lasinterval.cpp:83
LASinterval::last_index
I32 last_index
Definition: lasinterval.hpp:114
U8
unsigned char U8
Definition: mydefs.hpp:41
BOOL
int BOOL
Definition: mydefs.hpp:57
LASinterval::merged_cells
LASintervalStartCell * merged_cells
Definition: lasinterval.hpp:117
FALSE
#define FALSE
Definition: mydefs.hpp:133
LASinterval::cells_to_merge
void * cells_to_merge
Definition: lasinterval.hpp:111
LASintervalStartCell::full
U32 full
Definition: lasinterval.hpp:53
std
Definition: HalfEdge.hpp:124
LASinterval::has_cells
BOOL has_cells()
Definition: lasinterval.cpp:305
LASinterval::get_cell
BOOL get_cell(const I32 c_index)
Definition: lasinterval.cpp:331
LASinterval::total
U32 total
Definition: lasinterval.hpp:107
my_cell_set
set< LASintervalStartCell * > my_cell_set
Definition: lasinterval.cpp:60
U32
unsigned int U32
Definition: mydefs.hpp:39
LASintervalStartCell
Definition: lasinterval.hpp:50
LASintervalCell::start
U32 start
Definition: lasinterval.hpp:42
LASinterval::cells
void * cells
Definition: lasinterval.hpp:110
LASinterval::write
BOOL write(ByteStreamOut *stream) const
Definition: lasinterval.cpp:603
LASinterval::add_current_cell_to_merge_cell_set
BOOL add_current_cell_to_merge_cell_set()
Definition: lasinterval.cpp:346
LASinterval::merge_cells
BOOL merge_cells(const U32 num_indices, const I32 *indices, const I32 new_index)
Definition: lasinterval.cpp:166
LASinterval::add_cell_to_merge_cell_set
BOOL add_cell_to_merge_cell_set(const I32 c_index, const BOOL erase=FALSE)
Definition: lasinterval.cpp:360
LASintervalCell::next
LASintervalCell * next
Definition: lasinterval.hpp:44
ByteStreamIn::getBytes
virtual void getBytes(U8 *bytes, const U32 num_bytes)=0
LASinterval::get_number_cells
U32 get_number_cells() const
Definition: lasinterval.cpp:154
LASintervalCell::LASintervalCell
LASintervalCell()
Definition: lasinterval.cpp:62
ByteStreamOut::putBytes
virtual BOOL putBytes(const U8 *bytes, U32 num_bytes)=0
LASintervalCell::end
U32 end
Definition: lasinterval.hpp:43
LASinterval::merge
BOOL merge(const BOOL erase=FALSE)
Definition: lasinterval.cpp:376


lvr2
Author(s): Thomas Wiemann , Sebastian Pütz , Alexander Mock , Lars Kiesow , Lukas Kalbertodt , Tristan Igelbrink , Johan M. von Behren , Dominik Feldschnieders , Alexander Löhr
autogenerated on Wed Mar 2 2022 00:37:23