Оценка границы произвольно распределенных данных

Question

У меня есть двумерные дискретные пространственные данные. Я хотел бы сделать аппроксимацию пространственных границ этих данных, чтобы я мог создать график с другим набором данных поверх него.

В идеале это был бы упорядоченный набор точек (x, y), которые matplotlib может построить с помощью патча plt.Polygon ().

Моя первоначальная попытка очень не элегантна: я помещаю точную сетку над данными, и там, где данные находятся в ячейке, для этой ячейки создается квадратное пятно matplotlib. Таким образом, разрешение границы зависит от частоты дискретизации сетки. Вот пример, где серая область - это ячейки, содержащие данные, черная, где данных не существует.

1-я попытка http://astro.dur.ac.uk/~dmurphy/data_limits.png

ОК, проблема решена - почему я все еще здесь? Ну ... я бы хотел более "элегантное" решение или, по крайней мере, более быстрое (т.е. я не хочу продолжать "настоящую" работу, я хотел бы повеселиться с этим !). Лучший способ, которым я могу придумать, - это метод трассировки лучей, например:

1. от xmin до xmax, при y = ymin проверьте, пересекается ли граница данных в интервалах dx
2. y = ymin + dy, do 1
3. до 1-2, но теперь сэмпл у y

Альтернативой является определение центра и выборка в r-тета-пространстве - то есть радиальные спицы с приращениями dtheta.

И то, и другое даст набор (x, y) точек, но тогда как мне упорядочить / связать соседние точки с ними, чтобы создать границу?

Подход к ближайшему соседу не подходит, так как, например (позаимствовать у географии), перешеек (вспомним Панаму, соединяющий Н и Ю Америка) может затем закрыть и изолировать регионы. Это также может не очень хорошо работать с дырами, видимыми в данных, которые я хотел бы представить в виде другого plt.Polygon.

Возможно, решение заключается в решении проблемы максимизации площади. Для набора точек, определяющих пределы данных, какова максимальная смежная область, содержащаяся в этих точках? Каковы соседние точки для n-й точки? Как будут обрабатываться отверстия в этой схеме - это ошибка в топологии сейчас?

Извиняюсь, многое из этого я думаю вслух. Буду признателен за некоторые советы, предложения или решения. Я подозреваю, что это часто изучаемая проблема со многими методами решения, но я ищу что-то простое для программирования и быстрого запуска ... Я думаю, все действительно,

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

Хорошо, вот попытка №2 с использованием идеи Марка о выпуклых оболочках: альтернативный текст http://astro.dur.ac.uk/~dmurphy/data_limitsv2.png

Для этого я использовал qconvex из пакета qhull, чтобы он возвращал крайние вершины. Для заинтересованных:

кошка [данные] | qconvex Fx> out

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

Answer 1

Я думаю, что вы ищете Выпуклая оболочка данных Это даст набор точек, которые при подключении будут означать, что все ваши точки находятся на или внутри соединенных точек

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])