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

Question

我有一个庞大的坐标列表（60000多个），但我还没有找到识别外部边界的方法。在

坐标列表是非常随机的，但它们定义了一些真正特定的区域。在

我应该能够通过使用OpenLayers使用该列表绘制一个区域，因此它们也应该按顺序排列。在

这似乎是一个相对容易打破的坚果，但已证明是相当具有挑战性。在

解决这个问题的最佳方法是什么？在

• 海基

Answer 1

凸壳是我一直在寻找的主题。我从http://code.activestate.com/recipes/66527-finding-the-convex-hull-of-a-set-of-2d-points/找到了一个非常好的脚本。在

多谢各位嘉宾！在

Answer 2

你在找convex hull？在

Answer 3

如果只需要边界框，这很简单：

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等价物，只需从列表中选择第一个。它可能不是那么“漂亮”的代码，但它也可能以一个无意义的数量更快。在

当然，如果您的数据是以某种有意义的方式排序的，那么您可能可以做一些比迭代超过60k个项目并执行240k个比较更聪明的事情。（请记住，仅仅为了这一点而以某种重要的方式订购6万个积分可能不会为自己带来回报。）