Method merge_intervals

LASzip/src/lasinterval.cpp:185–298

merge adjacent intervals with small gaps in cells to reduce total interval number to maximum

// merge adjacent intervals with small gaps in cells to reduce total interval number to maximum
void LASinterval::merge_intervals(U32 maximum_intervals)
{
  U32 diff = 0;
  LASintervalCell* cell;
  LASintervalCell* delete_cell;

  // each cell has minimum one interval

  if (maximum_intervals < get_number_cells())
  {
    maximum_intervals = 0;
  }
  else
  {
    maximum_intervals -= get_number_cells();
  }

  // order intervals by smallest gap

  my_cell_map map;
  my_cell_hash::iterator hash_element = ((my_cell_hash*)cells)->begin();
  while (hash_element != ((my_cell_hash*)cells)->end())
  {
    cell = (*hash_element).second;
    while (cell->next)
    {
      diff = cell->next->start - cell->end - 1;
      map.insert(my_cell_map::value_type(diff, cell));
      cell = cell->next;
    }
    hash_element++;
  }

  // maybe nothing to do
  if (map.size() <= maximum_intervals)
  {
    if (map.size() == 0)
    {
      LASMessage(LAS_VERBOSE, "maximum_intervals: %u number of interval gaps: 0 ", maximum_intervals);
    }
    else
    {
      diff = (*(map.begin())).first;
      LASMessage(LAS_VERBOSE,"maximum_intervals: %u number of interval gaps: %u next largest interval gap %u", maximum_intervals, (U32)map.size(), diff);
    }
    return;
  }

  my_cell_map::iterator map_element;
  U32 size = (U32)map.size();

  while (size > maximum_intervals)
  {
    map_element = map.begin();
    diff = (*map_element).first;
    cell = (*map_element).second;
    map.erase(map_element);
    if ((cell->start == 1) && (cell->end == 0)) // the (start == 1 && end == 0) signals that the cell is to be deleted