quadtree.h

segmentation sample good luck

// QuadTree.h - this creates a set of objects, based on quadtrees

#ifndef QUADTREE_H
#define QUADTREE_H

#include <vector>

// The class used to define the specific quad tree must implement
// the method, "CPoint CQTLocation()".

template <class T> class CQuadTreeLeaf;
template <class T> class CQuadTreeBoringNode;

// First, we define the generic node, which might be a leaf or
// might be a tree with leaves.
template <class T> class CQuadTreeNode {
public:
	virtual ~CQuadTreeNode<T>() {}
	virtual bool IsLeaf() = 0;
	enum eQuad { eUpperLeft,eUpperRight,eLowerLeft,eLowerRight};
	virtual CQuadTreeNode<T> *GetQuad(eQuad quad) { return NULL; }
	virtual void GetItems(std::vector<T *> &vT) {
		vT.resize(0);
	}
	virtual bool RemoveItem(T *ptr) = 0;
	virtual CQuadTreeLeaf<T> &ToLeaf() { 
		ASSERT(FALSE);
		return *(CQuadTreeLeaf<T> *)NULL;
	}
	virtual CQuadTreeBoringNode<T> &ToBoringNode() {
		ASSERT(FALSE);
		return *(CQuadTreeBoringNode<T> *)NULL;
	}
};

// The leaf has a vector of pointers to the structures.

template <class T> class CQuadTreeLeaf: public CQuadTreeNode<T> {
protected:
	std::vector<T *> m_vT;
public:
	virtual ~CQuadTreeLeaf<T>()
	{
	}
	void AddItem(T *ptr) {
		m_vT.push_back(ptr);
	}
	virtual bool RemoveItem(T *ptr) {
		for (std::vector<T *>::iterator i = m_vT.begin();i != m_vT.end();i++) {
			if (*i == ptr) {
				m_vT.erase(i);
				return TRUE;
			}
		}
		return FALSE;
	}
	bool IsLeaf() { return TRUE; }
	virtual void GetItems(std::vector<T *> &vT) {
		vT = m_vT;
	}
	virtual CQuadTreeLeaf<T> &ToLeaf() {
		return *this;
	}
};

// The boring node has four pointers.

template <class T> class CQuadTreeBoringNode: public CQuadTreeNode<T> {
protected:
	CQuadTreeNode<T> *m_pUL;
	CQuadTreeNode<T> *m_pUR;
	CQuadTreeNode<T> *m_pLL;
	CQuadTreeNode<T> *m_pLR;
public:
	CQuadTreeBoringNode<T>() {
		m_pUL = NULL; m_pUR = NULL; m_pLL = NULL; m_pLR = NULL;
	}
	virtual ~CQuadTreeBoringNode<T>()
	{
	}
	bool IsLeaf() { return FALSE; }
	virtual void GetItems(std::vector<T *> &vT) {
		if (m_pUL) m_pUL->GetItems(vT);
		std::vector<T *> vTemp;
		if (m_pUR) m_pUR->GetItems(vTemp);
		vT.insert(vT.end(),vTemp.begin(),vTemp.end());
		vTemp.resize(0);
		if (m_pLL) m_pLL->GetItems(vTemp);
		vT.insert(vT.end(),vTemp.begin(),vTemp.end());
		vTemp.resize(0);
		if (m_pLR) m_pLR->GetItems(vTemp);
		vT.insert(vT.end(),vTemp.begin(),vTemp.end());
	}
	virtual CQuadTreeNode<T> *GetQuad(eQuad quad) {
		switch(quad) {
		default: ASSERT(FALSE);
		case eUpperLeft: return m_pUL;
		case eUpperRight: return m_pUR;
		case eLowerLeft: return m_pLL;
		case eLowerRight: return m_pLR;
		}
	}
	void SetQuad(eQuad quad,CQuadTreeNode<T> *pNode) {
		switch(quad) {
		default: ASSERT(FALSE);
		case eUpperLeft: m_pUL = pNode; break;
		case eUpperRight: m_pUR = pNode; break;
		case eLowerLeft:  m_pLL = pNode; break;
		case eLowerRight: m_pLR = pNode; break;
		}
	}
	virtual bool RemoveItem(T *pItem) {
		// You should probably be using CQuadTree::RemoveItem.
		// This can go through every leaf in the tree.

		if (m_pUL && m_pUL->RemoveItem(pItem)) return TRUE;
		if (m_pUR && m_pUR->RemoveItem(pItem)) return TRUE;
		if (m_pLL && m_pLL->RemoveItem(pItem)) return TRUE;
		if (m_pLR && m_pLR->RemoveItem(pItem)) return TRUE;
		return FALSE;
	}
	virtual CQuadTreeBoringNode<T> &ToBoringNode() {
		return *this;
	}
};

// The quad tree allows lookup of all items within a rectangle
// within O(log2(sizeof(int) * 8)).
// I've modeled this more after MFC CArray than the STL templates.

template <class T> class CQuadTree {
public:
	CQuadTree();
	virtual ~CQuadTree();
	void Insert(T *pItem);
	void GetItems(const CRect &cr,std::vector<T *> &);
	bool Remove(T *pItem);
	void RemoveAll();
	bool IsEmpty();
protected:
	CQuadTreeBoringNode<T> m_root;	
};

template <class T> CQuadTree<T>::CQuadTree<T>()
{
}

template <class T> CQuadTree<T>::~CQuadTree<T>()
{
	RemoveAll();
}

template <class T> bool CQuadTree<T>::IsEmpty()
{
	return ! (m_root.GetQuad(CQuadTreeNode<T>::eUpperLeft) ||
			  m_root.GetQuad(CQuadTreeNode<T>::eUpperRight) ||
			  m_root.GetQuad(CQuadTreeNode<T>::eLowerLeft) ||
			  m_root.GetQuad(CQuadTreeNode<T>::eLowerRight));
}

template <class T> void CQuadTree<T>::Insert(T *pItem)
{
	CPoint pt = pItem->CQTLocation();

	CQuadTreeNode<T> *pNode = &m_root;
	CQuadTreeNode<T>::eQuad quad;

	CPoint ptCompare(0,0);
	int nIncrement = 1 << (sizeof(int) * 8 - 2);

	while(TRUE) {
		if (pt.x >= ptCompare.x) {
			ptCompare.x += nIncrement;
			if (pt.y >= ptCompare.y) {
				quad = CQuadTreeNode<T>::eUpperRight;
				ptCompare.y += nIncrement;
			} else {
				quad = CQuadTreeNode<T>::eLowerRight;
				ptCompare.y -= nIncrement;
			}
		} else {
			ptCompare.x -= nIncrement;
			if (pt.y >= ptCompare.y) {
				quad = CQuadTreeNode<T>::eUpperLeft;
				ptCompare.y += nIncrement;
			} else {
				quad = CQuadTreeNode<T>::eLowerLeft;
				ptCompare.y -= nIncrement;
			}
		}

		CQuadTreeNode<T> *pNext = pNode->GetQuad(quad);
		if (pNext == NULL) {
			// EZ. Nobody has come through here before.
			// We just have to build a leaf to go here.

			CQuadTreeLeaf<T> *pLeaf = new CQuadTreeLeaf<T>;
			try {
				pNode->ToBoringNode().SetQuad(quad,pLeaf);
			} catch(CException *) {
				delete pLeaf;
				throw;
			}
			pLeaf->AddItem(pItem);
			return;
		} else if (pNext->IsLeaf()) {
			vector<T *> vItems;
			pNext->GetItems(vItems);
			CPoint ptOther;
			if (vItems.size() == 0 || 
				(ptOther = vItems[0]->CQTLocation()) == pt) {
				// This leaf either had no items, or all of the items
				// are at the same spot.

				pNext->ToLeaf().AddItem(pItem);
				return;
			} else {
				// We have to turn a leaf into a quad-tree, possibly
				// recursively.

				CQuadTreeBoringNode<T> *pNewNode = new CQuadTreeBoringNode<T>;

				try {
					// First, figure out the quadrant of the leaf.

					CQuadTreeNode<T>::eQuad quadOther;
					if (ptOther.x >= ptCompare.x) {
						if (ptOther.y >= ptCompare.y) {
							quadOther = CQuadTreeNode<T>::eUpperRight;
						} else {
							quadOther = CQuadTreeNode<T>::eLowerRight;
						}
					} else {
						if (ptOther.y >= ptCompare.y) {
							quadOther = CQuadTreeNode<T>::eUpperLeft;
						} else {
							quadOther = CQuadTreeNode<T>::eLowerLeft;
						}
					}
					pNewNode->SetQuad(quadOther,pNext);
					pNode->ToBoringNode().SetQuad(quad,pNewNode);
					pNode = pNewNode;
				} catch (CException *) {
					delete pNewNode;
					throw;
				}
			}
		} else {
			pNode = pNext;
		}
		ASSERT(nIncrement != 0);  // We're about to do two trips through zero!
		nIncrement = nIncrement >> 1;
	}
}

// The CGIStackItem class maintains the following items that need to
// be pushed onto the stack in order to perform GetItems:
//
// the center point of the node in question
// a pointer to the node in question
// the length of one quadrant within the node.

template <class T> class CGIStack
{
public:
	CPoint m_pt;
	CQuadTreeNode<T> *m_pNode;
	int m_nIncrement;
	CGIStack<T>() { }
	CGIStack<T>(CPoint pt,CQuadTreeNode<T> *pNode,int nIncrement) {
		m_pt = pt;
		m_pNode = pNode;
		m_nIncrement = nIncrement;
	}
	CGIStack<T>(const CGIStack<T> &src) {
		m_pt = src.m_pt;
		m_pNode = src.m_pNode;
		m_nIncrement = src.m_nIncrement;
	}
	bool operator < (const CGIStack<T> &src) const {
		// Really, I never intend that this should be called
		ASSERT(FALSE);
		return m_pt.y < src.m_pt.y || (m_pt.y == src.m_pt.y && m_pt.x < src.m_pt.x);
	}
	BOOL operator == (const CGIStack<T> &src) const {
		ASSERT(FALSE);
		return m_pt == src.m_pt;
	}
};

template <class T> void CQuadTree<T>::GetItems(const CRect &cr,std::vector<T *> &v)
{
	// Fill the vector with pointers to all items within the given rectangle.
	//
	// Here, we start descending the quad tree. If a node is wholly
	// within the rectangle, then we can call GetItems for it.
	// If it's wholly outside, we exclude it. If it's part in and 
	// part out, we descend and perform the test on the sub-nodes.

	int nIncrement = 1 << (sizeof(int) * 8 - 2);

	// Push (possibly) four node centers, four pointers and
	// four increments on the stack of things to do.
	std::vector<CGIStack<T> > stack;

	CQuadTreeNode<T> *pNode;

	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eUpperLeft)) {
		stack.push_back(CGIStack<T>(CPoint(-nIncrement,nIncrement),
									pNode,
									nIncrement));
	}

	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eUpperRight)) {
		stack.push_back(CGIStack<T>(CPoint(nIncrement,nIncrement),
									pNode,
									nIncrement));
	}

	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eLowerLeft)) {
		stack.push_back(CGIStack<T>(CPoint(-nIncrement,-nIncrement),
									pNode,
									nIncrement));
	}

	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eLowerRight)) {
		stack.push_back(CGIStack<T>(CPoint(nIncrement,-nIncrement),
									pNode,
									nIncrement));
	}

	while(stack.size()) {
		CGIStack<T> stackTop(stack[stack.size() - 1]);
		stack.pop_back();
		if (stackTop.m_pNode->IsLeaf()) {
			vector<T *> vItems;
			stackTop.m_pNode->GetItems(vItems);
			if (vItems.size() && cr.PtInRect(vItems[0]->CQTLocation())) {
				v.insert(v.end(),vItems.begin(),vItems.end());
			}
		} else {
			// Determine whether there's any overlap between the
			// rectangle and the quadrant. First, we have to build
			// the rectangle. We have an awful case: the rightmost
			// edge of the rightmost quadrant extends past MAX_INT
			// by one.

			CRect crQuad(stackTop.m_pt.x - stackTop.m_nIncrement, // left
						 stackTop.m_pt.y - stackTop.m_nIncrement, // top
						 stackTop.m_pt.x + stackTop.m_nIncrement, // right
						 stackTop.m_pt.y + stackTop.m_nIncrement);
			if (crQuad.right < crQuad.left) crQuad.right = INT_MAX;
			if (crQuad.bottom < crQuad.top) crQuad.bottom = INT_MAX;

			CRect crIntersect;
			if (crIntersect.IntersectRect(crQuad,cr)) {
				if (crQuad == crIntersect) {
					// Big win, the quadrant is wholly within the
					// rectangle.

					vector<T *> vItems;
					stackTop.m_pNode->GetItems(vItems);
					v.insert(v.end(),vItems.begin(),vItems.end());
				} else {
					// Push the quadrants onto the stack. At least one
					// overlaps.

					nIncrement = stackTop.m_nIncrement >> 1;
					ASSERT(nIncrement);
					pNode = stackTop.m_pNode->GetQuad(CQuadTreeNode<T>::eUpperLeft);
					if (pNode) {
						CPoint ptNew(stackTop.m_pt.x - nIncrement,stackTop.m_pt.y + nIncrement);
						stack.push_back(CGIStack<T>(ptNew,
													pNode,	
													nIncrement));
					}

					pNode = stackTop.m_pNode->GetQuad(CQuadTreeNode<T>::eUpperRight);
					if (pNode) {
						CPoint ptNew(stackTop.m_pt.x + nIncrement,stackTop.m_pt.y + nIncrement);
						stack.push_back(CGIStack<T>(ptNew,
													pNode,	
													nIncrement));
					}

					pNode = stackTop.m_pNode->GetQuad(CQuadTreeNode<T>::eLowerLeft);
					if (pNode) {
						CPoint ptNew(stackTop.m_pt.x - nIncrement,stackTop.m_pt.y - nIncrement);
						stack.push_back(CGIStack<T>(ptNew,
													pNode,	
													nIncrement));
					}

					pNode = stackTop.m_pNode->GetQuad(CQuadTreeNode<T>::eLowerRight);
					if (pNode) {
						CPoint ptNew(stackTop.m_pt.x + nIncrement,stackTop.m_pt.y - nIncrement);
						stack.push_back(CGIStack<T>(ptNew,
													pNode,	
													nIncrement));
					}
				}
			}
		}
	}
}

template <class T> bool CQuadTree<T>::Remove(T *pItem)
{
	CPoint pt = pItem->CQTLocation();

	CPoint ptCurrent(0,0);
	int nIncrement = 1 << (sizeof(int) * 8 - 2);

	CQuadTreeNode<T> *pNode = &m_root;
	while(TRUE) {
		CQuadTreeNode<T> *pNodeNext;
		if (pt.x >= ptCurrent.x) {
			ptCurrent.x += nIncrement;
			if (pt.y >= ptCurrent.y) {
				pNodeNext = pNode->GetQuad(CQuadTreeNode<T>::eUpperRight);
				ptCurrent.y += nIncrement;
			} else {
				pNodeNext = pNode->GetQuad(CQuadTreeNode<T>::eLowerRight);
				ptCurrent.y -= nIncrement;
			}
		} else {
			ptCurrent.x -= nIncrement;
			if (pt.y >= ptCurrent.y) {
				pNodeNext = pNode->GetQuad(CQuadTreeNode<T>::eLowerRight);
				ptCurrent.y += nIncrement;
			} else {
				pNodeNext = pNode->GetQuad(CQuadTreeNode<T>::eLowerLeft);
				ptCurrent.y += nIncrement;
			}
		}
		if (pNodeNext == NULL) return FALSE;

		if (pNodeNext->IsLeaf()) {
			return pNodeNext->RemoveItem(pItem);
		} else {
			pNode = pNodeNext;
			nIncrement = nIncrement >> 1;
			ASSERT(nIncrement);
		}
	}
}

template <class T> void CQuadTree<T>::RemoveAll()
{
	std::vector<CQuadTreeNode<T> *> v;

	CQuadTreeNode<T> *pNode;
	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eUpperLeft)) {
		v.push_back(pNode);
		m_root.SetQuad(CQuadTreeNode<T>::eUpperLeft,NULL);
	}
	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eUpperRight)) {
		v.push_back(pNode);
		m_root.SetQuad(CQuadTreeNode<T>::eUpperRight,NULL);
	}
	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eLowerLeft)) {
		v.push_back(pNode);
		m_root.SetQuad(CQuadTreeNode<T>::eLowerLeft,NULL);
	}

	if (pNode = m_root.GetQuad(CQuadTreeNode<T>::eLowerRight)) {
		v.push_back(pNode);
		m_root.SetQuad(CQuadTreeNode<T>::eLowerRight,NULL);
	}

	while(v.size()) {
		pNode = v[v.size() - 1];
		v.pop_back();
		if (! pNode->IsLeaf()) {
			CQuadTreeNode<T> *pSubNode;
			if (pSubNode = pNode->GetQuad(CQuadTreeNode<T>::eUpperLeft)) v.push_back(pSubNode);
			if (pSubNode = pNode->GetQuad(CQuadTreeNode<T>::eUpperRight)) v.push_back(pSubNode);
			if (pSubNode = pNode->GetQuad(CQuadTreeNode<T>::eLowerLeft)) v.push_back(pSubNode);
			if (pSubNode = pNode->GetQuad(CQuadTreeNode<T>::eLowerRight)) v.push_back(pSubNode);
		}
		delete pNode;
	}
}

#endif