C++ 凸包生成算法

由于我的极差记忆力，我打算把这个破玩意先记下来。因为以后会有改动(Delaunay三角网生成算法)，我不想把一个好的东西改坏了。。。

好吧……

凸包生成算法，：

1.先在指定的宽(width)高(height)范围内生成一堆随机点；

  1.1. 生成N个不重复的正整数，使用洗牌算法让生成的数字不重复；

  1.2. 将每个数字分解成坐标。可以设想一个二维数组，每个数字依次填进数组内。那么，对于数字A来说，它能够生成的坐标则为：

`x = A % width;`
`y = (A% width== 0) ? A / width : A / width+ 1);`
2. 对所有随机点进行排序；
  2.1.找到 y 值最小的点`pointYmin`；
  2.2. 计算每个离散点`pt`、`pointYmin`、和X轴组成角的弧度`radian`(或者角度`angle`也可以)。其中，点`pointYmin`为角心；
  2.3. 依照上面计算出的弧度进行排序。

3. 开始找凸包
  3.1.（我懒得写了……）https://www.cnblogs.com/aiguona/p/7232243.html
  3.2. 大体上就是，首先离散点集之中入栈两个点，然后需要计算每三个点`ptA`(栈内点，次顶点), `ptO`(栈内点，栈顶点), `ptB`(栈外点，当前点)之间的逆时针夹角，如果夹角是小于180（π）的,那么则`ptB`入栈，否则 `ptO`出栈。直到所有离散点都计算完成。

BugFix:

1.一系列的在VS2017（v141）无法编译通过的问题（SDK版本：10.0.17763.0）。

这其中包括STL模板参数中不允许存在const、va_start函数中不允许有引用变量、for each - in关键字被否决等等问题。

Note:

1. 重做，将成员函数改成了由index代表的点，而不是原来的存放点的原型。（2019.4.9）
2. 懒病作祟，有些代码值得优化，但现在没有那么做。

以下是代码……C++11

项目选项为 多字符集

File: stdinc.h

#include <cmath>
#include <random>
#include <stdarg.h>
#include <string>
#include <exception>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <cassert>
#include <windows.h>

#pragma once

#ifdef _DEBUG
	#define ErrorThrow(errMsg)  { LogThrow::ErrorOccur(errMsg, __FILE__, __LINE__);}
#else
	#define ErrorThrow(errMsg) {}
#endif // _DEBUG

#include <iostream>

static const double PI = 3.14159265358980/*...80... -> ...7932384626...*/;
static const double precision = 1000.0;
static const double doubleESP = 1e-008;

namespace LogThrow
{
	static void ErrorOccur(const std::string& errMsg, const std::string& fileName, int line)
	{
		std::string msg("[ERROR] " + errMsg + '\n' + "File: " + fileName + '\n' + "Line: " + std::to_string(line));
		std::logic_error(msg.c_str());
		MessageBox(NULL, msg.c_str(), NULL, MB_ICONINFORMATION | MB_OK);
		ExitProcess(0);
	}
};

namespace MyMathTools
{
	inline static bool LessThan(double a, double b)
	{
		if (a - b < doubleESP)
		{
			return true;
		}
		return false;
	}

	inline static bool IsEqual(double a, double b)
	{
		if (std::abs(a - b) <= doubleESP)
		{
			return true;
		}
		return false;
	}

};

File: Point2D.cpp

#include "stdinc.h"

#pragma once

//Point & Vector
template<typename T>
class Point2D
{
private:

public:
	typedef std::vector<Point2D<T>> Points;
	T x, y;

public:
	Point2D(T nx, T ny) :x(nx), y(ny)
	{
	}

	Point2D() :Point2D{ 0, 0 }
	{
	}

	Point2D(const Point2D& np) :Point2D{ np.x, np.y }
	{
	}

	void Init(T x, T y)
	{
		this->x = x;
		this->y = y;
	}

	void Transposition()
	{
		T total = x + y;
		x = total - x;
		y = total - y;
	}

	void operator= (const Point2D& np/*new point*/)
	{
		Init(np.x, np.y);
	}

	bool operator== (const Point2D& pointOther) const
	{
		if ((pointOther.x == this->x) &&
			(pointOther.y == this->y))
		{
			return true;
		}
		return false;
	}

	friend std::ostream& operator<<(std::ostream& out, const Point2D& pt)
	{
		out << "(" << pt.x << "," << pt.y << ")";
		return out;
	}

public:
	//[min, max)
	/*const */Point2D& RandomPoint(int maxX, int maxY)
	{
		if (maxX <= 0 || maxY <= 0)
		{
			std::logic_error("The less then 0!");
		}
		std::random_device rd;
		std::mt19937 mt(rd());

		this->x = mt() % maxX;
		this->y = mt() % maxY;

		//I can modify the left value.
		return *this;
	}

	template<typename T1, typename T2>
	static double Distance(const Point2D<T1>& ptA, const Point2D<T2>& ptB)
	{
		double cutX = ptB.x - ptA.x;
		double cutY = ptB.y - ptA.y;
		return std::pow((cutX * cutX + cutY * cutY), 0.50);
	}

	template<typename T1>
	double Distance(const Point2D<T1>& ptOther)
	{
		return Point2D::Distance<T, T1>(*this, ptOther);
	}

	//Without repetition: Shuffle algorithm.
	static void RandomPoints(int count, int maxX, int maxY, std::vector<Point2D<int>>& __out points)
	{
		//auto LcmFunc = [maxX, maxY](int numA, int numB)
		//{
		//  int max = (maxX > maxY) ? maxX : maxY;
		//  int min = maxX + maxY - max;
		//  long lcm = -1;
		//  for (int i = 1; i <= min; ++i)
		//  {
		//      lcm = static_cast<long>(max * i);
		//      if (lcm % min == 0)
		//      {
		//          break;
		//      }
		//  }
		//  return lcm;
		//};

		//int lcm = static_cast<char32_t>(LcmFunc(maxX, maxY));
		//if (lcm == -1)
		//{
		//  return false;
		//}

		if (count >= maxX * maxY * 0.5)
		{
			ErrorThrow("Error Count.");
		}

		points.clear();

		auto GetX = [maxX](int num)
		{
			return num % maxX;
		};

		auto GetY = [maxX](int num)
		{
			return (num % maxX == 0) ? num / maxX : num / maxX + 1;
		};

		static std::random_device rd;
		static std::mt19937 mt(rd());
		const long total = maxX * maxY;

		std::vector<long> nums;
		nums.resize(total);
		points.resize(count);
		for (long i = 0; i < total; ++i)
		{
			nums[i] = i;
		}

		for (int i = 0; i < count; ++i)
		{
			//It is array nums index.
			long randomNum = mt() % (total - i) + i;
			std::swap(nums[i], nums[randomNum]);

			//Swap over, the num[i] is new random number.
			//Get the point.
			points[i] = { GetX(nums[i]), GetY(nums[i]) };
		}
	}
};

template<typename T>
class Vector2D final : public Point2D<T>
{
public:
	Vector2D() : Point2D<T>()
	{
	}

	Vector2D(T nx, T ny) : Point2D<T>(nx, ny)
	{
	}

	Vector2D(const Vector2D& np) :Point2D<T>(np)
	{
	}

	double Length() const
	{
		return std::pow((this->x * this->x + this->y * this->y), .5);
	}

	//Vector AB
	void Vector(const Point2D<T>& ptA, const Point2D<T>& ptB)
	{
		this->Init(ptB.x - ptA.x, ptB.y - ptA.y);
	}

	double Radian(const Vector2D& otherVec, bool isQuadrant = true) const
	{
		return Vector2D::Radian(*this, otherVec, isQuadrant);
	}

	//anti-clockwise angle.
	//If the return value less than 0, the Radian is less than π.
	static double Radian(const Vector2D& vec1, const Vector2D& vec2, bool isQuadrant = true)
	{
		if (isQuadrant)
		{
			//CHECK IT:
			double radian = std::atan2(vec2.y, vec2.x) - std::atan2(vec1.y, vec1.x);        //return [-2π, 2π]
			if (radian < 0)
			{
				radian += 2 * PI;
			}
			return radian;
		}

		return std::acos(Vector2D::Dot(vec1, vec2) / (vec1.Length() * vec2.Length()));  //return [0, π]
	}

	double Angle(const Vector2D& otherVec, bool isQuadrant = true) const
	{
		return Vector2D::Angle(*this, otherVec, isQuadrant);
	}

	//The same as function Radian.
	static double Angle(const Vector2D& vec1, const Vector2D& vec2, bool isQuadrant = true)
	{
		return Vector2D::Radian(vec1, vec2, isQuadrant) / PI * 180;
	}

	T Dot(const Vector2D& otherVec) const
	{
		return Vector2D::Dot(*this, otherVec);
	}

	static T Dot(const Vector2D& vec1, const Vector2D& vec2)
	{
		return vec1.x * vec2.x + vec1.y * vec2.y;
	}

	T Cross(const Vector2D& otherVec) const
	{
		return Vector2D::Cross(*this, otherVec);
	}

	//2D Vector have no cross. But we can set the Z is 0.
	//So , return a value is (0, 0, Ax*By - Ay*Bx);
	static T Cross(const Vector2D& vec1, const Vector2D& vec2)
	{
		return vec1.x*vec2.y - vec1.y*vec2.x;
	}

};

File: ConvexHull.h

#pragma once

//#include "Line.cpp"
#include "Point2D.cpp"
#include "stdinc.h"
#include "ObjectSign.h"

typedef ObjectSign<Point2D<int>> Points;

using PointNode = ONode<Point2D<int>>;

class ConvexHull final
{
private:
	Points m_points;
	Points m_CHpoints;

public:
	void operator= (const ConvexHull&) = delete;

	ConvexHull();
	ConvexHull(const Points& points);
	~ConvexHull();

public:
	//void TestPoints();

	//void AddPoint(const Point2D<int>& __in newPoint);
	//void AddRandomPoints(int count, int maxX, int maxY);
	void GetConvexHullPoints(Points& __out points);
	void GetAllPoints(Points& __out points);

	void Generate();

	void Clear();

private:
	void SortPoints();
};

File: ConvexHull.cpp

#include "ConvexHull.h"
#include <algorithm>

ConvexHull::ConvexHull()
{

}

ConvexHull::ConvexHull(const Points& points) : m_points(points)
{
	//this->~ConvexHull();
	//m_points = points;
}

ConvexHull::~ConvexHull()
{

}

//void ConvexHull::AddPoint(const Point2D<int>& __in newPoint)
//{
//	m_points.Add(newPoint);
//}

void ConvexHull::GetConvexHullPoints(Points& __out points)
{
	points = m_CHpoints;
}

void ConvexHull::GetAllPoints(Points& __out points)
{
	points = m_points;
}

////Without repetition: Shuffle algorithm.
//void ConvexHull::AddRandomPoints(int count, int maxX, int maxY)
//{
//	std::vector<Point2D<int>> pointsArray;
//	Point2D<int>::RandomPoints(count, maxX, maxY, pointsArray);
//
//	m_points.Clear();
//	for (int i = 0; i < count; ++i)
//	{
//		const Point2D<int>& eachpt = pointsArray.at(i);
//		m_points[i] = eachpt;
//	}
//}

void ConvexHull::SortPoints()
{
	if (m_points.Size() == 0)
	{
		ErrorThrow("Empty Points.");
		return;
	}

	//Selecting a point what Y min.
	Point2D<int> pointYmin;
	m_points.Get(0, pointYmin);
	for(int i = 0; i < m_points.Size(); i++)
	{
		if (!m_points.IsExist(i))
		{
			continue;
		}

		const Point2D<int>& eachpt = m_points[i];
		if (eachpt.y < pointYmin.y)
		{
			pointYmin = eachpt;
		}
		else if (eachpt.y == pointYmin.y)
		{
			if (eachpt.x < pointYmin.x)
			{
				pointYmin = eachpt;
			}
		}
	}

	auto SortRuleFunc = [&pointYmin](const ONode<Point2D<int>>* pnA, const ONode<Point2D<int>>* pnB) -> bool
	{
		static const Vector2D<int> baseVecX = { 1, 0 };
		Point2D<int> ptA = pnA->_node;
		Point2D<int> ptB = pnB->_node;

		Vector2D<int> vecA;
		vecA.Vector(const_cast<const Point2D<int>&>(pointYmin), ptA);

		Vector2D<int> vecB;
		vecB.Vector(pointYmin, ptB);

		double radianA = Vector2D<int>::Radian(baseVecX, vecA);
		double radianB = Vector2D<int>::Radian(baseVecX, vecB);

		//If collinear occurs, the nearest is before.
		if (std::abs(radianA - radianB) <= doubleESP)
		{
			return vecA.Length() < vecB.Length();
		}

		//return (radianA - radianB) < doubleESP;   //ERROR: ATTENTION: Check the Strict Weak Ordering...
		return radianA < radianB;       //Ascending order.
	};

	m_points.Sort(SortRuleFunc);
}

void ConvexHull::Generate()
{
	const int pointsCount = static_cast<int>(m_points.Size());
	if (pointsCount < 3)
	{
		ErrorThrow("Points count too less.");
		return;
	}

	SortPoints();

	std::stack<PointNode> stackCHpt;
	stackCHpt.push(*(m_points.GetBySequence(0)));
	stackCHpt.push(*(m_points.GetBySequence(1)));

	int ptIndex = 2;    //Total is m_points.size().

	while (ptIndex < pointsCount)
	{
		PointNode pnO = stackCHpt.top();
		const Point2D<int>& ptO = pnO._node;

		stackCHpt.pop();
		PointNode pnA = stackCHpt.top();
		const Point2D<int>& ptA = pnA._node;

		stackCHpt.push(pnO);

		PointNode pnB = *(m_points.GetBySequence(ptIndex));
		Point2D<int> ptB = pnB._node;

		Vector2D<int> vecA, vecB;
		vecA.Vector(ptO, ptA);
		vecB.Vector(ptO, ptB);

		//Vector B turn to Vector A.
		double angle = Vector2D<int>::Angle(vecB, vecA);
		if ((angle - 0 >= 0) && (angle - 180 <= doubleESP))
		{
			stackCHpt.push(pnB);
			ptIndex++;
		}
		else
		{
			stackCHpt.pop(); //pop point O.
		}

		if (stackCHpt.size() < 2)
		{
			//If the sort rule is not ok...
			ErrorThrow("Error stackCHpt size.");
			return;
		}
	}
	/*Over Generation.*/

	//
	int lengthCHPoint = static_cast<int>(stackCHpt.size());
	m_CHpoints.Clear();
	for (int i = 0; i < lengthCHPoint; ++i)
	{
		const  PointNode& pn = stackCHpt.top();
		m_CHpoints.Add(pn);
		stackCHpt.pop();
	}
}

void ConvexHull::Clear()
{
	m_CHpoints.Clear();
	m_points.Clear();
}

//void ConvexHull::TestPoints()
//{
//	AddPoint({ 0, 0 });
//	AddPoint({ 5, 1 });
//	AddPoint({ 9, 2 });
//	AddPoint({ 1, 1 });
//	AddPoint({ 13, 6 });
//	AddPoint({ 12, 7 });
//}

File: Line.cpp (暂时没用到)

#include "Point2D.cpp"
#include <array>
#include <iostream>

#pragma once

template<typename T>
class Line
{
public:
	struct Equation
	{
	public:
		T A, B, C;

	public:
		//Ax + By + C = 0
		Equation()
		{
		}

		Equation(const Point2D<T>& ptA, const Point2D<T>& ptB)
		{
			(*this)(ptA, ptB);
		}
	public:
		void operator() (const Point2D<T>& ptA, const Point2D<T>& ptB)
		{
			A = ptB.y - ptA.y;
			B = ptA.x - ptB.x;
			C = ptB.x * ptA.y - ptA.x * ptB.y;
		}

		double GetY(double X)const
		{
			if (B == 0)
			{
				return INT_MAX;
			}

			return -1.0 * (C + A * X) / B;
		}

		double GetX(double Y) const
		{
			if (A == 0)
			{
				return INT_MAX;
			}

			return -1.0 * (C + B * Y) / A;
		}

		void GetSlope(Vector2D<double>& __out slope) const
		{
			if (B == 0) //X === -1.0 * C / A;
			{
				slope = { 0, -1.0 * C / A };
				return;
			}
			slope = { 1, -1.0 * A / B };
		}
	};

private:
	bool CheckLine(const Point2D<T>& ptA, const Point2D<T>& ptB) const
	{
		if (std::abs(ptA.x - ptB.x) <= doubleESP &&
			std::abs(ptA.y - ptB.y) <= doubleESP)
		{
			return false;
		}
		return true;
	}

public:
	Line() : Line({ 0, 0 }, { 1, 0 })
	{
	}

	Line(const Point2D<T>& a, const Point2D<T>& b) : ptA(a), ptB(b)
	{
		if (!CheckLine(a, b))
		{
			ErrorThrow("They are the same point.");
			return;
		}
		equation(a, b);
	}

	Line(const Line& nl) :Line{ nl.ptA, nl.ptB }
	{
	}

	Line(T xA, T yA, T xB, T yB) :Line({ xA, yA }, { xB, yB })
	{

	}

	void Init(const Point2D<T>& a, const Point2D<T>& b)
	{
		if (!CheckLine(a, b))
		{
			ErrorThrow("They are the same point.");
			return;
		}
		ptA = a;
		ptB = b;
		equation(a, b);
	}

	void Init(T xA, T yA, T xB, T yB)
	{
		if (!CheckLine({ xA, yA }, { xB, yB }))
		{
			ErrorThrow("They are the same point.");
			return;
		}
		ptA = { xA, yA };
		ptB = { xB, yB };
		equation(ptA, ptB);
	}

	void TransVector(Vector2D<T>& __out vec, bool isReverse/*B -> A*/ = false) const
	{
		if (isReverse) /*B -> A*/
			vec.Init(ptA.x - ptB.x, ptA.y - ptB.y);
		else /*A -> B*/
			vec.Init(ptB.x - ptA.x, ptB.y - ptA.y);
	}

	void operator= (const Line& nl)
	{
		Init(nl.ptA, nl.ptB);
	}

	void Midperpendicular(Line<double>& __out resLine) const
	{
		Point2D<double> midPoint = { 0.5 * (GetPointA().x + GetPointB().x), 0.5 * (GetPointA().y + GetPointB().y) };

		Vector2D<double> slope;
		equation.GetSlope(slope);

		Point2D<double> ptA, ptB;
		if (0 == slope.x)
		{
			//Perpendicular to the X-axis.
			ptA = { midPoint.x - 1.0, midPoint.y };
		}
		else
		{
			double k2 = -1.0 / (slope.y / slope.x);
			double b2 = midPoint.y - midPoint.x * k2;
			ptA = { midPoint.x + 1.0, k2 * (midPoint.x + 1.0) + b2 };   //Y = kX + b;
		}
		ptB = { midPoint.x, midPoint.y };

		resLine.Init(ptA, ptB);
	}

	static bool Intersection(const Line& __in lineA, const Line& __in lineB, Point2D<double>& __out pt)
	{
		if (Line::IsCollinear(4, lineA.ptA, lineA.ptB, lineB.ptA, lineB.ptB) == true)
		{
			return false;
		}

		T aA, aB, aC;
		T bA, bB, bC;

		aA = lineA.equation.A;
		aB = lineA.equation.B;
		aC = lineA.equation.C;

		bA = lineB.equation.A;
		bB = lineB.equation.B;
		bC = lineB.equation.C;

		double k = static_cast<double>(aA * bB - aB * bA);
		if (MyMathTools::IsEqual(k, 0.0))
		{
			return false;
		}
		pt = { (bB* -1 * aC - (-1) * bC * aB) / k, (aA * -1 * bC - (-1) * aC * bA) / k };
		return true;
	}

	void Intersection(const Line& __in lineOther, Point2D<double>& __out pt) const
	{
		Line::Intersection(*this, lineOther, pt);
	}

	static bool IsCollinear(int ptCount, const Point2D<T>& pt1, const Point2D<T>& pt2, const Point2D<T>& pt3, ...)
	{
		Vector2D<T> vecAB, vecBC;
		vecAB.Vector(pt1, pt2);
		vecBC.Vector(pt2, pt3);
		if (!MyMathTools::IsEqual(vecAB.x * 1.0 / vecBC.x, vecAB.y * 1.0 / vecBC.y))
		{
			return false;
		}

		//va_start argument must not have reference type
		auto tmppt = pt3;

		va_list aps;
		va_start(aps, tmppt);
		const Point2D<T>* pNextArg = &pt3;
		bool res = true;
		while (ptCount - 3 > 0)
		{
			const Point2D<T> ptX = va_arg(aps, const Point2D<T>);
			Vector2D<T> vecAx;
			vecAx.Vector(pt1, ptX);
			if (!MyMathTools::IsEqual(vecAB.x * 1.0 / vecAx.x, vecAB.y * 1.0 / vecAx.y))
			{
				res = false;
				break;
			}
			--ptCount;
		}

		va_end(aps);
		return res;
	}

	const Point2D<T>& GetPointA() const
	{
		return ptA;
	}

	const Point2D<T>& GetPointB() const
	{
		return ptB;
	}

private:
	Point2D<T> ptA, ptB;

public:
	Equation equation;
};

File: Triangle.h (暂时没用到)

#pragma once

#include "Point2D.cpp"
#include "Line.cpp"
#include "Circle.cpp"

class Triangle final
{
public:
	enum class EnumPTRelation: int
	{
		POINT_OUTSIDE = -1,
		POINT_INSIDE = 0,
		POINT_ON_VERTICE = 1,
		POINT_ON_LINE = 2
	};

	Triangle();
	Triangle(const Point2D<int>& ptA, const Point2D<int>& ptB, const Point2D<int>& ptC);

	~Triangle();

public:
	void Init(const Point2D<int>& ptA, const Point2D<int>& ptB, const Point2D<int>& ptC);

	//RelationPT: The Relation of Point and Triangle.
	EnumPTRelation RelationPT(const Point2D<int>& pt) const;
	void Circumcircle(Circle<double, double>& __out circle) const;
	double Area() const;

	void GetVertices(std::array<Point2D<int>, 3>& __out vs) const;
	void GetLines(std::array<Line<int>, 3>& __out ls) const;

private:
	std::array<Point2D<int>, 3> m_vertices /*m_vertex*/;
	std::array<Line<int>, 3> m_lines;
};

File: Triangle.cpp (暂时没用到)

#include "Triangle.h"

Triangle::Triangle() :Triangle({ 0, 0 }, { 0, 3 }, { 4, 0 })
{
}

Triangle::Triangle(const Point2D<int>& ptA, const Point2D<int>& ptB, const Point2D<int>& ptC)
{
	Init(ptA, ptB, ptC);
}

Triangle::~Triangle()
{
}

void Triangle::Circumcircle(Circle<double, double>& __out circle) const
{
	const Point2D<int> ptA = m_vertices[0];
	const Point2D<int> ptB = m_vertices[1];
	const Point2D<int> ptC = m_vertices[2];

	double A1, B1, C1, A2, B2, C2;
	A1 = 2.0 * (ptB.x - ptA.x);
	B1 = 2.0 * (ptB.y - ptA.y);
	C1 = ptB.x * ptB.x + ptB.y * ptB.y - ptA.x * ptA.x - ptA.y *ptA.y;

	A2 = 2.0 * (ptC.x - ptB.x);
	B2 = 2.0 * (ptC.y - ptB.y);
	C2 = ptC.x * ptC.x + ptC.y * ptC.y - ptB.x * ptB.x - ptB.y * ptB.y;

	circle.center.x = ((C1*B2) - (C2*B1)) / ((A1*B2) - (A2*B1));
	circle.center.y = ((A1*C2) - (A2*C1)) / ((A1*B2) - (A2*B1));
	circle.radius = std::pow((ptA.x - circle.center.x)*(ptA.x - circle.center.x) + (ptA.y - circle.center.y)*(ptA.y - circle.center.y), 0.5);
}

double Triangle::Area() const
{
	Vector2D<int> vecBA, vecBC;
	m_lines[0].TransVector(vecBA, true);
	m_lines[1].TransVector(vecBC);

	return 0.5 * Vector2D<int>::Cross(vecBA, vecBC);
}

void Triangle::GetVertices(std::array<Point2D<int>, 3>& vs) const
{
	vs = m_vertices;
}

void Triangle::GetLines(std::array<Line<int>, 3>& ls) const
{
	ls = m_lines;
}

void Triangle::Init(const Point2D<int>& ptA, const Point2D<int>& ptB, const Point2D<int>& ptC)
{
	if (Line<int>::IsCollinear(3, ptA, ptB, ptC))
	{
		ErrorThrow("It is Collinear.");
		return;
	}
	m_vertices[0] = ptA;
	m_vertices[1] = ptB;
	m_vertices[2] = ptC;

	m_lines[0].Init(ptA, ptB);
	m_lines[1].Init(ptB, ptC);
	m_lines[2].Init(ptC, ptA);
}

Triangle::EnumPTRelation Triangle::RelationPT(const Point2D<int>& pt) const
{
	Vector2D<int> vecPA, vecPB, vecPC;
	int64_t v1, v2, v3;

	vecPA.Vector(pt, m_vertices[0]);
	vecPB.Vector(pt, m_vertices[1]);
	vecPC.Vector(pt, m_vertices[2]);

	v1 = vecPA.Cross(vecPB);
	v2 = vecPB.Cross(vecPC);
	v3 = vecPC.Cross(vecPA);

	if (v1 * v2 * v3 == 0)
	{
		return EnumPTRelation::POINT_ON_VERTICE;	//The point and vertex coincidence.
	}

	//type long long, Do not use 'int'.
	int64_t relationR12 = v1 * v2;
	int64_t relationR13 = v1 * v3;
	if (relationR12 == 0 || relationR13 == 0)
	{
		return EnumPTRelation::POINT_ON_LINE; //The Point on the line.
	}

	if (relationR12 > 0 && relationR13 > 0)
	{
		return EnumPTRelation::POINT_INSIDE;	//The points inside triangle.
	}

	return EnumPTRelation::POINT_OUTSIDE;
}

File: Circle.cpp (暂时没用到)

#pragma once
#include "Point2D.cpp"

template<typename TC, typename TR>
class Circle final
{
public:
	Circle() :Circle({ 0,0 }, 1)
	{

	}

	Circle(const Point2D<TC>& centerPt, TR radius) :
		center(centerPt),
		radius(radius)
	{

	}

	double Area()
	{
		return PI * radius * radius;
	}

	double Perimeter()
	{
		return 2 * PI * radius;
	}

	template<typename TP>
	bool IsPointInCircle(const Point2D<TP>& pt)
	{
		return !MyMathTools::LessThan(radius, Point2D<TP>::Distance(center, pt));
	}

public:
	TR radius;
	Point2D<TC> center;
};

File: ObjectSign.h (命名不太好)

#pragma once

#include <unordered_map>
#include <set>
#include <functional>

#include "stdinc.h"

template <typename T>
class ONode
{
public:
	unsigned int _index;
	T _node;

private:

public:
	ONode()
	{
	}

	ONode(unsigned int index, const T& node)
	{
		Init(index, node);
	}

	ONode(const ONode<T>& other) :
		ONode(other._index, other._node)
	{
	}

	~ONode()
	{
	}

public:
	void Init(unsigned int index, const T& node) noexcept
	{
		if (static_cast<int>(index) > (INT_MAX >> 1))
		{
			ErrorThrow("The Index Is Too Large.");
			return;
		}

		_index = index;
		_node = node;
	}

	static ONode<T>* Alloc(unsigned int index, const T& node) noexcept
	{
		ONode<T>* ret;
		ret = new (std::nothrow) ONode<T>(index, node);

		return ret;
	}

	static void Free(ONode<T>*& p)
	{
		if (nullptr != p)
		{
			delete p;
			p = nullptr;
		}
	}
};

template <typename T>
class ObjectSign
{
public:
	ObjectSign()
	{
		Init();
	}

	ObjectSign(const ObjectSign& other)
	{
		Init(other);
	}

	~ObjectSign()
	{
		//Clear();
	}

	ObjectSign<T>& operator=(const ObjectSign& other)
	{
		this->Init(other);
		return *this;
	}

public:
	bool IsExist(unsigned index) const
	{
		return !(_relation.end() == _relation.find(index));
	}

	int Add(const T& ele)
	{
		const ONode<T> node(++_max, ele);
		return (Add(node)) ? _max : -1;
	}

	bool Add(const ONode<T>& node)
	{
		if (IsExist(node._index))
			return false;

		ONode<T>* pNewNode = ONode<T>::Alloc(node._index, node._node);
		if (pNewNode == nullptr)
		{
			return false;
		}

		_max = (_max < node._index) ? node._index : _max;
		if (!_lackIndex.empty())
		{
			std::set<size_t>::iterator lackIt = _lackIndex.begin();
			size_t index = *lackIt;

			_elements[index] = pNewNode;
			_relation.insert(std::make_pair(node._index, index));
			_lackIndex.erase(lackIt);

			return true;
		}

		_elements.push_back(pNewNode);
		_relation.insert(std::make_pair(node._index, _elements.size() - 1));
		return true;
	}

	bool Del(unsigned int index)
	{
		std::unordered_map<unsigned int, size_t>::iterator itRa = _relation.find(index);
		if (itRa == _relation.end())
		{
			return false;
		}

		size_t n = itRa->second;
		if (_elements[n]->_index != index)
		{
			ErrorThrow("Del Function Error! The Index Not Match.");
			return false;
		}
		_relation.erase(itRa);
		ONode<T>::Free(_elements[n]);
		_lackIndex.insert(n);

		return true;
	}

	bool Change(unsigned int index, const T& node)
	{
		std::unordered_map<unsigned int, size_t>::iterator itRa = _relation.find(index);
		if (itRa == _relation.end())
		{
			return false;
		}

		_elements[itRa->second]->_node = node;
		return true;
	}

	bool Get(unsigned int index, T& __out res) const
	{
		std::unordered_map<unsigned int, size_t>::const_iterator itRa = _relation.find(index);
		if (itRa == _relation.end())
		{
			return false;
		}

		res = _elements[itRa->second]->_node;
		return true;
	}

	const T& Get(unsigned int index) const
	{
		static T res;
		if (false == Get(index, res))
		{
			ErrorThrow("Not Found The Index.");
		}

		return res;
	}

	//Get element by index.
	T& operator[](unsigned int index)
	{
		if (!IsExist(index))
		{
			T tmp;
			ONode<T>* pNewNode = ONode<T>::Alloc(index, tmp);
			Add(*pNewNode);
		}
		return this->_elements[_relation[index]]->_node;
	}

	const T& operator[](unsigned int index) const
	{
		return Get(index);
	}

	//Get element by sequence.
	T& operator()(unsigned int sequence)
	{
		return GetBySequence(sequence)->_node;
	}

	const T& operator()(unsigned int sequence) const
	{
		ObjectSign* cthis = const_cast<ObjectSign*>(this);
		return cthis->GetBySequence(sequence)->_node;
	}

	const ONode<T>*const GetBySequence(unsigned int sequence) const
	{
		ObjectSign* cthis = const_cast<ObjectSign*>(this);
		return cthis->GetBySequence(sequence);
	}

	ONode<T>* GetBySequence(unsigned int sequence)
	{
		if (sequence >= _relation.size())
		{
			ErrorThrow("The sequence too large.");
			return nullptr;
		}

		if (_lackIndex.empty())
		{
			return _elements[sequence];
		}
		else
		{
			int lackCount = 0;
			for (std::set<size_t>::iterator it = _lackIndex.lower_bound(sequence); it != _lackIndex.begin(); --it)
			{
				lackCount++;
			}

			if (&*(_lackIndex.begin()) == nullptr)
			{
				lackCount += 1;
			}

			for (int i = sequence + lackCount; i < _elements.size(); i++)
			{
				ONode<T>* each = _elements[i];
				if (each == nullptr)
				{
					continue;
				}
				return _elements[i];
			}

			ErrorThrow("The element is not found. sequence is " + std::to_string(sequence) + "; Size is " + std::to_string(_relation.size()) + " .");
			return nullptr;
		}
	}

	void Clear()
	{
		if (_relation.empty())
		{
			return;
		}

		std::unordered_map<unsigned int, size_t>::iterator it = _relation.begin();
		for (; it != _relation.end(); it++)
		{
			ONode<T>::Free(_elements[it->second]);
		}

		_elements.clear();
		_relation.clear();
		_lackIndex.clear();
	}

	size_t Size() const
	{
		return _relation.size();
	}

	void Sort(
		const std::function<bool(const ONode<T>* A, const ONode<T>* B)>& SortRuleFunc)
	{
		std::vector<ONode<T>*> sortRes;
		sortRes.reserve(_elements.size());
		_lackIndex.clear();
		_relation.clear();

		for (auto it : _elements)
		{
			ONode<T>* pEach = &*it;
			if (pEach == nullptr)
			{
				continue;
			}

			sortRes.push_back(pEach);
		}

		std::sort(sortRes.begin(), sortRes.end(), SortRuleFunc);
		_elements.clear();

		_elements = sortRes;
		size_t idx = 0;
		for (auto it : _elements)
		{
			ONode<T>* pEach = &*it;
			_relation.insert(std::make_pair(pEach->_index, idx));
			++idx;
		}
	}

	private:
		void Init(int size = 0, bool isStrict = true)
		{
			Clear();
			_max = 0;
			_isStrict = isStrict;
			if (size <= 0)
			{
				return;
			}

			_elements.resize(size);
			for (int i = 0; i < size; ++i)
			{
				_lackIndex.insert(i);
			}
		}

		void Init(const ObjectSign& other)
		{
			this->Clear();

			this->_elements.assign(other._elements.begin(), other._elements.end());
			this->_lackIndex.insert(other._lackIndex.begin(), other._lackIndex.end());
			this->_relation.insert(other._relation.begin(), other._relation.end());
			this->_max = other._max;
			this->_isStrict = other._isStrict;
		}

private:
	std::vector<ONode<T>*> _elements;	

	std::unordered_map<unsigned int, size_t> _relation;
	std::set<size_t> _lackIndex;
	unsigned int _max;
	bool _isStrict;	//TODO:
};

执行结果：