XYIncrementalDelaunay.h

Go to the documentation of this file.

//* This file is part of the MOOSE framework
//* https://mooseframework.inl.gov
//*
//* All rights reserved, see COPYRIGHT for full restrictions
//* https://github.com/idaholab/moose/blob/master/COPYRIGHT
//*
//* Licensed under LGPL 2.1, please see LICENSE for details
//* https://www.gnu.org/licenses/lgpl-2.1.html
 
#pragma once
 
#include <array>
#include <cstddef>
#include <limits>
#include <set>
#include <string>
#include <utility>
#include <vector>
 
class XYIncrementalDelaunay
{
public:
  static constexpr std::size_t invalid_index = std::numeric_limits<std::size_t>::max();
 
  struct Point2D
  {
    double x;
    double y;
  };
 
  struct Triangle
  {
    std::array<std::size_t, 3> vertices;
    std::array<std::size_t, 3> neighbors;
  };
 
  using Segment = std::pair<std::size_t, std::size_t>;
 
  static Segment makeSegment(std::size_t v0, std::size_t v1);
 
  void initialize(const std::vector<Point2D> & points, const std::vector<Segment> & segments);
 
  std::size_t insertPoint(const Point2D & p);
 
  void insertSegment(std::size_t v0, std::size_t v1);
 
  std::size_t numPoints() const;
 
  const Point2D & point(std::size_t id) const;
 
  std::vector<Triangle> getTriangles() const;
 
  bool isConstrainedSegment(std::size_t v0, std::size_t v1) const;
 
  const std::set<Segment> & constrainedSegments() const { return _constraints; }
 
  std::vector<std::string> checkInvariants() const;
 
  std::vector<std::string> checkEmptyCircumcircle() const;
 
private:
  static constexpr std::size_t _num_bounding = 3;
 
  static constexpr double _bounding_reach = 1000.0;
 
  const double * xy(std::size_t v) const { return &_vertices[v].x; }
 
  static bool isBounding(std::size_t v) { return v < _num_bounding; }
 
  std::size_t toInternal(std::size_t id) const;
 
  std::size_t toCaller(std::size_t v) const;
 
  bool isConstrainedEdge(std::size_t v0, std::size_t v1) const;
 
  unsigned int localVertexIndex(std::size_t t, std::size_t v) const;
 
  unsigned int localEdgeIndex(std::size_t t, const Segment & edge) const;
 
  bool containsPoint(std::size_t t, const Point2D & p) const;
 
  std::size_t locate(const Point2D & p) const;
 
  void growCavity(std::size_t seed, std::size_t v_new, std::set<std::size_t> & cavity) const;
 
  std::vector<std::size_t> retriangulate(const std::vector<std::size_t> & removed,
                                         const std::vector<std::array<std::size_t, 3>> & added);
 
  void triangulatePseudopolygon(std::size_t v_start,
                                std::size_t v_end,
                                const std::vector<std::size_t> & chain,
                                std::size_t first,
                                std::size_t last,
                                std::vector<std::array<std::size_t, 3>> & triangles) const;
 
  bool isStrictlyBetween(std::size_t v_first, std::size_t v_mid, std::size_t v_last) const;
 
  std::string vertexName(std::size_t v) const;
 
  std::vector<Point2D> _vertices;
 
  std::vector<Triangle> _triangles;
 
  std::vector<std::size_t> _vertex_triangle;
 
  std::set<Segment> _constraints;
 
  std::size_t _last_triangle = invalid_index;
};