如何有效地找到一组点的边界框？

Question

我有几个点存储在一个数组中.我需要找到那些点的界限,即.限定所有点的矩形.我知道如何用普通的Python解决这个问题.

我想知道有没有比天真的最大,最小的数组或内置方法更好的方法来解决问题.

points = [[1, 3], [2, 4], [4, 1], [3, 3], [1, 6]]
b = bounds(points) # the function I am looking for
# now b = [[1, 1], [4, 6]]

Answer 1

我获得性能的方法是尽可能将事情降低到C级:

def bounding_box(points):
    x_coordinates, y_coordinates = zip(*points)

    return [(min(x_coordinates), min(y_coordinates)), (max(x_coordinates), max(y_coordinates))]

通过我的(粗略)测量,它比@ ReblochonMasque的速度快约1.5倍bounding_box_naive().而且显然更优雅.;-)

Answer 2

你无法做得更好O(n)，因为你必须遍历所有点才能确定max和min的x和y。

\n\n

但是，你可以减少常数因子，只遍历列表一次；但是，尚不清楚这是否会给您带来更好的执行时间，如果确实如此，则适用于大量点的集合。

\n\n

\n

[编辑]：事实上并非如此，“天真的”方法是最有效的。

\n

\n\n

这是“天真的”方法：（这是两种方法中最快的）

\n\n

def bounding_box_naive(points):\n    """returns a list containing the bottom left and the top right \n    points in the sequence\n    Here, we use min and max four times over the collection of points\n    """\n    bot_left_x = min(point[0] for point in points)\n    bot_left_y = min(point[1] for point in points)\n    top_right_x = max(point[0] for point in points)\n    top_right_y = max(point[1] for point in points)\n\n    return [(bot_left_x, bot_left_y), (top_right_x, top_right_y)]\n

\n\n

和（也许？）不那么天真：

\n\n

def bounding_box(points):\n    """returns a list containing the bottom left and the top right \n    points in the sequence\n    Here, we traverse the collection of points only once, \n    to find the min and max for x and y\n    """\n    bot_left_x, bot_left_y = float(\'inf\'), float(\'inf\')\n    top_right_x, top_right_y = float(\'-inf\'), float(\'-inf\')\n    for x, y in points:\n        bot_left_x = min(bot_left_x, x)\n        bot_left_y = min(bot_left_y, y)\n        top_right_x = max(top_right_x, x)\n        top_right_y = max(top_right_y, y)\n\n    return [(bot_left_x, bot_left_y), (top_right_x, top_right_y)]\n

\n\n

分析结果：

\n\n

import random\npoints = [(random.randrange(-1000, 1000), random.randrange(-1000, 1000))  for _ in range(1000000)]\n\n%timeit bounding_box_naive(points)\n%timeit bounding_box(points)\n

\n\n

大小 = 1,000 点

\n\n

1000 loops, best of 3: 573 \xc2\xb5s per loop\n1000 loops, best of 3: 1.46 ms per loop\n

\n\n

大小 = 10,000 点

\n\n

100 loops, best of 3: 5.7 ms per loop\n100 loops, best of 3: 14.7 ms per loop\n

\n\n

大小 100,000 点

\n\n

10 loops, best of 3: 66.8 ms per loop\n10 loops, best of 3: 141 ms per loop\n

\n\n

大小 1,000,000 点

\n\n

1 loop, best of 3: 664 ms per loop\n1 loop, best of 3: 1.47 s per loop\n

\n\n

显然，第一种“不那么幼稚”的方法速度要快一个因素2.5 - 3

\n