rtg.cpp

一个可执行的nbc算法设计与实现 有助大家互相探讨学习

#include "stdafx.h"
#include "rtg.h"


void RTG::compute_avgv()
{
	int num=0;
    double px=0;
	double py=0;

	cluster_line *tp=first_line;

	while (tp!=NULL)
	{
		if((tp->p1->num)>(tp->p2->num))
		{
			px+=(tp->p1->x-tp->p2->x);
			py+=(tp->p1->y-tp->p2->y);
		}
		else
		{
			px+=(tp->p2->x-tp->p1->x);
			py+=(tp->p2->y-tp->p1->y);
		}
		tp=tp->next;
		num++;
	}
	px=px/num;
	py=py/num;
	double l=sqrt(px*px+py*py);
	cosv=px/l;
	sinv=py/l;

}




int  RTG::insert_sort(double x)
{
	xpoint *xp=new xpoint;
	xp->x=x;

    if(xp_first==NULL)
	{
      xp_first=xp;
	  xp->next=NULL;
	}
	else
	{
		if(x<=xp_first->x)
		{
          xp->next=xp_first;
		  xp_first=xp;
		}
		else
		{    
			xpoint *txp;
		    xpoint *tvxp;	
		    tvxp=xp_first;
		    txp=tvxp->next;
			while(txp!=NULL)
			{
				if(x<=txp->x)
				{
					xp->next=txp;
					tvxp->next=xp;
					return 1;
				}
				else
				{
					tvxp=txp;
					txp=txp->next;	
				}												
			}
			tvxp->next=xp;
			xp->next=NULL;			
		}		
	}
	return 1;
}


void RTG::rotate_axes()
{
	cluster_line *tp=first_line;
    double x1,y1;

	while(tp!=NULL)
	{
		x1=tp->p1->x;
		y1=tp->p1->y;
		tp->p1->x=x1*cosv+y1*sinv;
		tp->p1->y=y1*cosv-x1*sinv;
        insert_sort(tp->p1->x);

		x1=tp->p2->x;
		y1=tp->p2->y;
		tp->p2->x=x1*cosv+y1*sinv;
		tp->p2->y=y1*cosv-x1*sinv;
        insert_sort(tp->p2->x);

        tp=tp->next;
	}
}

void RTG::undo_rotation()
{
	cluster_line *tp=first_line;
    double x1,y1;
	

	while(tp!=NULL)
	{
		x1=tp->p1->x;
		y1=tp->p1->y;
		tp->p1->x=x1*cosv-y1*sinv;
		tp->p1->y=(x1+y1*sinv*cosv-x1*cosv*cosv)/sinv;

		x1=tp->p2->x;
		y1=tp->p2->y;
		tp->p2->x=x1*cosv-y1*sinv;
		tp->p2->y=(x1+y1*sinv*cosv-x1*cosv*cosv)/sinv;

		tp=tp->next;
	}
	
}


void RTG::get_pointrange(cluster_line *cl,double &max,double &min)
{
  if((cl->p1->x)>(cl->p2->x))
  {
	  max=cl->p1->x;
	  min=cl->p2->x;
  }
  else
  {
	 max=cl->p2->x;
	 min=cl->p1->x;
  }
}


double RTG::compute_y(cluster_line *cl,double x)
{
	double x1=cl->p1->x;
	double y1=cl->p1->y;
	double x2=cl->p2->x;
	double y2=cl->p2->y;
	
	double k=(y2-y1)/(x2-x1);
	double y=k*(x-x1)+y1;
	
	return y;
}

int RTG::compute_nump(xpoint *xp,double &sumy)
{
	cluster_line *lp=first_line;
	int nump=0;
    double max,min;  
	sumy=0;
	
	while(lp!=NULL)
	{
      get_pointrange(lp,max,min);  
	  if(min<=(xp->x)&&(xp->x)<=max)
	  {
		  nump++;
		  sumy=sumy+compute_y(lp,xp->x);
	  }
	  lp=lp->next;		
	}
	return nump;
}

void RTG::sweep_line()
{
	xpoint *xp=xp_first;
	xpoint *tp;
    int nump;
	double pvx;
	double diff;
	double sumy;
	double avgy;
    double x;
	double y;

	new_tra();
	int mark=0;
	
	while(xp!=NULL)
	{
	    nump=compute_nump(xp,sumy);
		if(nump>=MinLns&&mark==0)
		{
			avgy=sumy/nump;
			x=(xp->x)*cosv-avgy*sinv;
			y=(xp->x+avgy*sinv*cosv-(xp->x)*cosv*cosv)/sinv;	
			insert_point(x,y);
			pvx=xp->x;
			mark=1;
		}
		else if(nump>=MinLns&&mark==1)
		{
			diff=xp->x-pvx;
			if(diff>=R)
			{
				avgy=sumy/nump;
				x=(xp->x)*cosv-avgy*sinv;
				y=(xp->x+avgy*sinv*cosv-(xp->x)*cosv*cosv)/sinv;	
				insert_point(x,y);
				pvx=xp->x;
			}
		}			
		tp=xp;
		xp=xp->next;
		delete tp;
	}
	xp_first=NULL;
}



void RTG::insert_point(double x,double y)
{
	point *np=new point;
	np->x=x;
	np->y=y;
    np->next=last_tra->first_point;
    last_tra->first_point=np;	
}

void RTG::new_tra()
{
   TRA *ntra=new TRA;
   ntra->first_point=NULL;
   ntra->next=NULL;

   if(first_tra==NULL)
   {
	   first_tra=last_tra=ntra;
   }
   else
   {
	   last_tra->next=ntra;
	   last_tra=ntra;
   }
}


void RTG::get_Rtra()
{
	cluster *current_cluster=first_cluster;
	int n=1;
	
	while(current_cluster!=NULL)
	{	  
		  first_line=current_cluster->first;
		  compute_avgv();
		  rotate_axes();
		  sweep_line();	
		  undo_rotation();
		  cout<<sinv<<"     "<<cosv<<endl;
		  current_cluster=current_cluster->next;		  
	}
}

TRA *RTG::get_first_tra()
{
	return first_tra; 
}

void RTG::output_Rta()
{
	ofstream outfile;
	outfile.open("rtr.txt",ios::out);
	if(!outfile)
	{
        cout<<"    "<<endl;
		exit(0);
	}
	TRA *current_tra=first_tra;
	int num=1;
	point *tp;
	
	while(current_tra!=NULL)
	{
       tp=current_tra->first_point;
	   while(tp!=NULL)
	   {
		   outfile<<num<<"      "<<tp->x<<"          "<<tp->y<<endl;
		   tp=tp->next;
	   }
	   current_tra=current_tra->next;
	   num++;
	}
	
}