lasindex.cpp
Go to the documentation of this file.
1 /*
2 ===============================================================================
3 
4  FILE: lasindex.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 
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include <string.h>
31 
32 #include "lasindex.hpp"
33 
34 #include "lasspatial.hpp"
35 #include "lasinterval.hpp"
36 #include "lasreader.hpp"
37 #include "bytestreamin_file.hpp"
38 #include "bytestreamout_file.hpp"
39 
40 //#ifdef UNORDERED
41 #include <unordered_map>
42 using namespace std;
43 //using namespace tr1;
44 typedef unordered_map<I32,U32> my_cell_hash;
45 //#else
46 
47 /*#if _MSC_VER
48 #include <hash_map>
49 using namespace stdext;
50 #else
51 #include <ext/hash_map>
52 using namespace __gnu_cxx;
53 #endif */
54 
55 //typedef hash_map<I32,U32> my_cell_hash;
56 //#endif
57 
59 {
60  spatial = 0;
61  interval = 0;
62  have_interval = FALSE;
63  start = 0;
64  end = 0;
65  full = 0;
66  total = 0;
67  cells = 0;
68 }
69 
71 {
72  if (spatial) delete spatial;
73  if (interval) delete interval;
74 }
75 
76 void LASindex::prepare(LASspatial* spatial, I32 threshold)
77 {
78  if (this->spatial) delete this->spatial;
79  this->spatial = spatial;
80  if (this->interval) delete this->interval;
81  this->interval = new LASinterval(threshold);
82 }
83 
84 BOOL LASindex::add(const LASpoint* point, const U32 p_index)
85 {
86  I32 cell = spatial->get_cell_index(point->get_x(), point->get_y());
87  return interval->add(p_index, cell);
88 }
89 
90 void LASindex::complete(U32 minimum_points, I32 maximum_intervals)
91 {
92  fprintf(stderr,"before complete %d %d\n", minimum_points, maximum_intervals);
93  print(FALSE);
94  if (minimum_points)
95  {
96  I32 hash1 = 0;
97  my_cell_hash cell_hash[2];
98  // insert all cells into hash1
99  interval->get_cells();
100  while (interval->has_cells())
101  {
102  cell_hash[hash1][interval->index] = interval->full;
103  }
104  while (cell_hash[hash1].size())
105  {
106  I32 hash2 = (hash1+1)%2;
107  cell_hash[hash2].clear();
108  // coarsen if a coarser cell will still have fewer than minimum_points (and points in all subcells)
109  BOOL coarsened = FALSE;
110  U32 i, full;
111  I32 coarser_index;
112  U32 num_indices;
113  U32 num_filled;
114  I32* indices;
115  my_cell_hash::iterator hash_element_inner;
116  my_cell_hash::iterator hash_element_outer = cell_hash[hash1].begin();
117  while (hash_element_outer != cell_hash[hash1].end())
118  {
119  if ((*hash_element_outer).second)
120  {
121  if (spatial->coarsen((*hash_element_outer).first, &coarser_index, &num_indices, &indices))
122  {
123  full = 0;
124  num_filled = 0;
125  for (i = 0; i < num_indices; i++)
126  {
127  if ((*hash_element_outer).first == indices[i])
128  {
129  hash_element_inner = hash_element_outer;
130  }
131  else
132  {
133  hash_element_inner = cell_hash[hash1].find(indices[i]);
134  }
135  if (hash_element_inner != cell_hash[hash1].end())
136  {
137  full += (*hash_element_inner).second;
138  (*hash_element_inner).second = 0;
139  num_filled++;
140  }
141  }
142  if ((full < minimum_points) && (num_filled == num_indices))
143  {
144  interval->merge_cells(num_indices, indices, coarser_index);
145  coarsened = TRUE;
146  cell_hash[hash2][coarser_index] = full;
147  }
148  }
149  }
150  hash_element_outer++;
151  }
152  if (!coarsened) break;
153  hash1 = (hash1+1)%2;
154  }
155  // tell spatial about the existing cells
156  interval->get_cells();
157  while (interval->has_cells())
158  {
159  spatial->manage_cell(interval->index);
160  }
161  fprintf(stderr,"after minimum_points %d\n", minimum_points);
162  print(FALSE);
163  }
164  if (maximum_intervals < 0)
165  {
166  maximum_intervals = -maximum_intervals*interval->get_number_cells();
167  }
168  if (maximum_intervals)
169  {
170  interval->merge_intervals(maximum_intervals);
171  fprintf(stderr,"after maximum_intervals %d\n", maximum_intervals);
172  print(FALSE);
173  }
174 }
175 
176 void LASindex::print(BOOL verbose)
177 {
178  U32 total_cells = 0;
179  U32 total_full = 0;
180  U32 total_total = 0;
181  U32 total_intervals = 0;
182  U32 total_check;
183  U32 intervals;
184  interval->get_cells();
185  while (interval->has_cells())
186  {
187  total_check = 0;
188  intervals = 0;
189  while (interval->has_intervals())
190  {
191  total_check += interval->end-interval->start+1;
192  intervals++;
193  }
194  if (total_check != interval->total)
195  {
196  fprintf(stderr,"ERROR: total_check %d != interval->total %d\n", total_check, interval->total);
197  }
198  if (verbose) fprintf(stderr,"cell %d intervals %d full %d total %d (%.2f)\n", interval->index, intervals, interval->full, interval->total, 100.0f*interval->full/interval->total);
199  total_cells++;
200  total_full += interval->full;
201  total_total += interval->total;
202  total_intervals += intervals;
203  }
204  fprintf(stderr,"total cells/intervals %d/%d full %d (%.2f)\n", total_cells, total_intervals, total_full, 100.0f*total_full/total_total);
205 }
206 
208 {
209  return spatial;
210 }
211 
213 {
214  return interval;
215 }
216 
217 BOOL LASindex::intersect_rectangle(const F64 r_min_x, const F64 r_min_y, const F64 r_max_x, const F64 r_max_y)
218 {
219  have_interval = FALSE;
220  cells = spatial->intersect_rectangle(r_min_x, r_min_y, r_max_x, r_max_y);
221 // fprintf(stderr,"%d cells of %g/%g %g/%g intersect rect %g/%g %g/%g\n", num_cells, spatial->get_min_x(), spatial->get_min_y(), spatial->get_max_x(), spatial->get_max_y(), r_min_x, r_min_y, r_max_x, r_max_y);
222  if (cells)
223  return merge_intervals();
224  return FALSE;
225 }
226 
227 BOOL LASindex::intersect_tile(const F32 ll_x, const F32 ll_y, const F32 size)
228 {
229  have_interval = FALSE;
230  cells = spatial->intersect_tile(ll_x, ll_y, size);
231 // fprintf(stderr,"%d cells of %g/%g %g/%g intersect tile %g/%g/%g\n", num_cells, spatial->get_min_x(), spatial->get_min_y(), spatial->get_max_x(), spatial->get_max_y(), ll_x, ll_y, size);
232  if (cells)
233  return merge_intervals();
234  return FALSE;
235 }
236 
237 BOOL LASindex::intersect_circle(const F64 center_x, const F64 center_y, const F64 radius)
238 {
239  have_interval = FALSE;
240  cells = spatial->intersect_circle(center_x, center_y, radius);
241 // fprintf(stderr,"%d cells of %g/%g %g/%g intersect circle %g/%g/%g\n", num_cells, spatial->get_min_x(), spatial->get_min_y(), spatial->get_max_x(), spatial->get_max_y(), center_x, center_y, radius);
242  if (cells)
243  return merge_intervals();
244  return FALSE;
245 }
246 
248 {
249  have_interval = FALSE;
250  return interval->get_merged_cell();
251 }
252 
254 {
255  if (interval->has_intervals())
256  {
257  start = interval->start;
258  end = interval->end;
259  full = interval->full;
260  have_interval = TRUE;
261  return TRUE;
262  }
263  have_interval = FALSE;
264  return FALSE;
265 }
266 
267 BOOL LASindex::read(const char* file_name)
268 {
269  if (file_name == 0) return FALSE;
270  char* name = strdup(file_name);
271  if (strstr(file_name, ".las") || strstr(file_name, ".laz"))
272  {
273  name[strlen(name)-1] = 'x';
274  }
275  else if (strstr(file_name, ".LAS") || strstr(file_name, ".LAZ"))
276  {
277  name[strlen(name)-1] = 'X';
278  }
279  else
280  {
281  name[strlen(name)-3] = 'l';
282  name[strlen(name)-2] = 'a';
283  name[strlen(name)-1] = 'x';
284  }
285  FILE* file = fopen(name, "rb");
286  if (file == 0)
287  {
288 // fprintf(stderr,"ERROR (LASindex): cannot open '%s' for read\n", name);
289  free(name);
290  return FALSE;
291  }
292  ByteStreamIn* stream;
293  if (IS_LITTLE_ENDIAN())
294  stream = new ByteStreamInFileLE(file);
295  else
296  stream = new ByteStreamInFileBE(file);
297  if (!read(stream))
298  {
299  fprintf(stderr,"ERROR (LASindex): cannot read '%s'\n", name);
300  delete stream;
301  fclose(file);
302  free(name);
303  return FALSE;
304  }
305  delete stream;
306  fclose(file);
307  free(name);
308  return TRUE;
309 }
310 
311 BOOL LASindex::write(const char* file_name) const
312 {
313  if (file_name == 0) return FALSE;
314  char* name = strdup(file_name);
315  if (strstr(file_name, ".las") || strstr(file_name, ".laz"))
316  {
317  name[strlen(name)-1] = 'x';
318  }
319  else if (strstr(file_name, ".LAS") || strstr(file_name, ".LAZ"))
320  {
321  name[strlen(name)-1] = 'X';
322  }
323  else
324  {
325  name[strlen(name)-3] = 'l';
326  name[strlen(name)-2] = 'a';
327  name[strlen(name)-1] = 'x';
328  }
329  FILE* file = fopen(name, "wb");
330  if (file == 0)
331  {
332  fprintf(stderr,"ERROR (LASindex): cannot open '%s' for write\n", name);
333  free(name);
334  return FALSE;
335  }
336  ByteStreamOut* stream;
337  if (IS_LITTLE_ENDIAN())
338  stream = new ByteStreamOutFileLE(file);
339  else
340  stream = new ByteStreamOutFileBE(file);
341  if (!write(stream))
342  {
343  fprintf(stderr,"ERROR (LASindex): cannot write '%s'\n", name);
344  delete stream;
345  fclose(file);
346  free(name);
347  return FALSE;
348  }
349  delete stream;
350  fclose(file);
351  free(name);
352  return TRUE;
353 }
354 
356 {
357  if (spatial)
358  {
359  delete spatial;
360  spatial = 0;
361  }
362  if (interval)
363  {
364  delete interval;
365  interval = 0;
366  }
367  char signature[4];
368  try { stream->getBytes((U8*)signature, 4); } catch (...)
369  {
370  fprintf(stderr,"ERROR (LASindex): reading signature\n");
371  return FALSE;
372  }
373  if (strncmp(signature, "LASX", 4) != 0)
374  {
375  fprintf(stderr,"ERROR (LASindex): wrong signature %4s instead of 'LASX'\n", signature);
376  return FALSE;
377  }
378  U32 version;
379  try { stream->get32bitsLE((U8*)&version); } catch (...)
380  {
381  fprintf(stderr,"ERROR (LASindex): reading version\n");
382  return FALSE;
383  }
384  // read spatial
385  LASspatialReadWrite spatialRW;
386  spatial = spatialRW.read(stream);
387  if (!spatial)
388  {
389  fprintf(stderr,"ERROR (LASindex): cannot read LASspatial\n");
390  return FALSE;
391  }
392  // read interval
393  interval = new LASinterval();
394  if (!interval->read(stream))
395  {
396  fprintf(stderr,"ERROR (LASindex): reading LASinterval\n");
397  return FALSE;
398  }
399  // tell spatial about the existing cells
400  interval->get_cells();
401  while (interval->has_cells())
402  {
403  spatial->manage_cell(interval->index);
404  }
405  return TRUE;
406 }
407 
409 {
410  if (!stream->putBytes((U8*)"LASX", 4))
411  {
412  fprintf(stderr,"ERROR (LASindex): writing signature\n");
413  return FALSE;
414  }
415  U32 version = 0;
416  if (!stream->put32bitsLE((U8*)&version))
417  {
418  fprintf(stderr,"ERROR (LASindex): writing version\n");
419  return FALSE;
420  }
421  // write spatial
422  LASspatialReadWrite spatialRW;
423  if (!spatialRW.write(spatial, stream))
424  {
425  fprintf(stderr,"ERROR (LASindex): cannot write LASspatial\n");
426  return FALSE;
427  }
428  // write interval
429  if (!interval->write(stream))
430  {
431  fprintf(stderr,"ERROR (LASindex): writing LASinterval\n");
432  return FALSE;
433  }
434  return TRUE;
435 }
436 
437 // read next interval point
439 {
440  if (!have_interval)
441  {
442  if (!has_intervals()) return FALSE;
443  lasreader->seek(start);
444  }
445  if (lasreader->p_count == end)
446  {
447  have_interval = FALSE;
448  }
449  return lasreader->read_point();
450 }
451 
452 // seek to next interval point
454 {
455  if (!have_interval)
456  {
457  if (!has_intervals()) return FALSE;
458  lasreader->seek(start);
459  }
460  if (lasreader->p_count == end)
461  {
462  have_interval = FALSE;
463  }
464  return TRUE;
465 }
466 
467 // merge the intervals of non-empty cells
469 {
470  if (spatial->get_intersected_cells())
471  {
472  U32 used_cells = 0;
473  while (spatial->has_more_cells())
474  {
475  if (interval->get_cell(spatial->current_cell))
476  {
477  interval->add_current_cell_to_merge_cell_set();
478  used_cells++;
479  }
480  }
481 // fprintf(stderr,"LASindex: used %d cells of total %d\n", used_cells, interval->get_number_cells());
482  if (used_cells)
483  {
484  BOOL r = interval->merge();
485  full = interval->full;
486  total = interval->total;
487  interval->clear_merge_cell_set();
488  return r;
489  }
490  }
491  return FALSE;
492 }
LASreader::seek
virtual BOOL seek(const I64 p_index)=0
LASindex::read
BOOL read(const char *file_name)
Definition: lasindex.cpp:267
LASpoint
Definition: lasdefinitions.hpp:472
my_cell_hash
unordered_map< I32, U32 > my_cell_hash
Definition: lasindex.cpp:44
lasreader.hpp
LASindex::get_intervals
BOOL get_intervals()
Definition: lasindex.cpp:247
F64
double F64
Definition: mydefs.hpp:52
LASindex::~LASindex
~LASindex()
Definition: lasindex.cpp:70
I32
int I32
Definition: mydefs.hpp:35
TRUE
#define TRUE
Definition: mydefs.hpp:137
LASreader::p_count
I64 p_count
Definition: lasreader.hpp:56
lasinterval.hpp
ByteStreamOut::put32bitsLE
virtual BOOL put32bitsLE(const U8 *bytes)=0
LASspatial
Definition: lasspatial.hpp:42
LASindex::complete
void complete(U32 minimum_points=100000, I32 maximum_intervals=-1)
Definition: lasindex.cpp:90
LASindex::intersect_tile
BOOL intersect_tile(const F32 ll_x, const F32 ll_y, const F32 size)
Definition: lasindex.cpp:227
LASindex::seek_next
BOOL seek_next(LASreader *lasreader)
Definition: lasindex.cpp:453
ByteStreamOut
Definition: bytestreamout.hpp:36
LASreader
Definition: lasreader.hpp:49
LASindex::intersect_rectangle
BOOL intersect_rectangle(const F64 r_min_x, const F64 r_min_y, const F64 r_max_x, const F64 r_max_y)
Definition: lasindex.cpp:217
ByteStreamIn::get32bitsLE
virtual void get32bitsLE(U8 *bytes)=0
LASpoint::get_y
F64 get_y() const
Definition: lasdefinitions.hpp:812
LASindex::read_next
BOOL read_next(LASreader *lasreader)
Definition: lasindex.cpp:438
LASindex::intersect_circle
BOOL intersect_circle(const F64 center_x, const F64 center_y, const F64 radius)
Definition: lasindex.cpp:237
LASspatialReadWrite::write
BOOL write(const LASspatial *spatial, ByteStreamOut *stream) const
Definition: lasspatial.cpp:76
ByteStreamIn
Definition: bytestreamin.hpp:36
LASindex::get_interval
LASinterval * get_interval() const
Definition: lasindex.cpp:212
LASindex::merge_intervals
BOOL merge_intervals()
Definition: lasindex.cpp:468
LASindex::LASindex
LASindex()
Definition: lasindex.cpp:58
LASindex::prepare
void prepare(LASspatial *spatial, I32 threshold=1000)
Definition: lasindex.cpp:76
U8
unsigned char U8
Definition: mydefs.hpp:41
BOOL
int BOOL
Definition: mydefs.hpp:57
bytestreamout_file.hpp
FALSE
#define FALSE
Definition: mydefs.hpp:133
file
FILE * file
Definition: arithmeticencoder.cpp:77
ByteStreamOutFileBE
Definition: bytestreamout_file.hpp:87
F32
float F32
Definition: mydefs.hpp:51
ByteStreamInFileLE
Definition: bytestreamin_file.hpp:65
LASindex::write
BOOL write(const char *file_name) const
Definition: lasindex.cpp:311
bytestreamin_file.hpp
std
Definition: HalfEdge.hpp:124
LASspatialReadWrite
Definition: lasspatial.hpp:84
IS_LITTLE_ENDIAN
BOOL IS_LITTLE_ENDIAN()
Definition: mydefs.hpp:144
lasspatial.hpp
lasindex.hpp
U32
unsigned int U32
Definition: mydefs.hpp:39
LASspatialReadWrite::read
LASspatial * read(ByteStreamIn *stream) const
Definition: lasspatial.cpp:38
LASindex::get_spatial
LASspatial * get_spatial() const
Definition: lasindex.cpp:207
LASpoint::get_x
F64 get_x() const
Definition: lasdefinitions.hpp:811
LASreader::read_point
BOOL read_point()
Definition: lasreader.hpp:74
ByteStreamIn::getBytes
virtual void getBytes(U8 *bytes, const U32 num_bytes)=0
LASindex::add
BOOL add(const LASpoint *point, const U32 index)
Definition: lasindex.cpp:84
ByteStreamOut::putBytes
virtual BOOL putBytes(const U8 *bytes, U32 num_bytes)=0
LASindex::print
void print(BOOL verbose)
Definition: lasindex.cpp:176
LASinterval
Definition: lasinterval.hpp:61
LASindex::has_intervals
BOOL has_intervals()
Definition: lasindex.cpp:253
ByteStreamOutFileLE
Definition: bytestreamout_file.hpp:67
ByteStreamInFileBE
Definition: bytestreamin_file.hpp:85


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