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增长的小的