vtkVoronoiCore2D.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
#ifndef vtkVoronoiCore2D_h
#define vtkVoronoiCore2D_h

#include "vtkAnnularBinIterator.h"   // Iteration over the bins of the locator
#include "vtkLocatorInterface.h"     // Interface to spatial locators
#include "vtkPoints.h"               // for input points
#include "vtkSMPTools.h"             // SMP parallel processing
#include "vtkStaticPointLocator2D.h" // for locating nearby points
#include "vtkVoronoiCore.h"          // Core includes
#include "vtkVoronoiTile.h"          // Generate Voronoi convex tiles

VTK_ABI_NAMESPACE_BEGIN

struct vtkVoronoiClassifier2D
{
  // Optional regions ids for point classification.
  const int* Regions;

  // Constructors
  vtkVoronoiClassifier2D()
    : Regions(nullptr)
  {
  }
  vtkVoronoiClassifier2D(const int* regions)
    : Regions(regions)
  {
  }

  // Method required by vtkVoronoiCore2D.
  void Initialize(vtkVoronoiClassifier2D* c)
  {
    if (c)
    {
      this->Regions = c->Regions;
    }
  }

  // Method required by vtkVoronoiCore2D.
  const vtkVoronoiSpoke* AddAdjacencyInformation(vtkVoronoiTile& tile, vtkVoronoiWheelsType& wheels,
    vtkVoronoiSpokesType& spokes, int& numSpokes, int& maxPoints);

  // Method required by vtkVoronoiCore2D. By default, any region id >= 0 is
  // considered a valid inside region (<0 region values are reserved for
  // algorithm use). If no region ids have been specified, and the point id
  // is ptId >=0, then the point ptId is inside an interior region.
  bool IsInsideRegion(vtkIdType ptId)
  {
    if (!this->Regions)
    {
      return (ptId >= 0);
    }
    else
    {
      return (ptId >= 0 && this->Regions[ptId] >= 0);
    }
  }

  // Method required by vtkVoronoiCore2D. Determine if the two points
  // ptId and neiId (which form a spoke) are in the same region. It is
  // assumed that both (ptId,neiId >= 0), i.e., inside.
  bool IsSameRegion(vtkIdType ptId, vtkIdType neiId)
  {
    return (!this->Regions || this->Regions[ptId] == this->Regions[neiId]);
  }
}; // vtkVoronoiClassifier2D

template <class TCompositor, class TClassifier>
struct vtkVoronoi2DLocalData
{
  vtkIdType ThreadId;                         // assign a thread id [0,NumThreadsUsed)
  int MaxPoints;                              // the maximum number of points in any tile
  int NumPrunes;                              // total number of pruning operations
  vtkBatchIdsType LocalBatches;               // list of batches processed by this thread
  vtkVoronoiSpokesType LocalSpokes;           // connecting edges/spokes for each tile
  vtkAnnularBinIterator BIter;                // iterator over static point locator bins
  vtkVoronoiTile Tile;                        // computational 2D Voronoi tile algorithm
  typename TCompositor::LocalData Compositor; // gather data from compositing operations
  TClassifier Classifier;                     // Used to classify spokes (based on regions)

  vtkVoronoi2DLocalData()
    : ThreadId(-1)
    , MaxPoints(0)
    , NumPrunes(0)
  {
    this->LocalBatches.reserve(2048);
    this->LocalSpokes.reserve(2048);
  }
}; // vtkVoronoi2DLocalData

template <class TCompositor, class TClassifier>
using ThreadMapType = std::vector<vtkVoronoi2DLocalData<TCompositor, TClassifier>*>;

template <class TCompositor, class TClassifier = vtkVoronoiClassifier2D>
class vtkVoronoiCore2D
{
public:
  static std::unique_ptr<vtkVoronoiCore2D<TCompositor, TClassifier>> Execute(vtkAlgorithm* filter,
    unsigned int batchSize, vtkStaticPointLocator2D* loc, vtkPoints* inPts, double padding,
    vtkIdType maxClips, bool validate, double pruneTol, TCompositor* comp, TClassifier* cl);


  int GetNumberOfThreads() { return this->NumberOfThreads; }
  vtkVoronoi2DLocalData<TCompositor, TClassifier>* GetThreadData(int threadNum)
  {
    return this->ThreadMap[threadNum];
  }


  int GetMaximumNumberOfPoints() { return this->MaximumNumberOfPoints; }
  int GetNumberOfPrunes() { return this->NumberOfPrunes; }

  vtkVoronoiAdjacencyGraph& GetAdjacencyGraph() { return this->Graph; }

  vtkVoronoiCore2D(vtkAlgorithm* filter, vtkVoronoiBatchManager& batcher,
    vtkStaticPointLocator2D* loc, vtkPoints* inPts, double padding, vtkIdType maxClips,
    bool validate, double pruneTol, TCompositor* comp, TClassifier* c);


  void Initialize();
  void operator()(vtkIdType batchId, vtkIdType endBatchId);
  void Reduce();

  TCompositor Compositor;

  TClassifier Classifier;

  vtkVoronoiBatchManager Batcher;
  ThreadMapType<TCompositor, TClassifier> ThreadMap;

  vtkVoronoiAdjacencyGraph Graph;

  vtkIdType GetNumberOfPoints() { return this->NPts; }
  const double* GetPoints() { return this->Points; }

  vtkAlgorithm* Filter;

private:
  vtkIdType NPts;                   // The number of input points
  vtkPoints* InPoints;              // Input points as data array
  const double* Points;             // Input points as pointer to x-y-z AOS doubles
  vtkStaticPointLocator2D* Locator; // Used to (quickly) find nearby points
  double Padding;                   // The padding distance around the bounding box
  double Bounds[6];                 // locator bounds
  double PaddedBounds[6];           // the domain over which Voronoi is calculated
  vtkIdType MaxClips;               // Limit the number of half-space clips

  // Enable pruning of spokes (equivalent to deletion of a degenerate tile edges)
  bool Validate;            // Indicate whether to explicitly validate the mesh
  vtkIdType NumberOfPrunes; // If pruning is on, keep track of the number of prunes
  double PruneTolerance;    // Specify the square spoke prune tolerance

  // High-level information captured during processing
  int NumberOfThreads;       // Keep track of the number of threads used durinf processing
  int MaximumNumberOfPoints; // Maximum number of points in a generated Voronoi tile (this
                             // equals the maximum number of edges).

  // Storage local to each thread, as well as working/scratch arrays. We
  // don't want to allocate working arrays on every thread invocation. Thread
  // local storage saves lots of new/delete (e.g. the locator tuples).
  vtkSMPThreadLocal<vtkDist2TupleArray> Dist2Tuples;
  vtkSMPThreadLocal<vtkVoronoi2DLocalData<TCompositor, TClassifier>> LocalData;

  using vtkBinIterator = vtkAnnularBinIterator;
  bool BuildTile(vtkVoronoiTile& tile, vtkBinIterator* biter, const double* pts, vtkIdType maxClips,
    vtkDist2TupleArray& results, int& numPrunes);

public:
  struct ProduceWheelsAndSpokes
  {
    vtkVoronoiCore2D<TCompositor, TClassifier>* VC;
    ProduceWheelsAndSpokes(vtkVoronoiCore2D<TCompositor, TClassifier>* vc);
    void operator()(vtkIdType threadId, vtkIdType endThreadId);

    // Invoke the production of wheels and spokes
    static void Execute(vtkVoronoiCore2D<TCompositor, TClassifier>* vc);
  }; // ProduceWheelsAndSpokes

  struct TopologicalMerge
  {
    vtkVoronoiCore2D<TCompositor, TClassifier>* VC;
    TopologicalMerge(vtkVoronoiCore2D<TCompositor, TClassifier>* vc);

    vtkMergeTuples2DType MergeTuples; // temporary array for merging points
    vtkMergeMapType MergeMap;         // maps tile/hull point ids to merged point ids
    vtkIdType NumMergedPts;           // after merging, the number of points remaining

    vtkIdType GetNumberOfMergedPoints() { return this->NumMergedPts; }

    // Core Voronoi methods in support of vtkSMPTools
    void Initialize() {}
    void operator()(vtkIdType threadId, vtkIdType endThreadId);
    void Reduce();

    // Execute the topological point merge to produce a merge map.
    static std::unique_ptr<TopologicalMerge> Execute(
      vtkVoronoiCore2D<TCompositor, TClassifier>* vc);
  }; // TopologicalMerge

}; // vtkVoronoiCore2D

struct vtkEmptyVoronoi2DCompositor
{
  void Initialize(vtkIdType vtkNotUsed(numPts), vtkEmptyVoronoi2DCompositor*) {}
  void Finalize() {}

  struct LocalData
  {
    void Initialize(vtkEmptyVoronoi2DCompositor*) {}
    void AddData(vtkVoronoiTile&, int vtkNotUsed(numSpokes), const vtkVoronoiSpoke*) {}
  };
}; // vtkEmptyVoronoi2DCompositor

// Minimal classifier - just records the tile's number of points and edges. It
// still supports region classification.
struct vtkEmptyVoronoi2DClassifier
{
  // Optional regions ids for point classification.
  const int* Regions;

  // Constructor
  vtkEmptyVoronoi2DClassifier()
    : Regions(nullptr)
  {
  }
  vtkEmptyVoronoi2DClassifier(const int* regions)
    : Regions(regions)
  {
  }

  // Initialize
  void Initialize(vtkEmptyVoronoi2DClassifier* c)
  {
    if (c)
    {
      this->Regions = c->Regions;
    }
  }

  // Method required by vtkVoronoiCore2D. This vtkEmptyClassifier provides
  // the minimum information needed.
  const vtkVoronoiSpoke* AddAdjacencyInformation(vtkVoronoiTile& tile, vtkVoronoiWheelsType& wheels,
    vtkVoronoiSpokesType& vtkNotUsed(spokes), int& numSpokes, int& maxPoints)
  {
    int numPts = tile.GetNumberOfPoints();
    wheels[tile.GetGeneratorPointId()] = numPts; // numEdges == numSpokes == numPts
    maxPoints = (numPts > maxPoints ? numPts : maxPoints);
    numSpokes = 0;
    return nullptr;
  }

  // Method required by vtkVoronoiCore2D. By default, any region id >= 0 is
  // considered a valid inside region (<0 region values are reserved for
  // algorithm use). If no region ids have been specified, and the point id
  // is ptId >=0, then the point ptId is inside an interior region.
  bool IsInsideRegion(vtkIdType ptId)
  {
    if (!this->Regions)
    {
      return (ptId >= 0);
    }
    else
    {
      return (ptId >= 0 && this->Regions[ptId] >= 0);
    }
  }

  // Method required by vtkVoronoiCore2D. Determine if the two points
  // ptId and neiId (which form a spoke) are in the same region. It is
  // assumed that both (ptId,neiId >= 0), i.e., inside.
  bool IsSameRegion(vtkIdType ptId, vtkIdType neiId)
  {
    return (!this->Regions || this->Regions[ptId] == this->Regions[neiId]);
  }
}; // vtkEmptyVoronoi2DClassifier

VTK_ABI_NAMESPACE_END
#include "vtkVoronoiCore2D.txx"

#endif
// VTK-HeaderTest-Exclude: vtkVoronoiCore2D.h