Implementation of Delaunary Triangulation with Point-by-Point Insertion Method (with C++ Code)

Point-by-point insertion method is a classic convex closure shrinkage algorithm. The idea is to first find the smallest convex hull edge containing the data area, and form a Delaunary triangulation from the outside to the inside from the polygon. Therefore, every time it inserts a new point, it will delete the corresponding triangles to construct a triangulation network. This process is often accompanied by a large number of query calculations, which also leads to its powerlessness in the face of a large amount of data. But its idea is very simple and ingenious, and it is more suitable for implementation through programs

Point2.hpp

#ifndef POINT2
#define POINT2

#include <math.h>

namespace DT {

  //因为并没有用的指针动态分配内存，所以这里使用class与struct没有什么区别
  template<typename T>
  class Point2
  {
  public:
   T x;
   T y;
   Point2() = default;  //使用默认的构造函数
   Point2(const Point2<T> &point) = default;  //使用默认的拷贝构造函数
   Point2(const T point_x, const T point_y) //一般构造函数
    :x(point_x), y(point_y)
   {}

   T Distance2(const Point2<T> &point) const {  //两点之间距离的平方
    const T dx = this->x - point.x;
    const T dy = this->y - point.y;
    return dx * dx + dy *dy;
   }

   T Distance(const Point2<T> &point)const {
    return sqrt(Distance2(point));
   }

   T Norm2() const {  //点到原点的距离平方
    return x*x + y*y;
   }

   Point2 &operator= (const Point2<T>&) = default; //使用默认的拷贝构造函数
   Point2 &operator= (Point2&&) = default;
   bool operator ==…