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 ==…