如何有效地找到点集合的边界框? [英] How to efficiently find the bounding box of a collection of points?

问题描述

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

I have several points stored in an array. I need to find bounds of that points ie. the rectangle which bounds all the points. I know how to solve this in plain Python.

我想知道有没有比数组上的朴素最大值、最小值或内置方法更好的方法来解决问题.

I would like to know is there a better way than the naive max, min over the array or built-in method to solve the problem.

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]]

推荐答案

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

My approach to getting performance is to push things down to C level whenever possible:

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

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

根据我的(粗略)测量，它的运行速度比 @ReblochonMasque 的 bounding_box_naive() 快约 1.5 倍.而且明显更优雅.;-)

By my (crude) measure, this runs about 1.5 times faster than @ReblochonMasque's bounding_box_naive(). And is clearly more elegant. ;-)

这篇关于如何有效地找到点集合的边界框?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！