跟踪一组点中最大距离的最佳方法？

Question

假设我有一个2维点的集合,以及确定它们之间距离的方法.经常修改此集合,添加其他点并删除现有点.在任何给定的时间,我需要知道点之间的最大和最小距离,即最远的两个点之间的距离,以及最靠近在一起的两个点之间的距离.有没有一种数据结构或算法能够很好地完成这项任务？我希望每次点数改变时都不必重新计算整个距离.

Answer 1

从理论上讲,你可以通过存储你所拥有的点的凸包来有效地做到这一点.

无论何时添加新点,都要测试它是否位于此多面体的内部.如果是,则保留最大距离.如果没有,那么它可能已经改变了.

同样,如果从内部删除一个点,则保留最大距离(直径),因此不进行任何更改.但是,如果删除边界点,则必须重新计算凸包.

如果您处于2维,那么当您从边界添加或删除时,多边形的最多两侧都会受到影响.这些应该易于计算,具体取决于您存储信息的方式(例如,一系列线段).

编码这可能有点痛苦,但最简单的方法是在边界上标记点,然后有一个函数来测试点是否位于标记点的凸包内.

Answer 2

而不是使用凸壳(如另一个答案所示)你可以使用Delaunay三角剖分吗？

最小距离:

要计算从节点到集合中任何其他节点的最小距离,您应该只需要检查节点的直接邻居,即通过三角测量中的边缘连接到节点的邻居.

因此,如果插入了新节点,请更新三角测量,找到新节点的邻居以及更新中"涉及"的任何其他节点,计算此本地"更新"集中所有节点的距离并检查是否为新节点发现最低限度.同样,如果删除现有节点,则再次更新三角测量并重新计算"涉及"的所有节点的距离.

有一类所谓的"增量"算法可用于构建Delaunay三角网,只需要在插入/删除新节点时对整体三角测量进行局部修改,因此这是我建议频繁插入的方法类型/缺失.

最大距离:

如凸壳样式答案中所建议的,如果在现有三角剖分之外添加了新节点或者删除了现有边界节点,则只需要重新计算边界节点之间的距离.

希望这可以帮助.