Нахождение внешних границ из списка случайных координат - PullRequest
Новая
       44

Нахождение внешних границ из списка случайных координат

4 голосов
/ 13 января 2011

У меня огромный список (более 60 000) координат, и я не нашел способа распознать внешние границы.

Список координат довольно случайный, но он определяет некоторыедействительно конкретная область.

Я должен быть в состоянии нарисовать область, используя этот список, используя OpenLayers, так что они также должны быть в порядке.оказались довольно сложными.

Каков наилучший подход к этой проблеме?

  • Хейкки

Ответы [ 3 ]

4 голосов
/ 13 января 2011
1 голос
/ 13 января 2011

Выпуклая оболочка - это предмет, который я искал.Я нашел действительно хороший сценарий от http://code.activestate.com/recipes/66527-finding-the-convex-hull-of-a-set-of-2d-points/.

Большое спасибо всем участникам!

1 голос
/ 13 января 2011

Если вам нужен просто ограничивающий прямоугольник, это достаточно просто: 

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 тыс. Предметов и выполнение 240 тыс. Сравнений.(Имейте в виду, что заказ 60 тыс. Баллов каким-то существенным образом только для этого может не окупиться.)

...