c++ - 从二维坐标列表（向量）中提取上下边界

Question

我的程序包含具有包含点的向量形式的多边形（二维双坐标，存储在自制结构中）。我正在寻找一种快速找到包含我的多边形的最小正方形的方法（即知道所有点的最大和最小坐标）。

有没有比解析所有点并存储最小值和最大值更快的方法？

Answer 1

您描述的算法很简单：遍历所有点并找到每个坐标的最小值和最大值。这是一个 O(n) 算法，n 是您拥有的点数。

您不能做得更好，因为您至少需要检查一次所有点，否则最后一个可能在您找到的方格之外。

现在，复杂度最多为 O(n)，因此您只需最小化常数因子，但在这种情况下，它已经很小了：只有一个循环遍历您的向量，寻找两个最大值和两个最小值。

Answer 2

您可以遍历所有点并找到最大值和最小值，或者进行一些预处理，例如，将您的点存储在 treap ( http://en.wikipedia.org/wiki/Treap ) 中。没有任何预处理比迭代所有点更好。

Answer 3

我不确定是否有比线性时间更快的方法来找到值数组中的最小值和最大值。我能想到的唯一“优化”是在您迭代数组的其他一种情况下找到这些值（填充它/对所有点执行函数），然后对任何数据更新执行检查。