Filters/General/vtkMergeCells.cxx
//-----------------------------------------------------------------------------
// Use a spatial locator to filter out duplicate points and map
// the new ids to their ids in the merged grid.
Use a spatial locator to filter out duplicate points and map
the new ids to their ids in the merged grid.
Use a spatial locator to filter out duplicate points and map the new ids to their ids in the merged grid .
vtkIdType* vtkMergeCells::MapPointsToIdsUsingLocator(vtkDataSet* set)
{
  vtkUnstructuredGrid* grid = this->UnstructuredGrid;
  vtkPoints* points0 = grid->GetPoints();
  vtkIdType npoints0 = this->NumberOfPoints;
  vtkPointSet* ps = vtkPointSet::SafeDownCast(set);
  vtkIdType npoints1 = set->GetNumberOfPoints();
  vtkSmartPointer<vtkPoints> points1;
  if (ps)
  {
    points1 = ps->GetPoints();
  }
  else
  {
    points1 = vtkSmartPointer<vtkPoints>::New();
    points1->SetNumberOfPoints(npoints1);
    for (vtkIdType ptId = 0; ptId < npoints1; ptId++)
    {
      points1->SetPoint(ptId, set->GetPoint(ptId));
    }
  }
  vtkIdType* idMap = new vtkIdType[npoints1];
  if (this->PointMergeTolerance == 0.0)
  {
    double bounds[6];
    set->GetBounds(bounds);
    if (npoints0 > 0)
    {
      double tmpBounds[6];
      points0->GetData()->SetNumberOfTuples(npoints0);
      grid->GetBounds(tmpBounds); 
      points0->GetData()->SetNumberOfTuples(this->TotalNumberOfPoints);
      bounds[0] = ((tmpBounds[0] < bounds[0]) ? tmpBounds[0] : bounds[0]);
      bounds[2] = ((tmpBounds[2] < bounds[2]) ? tmpBounds[2] : bounds[2]);
      bounds[4] = ((tmpBounds[4] < bounds[4]) ? tmpBounds[4] : bounds[4]);
      bounds[1] = ((tmpBounds[1] > bounds[1]) ? tmpBounds[1] : bounds[1]);
      bounds[3] = ((tmpBounds[3] > bounds[3]) ? tmpBounds[3] : bounds[3]);
      bounds[5] = ((tmpBounds[5] > bounds[5]) ? tmpBounds[5] : bounds[5]);
    }
    if (!this->Locator)
    {
      this->Locator = vtkSmartPointer<vtkMergePoints>::New();
      vtkNew<vtkPoints> ptarray;
      this->Locator->InitPointInsertion(ptarray, bounds);
    }
    vtkIdType newId;
    double x[3];
    for (vtkIdType ptId = 0; ptId < npoints1; ptId++)
    {
      points1->GetPoint(ptId, x);
      this->Locator->InsertUniquePoint(x, newId);
      idMap[ptId] = newId;
    }
  }
  else
  {
    vtkKdTree* kd = vtkKdTree::New();
    vtkPoints* ptArrays[2];
    int numArrays;
    if (npoints0 > 0)
    {
      points0->GetData()->SetNumberOfTuples(npoints0);
      ptArrays[0] = points0;
      ptArrays[1] = points1;
      numArrays = 2;
    }
    else
    {
      ptArrays[0] = points1;
      numArrays = 1;
    }
    vtkIdType nextNewLocalId = npoints0;
    kd->BuildLocatorFromPoints(ptArrays, numArrays);
    vtkIdTypeArray* pointToEquivClassMap =
      kd->BuildMapForDuplicatePoints(this->PointMergeTolerance);
    kd->Delete();
    if (npoints0 > 0)
    {
      points0->GetData()->SetNumberOfTuples(this->TotalNumberOfPoints);
    }
    std::map<vtkIdType, vtkIdType> newIdMap;
    if (npoints0 > 0) 
    {
      for (vtkIdType ptId = 0; ptId < npoints0; ptId++)
      {
        vtkIdType eqClassRep = pointToEquivClassMap->GetValue(ptId);
        if (eqClassRep != ptId)
        {
          newIdMap.insert(std::map<vtkIdType, vtkIdType>::value_type(eqClassRep, ptId));
        }
      }
    }
    for (vtkIdType ptId = 0; ptId < npoints1; ptId++)
    {
      vtkIdType eqClassRep = pointToEquivClassMap->GetValue(ptId + npoints0);
      if (eqClassRep < npoints0)
      {
        idMap[ptId] = eqClassRep; 
        continue;
      }
      std::pair<std::map<vtkIdType, vtkIdType>::iterator, bool> inserted =
        newIdMap.insert(std::map<vtkIdType, vtkIdType>::value_type(eqClassRep, nextNewLocalId));
      bool newEqClassRep = inserted.second;
      if (newEqClassRep)
      {
        idMap[ptId] = nextNewLocalId; 
        nextNewLocalId++;
      }
      else
      {
        idMap[ptId] = inserted.first->second; 
      }
    }
    pointToEquivClassMap->Delete();
    newIdMap.clear();
  }
  return idMap;
}
vtkIdType * vtkMergeCells :: MapPointsToIdsUsingLocator ( vtkDataSet * set ) { vtkUnstructuredGrid * grid = this -> UnstructuredGrid ; vtkPoints * points0 = grid -> GetPoints ( ) ; vtkIdType npoints0 = this -> NumberOfPoints ; vtkPointSet * ps = vtkPointSet :: SafeDownCast ( set ) ; vtkIdType npoints1 = set -> GetNumberOfPoints ( ) ; vtkSmartPointer < vtkPoints > points1 ; if ( ps ) { points1 = ps -> GetPoints ( ) ; } else { points1 = vtkSmartPointer < vtkPoints > :: New ( ) ; points1 -> SetNumberOfPoints ( npoints1 ) ; for ( vtkIdType ptId = 0 ; ptId < npoints1 ; ptId ++ ) { points1 -> SetPoint ( ptId , set -> GetPoint ( ptId ) ) ; } } vtkIdType * idMap = new vtkIdType [ npoints1 ] ; if ( this -> PointMergeTolerance == 0.0 ) { double bounds [ 6 ] ; set -> GetBounds ( bounds ) ; if ( npoints0 > 0 ) { double tmpBounds [ 6 ] ; points0 -> GetData ( ) -> SetNumberOfTuples ( npoints0 ) ; grid -> GetBounds ( tmpBounds ) ; points0 -> GetData ( ) -> SetNumberOfTuples ( this -> TotalNumberOfPoints ) ; bounds [ 0 ] = ( ( tmpBounds [ 0 ] < bounds [ 0 ] ) ? tmpBounds [ 0 ] : bounds [ 0 ] ) ; bounds [ 2 ] = ( ( tmpBounds [ 2 ] < bounds [ 2 ] ) ? tmpBounds [ 2 ] : bounds [ 2 ] ) ; bounds [ 4 ] = ( ( tmpBounds [ 4 ] < bounds [ 4 ] ) ? tmpBounds [ 4 ] : bounds [ 4 ] ) ; bounds [ 1 ] = ( ( tmpBounds [ 1 ] > bounds [ 1 ] ) ? tmpBounds [ 1 ] : bounds [ 1 ] ) ; bounds [ 3 ] = ( ( tmpBounds [ 3 ] > bounds [ 3 ] ) ? tmpBounds [ 3 ] : bounds [ 3 ] ) ; bounds [ 5 ] = ( ( tmpBounds [ 5 ] > bounds [ 5 ] ) ? tmpBounds [ 5 ] : bounds [ 5 ] ) ; } if ( ! this -> Locator ) { this -> Locator = vtkSmartPointer < vtkMergePoints > :: New ( ) ; vtkNew < vtkPoints > ptarray ; this -> Locator -> InitPointInsertion ( ptarray , bounds ) ; } vtkIdType newId ; double x [ 3 ] ; for ( vtkIdType ptId = 0 ; ptId < npoints1 ; ptId ++ ) { points1 -> GetPoint ( ptId , x ) ; this -> Locator -> InsertUniquePoint ( x , newId ) ; idMap [ ptId ] = newId ; } } else { vtkKdTree * kd = vtkKdTree :: New ( ) ; vtkPoints * ptArrays [ 2 ] ; int numArrays ; if ( npoints0 > 0 ) { points0 -> GetData ( ) -> SetNumberOfTuples ( npoints0 ) ; ptArrays [ 0 ] = points0 ; ptArrays [ 1 ] = points1 ; numArrays = 2 ; } else { ptArrays [ 0 ] = points1 ; numArrays = 1 ; } vtkIdType nextNewLocalId = npoints0 ; kd -> BuildLocatorFromPoints ( ptArrays , numArrays ) ; vtkIdTypeArray * pointToEquivClassMap = kd -> BuildMapForDuplicatePoints ( this -> PointMergeTolerance ) ; kd -> Delete ( ) ; if ( npoints0 > 0 ) { points0 -> GetData ( ) -> SetNumberOfTuples ( this -> TotalNumberOfPoints ) ; } std :: map < vtkIdType , vtkIdType > newIdMap ; if ( npoints0 > 0 ) { for ( vtkIdType ptId = 0 ; ptId < npoints0 ; ptId ++ ) { vtkIdType eqClassRep = pointToEquivClassMap -> GetValue ( ptId ) ; if ( eqClassRep != ptId ) { newIdMap . insert ( std :: map < vtkIdType , vtkIdType > :: value_type ( eqClassRep , ptId ) ) ; } } } for ( vtkIdType ptId = 0 ; ptId < npoints1 ; ptId ++ ) { vtkIdType eqClassRep = pointToEquivClassMap -> GetValue ( ptId + npoints0 ) ; if ( eqClassRep < npoints0 ) { idMap [ ptId ] = eqClassRep ; continue ; } std :: pair < std :: map < vtkIdType , vtkIdType > :: iterator , bool > inserted = newIdMap . insert ( std :: map < vtkIdType , vtkIdType > :: value_type ( eqClassRep , nextNewLocalId ) ) ; bool newEqClassRep = inserted . second ; if ( newEqClassRep ) { idMap [ ptId ] = nextNewLocalId ; nextNewLocalId ++ ; } else { idMap [ ptId ] = inserted . first -> second ; } } pointToEquivClassMap -> Delete ( ) ; newIdMap . clear ( ) ; } return idMap ; }
Use a spatial locator to filter out duplicate points and map
the new ids to their ids in the merged grid.
Use a spatial locator to filter out duplicate points and map the new ids to their ids in the merged grid .
// testing shows vtkMergePoints is fastest when tolerance is 0 // Prior to MapPointsToIdsUsingLocator(), points0->SetNumberOfPoints() // has been called to set the number of points to the upper bound on the // points TO BE merged and now points0->GetNumberOfPoints() does not // refer to the number of the points merged so far. Thus we need to // temporarily set the number to the latter such that grid->GetBounds() // is able to return the correct bounding information. This is a fix to // bug #0009626. // safe to call GetBounds() for real info // testing shows vtkKdTree is fastest when tolerance is > 0 // points0->GetNumberOfPoints() is equal to the upper bound // on the points in the final merged grid.  We need to temporarily // set it to the number of points added to the merged grid so far. // The map we get back isn't quite what we need. The range of // the map is a subset of original point IDs which each // represent an equivalence class of duplicate points. But the // point chosen to represent the class could be any one of the // equivalent points. We need to create a map that uses IDs // of points in the points0 array as the representative, and // then new logical contiguous point IDs // (npoints0, npoints0+1, ..., numUniquePoints-1) for the // points in the new set that are not duplicates of points // in the points0 array. // these were already a unique set // a duplicate of a point in the first set // here's a new unique point // a duplicate of a point in the new set