接触Р行为,如图所示, 搜索到的最近的主节点并不包含最近的主段。Р Р 从节点Р 最近的主段Р 最近的主节点Р Р Р 基于段的基于段的 bucket 分类搜索方式分类搜索方式Р 基于段的 bucket 分类搜索方式是新的接触搜索方式,主要是为了解决如上面提到的接Р触搜索问题。它的原理是对于每个从节点, 搜索最近的主段, 首先把接触空间划分成很多小Р的 bucket ,对于每个从节点, 按照它的空间位置指定于某个 bucket 中, 然后在该范围内搜Р索最近的主段, 运行一定的时间后( 比如 100 个时间循环), 根据该节点空间位置的变化再Р重新指定新的 bucket 。如图所示: Р 一维 bucket 分类搜索分类搜索Р Р Р 比如在一维 bucket 分类方式下,图中的黑点代表接触段的质心点(通过该质心点定位Р主段), 对于落入某 bucket 的从节点而言, 搜索该 bucket 中的段, 找到最近的主段,若没有Р找到,再搜索附近的 bucket ,直到找到最近的主段。这种方法由于不断更新 bucket 分类,Р所以要耗费更多的 CPU 时间。Р 同理在二维和三维 bucket 分类搜索方式下搜索最近的主段。Р Р 二维 bucket 分类搜索分类搜索:: Р Р 20Р三维 bucket 分类搜索分类搜索:: Р Р Р 如下图所示,若应用基于节点的增量搜索方式, 找到最近的主节点,与该节点相联Р的主段是 1, 2, 3,但都不包含该从节点,所以接触搜索失效,但若使用基于段的 bucketР分类搜索方式,可以很方便的找到包含该从节点的主段,建立接触关系。Р 最近的节点Р 从节点Р Bucket 搜索后得到包含该从节点的段Р 总的来说, 非自动接触类型采用基于节点的增量搜索,自动接触类型采用基于段的Рbucket 分类搜索。所以总是建议使用自动接触类型。Р 21
全文预览
