Алгоритм Киркпатрика-Зайделя / Source / chnew

#include "stdafx.h"
#include <math.h>
#include "CH.h"

//#define n_fin "List_p.TXT"
const gr_x=1024,gr_y=768;
const double sc_x=gr_x,sc_y=gr_y,NaN=1e20;
const double eps=0.00001;

uint all_el=0;

COLORREF cDivLine=RGB(255,0,0);
int psDivLine = PS_SOLID;
int wDivLine = 1;

COLORREF cDivPoint=RGB(255,0,0);
int psDivPoint = PS_SOLID;
int wDivPoint = 1;

COLORREF cMedia=RGB(100,0,100);
int psMedia = PS_SOLID;
int wMedia = 1;

COLORREF cPairs=RGB(0,255,0);
int psPairs = PS_SOLID;
int wPairs = 1;

COLORREF cLifePoint=RGB(0,0,255);
int psLifePoint = PS_SOLID;
int wLifePoint = 1;

COLORREF cDiedPoint=RGB(40,200,200);
int psDiedPoint = PS_SOLID;
int wDiedPoint = 1;

COLORREF cOpora=RGB(0,0,0);
int psOpora = PS_DASH;
int wOpora = 1;

COLORREF cCurCH=RGB(45,0,0);
int psCurCH = PS_SOLID;
int wCurCH = 1;

COLORREF cCH=RGB(255,255,0);
int psCH = PS_SOLID;
int wCH = 2;

COLORREF cNewEdge=RGB(255,255,0);
int psNewEdge=PS_SOLID;
int wNewEdge=1;

//===================================
void PrErr(char *s,char *FName)
{ char s1[256]="";
	sprintf(s1,s,FName);
	AfxMessageBox(s1,MB_OK|MB_ICONSTOP);	
	exit (1);
}

//===================================
tpoint* ReadMas(TMyPointVector &p)
{  
		char *FName="ReadFin";
		uint i;
		tpoint *Ar=NULL;
	 	 
	 all_el=p.N();
	 Ar=(tpoint*) calloc(all_el,sizeof(tpoint));
//com	 if (Ar==NULL) { PrErr("%s :Error not enough memory\n",FName);}
	 for (i=0;i<all_el;i++)
	 {
		 Ar[i].x=(double) p.X(i);
		 Ar[i].y=(double) p.Y(i);
	 }
	return Ar;
}
//===================================
int VDraw_A(tpoint* Ar,uint end,TImage &Img,COLORREF Color, int PenStyle, int nWidth,int f)
{
	CPen pen(PenStyle, nWidth, Color);
    CPen *pOldPen = Img.hMem.SelectObject(&pen);

	CBrush hBrush(Color);
    CBrush  *pOldBrush = Img.hMem.SelectObject(&hBrush);

	for (uint i=0;i<=end;i++)
	{
		if (f)
		 {	
	 Img.hMem.MoveTo((int) Ar[i].x, 0);
     Img.hMem.LineTo((int) Ar[i].x, (int) gr_y);
		}
	 	else
		 {	//fillellipse(Ar[i].x*sc_x,gr_y-Ar[i].y*sc_y,2,2);
			//circle(Ar[i].x*sc_x,gr_y-Ar[i].y*sc_y,2);
		Img.hMem.Ellipse(Ar[i].x-3, Ar[i].y-3,Ar[i].x+4, Ar[i].y+4);
			}
	}
	
	Img.hMem.SelectObject(pOldBrush);
	Img.hMem.SelectObject(pOldPen);
	return 0;
}
//===================================
int VDraw_P(const tpqs* P,uint end,TImage &Img,COLORREF Color, int PenStyle, int nWidth)
{
	CPen pen(PenStyle, nWidth, Color);
    CPen *pOldPen = Img.hMem.SelectObject(&pen);

	CString hString;
	uint i=0;
	for (i=0;i<=end;i++)
	{
	 Img.hMem.MoveTo((int) P[i].p.x, (int) P[i].p.y);
     Img.hMem.LineTo((int) P[i].q.x, (int) P[i].q.y);
	 	
	 if (P[i].s>=NaN) {hString.Format("%2.2f",NaN);}
	  else {hString.Format("%2.2f",P[i].s);}
	 
	 Img.hMem.TextOut((int) P[i].p.x, (int) P[i].p.y, hString);
	}
	Img.hMem.SelectObject(pOldPen);
	return 0;
}
//===================================
int VDraw_Q(QUEUE<tpqs> *Q,TImage &Img,COLORREF Color, int PenStyle, int nWidth)
{
	CPen pen(PenStyle, nWidth, Color);
    CPen *pOldPen = Img.hMem.SelectObject(&pen);

	CString hString;
	const tpqs* p;
		Q->Go_Beg();
		do
		{
			if (Q->IsEnd()) {break;}
			p=Q->Go_Next();

	 Img.hMem.MoveTo((int) p->p.x, (int) p->p.y);
     Img.hMem.LineTo((int) p->q.x, (int) p->q.y);

		if (p->s>=NaN)
			{hString.Format("%2.2f",NaN);}
		else
			{hString.Format("%2.2f",p->s);}

		
       Img.hMem.TextOut((int) p->p.x, (int) p->p.y, hString);
		
		}
		while(!Q->IsEnd());
		Q->Go_Beg();

  Img.hMem.SelectObject(pOldPen);
	return 0;
}
//===================================
int sort_points(const void *a,const void *b)
{
   tpoint *l,*r;
   l=(tpoint*) a;r=(tpoint*) b;
   if (l->x  >  r->x) return 1;
   if (l->x  <  r->x) return -1;
   if (l->x ==  r->x)
     { if (l->y >  r->y) return 1;
       if (l->y <  r->y) return -1;
       if (l->y ==  r->y) return 0;
     }
   return 0;
}
//===================================
int sort_pairs(const void *a,const void *b)
{
   tpqs *l,*r;
   l=(tpqs*) a;r=(tpqs*) b;
   if (l->s  >  r->s) return 1;
   if (l->s  <  r->s) return -1;
   if (l->s ==  r->s) return 0;
  return 0;
}
//===================================
int Search_Median(tpoint *Ar,uint beg,uint end,tpoint* M,uint *fl)
{ double m;
    m=(beg+end)/2.0;
    if ((int) m!=m)
      {*fl=1;}
     else {*fl=0;}
     M->x = (Ar[(int) m].x+Ar[(int) (m+*fl)].x)/2.0;
     M->y = (Ar[(int) m].y+Ar[(int) (m+*fl)].y)/2.0;
  return (int) m;
}
//===================================
tpqs* Pairs(tpoint *Ar,uint beg,uint end,tpoint M,uint fl,double *s,uint *vf)
{uint k=0,i=0;
 tpqs* R;
 tpoint a,b;
 char *FName="Pairs";

		k=(beg+end+1)/2 ;
		R= (tpqs *) calloc(k, sizeof(tpqs));
		if (R==NULL)
			{ PrErr("%s :Error not enough memory\n",FName);}
    for (i=0;i<k;i++)
    { a=Ar[i];b=Ar[i+k+!fl];
      R[i].p=a;//moget ne xranit`?
      R[i].q=b;//moget ne xranit`?
      if ((a.x-b.x)==0)
				{R[i].s=NaN;}//Warning
			else
				{R[i].s=(a.y-b.y)/(a.x-b.x);}
			//draw pairs
		}
		//Search Median for sl
		qsort((void *)R, k, sizeof(tpqs), sort_pairs);
		if (k%2==0)
		{*s=(R[(int) ((k-1)/2)].s+R[(int) (k/2)].s)/2;
		 *vf=1;
		}
		else
		{*s=(R[(int) ((k-1)/2)].s);
		 *vf=0;
		}
		//*s=R[(int) (k/2.0)].s;//or *s=(R[k/2.0]+R[k/2.0+1])/2.0 ???

		return R;

}
//===================================
int Opor_Line(tpoint* Ar,uint beg,uint end,uint fl,double s,
		       uint *num,int fl_up,TImage &Img,BOOL hDraw)
{ uint k=0,i=0,j=0,l=0,r=0;
	double b_m=-fl_up*NaN,b;
	char *FName="Opor_Line";
	tpqs P;
		if (s==NaN) {*num=beg;return 0;}
		for(i=beg;i<=end;i++)
		{
			b=Ar[i].y-Ar[i].x*s;
			//P.p.x=0;P.p.y=b;
			//P.q.x=sc_x;P.q.y=s*P.q.x+b;
			//P.s=s;
			//setcolor(10);
			//Draw_P(&P,0,0);
			if (fl_up*b>fl_up*b_m)
			{
				b_m=b;
				j=i;
			}
		}
		*num=j;
		if (j>end)
		{PrErr("%s:num>end",FName);}
		P.p.x=0;P.p.y=b_m;
		P.q.x=sc_x;P.q.y=s*P.q.x+b_m;
		P.s=s;		

 	 	if(Img.hDraw) VDraw_P(&P,0,Img,cOpora,psOpora,wOpora);

		k=(beg+end+1)/2;
		for (i=0;i<k;i++)
		{ if(fabs(Ar[i].x*s+b_m-Ar[i].y)<eps)
			 {l++;}
		   if(fabs(Ar[i+k+!fl].x*s+b_m-Ar[i+k+!fl].y)<eps)
			 {r++;}
		}
		if (!fl&&fabs(Ar[k].x*s+b_m-Ar[k].y)<eps)
		{r++;}
		if ((l>1&&r>=1)||(l>=1&&r>1))
		 {i=0;
		  return 1;
		 }
		if (l&&r) return 0;
		if (l) return -1;
		if (r) return 1;
	 return 2;
}

//===================================
tpoint* Update(tpqs* R,double sl,uint vf,uint k,tpoint *M,uint fl,int side,
						tpoint* El,uint *n,int fl_up)
{ QUEUE<tpoint> Q;
	tpoint* P;
	const tpoint *el;
	uint i,j=0;
	double b;
	char* FName="Update";

		if (side==0&&vf)
		{ for(i=0;i<k;i++)
			 {
					if ((fabs(El->x-R[i].p.x)<eps&&fabs(El->y-R[i].p.y)<eps)||
							(fabs(El->x-R[i].q.x)<eps&&fabs(El->y-R[i].q.y)<eps))
					{	b=El->y-El->x*sl;}
				}
		 }

		for(i=0;i<k;i++)
		{
			if (side<0)
			{
			 if (R[i].s*fl_up<sl*fl_up)
				{Q.Push(&R[i].p);}
			   Q.Push(&R[i].q);
			  }
			if (side>0)
			 {  if (R[i].s*fl_up>sl*fl_up)
				{Q.Push(&R[i].q);}
			     Q.Push(&R[i].p);
			     if (side==2) Q.Push(El);
			 }
			 if (side==0)
			  {
					 if (vf)
					 {
						 if (fabs(R[i].p.x*sl+b-R[i].p.y)<eps)
							{Q.Push(&R[i].p);}
						 if (fabs(R[i].q.x*sl+b-R[i].q.y)<eps)
							{Q.Push(&R[i].q);}
					 }
					 else
					 {
						if ((fabs(El->x-R[i].p.x)<eps&&(fabs(El->y-R[i].p.y)<eps)||
							 (fabs(El->x-R[i].q.x)<eps)&&fabs(El->x-R[i].q.x)<eps))
						{
							Q.Push(&R[i].p);
							Q.Push(&R[i].q);
							if (Q.IsEmpty())
								{PrErr("%s:Error QUEUE\n",FName);}
							}
					}
				}
		}
	if (side!=0&&!fl) {Q.Push(M);};
	*n=Q.Count();
	if (*n==0)
	{ PrErr("%s:n==0 \n",FName);}
	P=(tpoint*) calloc(*n,sizeof(tpoint));
	if (P!=NULL)
	{ Q.Go_Beg();
			for(i=0;i<*n;i++)
			{  if (!Q.IsEnd())
				 {el=Q.Go_Next();
					P[i].x=el->x;
					P[i].y=el->y;
				 }
			}
			Q.Go_Beg();
			qsort((void *)P, (int)*n, sizeof(tpoint), sort_points);
	}
	else
	{ PrErr("%s :Error not enough memory\n",FName);}

	return P;
}
//===================================
tpqs* Bridge(tpoint *Ar,uint beg,uint end,int fl_up,TImage &Img,BOOL hDraw,int f)
{uint b,e,m,fl,n,num,vf;
 tpoint M,*UAr;
 tpqs *R,*Rez;
 double sl;
 int side,c;
 char *FName="Bridge";
 static int ind=1;
 static tpoint *W;
 static uint w;
 
//com if (f) VDraw_A(W,w,Img,RGB(250,50,0),PS_SOLID, 1);

 if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) Img.hDraw=true;
	}	
		if(Img.hDraw) VDraw_A(Ar,end,Img,cDiedPoint,psDiedPoint,wDiedPoint);

		b=beg;	e=end;
		m=Search_Median(Ar,b,e,&M,&fl);//Sl=[b,m-!fl] Sr=[m+1,e]
		
        if(Img.hDraw) VDraw_A(&M,0,Img,cMedia,psMedia,wMedia,1);
		
		R=Pairs(Ar,b,e,M,fl,&sl,&vf);
  
		if(Img.hDraw) VDraw_P(R,(b+e-!fl)/2,Img,cPairs,psPairs,wPairs);
	
		side=Opor_Line(Ar,b,e,fl,sl,&num,fl_up,Img,hDraw);
 		UAr=Update(R,sl,vf,(uint)(b+e+1)/2,&M,fl,side,&Ar[num],&n,fl_up);		

		if(Img.hDraw) 
		{ VDraw_A(UAr,n-1,Img,cLifePoint,psLifePoint,wLifePoint);			
		  Img.hDraw=false;
		}

		if (R!=NULL) free(R);
		if (side==0)
		 { Rez=new  tpqs;
		   if (Rez==NULL) {PrErr("%s:Error -not enough memory",FName);}
		   Rez->p=UAr[0];
		   Rez->q=UAr[1];
		   if ((UAr[0].x-UAr[1].x)==0)
		   { Rez->s=NaN;}
		   else
		   { Rez->s=(UAr[0].y-UAr[1].y)/(UAr[0].x-UAr[1].x);}		   
		    
if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) VDraw_P(Rez,0,Img,cNewEdge,psNewEdge,wNewEdge);
	}
		   
		 if (UAr!=NULL) free(UAr);
		   
		 };
		
		if (f)
		 {if (Ar!=NULL) free(Ar);}
		 else
		 {W=Ar;w=end;}
		if (side!=0)
		{Rez=Bridge(UAr,0,n-1,fl_up,Img,hDraw,1);}
    return Rez;
}
//===================================
UandD(tpoint* Ar,uint end,uint lb,uint le,
	 tpoint** ArU,uint *U,tpoint** ArD,uint *D,int fl_up,TImage &Img,BOOL hDraw,tpqs &P)
{uint u=0,d=0,i=0,c;
 double k=0,b=0;
 tpoint *AU=NULL,*AD=NULL;
 char *FName="UandD";

	 if (lb>end||le>end)
	 { PrErr("%s:lb>end||le>end\n",FName);}
	 if (le==lb)
	 {*U=2;*D=0;
		*ArU=NULL;*ArD=NULL;
		return 1;
	 }
	 if ((Ar[lb].x-Ar[le].x)==0)
		{k=NaN;}
		 else
		{ k=(Ar[lb].y-Ar[le].y)/(Ar[lb].x-Ar[le].x);}
	 b=Ar[lb].y-Ar[lb].x*k;
	 P.p=Ar[lb]; P.q=Ar[le];P.s=k;
	 
 	 for (i=lb;i<=end;i++)
	 {
	   if (Ar[i].x*k+b>=Ar[i].y||i==lb||i==le)
		{d++;}
	  if (Ar[i].x*k+b<=Ar[i].y||i==lb||i==le)
		{u++;}
	 }
	 *U=u;*D=d;
	 if (fl_up>=0)
		{AU=(tpoint*) calloc(u,sizeof(tpoint));
		if (AU==NULL)
		 { PrErr("%s :Error not enough memory\n",FName);}
		}
	 if(fl_up<=0)
		{AD=(tpoint*) calloc(d,sizeof(tpoint));
		 if (AD==NULL)
		  { PrErr("%s :Error not enough memory\n",FName);}
		}

	 *ArU=AU;*ArD=AD;
	 d=0;u=0;
	 for (i=lb;i<=end;i++)
	 {
	  if ((Ar[i].x*k+b>=Ar[i].y||i==lb||i==le)&&fl_up<=0)
	     {AD[d]=Ar[i];
	      d++;
	     }
	 if  ((Ar[i].x*k+b<=Ar[i].y||i==lb||i==le)&&fl_up>=0)
	     {AU[u]=Ar[i];
		u++;
	      }
	 }
	return 0;
}


//=========================================
int CH(tpoint* Ar,uint u,QUEUE<tpqs> *Q,int fl_up,TImage &Img)

{tpqs *Br;
 tpoint *Ar_lu,*Ar_ld,*Ar_ru,*Ar_rd,*Ar_l,*Ar_r;
 uint lu,ld,ru,rd;
 uint i,l,r;
 static int fl_u=0,fl_d=0;
 int rez_l=0,rez_r=0;
 char *FName="CH";
  BOOL hDraw=false;
  tpqs P;
  
	 Br=Bridge(Ar,0,u-1,fl_up,Img,hDraw);

	 for(i=0;i<u;i++)
	 {
		if ( fabs(Ar[i].x-Br->p.x)<eps&&fabs(Ar[i].y-Br->p.y)<eps)
			{l=i;}//number point p
		if (fabs(Ar[i].x-Br->q.x)<eps&&fabs(Ar[i].y-Br->q.y)<eps)
			{r=i;}//number point q
	 }

	 Q->Push(Br);

     if(Img.cur_step<=Img.cal_step) VDraw_Q(Q,Img,cCurCH,psCurCH,wCurCH);
	  	 
	 rez_l=UandD(Ar,u-1,0,l,&Ar_lu,&lu,&Ar_ld,&ld,fl_up,Img,hDraw,P);
 
	 if (fl_u) return 0;
	 if (fl_d) return 0;
	 if (fl_up==1)
	   {l=lu;Ar_l=Ar_lu;}
	 else
	   {l=ld;Ar_l=Ar_ld;}

	 if (l>=2&&!fl_u&&!rez_l)
	 { if (l==2) fl_u=1;

 if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) Img.hDraw=true;
	}
	 if (Img.hDraw)
	 {
	  VDraw_P(&P,0,Img,cDivLine,psDivLine,wDivLine);
	  VDraw_A(Ar_l,l-1,Img,cDivPoint,psDivPoint,wDivPoint);
	  Img.hDraw=false;
	 }
	    CH(Ar_l,l,Q,fl_up,Img);
	    if (fl_u) fl_u=0;
	  }

	 if (Ar_lu!=NULL) free(Ar_lu);
	 if (Ar_ld!=NULL) free(Ar_ld);

	 rez_r=UandD(Ar,u-1,r,u-1,&Ar_ru,&ru,&Ar_rd,&rd,fl_up,Img,hDraw,P);
 if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) Img.hDraw=true;
	}

	 if (fl_up==1)
	   {r=ru;Ar_r=Ar_ru;}
	 else
	   {r=rd;Ar_r=Ar_rd;}
	 if (r>=2&&!fl_d&&!rez_r)
	 { if (r==2) fl_d=1;

	 if (Img.hDraw)
	  {
	   VDraw_P(&P,0,Img,cDivLine,psDivLine,wDivLine);
	   VDraw_A(Ar_r,r-1,Img,cDivPoint,psDivPoint,wDivPoint);
	   Img.hDraw=false;
	  }
	   CH(Ar_r,r,Q,fl_up,Img);
	   if (fl_d) fl_d=0;
	 }
	 if (Ar_ru!=NULL) free(Ar_ru);
	 if (Ar_rd!=NULL) free(Ar_rd);

	 return 0;
}
//===================================
int Del_El_Q(QUEUE<tpqs> *Q)
{  tpqs *E;
	 while (!Q->IsEmpty())
	 {
		 E=Q->Pop();
		 if (E!=NULL) delete(E);
	 }
 return 0;
}
//===================================

tpqs* CH_all(tpoint* Ar,uint end,TImage &Img)
{uint u=0,d=0;

 char *FName="CH";
 tpoint* ArU,*ArD;
 QUEUE <tpqs> Q_U,Q_D;
 BOOL hDraw=false;
 tpqs P;

 Img.hDraw=false;

 	UandD(Ar,end,0,end,&ArU,&u,&ArD,&d,0,Img,hDraw,P);
 
 if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) Img.hDraw=true;
	}

   if (Img.hDraw) 
	{ VDraw_P(&P,0,Img,cDivLine,psDivLine,wDivLine);
	  VDraw_A(ArU,u-1,Img,cDivPoint,psDivPoint,wDivPoint);
	  Img.hDraw=false;
	}
	   
	CH(ArU,u,&Q_U,1,Img);
	if (ArU!=NULL) free(ArU);
	
 if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) VDraw_Q(&Q_U,Img,cCH,psCH,wCH);
	}
   
 if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) Img.hDraw=true;
	}

    if (Img.hDraw) 
	{ VDraw_P(&P,0,Img,cDivLine,psDivLine,wDivLine);
	  VDraw_A(ArD,d-1,Img,cDivPoint,psDivPoint,wDivPoint);
	  Img.hDraw=false;
	}
 
	CH(ArD,d,&Q_D,-1,Img);
	if (ArD!=NULL) free(ArD);

  if (Img.hStepOn)
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) VDraw_Q(&Q_U,Img,cCH,psCH,wCH);
	}
 	
 if (Img.hStepOn)
 {
  if(!Img.hKnow) Img.all_step++;
   else
	{
	 Img.cur_step++;  
	 if(Img.cur_step==Img.cal_step) 
	 { VDraw_Q(&Q_U,Img,cCH,psCH,wCH);
	   VDraw_Q(&Q_D,Img,cCH,psCH,wCH);
	 }
	}
 }
 else  
 {
  VDraw_Q(&Q_U,Img,cCH,psCH,wCH);
  VDraw_Q(&Q_D,Img,cCH,psCH,wCH);
 }
 	
	Del_El_Q(&Q_U);
	Del_El_Q(&Q_D);

 return NULL;
}
//===================================
int Check(tpoint **Ar,uint *a)
{uint i=0,n,j=1;
 QUEUE <tpoint> Q;
 tpoint *A;
 const tpoint *el,*B;
 int fl=0;
  B=*Ar;
  while(i<*a&&j<*a)
  {
    if(fabs(B[i].x-B[j].x)>eps&&
       fabs(B[i].y-B[j].y)>eps)
    {
	    Q.Push(&B[i]);
	    i=j;j++;
    }
    else
    {      j++;
	   fl=1;
    }
  }
  n=Q.Count();
  if (n==0||!fl) return 0;
  A=(tpoint*) calloc(n,sizeof(tpoint));
  if (A!=NULL)
   { Q.Go_Beg();
     for(i=0;i<n;i++)
     {  if (!Q.IsEnd())
	 {el=Q.Go_Next();
	  A[i].x=el->x;
	  A[i].y=el->y;
	 }
     }
   }
   Q.Go_Beg();
   free(*Ar);
    *Ar=A;
    *a=n;
  return 1;
}
//===================================
MyUpdate(TMyPointVector &p, TImage &Img)
{
 tpoint *Ar;
 tpqs *Br;
 uint r=0,m=0,n=0;

     Img.ClearImage();
	 Img.Update(p);
	 if (Img.hDiagram &&(p.N()>1)) 
	 {
	  Img.hStepOn = false;
      Ar=ReadMas(p);
	  qsort((void *)Ar, all_el, sizeof(tpoint), sort_points);
	  CH_all(Ar,all_el-1,Img);
	 }
}