topenchoose.java

Thalmann算法的java实现。有详细注释。

/**
 * Thalmann算法中，在回溯时在open表中选择一个合适节点：
 * 创建一个LinkedList，将所有的layer值最小的节点均加入该链表
 * 如果该链表中只有一个元素，则该节点就是需要寻找的节点
 * 如果该链表中有多个元素，则对这多个元素进行进一步的比较
 * 如果只有一个直交节点，则该节点为搜索对象，
 * 如果有多个直交节点，则随机选择一个直交节点
 * 如果均为斜交节点，则亦随机选择一个
**/

package page;

import java.util.*;       //LinkedList

public class TOpenChoose 
{
	TNodes now=new TNodes();     
	TNodes result=new TNodes();     
	LinkedList Lresult=new LinkedList();  //用于保存layer最小的节点
	
	int nowlayer=0,resultlayer=0;
	
	public TOpenChoose()
	{
	}
	
	//有参构造函数，参数是当前正在处理的节点nownode和open表，其open表中保存了当前正在处理节点的八个邻近节点
	public TOpenChoose(LinkedList open,TNodes nownode)
	{
		if(open.size()>0)
		{
			//首先获得open表中的第一元素的引用，将其加入Lresult表中		
			result=(TNodes)open.get(0);	
			resultlayer=result.getLayer();
			Lresult.add(result);	
		
			for(int i=1;i<open.size();i++)
			{
				now=(TNodes)open.get(i);
				nowlayer=now.getLayer();
			
				//如果有新的节点的layer小于result，则将Lresult清空，将新的节点加入Lresult中
				if(nowlayer<resultlayer)
				{
					result=now;
					resultlayer=nowlayer;
					Lresult.clear();
					Lresult.add(result);
				}
			
				//如果有新的节点的layer与result的layer相同，则将该节点加入Lresult中
				else if(nowlayer==resultlayer)
				{
					Lresult.add(now);
				}
			}//for(int i=1;i<open.size();i++)  open表中的节点处理完毕
		
			//如果Lresult表中只有一个元素，则该节点就是要寻找的节点
			if(Lresult.size()==1)
				result=(TNodes)Lresult.get(0);
				
			//如果Lresult表中有多个元素，则需要对其进行比较选择
			else 
			{			
				int nowX=0,nowY=0,x=0,y=0,add=0;
				nowX=nownode.getX();
				nowY=nownode.getY();
				now=(TNodes)Lresult.get(0);
				x=now.getX();
				y=now.getY();
				add=java.lang.Math.abs(nowX-x)+java.lang.Math.abs(nowY-y);
			
				//有直交节点，则任意选择一个直交节点；没有直交节点，则任意选择一个斜交节点
				if(add==1)  //Lresult表中第一个元素即为直交节点
				{
					result=now;
				}		
				else
				{
					result=now;
					for(int i=1;i<Lresult.size();i++)
					{
						now=(TNodes)Lresult.get(i);
						x=now.getX();
						y=now.getY();
						if(java.lang.Math.abs(nowX-x)+java.lang.Math.abs(nowY-y)==1)
						{
							result=now;
							break;
						}
					}
				}
			}  //else   如果Lresult表中有多个元素，则需要对其进行比较选择
		}
		else   
			result=null;
	}//public TOpenChoose(LinkedList open,int layer)
	
	public TNodes getNode()
	{
		return result;
	}
}