기하학 적 알고리즘 - 점 집합 볼록 패키지

extern "C" class ALGORITHMLIB ConvexHull
{
public:
	ConvexHull();
	~ConvexHull();

	DataStruct::Stack::DynStack<:point>> Run(const DataStruct::Array::DynArray<:point>>& poArr_);
};

ConvexHull::ConvexHull()
{

}

ConvexHull::~ConvexHull()
{

}

DataStruct::Stack::DynStack<:point>> ConvexHull::Run(
	const DataStruct::Array::DynArray<:point>>& arrPos_)
{
	//      s
	//     n   y      ，       y     ，   x       
	//     n-1  ，      s            ，          n-1      
	DataStruct::Stack::DynStack<:point>> _sRet;
	int _nSize = arrPos_.GetSize();
	if (_nSize <= 3)
	{
		return _sRet;
	}

	Math::Point<2> _poS = arrPos_[0];
	for (int _i = 1; _i < _nSize; _i++)
	{
		if (arrPos_[_i].m_nPos[1] < _poS.m_nPos[1]
			|| (arrPos_[_i].m_nPos[1] == _poS.m_nPos[1] && arrPos_[_i].m_nPos[0] < _poS.m_nPos[0]))
		{
			_poS = arrPos_[_i];
		}
	}

	//  n  ，      _poS            n    
	DataStruct::Array::DynArray<:point>> _arrPos = arrPos_;
	_arrPos.Sort([_poS](const Math::Point<2>& po1_, const Math::Point<2>& po2_)->int
	{
		Math::Vector<2> _vec1(_poS, po1_);
		Math::Vector<2> _vec2(_poS, po2_);
		double _nAngle1 = Geometry::GetAngle(_vec1);
		double _nAngle2 = Geometry::GetAngle(_vec2);
		double _nRet = _nAngle1 - _nAngle2;
		if (_nRet > 0)
		{
			return 1;
		}
		else if (_nRet < 0)
		{
			return -1;
		}
		else
		{
			double _nLen1 = _vec1.GetLength();
			double _nLen2 = _vec2.GetLength();
			_nRet = _nLen1 - _nLen2;
			if (_nRet > 0)
			{
				return 1;
			}
			else if (_nRet < 0)
			{
				return -1;
			}
			else
			{
				return 0;
			}
		}
	});

	//  s  ，       p  
	_sRet.Push(_poS);
	int _nIndex = 0;
	while (_nIndex < _nSize)
	{
		if (_poS == _arrPos[_nIndex])
		{
			_nIndex++;
		}
		else
		{
			_sRet.Push(_arrPos[_nIndex]);
			_nIndex++;
			break;
		}
	}

	//         ，       
	for (int _i = _nIndex; _i < _nSize; _i++)
	{
		//      q
		//  q，   ，        
		while (true)
		{
			//              ，             q   ， ， q    ，         
			//              ，                q   ，       。
			//    ，    q，   ，       
			//         q    ，         ，  ，         。
			if (_sRet.Peek() == _arrPos[_i])
			{
				break;
			}

			Math::Vector<2> _vec1(_sRet.Peek(1), _sRet.Peek());
			Math::Vector<2> _vec2(_sRet.Peek(), _arrPos[_i]);
			Geometry::ROTATE_DIRECTION _dir = Geometry::TestDirection(_vec1, _vec2);
			if (_dir == Geometry::ROTATE_DIRECTION::ANTICLOCK)
			{
				_sRet.Push(_arrPos[_i]);
				break;
			}
			else if (_dir == Geometry::ROTATE_DIRECTION::NO_ROTATE)
			{
				_sRet.Pop();
				_sRet.Push(_arrPos[_i]);
				break;
			}
			else
			{
				_sRet.Pop();
			}
		}
	}

	//       ，
	//            3，          
	//          3，               
	if (_sRet.GetSize() < 3)
	{
		return DataStruct::Stack::DynStack<:point>>();
	}
	else
	{
		return _sRet;
	}
} 

     ：
    ：    ，        。
   
               A
                    
    A           ：
        y  【  y    x   】 p         n    0,...,n-1  ，
    
 i  [0,n-1], j=(i+1) % (n)
 
i                           j     

           
        

     ：
    ，            y  【  y    x   】 p               。
           ，             。
       p      q          。

  ：
   ，
 p q         ，     。       。
 k    
    t   p     ，       ， ，  ，    +t，       p             。
    t   p      ，       ，       
  t        ，     t
  t  p             ，           ，  t               p             。

1.    t   p     ，        ，
 q1     ，q2      
1.1. q2->q1        q1->t
 ，     1
  q2->q1,q1->t      
q1->t,t->p       
       ，p...q1          
     p...q1,t               。       。
1.2. q2->q1        q1->t
      q1
       p->...->q2->t->p       q1
  ，      ，    q2->q1,q1->t        ，  t p->q1     ，     。
    ，       
p->...->t          
2.    t   p     ，        ，
2.1.  t        ，     t，
     p...q1               。       。
2.1.   t  p             ，           ，       
     p...p2,t               。       。
  ，
k