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

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

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

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

Казалось, что это был относительно легкий орешек, но он оказался довольно сложным.

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

  • Хейкки

Вы ищете выпуклый корпус ?

Если вы просто хотите ограничительную рамку, это достаточно просто:

min_x = MAX_INT; min_y = MAX_INT; max_x = MIN_INT; max_y = MIN_INT; for p in points: if px < min_x then min_x = px; if py < min_y then min_y = py; if px > max_x then max_x = px; if py > max_y then max_y = px; 

Если на вашей платформе нет простого эквивалента MAX_INT и MIN_INT, просто выберите первый в списке. Это, возможно, менее «красивый» код, но он также, возможно, быстрее бессмысленной суммой.

Конечно, если ваши данные были заказаны каким-то значительным образом, вы могли бы сделать что-то более умное, чем повторение более 60 тыс. Элементов и выполнение сравнений в 240 тыс. (Имея в виду, что упорядочение 60 тыс. Точек некоторым существенным образом только для этого может не платить за себя.)

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

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