从随机坐标列表中找出外边界

Question

我有一个很大的坐标列表（超过60,000个），但我还没找到识别外边界的方法。

这些坐标看起来很随机，但它们实际上定义了一个非常特定的区域。

我应该能够通过这个列表在OpenLayers中绘制出一个区域，所以这些坐标也应该是有顺序的。

这看起来是个相对简单的问题，但实际上却很有挑战性。

对于这个问题，最好的解决办法是什么呢？

• Heikki

Answer 1

凸包是我一直在寻找的主题。我在这个网站上找到了一个非常不错的脚本，地址是 http://code.activestate.com/recipes/66527-finding-the-convex-hull-of-a-set-of-2d-points/。

非常感谢所有参与者！

Answer 2

如果你只想要一个边界框，那其实很简单：

min_x = MAX_INT;
min_y = MAX_INT;
max_x = MIN_INT;
max_y = MIN_INT;

for p in points:
  if p.x < min_x then min_x = p.x;
  if p.y < min_y then min_y = p.y;
  if p.x > max_x then max_x = p.x;
  if p.y > max_y then max_y = p.x;

如果你的平台上没有简单的 MAX_INT 和 MIN_INT 的替代品，那就随便选个列表里的第一个。这样写的代码可能看起来不那么“好看”，但在速度上可能会快一点，虽然这个速度提升几乎可以忽略不计。

当然，如果你的数据有某种重要的排序方式，你可能可以用更聪明的方法来处理，而不是简单地遍历 60,000 个项目并进行 240,000 次比较。（不过要记住，为了这个目的而对 60,000 个点进行排序，可能并不划算。）

Answer 3

你是在找一个凸包吗？