nnsearch.cpp

在Ｎ维空间中从海量的点中高效求出中距某点最近的点（即NNProblem)

#include"RTree.h"
#include<iostream>
//#define NDEBUG //**** enable/disable assertions
#include<cassert>
#include<string>
#include<fstream>
#include<math.h>

using namespace std;
#define N 2
#define BIT 1000
#define NUM 1000
int K=0;

//data generate function from the data.dll
_declspec(dllimport)void GenerateData(int Dimensions,char Distribution,int Count,char* FileName);

/*////////////////////////////////////////////////////////////
/*/
//the structure which will be used to sort in PushHeap(Node* ,int*)
struct DisList
{
	int Dist;
	int id;
	struct DisList* next;
};

//
class NRTree : public RTree<long,int,N>
{
public:
	int Min_DIST(Branch *branch,int*);		//MinDist()
	int Min_MAXDIST(Branch *branch,int*);	//MinMaxDist()
	void PushHeap(Node*,int*);	//push the Branch into the heap
	void NearPoint(int*);	//search the nearest point
private:
	struct Heap			//the structure the heap will use 
	{
		Branch* branch;
		int level;
	};
	
	int point[NUM][N];	//the buffer to save the point which "may be" the nearest point
	Heap heap[100];		//the heap to store the rectangle
};

///push the Branch into the heap
void NRTree::PushHeap(Node* node,int p[])
{
	DisList* head=NULL,*Lp=NULL,*pfirst=NULL,*psecond=NULL;

	for(int i=0;i<MAXNODES;i++)
	{
		
		if((node->m_branch[i].m_rect.m_min[0]<0)
			&&(node->m_branch[i].m_rect.m_max[0]<0))//this node has nothing 
			continue;

		Lp=new DisList;
		Lp->Dist=Min_DIST(node->m_branch+i,p);
		Lp->id=i;
		Lp->next=NULL;

		if(head==NULL)
		{
			head=Lp;
			continue;
		}

		pfirst=head;
		while((pfirst!=NULL)&&(pfirst->Dist<Lp->Dist))
			pfirst=pfirst->next;
			
		psecond=head;
		if(psecond==pfirst)
		{
			Lp->next=pfirst;
			head=Lp;
			continue;
		}
		while(psecond->next!=pfirst)
			psecond=psecond->next;

		psecond->next=Lp;
		Lp->next=pfirst;
	}
	
	pfirst=head;
	while(pfirst!=NULL)
	{
		i=pfirst->id;
		heap[K].branch=node->m_branch+i;
		heap[K].level=node->m_level;
		K++;
		pfirst=pfirst->next;
	}
}

///search the nearest point 
void NRTree::NearPoint(int p[])
{
	int maxdis;
	int mindis;
	int dis;
	int Best = 2147483647;
	int sign=0;
	int i=0,j=0;
	int MinDis[NUM];

	PushHeap(m_root,p);

	while(K>0)
	{
		K--;
		//if(heap[K].branch->m_rect.m_min[0]==-858993460)
		//	continue;

		if((dis=Min_DIST(heap[K].branch,p))>Best)
			continue;
		else if((maxdis=Min_MAXDIST(heap[K].branch,p))<Best)
			Best=maxdis;

		if(heap[K].level!=0)//not leaf node
			PushHeap(heap[K].branch->m_child,p);
		else	//leaf node
			{
				for(j=0;j<N;j++)
				{
					point[i][j]=heap[K].branch->m_rect.m_min[j];
				}
				i++;
			}
	}

	//
	for(int z=0;z<i;z++)
	{
		MinDis[z]=0;

		for(j=0;j<N;j++)
		{
			MinDis[z]+=(point[z][j]-p[j])*(point[z][j]-p[j]);
		}

		MinDis[z]=sqrt(MinDis[z]);
	}

	mindis=MinDis[0];
	for(z=0;z<i;z++)
	{
		if(mindis>MinDis[z])
		{
			mindis=MinDis[z];
			j=z;//point[j][N] is the nearest point
		}	
	}

	cout<<"The neares distance is "<<mindis<<endl
		<<"The nearest point is :	";
	for(i=0;i<N;i++)
	{
		cout<<point[j][i]<<"  ";
	}

	cout<<endl;
}

///MinDist
int NRTree::Min_DIST(Branch* branch,int p[])
{
	int S,sum=0;
	for(int i=0;i<N;i++)
	{
		//
		if(p[i]<branch->m_rect.m_min[i])
			S=branch->m_rect.m_min[i];
		else if(p[i]>branch->m_rect.m_max[i])
			S=branch->m_rect.m_max[i];
		else
			S=p[i];

		//
		sum+=(p[i]-S)*(p[i]-S);
	}

	return sum;
}

///MinMaxDist
int NRTree::Min_MAXDIST(Branch* branch,int p[])
{
	int S,sum=0,nums[N];
	for(int i=0;i<N;i++)
	{
		sum=0;		//reset	sum
		for(int j=0;j<N;j++)
		{

			if(j!=i)
			{
				if(p[j]>=(branch->m_rect.m_min[j]+branch->m_rect.m_max[j])/2)
					S=branch->m_rect.m_min[j];
				else S=branch->m_rect.m_max[j];
			}
			else if(j==i)
			{
				if(p[j]<=(branch->m_rect.m_min[j]+branch->m_rect.m_max[j])/2)
					S=branch->m_rect.m_min[j];
				else S=branch->m_rect.m_max[j];
			}

			sum+=(p[j]-S)*(p[j]-S);			//
		}

		nums[i]=sum;	//record the sum
	}

	//
	sum=nums[0];
	for(i=0;i<N;i++)
		if(sum>nums[i]) sum=nums[i];
		
	return sum;
}

///********************************************************
int main()
{
	int point[N];
	int count,dim;
	float num;
	long j=0;
	int p[N],i=0;
	NRTree tree;
	ifstream infile;

	cout<<"Please input the dimension and amounts of point:"<<endl;
	cin>>dim>>count;
	if(dim!=N)
	{
		cout<<"Error! Dimension doesn't accord with the N"<<endl;
		return 0;
	}
	GenerateData(dim,'E',count,"1.txt");

	infile.open("1.txt");

	//tree construct
	infile>>count>>dim;
	while(!infile.eof())
	{
		for(int i=0;i<N;i++)
		{
			infile>>num;
			point[i]=num*BIT;
		}
		tree.Insert(point,point,j);
		j++;
	}
	
	cout<<endl<<"Input the point :"<<endl;

	while(i<N)
	{
		cin>>p[i];
		if(p[i]>0.999999*BIT*10)
		{
			cout<<"The point is too large!"<<endl;
			return 0;
		}
		i++;
	}
	tree.NearPoint(p);
	
	cout<<endl;
	return 1;
}