rtree.h

c++课程中要求的实现KNN的问题。解决了数据的产生问题

  {
    a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;
  }
  else
  {
    a_parVars->m_cover[a_group] = CombineRect(&a_parVars->m_branchBuf[a_index].m_rect, &a_parVars->m_cover[a_group]);
  }
  a_parVars->m_area[a_group] = CalcRectVolume(&a_parVars->m_cover[a_group]);
  ++a_parVars->m_count[a_group];
}


// Delete a data rectangle from an index structure.
// Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.
// Returns 1 if record not found, 0 if success.
// RemoveRect provides for eliminating the root.
RTREE_TEMPLATE
bool RTREE_QUAL::RemoveRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root)
{
  ASSERT(a_rect && a_root);
  ASSERT(*a_root);

  Node* tempNode;
  ListNode* reInsertList = NULL;

  if(!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))
  {
    // Found and deleted a data item
    // Reinsert any branches from eliminated nodes
    while(reInsertList)
    {
      tempNode = reInsertList->m_node;

      for(int index = 0; index < tempNode->m_count; ++index)
      {
        InsertRect(&(tempNode->m_branch[index].m_rect),
                   tempNode->m_branch[index].m_data,
                   a_root,
                   tempNode->m_level);
      }
      
      ListNode* remLNode = reInsertList;
      reInsertList = reInsertList->m_next;
      
      FreeNode(remLNode->m_node);
      FreeListNode(remLNode);
    }
    
    // Check for redundant root (not leaf, 1 child) and eliminate
    if((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())
    {
      tempNode = (*a_root)->m_branch[0].m_child;
      
      ASSERT(tempNode);
      FreeNode(*a_root);
      *a_root = tempNode;
    }
    return false;
  }
  else
  {
    return true;
  }
}


// Delete a rectangle from non-root part of an index structure.
// Called by RemoveRect.  Descends tree recursively,
// merges branches on the way back up.
// Returns 1 if record not found, 0 if success.
RTREE_TEMPLATE
bool RTREE_QUAL::RemoveRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, ListNode** a_listNode)
{
  ASSERT(a_rect && a_node && a_listNode);
  ASSERT(a_node->m_level >= 0);

  if(a_node->IsInternalNode())  // not a leaf node
  {
    for(int index = 0; index < a_node->m_count; ++index)
    {
      if(Overlap(a_rect, &(a_node->m_branch[index].m_rect)))
      {
        if(!RemoveRectRec(a_rect, a_id, a_node->m_branch[index].m_child, a_listNode))
        {
          if(a_node->m_branch[index].m_child->m_count >= MINNODES)
          {
            // child removed, just resize parent rect
            a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);
          }
          else
          {
            // child removed, not enough entries in node, eliminate node
            ReInsert(a_node->m_branch[index].m_child, a_listNode);
            DisconnectBranch(a_node, index); // Must return after this call as count has changed
          }
          return false;
        }
      }
    }
    return true;
  }
  else // A leaf node
  {
    for(int index = 0; index < a_node->m_count; ++index)
    {
      if(a_node->m_branch[index].m_child == (Node*)a_id)
      {
        DisconnectBranch(a_node, index); // Must return after this call as count has changed
        return false;
      }
    }
    return true;
  }
}


// Decide whether two rectangles overlap.
RTREE_TEMPLATE
bool RTREE_QUAL::Overlap(Rect* a_rectA, Rect* a_rectB)
{
  ASSERT(a_rectA && a_rectB);

  for(int index=0; index < NUMDIMS; ++index)
  {
    if (a_rectA->m_min[index] > a_rectB->m_max[index] ||
        a_rectB->m_min[index] > a_rectA->m_max[index])
    {
      return false;
    }
  }
  return true;
}


// Add a node to the reinsertion list.  All its branches will later
// be reinserted into the index structure.
RTREE_TEMPLATE
void RTREE_QUAL::ReInsert(Node* a_node, ListNode** a_listNode)
{
  ListNode* newListNode;

  newListNode = AllocListNode();
  newListNode->m_node = a_node;
  newListNode->m_next = *a_listNode;
  *a_listNode = newListNode;
}


// Search in an index tree or subtree for all data retangles that overlap the argument rectangle.
RTREE_TEMPLATE
bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect, int& a_foundCount, bool __cdecl a_resultCallback(DATATYPE a_data, void* a_context), void* a_context)
{
  ASSERT(a_node);
  ASSERT(a_node->m_level >= 0);
  ASSERT(a_rect);

  if(a_node->IsInternalNode()) // This is an internal node in the tree
  {
    for(int index=0; index < a_node->m_count; ++index)
    {
      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
      {
        if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, a_resultCallback, a_context))
        {
          return false; // Don't continue searching
        }
      }
    }
  }
  else // This is a leaf node
  {
    for(int index=0; index < a_node->m_count; ++index)
    {
      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))
      {
        DATATYPE& id = a_node->m_branch[index].m_data;
        
        // NOTE: There are different ways to return results.  Here's where to modify
        if(&a_resultCallback)
        {
          ++a_foundCount;
          if(!a_resultCallback(id, a_context))
          {
            return false; // Don't continue searching
          }
        }
      }
    }
  }

  return true; // Continue searching
}

//given a point,Rect,caculate the min distance
//Mindist fuction
RTREE_TEMPLATE
ELEMTYPE RTREE_QUAL::Mindist(Rect* a_rect, ELEMTYPE point[NUMDIMS])
{
	ASSERT(a_rect) ;
	ELEMTYPE res ;
	ELEMTYPE r ;
	res = 0 ;
	for( int i = 0 ; i < NUMDIMS ; i++ )
	{
		if( point[i] < a_rect->m_min[i] )
			r = a_rect->m_min[i] ;
		else if( point[i] > a_rect->m_max[i] )
			r = a_rect->m_max[i] ;
		else r = point[i] ;
		res += ( r - point[i]) * ( r - point[i]) ;
	}
	return res ;
}

RTREE_TEMPLATE
ELEMTYPE RTREE_QUAL::Minmaxdist(Rect* a_rect,ELEMTYPE point[NUMDIMS])
{
	ASSERT(a_rect) ;
	ELEMTYPE res,flag ;
	ELEMTYPE rm,rM ;
	res = 1000000 ;
	for( int k = 0 ; k < NUMDIMS ; k++ )
	{
		if( point[k] <= ( a_rect->m_min[k] + a_rect->m_max[k] ) / 2 )
			rm = a_rect->m_min[k] ;
		else rm = a_rect->m_max[k] ;
		flag = ( rm - point[k] ) * ( rm - point[k] ) ;

		for( int i = 0 ; i < NUMDIMS ; i++ )
		{
			if( i == k )
				continue ;
			if( point[i] >= ( a_rect->m_min[i] + a_rect->m_max[i] ) / 2 ) 
				rM = a_rect->m_min[i] ;
			else
				rM = a_rect->m_max[i] ;
			flag += ( rM - point[i] ) * ( rM - point[i]);
		}
		if( flag < res ) 
			res = flag ;
	}
	return res ;
}


RTREE_TEMPLATE
void RTREE_QUAL::sort(BranchLevel h[MAX_HEAP],int flag,ELEMTYPE point[NUMDIMS] )
{
	int i,j ;
	BranchLevel temp ;
	for( i = 0 ; i < flag ; i++ )
	{
		for( j = 0 ; j < flag - i - 1 ; j++ )
		{
			if( Mindist( &(h[j].m_branch.m_rect),point ) < Mindist( &(h[j+1].m_branch.m_rect),point) )
			{
				temp = h[j+1] ;
				h[j+1] = h[j] ;
				h[j] = temp ;
			}
		}
	}
}

RTREE_TEMPLATE
void RTREE_QUAL::caculateBestSort(BranchLevel heap[MAX_HEAP],int count_branch,ELEMTYPE * best,int k,ELEMTYPE point[NUMDIMS])//对堆中的branch计算k个minMax
{
	int i;
	int min;
	BranchLevel temp ;
	int j;

	min=count_branch> k ? count_branch:k;//这个东西都没写过了
	
	for( i = 0 ; i < count_branch; i++ )
	{
		for( j = 0 ; j < count_branch - i - 1 ; j++ )
		{
		   /*	Minmaxdist(Rect* a_rect,ELEMTYPE point[NUMDIMS])*/
			if( Minmaxdist( &(heap[j].m_branch.m_rect),point ) > Minmaxdist( &(heap[j+1].m_branch.m_rect),point) )
			{
				temp = heap[j+1] ;
				heap[j+1] = heap[j] ;
				heap[j] = temp ;
			}
		}
	}

	*best=Minmaxdist(&(heap[min-1].m_branch.m_rect),point);
}



RTREE_TEMPLATE
void RTREE_QUAL::find( ELEMTYPE point[NUMDIMS],Node * node,int k)
{
	ELEMTYPE Best;
	struct BranchLevel heap[MAX_HEAP],t_branch,temp_branch;
	int  num_branch;
	Rect Result[MAX_RESULT];
	int result=0;
	int i,j;
//	Node *current_node;
    int level=0;
	ELEMTYPE distance=0;
	int initial=k;


    level=node->m_level;
	for( i = 0 ; i < node->m_count ; i++ )//将节点的rect加入到堆中
	{
		heap[i].m_branch = node->m_branch[i];
		heap[i].m_level=level;
	}

	num_branch = node->m_count ;//堆中有效矩形的个数
    caculateBestSort(heap,num_branch,&Best,k,point);
	sort(heap,num_branch,point);
    //current_node=node;

	 while(num_branch&&k>0)//堆中还有矩形且还没有找到k点的时候
	 {
		t_branch=heap[num_branch-1];
		num_branch--;
		if(Minmaxdist(&t_branch.m_branch.m_rect,point)>Best)
			continue;
		else
		{
			if(t_branch.m_level==0)//如果是叶子接点的话，则必然是满足条件的点，因为最小的值，minDist且是叶子接点的话必然是最小值
			{
				Result[result++]=t_branch.m_branch.m_rect;
				k--;//将要查找的点减少
				caculateBestSort(heap,num_branch,&Best,k,point);//重新进行计算best值
				sort(heap,num_branch,point);//对堆进行重排列
			}
        	else
			{
              level=(t_branch.m_branch.m_child)->m_level;
		      for(i=0;i<(t_branch.m_branch.m_child)->m_count;i++)
			  {
				temp_branch.m_branch=((t_branch.m_branch.m_child)->m_branch[i]);
				temp_branch.m_level=level;
				heap[num_branch++]=temp_branch;
			  }//end of for
			  caculateBestSort(heap,num_branch,&Best,k,point);
		      sort(heap,num_branch,point);
			}//end of else
		}//end of else
	 }//end of while
 
   printf("The nearest %d points are:\n",initial);

   for(i=0;i<result;i++)
   {
         printf("The %d nearest point is\n",i+1);
		 for(j=0;j<NUMDIMS;j++)
	        printf("%1.6f  ",Result[i].m_min[j]);
		 for(j=0;j<NUMDIMS;j++)
			 distance+=(Result[i].m_min[j]-point[j])*(Result[i].m_min[j]-point[j]);

		 printf("\nThe distance is %4.6f\n",distance);
		 distance=0;
    	 printf("%s","\n");
   }

}


/*void RTREE_QUAL::find( ELEMTYPE point[NUMDIMS],Node* node )
{
//	ASSERT(n) ;
	ELEMTYPE Best = 1000000 ;
	struct Branch heap[MAX_HEAP],t_branch ;
	long count = 0 ;
	ELEMTYPE r ;
	Rect E[10000] ;
	int flag1 = 0 ;
	int i ;
	int flag ;

	//for( i = 0 ; i < NUMDIMS ; i++ )
	//	s[i] = p[i] ;

	for( i = 0 ; i < node->m_count ; i++ )//将节点的rect加入到堆中
		heap[i] = node->m_branch[i] ;

	flag = node->m_count ;//堆中有效矩形的个数
	
  if( !node->IsLeaf() )//如果此接点是叶子接点，则将其下的点放至结果集中
	{
		while( flag )
		{
			//count++ ;
			t_branch = heap[flag-1] ;
			flag-- ;
			//if( count == 100 )
			//	break ;
			if( t_branch.m_child->IsLeaf() )
			{
				for( int k = 0 ; k < t_branch.m_child->m_count ; k++ )
				{
					if ( Mindist( &t.m_child->m_branch[k].m_rect,point) > Best )//大于best值，prune off
						continue ;
				
					else if( Minmaxdist(&t_branch.m_rect,point) < Best )//将best值改变
						Best = Minmaxdist( &t_branch.m_rect,point ) ;
					E[flag1++] = t_branch.m_child->m_branch[k].m_rect ;//添加到结果集中
				}	
				continue ;//跳过本次循环
			}

			if( Mindist(&t.m_rect,p) > Best )//非叶子接点的情况
				continue ;
			else if( Minmaxdist(&t.m_rect,p) < Best )
				Best = Minmaxdist(&t.m_rect,p) ;
			for( int i = 0 ; i < t.m_child->m_count ; i++ )
				heap[flag++] = t.m_child->m_branch[i] ;
			//qsort(heap,flag,sizeof(heap[0]),cmp) ;
			sort(heap,flag,p) ;//理应是大到小的排序
		}
	}
	else {//根是叶子接点的情况
		for( i = 0 ; i < node->m_count ; i++ )
		{
			E[i] = heap[i].m_rect ;
		}
		flag1 = n.m_count ;
	}
	
	for( i = 0 ; i < flag1 ; i++ )//flag 1 是结果集中点的个数
	{
		r = 0 ;
		for( int j = 0 ; j < NUMDIMS ; j++ )
		{
			r += ( E[i].m_min[j] - point[j] ) * ( E[i].m_min[j] - point[j] ) ;//计算点的距离
		}
		if( r < Best )//找到距离最小的点
		{
			Best = r ;
			flag = i ;
		}
	}
	
	cout<<"the nearest point is   \n" ;	
	for( i = 0 ; i < NUMDIMS ; i++ )
		cout<<E[flag].m_min[i]<<endl ;//1nn algorithm
}*/


 








#undef RTREE_TEMPLATE
#undef RTREE_QUAL

#endif //RTREE_H