Sign in to follow this  

Infinite Recursion in kD-Tree

This topic is 3727 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I can't find the bug in this little piece of code :( I get an stack-overflow exception, because the recursion does not stop. Am I blind or does anyone see an obvious error? thanx, nick
public class KDTree 
{
	private Photon       m_Photon     = null;
	private KDTree       m_Left       = null;
	private KDTree       m_Right      = null;
//	----------------------------------------------------------------------------
	public KDTree ()
	{
		//m_lstPhotons = new ArrayList<Photon> ();
	}
//	----------------------------------------------------------------------------
	public KDTree makeKDTree (final List<Photon> lstPhoton, final int iDepth)
	{
		//if (iDepth > 10)
		//	return null;
					
		if (lstPhoton.size () == 1)
		{
			KDTree t = new KDTree ();
			t.m_Photon = new Photon (lstPhoton.get (0));
			return t;
		}
		
		final int iAxis = iDepth % 3;			
		final Photon median = lstPhoton.get (lstPhoton.size() / 2);
		
		if (lstPhoton.size() == 0)
			System.out.println("HA");
		
		List<Photon> lstLeft = new ArrayList<Photon> ();
		List<Photon> lstRight = new ArrayList<Photon> ();
		for (Photon p : lstPhoton)
		{
			if (p.getOrigin().get (iAxis) < median.getOrigin ().get (iAxis))
			{
				lstLeft.add (p);
			}
			else
			{
				lstRight.add (p);
			}
		}		
		//lstPhoton.clear();
		
		KDTree left = null;
		KDTree right = null;
		
		if (!lstLeft.isEmpty ())
		{
			left = makeKDTree (lstLeft, iDepth + 1);
		}
		if (!lstRight.isEmpty ())
		{
			right = makeKDTree (lstRight, iDepth + 1);
		}		
				
		return compose (left, median, right);
	}
//	----------------------------------------------------------------------------
	private KDTree compose (
			final KDTree left,
			final Photon p,
			final KDTree right)
	{
		KDTree result = new KDTree ();
		result.m_Left = left;
		result.m_Photon = new Photon (p);
		result.m_Right = right;
		return result;
	}
//	----------------------------------------------------------------------------
	public boolean isLeaf (final KDTree tree)
	{
		if (tree.m_Left == null && tree.m_Right == null)
			return true;
		return false;
	}
//	----------------------------------------------------------------------------
}

Share this post


Link to post
Share on other sites
Sign in to follow this