用于更新动态场景的Voronoi图的方法及设备

摘要

本发明提供了用于更新动态场景的Voronoi图的方法。该方法根据场景变化，确定要执行的基本更新操作序列；然后，对于基本更新操作序列中的每个操作，确定该操作的局部更新范围并对Voronoi图进行更新。每次操作的局部更新范围仅包括该操作能够影响到的Voronoi区域，所以，更新会被限定在一个很小的范围内。针对场景的变化进行局部更新，插入和删除一个基点的效率很高，能够达到毫秒级，其他变化都可以用一次删除紧接一次重新插入实现，速度也会非常快，能够满足实时交互的速度要求。

主权项

一种用于更新动态场景的Voronoi图的方法，所述方法包括：步骤1）根据场景变化，确定要执行的基本更新操作序列；所述基本更新操作包括：插入操作和删除操作；步骤2）对于基本更新操作序列中的每个操作，确定该操作的局部更新范围，所述局部更新范围指所有受到该操作影响的Voronoi区域的集合；步骤3）计算该局部范围的Voronoi图，并将经计算得到的该局部范围内的Voronoi图拼接回原Voronoi图，以覆盖该局部范围内原有的Voronoi图。