任意分布d的边界估计

Question

我有二维离散空间数据。我想对这个数据的空间边界做一个近似，这样我就可以在它上面生成另一个数据集的绘图。在

理想情况下，这是一组有序的（x，y）点，matplotlib可以用它来绘制多边形（）修补程序。在

我最初的尝试是非常不雅观的：我在数据上放置了一个精细的网格，在一个单元格中找到数据的地方，就会创建一个正方形的matplotlib补丁。因此，边界的分辨率取决于网格的采样频率。下面是一个例子，灰色区域是包含数据的单元格，黑色区域是没有数据的单元格。在

1st attempt http://astro.dur.ac.uk/~dmurphy/data_limits.png

好吧，问题解决了-为什么我还在这里？好。。。。我想要一个更“优雅”的解决方案，或者至少是一个更快的解决方案（即，我不想继续“真正的”工作，我想从中得到一些乐趣！）。我能想到的最好方法是光线跟踪方法-例如：

1. 从xmin到xmax，在y=ymin时，检查数据边界是否以dx为间隔跨越
2. y=ymin+dy，执行1
3. 做1-2，但现在在y中取样

另一种选择是定义一个中心，并在r-theta空间采样-即以dtheta增量的径向辐条。在

两者都会产生一组（x，y）点，但我如何排序/链接相邻点以创建边界？在

最近邻的方法是不合适的，例如（借用地理位置），地峡（想想连接北美和南美洲的巴拿马）可能会封闭和孤立地区。这也可能不能很好地处理数据中的漏洞，我想用另一种方法来表示多边形. 在

解决方案可能来自于解决面积最大化问题。对于一组定义数据界限的点，在这些点内形成封闭区域的最大连续面积是多少，第n个点的相邻点是什么？在这个方案中，如何处理这些洞-这是否会导致拓扑错误？在

抱歉，这大部分都是我在大声思考。如果能给我一些提示、建议或解决办法，我将不胜感激。我怀疑这是一个经常研究的问题，有许多解决方案技术，但我正在寻找一些简单的代码和快速运行。。。我想每个人都是，真的！在

~~~~~~~~~~~~~~~~~~~~~~~~~~~

好吧，下面是利用马克的凸壳概念的尝试2： alt text http://astro.dur.ac.uk/~dmurphy/data_limitsv2.png

为此，我使用了qhull包中的qconvex，让它返回极端顶点。对于感兴趣的人：

类别[数据]| qconvex Fx>；输出

周长的采样似乎很低，虽然我没有玩太多的设置，我不相信我可以提高保真度。在

Answer 1

我想你要找的是the Convex Hull of the data它将给出一组点，如果连接，则意味着所有点都在连接点上或内部

Answer 2

我可能混合了一些东西，但是没有确定x和y的最大和最小水平的动机是什么？除非你有大量的数据，否则你可以很快地遍历你的点来确定最小值和最大值。在

这不是最有效的例子，但是如果您的数据集很小，这不会特别慢：

import random
data = [(random.randint(-100, 100), random.randint(-100, 100)) for i in range(1000)]

x_min = min([point[0] for point in data])
x_max = max([point[0] for point in data])

y_min = min([point[1] for point in data])
y_max = max([point[1] for point in data])