RTree 分裂节点算法流程

D

group2

mbr2

C

候选节点列表（remaining）

A

splitNode

F

2.得到“最佳”候选点：即加入group1后引起mbr增长最小的候选点

E

1.传入候选列表逐个加入group1

y

mbr1

B

在列表中查找\"最坏\"的节点对：也就是能组成最大mbr的对角线点

SplitterQuadratic(二次分裂器)

splitNode()

找出列表中两两配对 能组成最大MBR的对角线点对 Pair（A，B）

3.删除已筛选出的候选点

x

min_let_bottom和max_right_top两个点组成了新的mbr

group1

以这两个点为核心，将原节点分裂成两个新的组节点

假设原节点的MBR为 oldMBR如果这两个节点在同一组里，假设为group1newMBR=group1MBR+group2MBR因为group1MBR=worstMBR而如果打散这两个节点分入不同组newMBR'=betterMBR+maybeBetterMBRnewMBR'<=newMBR肯定是不如将这两个节点打散分入不同组的MBR增长的小的