itkVoronoiDiagram2DGenerator.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright NumFOCUS
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://www.apache.org/licenses/LICENSE-2.0.txt
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *
 *=========================================================================*/
#ifndef itkVoronoiDiagram2DGenerator_h
#define itkVoronoiDiagram2DGenerator_h
 
#include "itkMeshSource.h"
#include "itkVoronoiDiagram2D.h"
 
#include <vector>
 
namespace itk
{
template <typename TCoordType>
class ITK_TEMPLATE_EXPORT VoronoiDiagram2DGenerator : public MeshSource<VoronoiDiagram2D<TCoordType>>
{
public:
  ITK_DISALLOW_COPY_AND_MOVE(VoronoiDiagram2DGenerator);
 
  using Self = VoronoiDiagram2DGenerator;
  using Superclass = MeshSource<VoronoiDiagram2D<TCoordType>>;
  using Pointer = SmartPointer<Self>;
  using ConstPointer = SmartPointer<const Self>;
 
  itkNewMacro(Self);
 
  itkOverrideGetNameOfClassMacro(VoronoiDiagram2DGenerator);
 
  using VoronoidDiagramType = VoronoiDiagram2D<TCoordType>;
  using VDMesh = VoronoidDiagramType;
  using SeedsIterator = typename VDMesh::SeedsIterator;
  using OutputType = typename VDMesh::Pointer;
  using PointType = typename VDMesh::PointType;
  using SeedsType = typename VDMesh::SeedsType;
  using EdgeInfo = typename VDMesh::EdgeInfo;
  using EdgeInfoDQ = typename VDMesh::EdgeInfoDQ;
  using CoordRepType = typename VDMesh::CoordRepType;
  using VoronoiEdge = typename VDMesh::VoronoiEdge;
 
  itkGetConstMacro(NumberOfSeeds, unsigned int);
 
  void
  SetSeeds(int num, SeedsIterator begin);
 
  void
  AddSeeds(int num, SeedsIterator begin);
 
  void AddOneSeed(PointType);
 
  void
  SortSeeds();
 
  void
  GenerateOutputInformation() override
  {}
 
  void
  UpdateDiagram();
 
  void
  SetBoundary(PointType vorsize);
 
  void
  SetOrigin(PointType vorsize);
 
  void
  SetRandomSeeds(int num);
 
  PointType
  GetSeed(int SeedID);
 
protected:
  VoronoiDiagram2DGenerator();
  ~VoronoiDiagram2DGenerator() override = default;
  void
  PrintSelf(std::ostream & os, Indent indent) const override;
 
  void
  GenerateData() override;
 
private:
  unsigned int m_NumberOfSeeds{ 0 };
  PointType    m_VorBoundary{};
  OutputType   m_OutputVD{};
  SeedsType    m_Seeds{};
 
  static bool
  comp(PointType arg1, PointType arg2);
 
  class FortuneSite;
  class FortuneEdge;
  class FortuneHalfEdge;
 
  // All private nested classes must be friend classes to work with SunOS-CC
  // compiler. If not, the private nested classes will not be able to access
  // each other.
  friend class FortuneSite;
  friend class FortuneEdge;
  friend class FortuneHalfEdge;
 
  class FortuneSite
  {
  public:
    PointType m_Coord;
    int       m_Sitenbr;
 
    FortuneSite()
      : m_Sitenbr(NumericTraits<int>::max())
    {
      m_Coord.Fill(NumericTraits<CoordRepType>::max());
    }
 
    ~FortuneSite() = default;
  };
 
  class FortuneEdge
  {
  public:
    float         m_A{ 0.0 }, m_B{ 0.0 }, m_C{ 0.0 }; // explicit line function: Ax + By = C;
    FortuneSite * m_Ep[2];
    FortuneSite * m_Reg[2];
    int           m_Edgenbr{ 0 };
 
    FortuneEdge() { m_Ep[0] = m_Ep[1] = m_Reg[0] = m_Reg[1] = nullptr; }
 
    ~FortuneEdge() = default;
  };
 
  class FortuneHalfEdge
  {
  public:
    FortuneHalfEdge * m_Left;
    FortuneHalfEdge * m_Right;
    FortuneEdge *     m_Edge;
    bool              m_RorL{ false };
    FortuneSite *     m_Vert;
    double            m_Ystar{ 0.0 };
    FortuneHalfEdge * m_Next;
 
    FortuneHalfEdge()
      : m_Left(nullptr)
      , m_Right(nullptr)
      , m_Edge(nullptr)
      , m_Vert(nullptr)
      , m_Next(nullptr)
    {}
 
    FortuneHalfEdge(const FortuneHalfEdge & edge)
      : m_Left(edge.m_Left)
      , m_Right(edge.m_Right)
      , m_Edge(edge.m_Edge)
      , m_RorL(edge.m_RorL)
      , m_Vert(edge.m_Vert)
      , m_Ystar(edge.m_Ystar)
      , m_Next(edge.m_Next)
    {}
 
    ~FortuneHalfEdge() = default;
  };
 
  double m_Pxmin{ 0.0 };
  double m_Pxmax{ 0.0 };
  double m_Pymin{ 0.0 };
  double m_Pymax{ 0.0 };
  double m_Deltax{ 0.0 };
  double m_Deltay{ 0.0 };
  double m_SqrtNSites{ 0.0 };
 
  unsigned int                 m_PQcount{ 0 };
  int                          m_PQmin{ 0 };
  unsigned int                 m_PQhashsize{ 0 };
  unsigned int                 m_Nedges{ 0 };
  unsigned int                 m_Nvert{ 0 };
  FortuneSite *                m_BottomSite{};
  std::vector<FortuneHalfEdge> m_PQHash{};
 
  unsigned int                   m_ELhashsize{ 0 };
  FortuneHalfEdge                m_ELleftend{};
  FortuneHalfEdge                m_ELrightend{};
  std::vector<FortuneHalfEdge *> m_ELHash{};
 
  FortuneEdge              m_DELETED{};
  std::vector<FortuneSite> m_SeedSites{};
 
  bool
  differentPoint(PointType p1, PointType p2);
 
  bool
  almostsame(CoordRepType p1, CoordRepType p2);
 
  unsigned char
  Pointonbnd(int VertID);
 
  void
  GenerateVDFortune();
 
  void
  ConstructDiagram();
 
  void
  createHalfEdge(FortuneHalfEdge * task, FortuneEdge * e, bool pm);
 
  void
  PQshowMin(PointType * answer);
 
  FortuneHalfEdge *
  findLeftHE(PointType * p);
 
  FortuneHalfEdge *
  ELgethash(int b);
 
  bool
  right_of(FortuneHalfEdge * el, PointType * p);
 
  FortuneSite *
  getRightReg(FortuneHalfEdge * he);
 
  FortuneSite *
  getLeftReg(FortuneHalfEdge * he);
 
  void
  bisect(FortuneEdge *, FortuneSite * s1, FortuneSite * s2);
 
  void
  insertEdgeList(FortuneHalfEdge * lbase, FortuneHalfEdge * lnew);
 
  void
  intersect(FortuneSite * newV, FortuneHalfEdge * el1, FortuneHalfEdge * el2);
 
  void
  deletePQ(FortuneHalfEdge * task);
 
  void
  deleteEdgeList(FortuneHalfEdge * task);
 
  int
  PQbucket(FortuneHalfEdge * task);
 
  void
  clip_line(FortuneEdge * task);
 
  void
  insertPQ(FortuneHalfEdge * he, FortuneSite * v, double offset);
 
  double
  dist(FortuneSite * s1, FortuneSite * s2);
 
  FortuneHalfEdge *
  getPQmin();
 
  void
  makeEndPoint(FortuneEdge * task, bool lr, FortuneSite * ends);
};
} // end namespace itk
 
#ifndef ITK_MANUAL_INSTANTIATION
#  include "itkVoronoiDiagram2DGenerator.hxx"
#endif
 
#endif