ls_clustering.cpp

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

#include "stdafx.h"
#include "ls_clustering.h"



line *LS_CLUSTERING::get_last()
{
	return last;
}

double LS_CLUSTERING::distance(line *lp,line *tp)
{
	point *si;
	point *ei;
	point *sj;
	point *ej;
	
	si=lp->p1;
	ei=lp->p2;
	sj=tp->p1;
	ej=tp->p2;
	
	double x1=sj->x-si->x;
	double y1=sj->y-si->y;
	
	double x2=ei->x-si->x;
	double y2=ei->y-si->y;
	
	double x3=ej->x-si->x;
	double y3=ej->y-si->y;
	
	double x=pow(x2,2)+pow(y2,2);
	
	double u1=(x1*x2+y1*y2)/x;
	double u2=(x3*x2+y3*y2)/x;
    
    double psx=si->x+u1*x2;
	double psy=si->y+u1*y2;
	
	double pex=si->x+u2*x2;
	double pey=si->y+u2*y2;
	
	double Lper1=sqrt(pow(psx-sj->x,2)+pow(psy-sj->y,2));
	double Lper2=sqrt(pow(pex-ej->x,2)+pow(pey-ej->y,2));
	double d_perpen;
	
	if(Lper1==0&&Lper2==0)
	{
		d_perpen=0;
	}
	else
	{
		d_perpen=(pow(Lper1,2)+pow(Lper2,2))/(Lper1+Lper2);
	}
	
	double x4=ej->x-sj->x;
	double y4=ej->y-sj->y;
	
	double xi=sqrt(pow(x4,2)+pow(y4,2));
	double yi=sqrt(pow(x2,2)+pow(y2,2));
	
	double cos=(x4*x2+y4*y2)/(xi*yi);
	float m=cos*cos;
	float s=1-m;
	float t=sqrt(s);
	
	double angle=sqrt(pow(x4,2)+pow(y4,2))*t;
	
    double Lpar1=sqrt(pow(psx-si->x,2)+pow(psy-si->y,2));
	double Lpar2=sqrt(pow(pex-ei->x,2)+pow(pey-ei->y,2));
	
	double d_parallel;
	
	if(Lpar1>Lpar2)	
		d_parallel=Lpar2;
	else
		d_parallel=Lpar1;
	
	return (d_parallel+d_perpen+angle);
}


double LS_CLUSTERING::l_distance(line *lp)
{
	double x=(lp->p1->x)-(lp->p2->x);
	double y=(lp->p1->y)-(lp->p2->y);
	return sqrt(pow(x,2)+pow(y,2));
}


double LS_CLUSTERING::dist(line *lp,line *tp)
{
	if(l_distance(lp)>=l_distance(tp))
	{
		return distance(lp,tp);
	}
	else
		return distance(tp,lp);
}


int  LS_CLUSTERING::Dp_insert(double dt,line *ls)
{
	Dpoint *Dp=new Dpoint;
	Dp->dist=dt;
	Dp->lp=ls;

	if(Dp_first==NULL)
	{
      Dp_first=Dp;
	  Dp->next=NULL;
	}
	else
	{
	   
	   if(dt<=Dp_first->dist)
	   {
         Dp->next=Dp_first;
		 Dp_first=Dp;
	   }
	   else
	   {
		   Dpoint *TVDp=Dp_first;	   
		   Dpoint *TDp=TVDp->next;
		   while(TDp!=NULL)
		   {
			   if(TDp->dist>=dt)
			   {
				 TVDp->next=Dp;
				 Dp->next=TDp;
				 return 1;
			   }
			   else
			   {
				   TVDp=TDp;
				   TDp=TDp->next;
			   }
		   }		   
		   TVDp->next=Dp;
		   Dp->next=NULL;		  
	   }
	}
	return 1;
}	


void LS_CLUSTERING::CalcNDF(line *ls)
{
	line *tlp=first;
	double dt;
	
	while(tlp!=NULL)
	{
		dt=dist(ls,tlp);
		if(dt!=0)
		{
          Dp_insert(dt,tlp);
		}
		tlp=tlp->next;
	}

	Dpoint *TDp=Dp_first;
	
	double d;
	tlp=first;

	TDp->lp->R_kNB++;
	ls->kNB=1;
	while(TDp!=NULL)
	{
		if(ls->kNB<k)
		{	
			TDp=TDp->next;
            TDp->lp->R_kNB++;
			ls->kNB++;			
		}
		else
		{
		    d=TDp->dist;
			break;
		}        
	} 


	TDp=TDp->next;
	while(TDp!=NULL)
	{
      if(TDp->dist<=d)
	  {
          TDp->lp->R_kNB++;
		  ls->kNB++;
		  TDp=TDp->next;
	  }
	  else
		  break;
	}

    TDp=Dp_first;
	while(TDp!=NULL)
	{
		Dp_first=Dp_first->next;
		delete TDp;
		TDp=Dp_first;
	}	
		
}



void LS_CLUSTERING::CalcNDFs()
{
	line *tlp=first;
	
	while(tlp!=NULL)
	{
	 	CalcNDF(tlp);		
		tlp=tlp->next;
	}
}



void LS_CLUSTERING::ouputNDF()
{
	ofstream outfile;
	outfile.open("ndf.txt",ios::out);

	line *lp=first;
	while(lp!=NULL)
	{
		outfile<<lp->kNB<<"    "<<lp->R_kNB<<endl;
		lp=lp->next;
	}
}	


void LS_CLUSTERING::ComputeKNB(line *ls)
{
	line *tlp=first;
	double dt;
	
	while(tlp!=NULL)
	{
		dt=dist(ls,tlp);
		if(dt!=0)
		{
			Dp_insert(dt,tlp);
		}
		tlp=tlp->next;
	}

	ls->neigh_next=NULL;
	line *tls;
	Dpoint *Dp=Dp_first;
	for(int i=0;i<ls->kNB;i++)
	{
	   tls=ls->neigh_next;       //首插入法
       ls->neigh_next=Dp->lp;
	   Dp->lp->neigh_next=tls;
	   Dp=Dp->next;	   
	}

	Dpoint *TDp=Dp_first;
	while(TDp!=NULL)
	{
		Dp_first=Dp_first->next;
		delete TDp;
		TDp=Dp_first;
	}	

}



void LS_CLUSTERING::ExpandCluster(int clusterId)
{
	QNode *Nd;
	line *TP;
	line *FP;
	double ndf;
	
	while(!Q.Que_Empty())
	{
		Nd=Q.GetHead();
		FP=Nd->po;		
        
		
		ndf=FP->R_kNB/FP->kNB;
		if(ndf >= 1)
		{
		    ComputeKNB(FP);
			TP=FP;
			while(TP!=NULL)
			{
				if(TP->line_mark==0||TP->line_mark==1)
				{
					TP->clusterId=clusterId;
					TP->line_mark=2;
                    insert_line(TP);
				}
				if(TP->line_mark==0)
				{
					Q.Insert_Queue(TP);
				}
				TP=TP->neigh_next;
			}
		}
		Q.Del_Queue();
	}
}


void LS_CLUSTERING::new_cluster(int clusterId)
{
	cluster *CL=new cluster;
	CL->tra_num=0;
	CL->cluster_id=clusterId;
	CL->next=NULL;
	CL->first=NULL;
	
	if(first_cluster==NULL)
	{
		first_cluster=last_cluster=CL;
	}
	else
	{
		last_cluster->next=CL;
		last_cluster=CL;
	}	
}




int  LS_CLUSTERING::insert_line(line *ls)
{
	cluster_line *csl=new cluster_line;
	csl->tra_id=ls->tra_id;
	csl->p1=ls->p1;
	csl->p2=ls->p2;
	csl->next=NULL;
	
	cluster_line *tcl=last_cluster->first;
	
	if(last_cluster->tra_num==0)
	{
		last_cluster->first=csl;
		last_cluster->tra_num++;
	}
	else
	{
		while(tcl!=NULL) 
		{
			if(tcl->tra_id!=csl->tra_id)
			{
				tcl=tcl->next;
			}
			else
			{
				csl->next=last_cluster->first;
				last_cluster->first=csl;
				return 1;       
			}
		}
		csl->next=last_cluster->first;    //当簇内线段中没有来自同一条轨道的时,将轨道数目加1
		last_cluster->first=csl;
		last_cluster->tra_num++;	
	}
	
	return 1;
}


void LS_CLUSTERING::ls_clustering()
{
	  
	   line *LP;
	   line *TP;
	   int clusterId=1;
	   
	   LP=first;
	   double ndf;

	   while(LP!=NULL)
	   {
		   if(LP->line_mark==0)
		   {
			   ndf=LP->R_kNB/LP->kNB;
			   if(ndf>=1)
			   {				  
                   ComputeKNB(LP);
				   TP=LP->neigh_next;
				   LP->clusterId=clusterId;
				   LP->line_mark=2;
				   new_cluster(clusterId);
				   insert_line(LP);
				   
				   while(TP!=NULL)
				   {
					   TP->clusterId=clusterId;
					   TP->line_mark=2;						  
					   insert_line(TP);
					   Q.Insert_Queue(TP);
					   TP=TP->neigh_next;
				   }
				   ExpandCluster(clusterId);
				   clusterId++;
			   }
			   else
			   {
				   LP->line_mark=1;  //Mark L as noise
			   }
		   }
		   LP=LP->next;		
	   } 
	   
	 
}




void LS_CLUSTERING::check_tra_num(int k)
{
	cluster *CVL=first_cluster;
	cluster *CL=CVL->next;
	while(CL!=NULL)
	{
		if(CL->tra_num<k)
		{
			CVL->next=CL->next;
			delete CL;
			CL=CVL->next;
		}
		else
		{
			CVL=CL;
			CL=CL->next;
		}
	}

	if(first_cluster->tra_num<k)
	{
		CVL=first_cluster;
		first_cluster=first_cluster->next;
		delete CVL;
	}
}



void LS_CLUSTERING::output_cluster()
{
	ofstream outfile;
	outfile.open("cluster.txt",ios::out);
	if(!outfile)
	{
		cout<<"      "<<endl;
		exit(0);
	}
	cluster *CL=first_cluster;
	cluster_line *CS_L;
	int num=1;
	
	while(CL!=NULL)
	{
		CS_L=CL->first;
		while(CS_L!=NULL)
		{
			outfile<<num<<"      "<<CL->tra_num<<"      "<<CS_L->p1->x<<"       "<<CS_L->p1->y<<"       "<<CS_L->p2->x<<"        "<<CS_L->p2->y<<endl;
			CS_L=CS_L->next;			
		}
		CL=CL->next;
		num++;	         
	}
}



cluster *LS_CLUSTERING::get_first_cluster()
{
	return first_cluster;
}