作者littleshan (我要加入剑道社!)
看板C_and_CPP
标题Re: [问题] 有关资料结构的问题(如何蒐寻.分类)
时间Fri Jul 24 09:10:59 2009
※ 引述《luckychild (兑现承诺)》之铭言：
: 一个3D空间有很多具有不同几何形状的物体会持续生成.
: 我想要知道某一瞬间各个粒子间是否互相重叠.
: 所以我应该先取得特定时刻每个物体特定点的座标.这些特定点足以标定物体的位置.
: 譬如圆心或长杆物的两端点.
: 我需要知道物体有哪些邻居然後做一些计算判断是否重叠.
: 像蒐集很多物体的资料并判断哪些是邻居这件事有没有什麽好的方法可以达成?
用 grid。
原理是把空间切割成许多小方格，每个方格都记录该方格中包含了哪些物体。
这麽一来要判断有哪些邻居，只要去查询邻近的方格内有哪些物体即可。
方格的大小必须约略大於物体的平均大小，这样会比较有效率。
然而当物体的大小差异很大时，最好使用阶层性的资料结构 (ex. adaptive grid)
会比固定大小的方格切割法好一点。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.87.151.2