//Алгоритм построения выпуклой оболочки методом "упаковки подарка"
#ifndef _CONVEX_1_H_
#define _CONVEX_1_H_

#include "pointsandlines.h"
//Алгоритм возвращает индексы точек множества pset, которые принадлежат его выпуклой оболочке.
//Точки выпуклой оболочки множества pset, в hull упорядочены против часовой стрелки.
template <class Num> void CalcConvexHull(SPointSet<Num>& pset, SChain<Num>& hull){
    if(hull.Indexes!=NULL)
        delete[] hull.Indexes;
    hull.point_set=pset.points;
    hull.Indexes=new int[pset.n];       //выделяем память под хранение индексов точек выпуклой оболочки
    hull.n=0;                           //количество точек выпуклой оболочки - на данный момент - 0
    hull.Indexes[0]=pset.LeftMost();    //ищем первую точку выпуклой оболочки - например, самую левую
    int mindex;                         //индекс точки-кандидата на добавление в выпуклую оболочку
    do{
        if(hull.Indexes[hull.n]!=0)     //инициализирем индекс точки-кандидата (теоретчески, в качестве начального индекса можно взять индекс произвольной точки множества pset)
            mindex=0;
        else
            mindex=1;
        for(int i=1;i<pset.n;i++){      //цикл для всех точек множества pset TODO: i=2
            int cmpi;
            if((i!=mindex)&&(i!=hull.Indexes[hull.n])){
                cmpi=Orientation(pset.points[hull.Indexes[hull.n]],pset.points[mindex],pset.points[i]); //вычисляем ориентацию трёх точек: последняя найденная точка, точка-кандидат, текущая точка
                if(cmpi>0)              //если ориентация тройки точек положительна - точкой-кандидатом становится текущая точка
                    mindex=i;
                else if(cmpi==0){       //если три точки лежат на одной прямой, точкой-кандидитом становится точка, расопложенная дальше от последняя найденная точка
                    cmpi=SelectByR(pset.points[mindex],pset.points[i],pset.points[hull.Indexes[hull.n]]);
                    if(cmpi==COMPARE_SMALLER)
                        mindex=i;       //из двух точек под одинаковым углом выбираем дальнюю.
                }
            }
        }
        //записываем новую найденную точку в hull
        hull.n++;
        if(hull.Indexes[0]==mindex)     //условие окончания цикла - индекс найденной точки совпадает с индексом первой точки, т.е. оболочка замкнулась
            break;
        hull.Indexes[hull.n]=mindex;    //hull.Indexes[hull.n] в этом цикле содержит последнюю найденную точку выпуклой оболочки
    }while(1);
}

#endif