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

Question

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

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

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

1st attempt http://astro.dur.ac.uk/~dmurphy/data_limits.png

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

1. от Xmin до Xmax, при у = Ymin, проверьте граничная данные пересеклись в интервалах дх
2. у = Ymin + ау, сделайте 1
3. сделать 1-2, но теперь в образец у

альтернативой является определение центра, и отбор проб в г-тета пространства - т.е. радиальные спицы в dtheta шагом.

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

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

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

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

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

ОК, вот попытка # 2, используя идею Марка выпуклых оболочек: alt text http://astro.dur.ac.uk/~dmurphy/data_limitsv2.png

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

cat [data] | qconvex Fx> out

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

Answer 1

Я думаю, что вы ищете the Convex Hull of the data Это даст множество точек, что при подключении будет означать, что все точки находятся на или внутри соединенных точек

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