文档章节

四叉树

梦想游戏人
 梦想游戏人
发布于 2016/09/18 14:20
字数 453
阅读 3
收藏 0

 


class Rect
{
public:
	int x = 0, y = 0, w = 100, h = 100;
	Rect(int x, int y, int w, int h) :x(x), y(y), w(w), h(h){}
	Rect(){};
};

class Point
{
public:
	int x = 90, y = 10;
	Point(){};
	Point(int x, int y) :x(x), y(y){};


};

class QuadTree
{
public:
	Rect *rect;
	int depth = 0;
	vector<QuadTree*> child;
	vector<Point*> obj;

	void insert(Point* p)
	{
		obj.push_back(p);
	}
	void insert(QuadTree* child)
	{
		if (child == 0)return;

		this->child.push_back(child);
	}


	QuadTree* getByPoint(Point*p)//获取该点的Node
	{

		if (p->x > rect->x + rect->w &&  p->y > rect->y + rect->h)return 0;

		if (child.size() ==0) return this;

		int cx = (rect->x + rect->w) / 2;
		int cy = (rect->y + rect->h) / 2;



		int index = 0;

		if (p->x > cx && p->y > cy)
		{
			index = 0;
	
		}
		 
		else if (p->x<=cx && p->y>=cy)
		{
			index = 1;
		}

		else if (p->x <= cx && p->y <= cy)
		{
			index = 2;
		}
		else if (p->x>cx&&p->y<cy)
		{
			index = 3;

		}

		return child[index]->getByPoint(p);









		return 0;

		for (int i = 0; i < child.size(); i++)
		{
			QuadTree * b = child[i]->getByPoint(new Point(p->x / 2, p->y / 2));

			if (b == 0)
			{
		

			}
			else
			{
				return    b->getByPoint(new Point(p->x/2,p->y/2));
			}
		}

	//	if (child.size() != 0)return 0;


		if (p->x >= rect->x && p->x <= rect->x + rect->w)
		{
			if (p->y >= rect->y && p->y <= rect->y + rect->h)
			{
				cout << " find " << endl;

				return this;
			}

		}
		return 0;

		 cout << "root   " << rect->x << "      " << rect->y << endl;


		
	}


	/*QuadTree * getObjs(Rect* rec)
	{

	QuadTree * n=0;
	for (auto & node : child)
	{
	if (node->getObjs(rec) == 0)
	{
	n = node;
	}
	}


	if (n)
	{
	return n->getObjs(rec);

	}
	return 0;
	}*/



	Rect** split()
	{
		Rect ** ret = new Rect *[4];
		ret[0] = new Rect;
		ret[1] = new Rect;
		ret[2] = new Rect;
		ret[3] = new Rect;

		int x = rect->x;
		int y = rect->y;
		int w = rect->w;
		int h = rect->h;

		for (int i = 0; i < 4; i++)
		{
			ret[i]->h = h / 2;
			ret[i]->w = w / 2;
		}

		ret[0]->x = (x + w) / 2;
		ret[0]->y = (y + h) / 2;

		ret[1]->x = x;
		ret[1]->y =( y+h) / 2;

		ret[2]->x = x;
		ret[2]->y = y;

		ret[3]->x = (x+w) / 2;
		ret[3]->y = y;

		return ret;

	}




};






QuadTree* creater(int depth, Rect* rect)
{
	if (depth == 0) return 0;

	QuadTree * Parent = new QuadTree;
	Parent->depth = depth;
	Parent->rect = rect;
	Rect ** path4 = Parent->split();





	Parent->insert(creater(depth - 1, path4[0]));
	Parent->insert(creater(depth - 1, path4[1]));
	Parent->insert(creater(depth - 1, path4[2]));
	Parent->insert(creater(depth - 1, path4[3]));


	return Parent;

}



int main(...)
{
	QuadTree *root = creater(4, new Rect(0, 0, 100, 100));





	QuadTree* area = root->getByPoint(new Point(14,14));


	system("pause");
	return 0;
}


 

 

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 38
博文 444
码字总数 127453
作品 0
成都
私信 提问
四叉树空间索引原理及其实现

今天依然在放假中,在此将以前在学校写的四叉树的东西拿出来和大家分享。 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间,如此递...

长平狐
2013/12/25
1K
0
四叉树与八叉树

前序 四叉树或四元树也被称为Q树(Q-Tree)。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等,而八叉树(Octree)主要应用于3D图形处理。对游戏编程,这会很有...

zhanxinhang
2011/08/21
0
0
LeetCode算法题-Quad Tree Intersection(Java实现)

这是悦乐书的第260次更新,第273篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第127题(顺位题号是558)。四叉树是树数据,其中每个内部节点恰好有四个子节点:topLeft,top...

小川94
02/26
0
0
四叉树算法:iOS地图点标记聚合方案

前言 在地图相关应用的开发中,我们常常遇到一个问题,当地图标注点过多的时候,会造成用户体验差、应用卡顿的情况。所以,我们需要一套高效的算法来解决标注的聚合、分散的逻辑。 先上代码:...

indulge_in
2017/11/21
0
0
【javascript实现】几道题目带你学习二叉搜索树

二叉树大家都知道,二叉搜索树满足以下特征: 节点的左子树只包含小于当前节点的数 节点的右子树只包含大于当前节点的数 所有左子树和右子树自身必须也是二叉搜索树 二叉搜索树也叫二叉排序树...

陈小俊
2018/11/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot 2.x基础教程:快速入门

简介 在您第1次接触和学习Spring框架的时候,是否因为其繁杂的配置而退却了?在你第n次使用Spring框架的时候,是否觉得一堆反复黏贴的配置有一些厌烦?那么您就不妨来试试使用Spring Boot来让...

程序猿DD
昨天
1
0
SpringSecurity认证流程源码级详解

SpringSecurity认证流程源码级详解 认证流程说明 认证结果如何在多个请求之间共享 获取认证用户信息

chendom
昨天
1
0
C语言中的volatile——让我保持原样

volatile译为:易变的。这不是和题目的让我保持原样矛盾了吗?其实不然,在变量前加上该关键字修饰,确实是告诉编译器,这个变量是一个容易改变的变量,不要对它进行优化,每次都要到变量的地...

天王盖地虎626
昨天
1
0
五、RabbitMQ的消息属性(读书笔记)

简介 当使用RabbitMQ发布消息时,消息又AMQP规范中的三个低层帧类型组成: Basic.publish方法帧; 内容头帧; 消息体帧; 这三种帧类型按顺序一起工作,以便消息传递时完好无损。 其中,内容...

XuePeng77
昨天
1
0
JavaEE开发的颠覆者SpringBoot实战摘要笔记

一、注解理解 1.spring注解 1)@Configuration/@ComponentScan/@Bean注解实现java方式的配置。 @Configuration代替xml文件 @ComponentScan指定扫描范围 @Bean代替bean标签 2)@Bean、@Componen...

啃不动地大坚果
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部