按区间端点扫描怎样找出横向重叠候选：独立演算第20例

场景对象很多时，可以先只看横向范围，把完全分开的对象排除。按端点从左到右扫描，只需在一个对象刚进入时与当前仍未离开的对象配对。

所有区间为左闭右开，起点小于终点。端点坐标相同时先处理结束事件，再处理开始事件；同类事件按对象编号。新对象与活动集合里的每个对象生成一对，然后加入集合。

这一例的完整输入

对象编号从零至九，横向区间依次为[[15, 16], [4, 5], [4, 12], [14, 20], [11, 19], [0, 2], [0, 9], [12, 17], [3, 9], [8, 14]]。

逐项计算记录

坐标 | 事件 | 活动集合变化 | 新候选对 0 | 进入5 | []→[5] | [] 0 | 进入6 | [5]→[5, 6] | [[5, 6]] 2 | 离开5 | [5, 6]→[6] | [] 3 | 进入8 | [6]→[6, 8] | [[6, 8]] 4 | 进入1 | [6, 8]→[1, 6, 8] | [[1, 6], [1, 8]] 4 | 进入2 | [1, 6, 8]→[1, 2, 6, 8] | [[1, 2], [2, 6], [2, 8]] 5 | 离开1 | [1, 2, 6, 8]→[2, 6, 8] | [] 8 | 进入9 | [2, 6, 8]→[2, 6, 8, 9] | [[2, 9], [6, 9], [8, 9]] 9 | 离开6 | [2, 6, 8, 9]→[2, 8, 9] | [] 9 | 离开8 | [2, 8, 9]→[2, 9] | [] 11 | 进入4 | [2, 9]→[2, 4, 9] | [[2, 4], [4, 9]] 12 | 离开2 | [2, 4, 9]→[4, 9] | [] 12 | 进入7 | [4, 9]→[4, 7, 9] | [[4, 7], [7, 9]] 14 | 离开9 | [4, 7, 9]→[4, 7] | [] 14 | 进入3 | [4, 7]→[3, 4, 7] | [[3, 4], [3, 7]] 15 | 进入0 | [3, 4, 7]→[0, 3, 4, 7] | [[0, 3], [0, 4], [0, 7]] 16 | 离开0 | [0, 3, 4, 7]→[3, 4, 7] | [] 17 | 离开7 | [3, 4, 7]→[3, 4] | [] 19 | 离开4 | [3, 4]→[3] | [] 20 | 离开3 | [3]→[] | []

读表时先把输入与计算后的结果分开。空值表示这一步没有适用对象或没有可用结果，不应自动换成零。编号只负责识别本例中的元素，同一个数字出现在不同字段时，要先确认它代表位置、对象还是数值。

怎样复核和使用

每一对只应生成一次，区间仅在端点接触时不算重叠。把扫描结果与逐对检查两个起点中的较大值小于两个终点中的较小值进行对照，可以验证是否漏报或重复。

这里得到的只是横轴投影候选；两个对象还可能在纵向或深度上分开。完整碰撞检测仍要检查其他方向和实际形状，候选数量也不能直接当成真正碰撞次数。

可以先遮住记录表，只按上述规则重算前两步，再选择一个边界条件重新试算。若结果不一致，应逐项检查输入顺序、端点是否包含以及状态在哪一步更新；不要只看最终合计相同就认为中间处理也完全正确。