Поиск ближайших соседей

Ответ 1

Вы можете реализовать свою первую идею выбора ребер, средние точки которых попадают на пересечение с линиями Вороного, используя DelaunayTri class и edges и nearestNeighbor, Здесь пример с 10 случайными парами значений x и y:

x = rand(10,1);                     %# Random x data
y = rand(10,1);                     %# Random y data
dt = DelaunayTri(x,y);              %# Compute the Delaunay triangulation
edgeIndex = edges(dt);              %# Triangulation edge indices
midpts = [mean(x(edgeIndex),2) ...  %# Triangulation edge midpoints
          mean(y(edgeIndex),2)];
nearIndex = nearestNeighbor(dt,midpts);  %# Find the vertex nearest the midpoints
keepIndex = (nearIndex == edgeIndex(:,1)) | ...  %# Find the edges where the
            (nearIndex == edgeIndex(:,2));       %#   midpoint is not closer to
                                                 %#   another vertex than it is
                                                 %#   to one of its end vertices
edgeIndex = edgeIndex(keepIndex,:);      %# The "good" edges

И теперь edgeIndex является матрицей N-на-2, где каждая строка содержит индексы в x и y для одного ребра, которое определяет "близкое" соединение. Следующий график иллюстрирует триангуляцию Делане (красные линии), диаграмму Вороного (синие линии), середины краев триангуляции (черные звездочки) и "хорошие" ребра, которые остаются в edgeIndex (толстые красные линии):

triplot(dt,'r');  %# Plot the Delaunay triangulation
hold on;          %# Add to the plot
plot(x(edgeIndex).',y(edgeIndex).','r-','LineWidth',3);  %# Plot the "good" edges
voronoi(dt,'b');  %# Plot the Voronoi diagram
plot(midpts(:,1),midpts(:,2),'k*');  %# Plot the triangulation edge midpoints

Как это работает...

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

Однако, когда есть третья вершина, близкая к линии, соединяющей 2 заданные вершины, ячейка Вороного для третьей вершины может простираться между двумя заданными вершинами, пересекая линию, соединяющую их и охватывающую эту среднюю точку. Следовательно, эта третья вершина может рассматриваться как "ближе" к двум заданным вершинам, чем две вершины друг к другу. На вашем изображении ячейка Вороного для вершины 7 проходит в область между вершинами 1 и 2 (и 1 и 3), поэтому вершина 7 считается ближайшим соседом к вершине 1, чем вершина 2 (или 3).

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

Ответ 2

Я бы согласился с тем, что общие границы ячеек являются критерием хорошего соседа (на основе этого примера). Если вы использовали структуру данных, ориентированную на сетку (например, что-то из Gts), то определение общих ребер было бы тривиальным.

Matlab, с другой стороны, делает это более "интересным". Предполагая, что ячейки voronoi хранятся в виде патчей, вы можете попробовать получить свойство патча "Faces" (см. эта ссылка). Это должно возвращать нечто вроде матрицы смежности, которая идентифицирует связанные вершины. Из этого (и немного магии) вы должны иметь возможность определять общие вершины, а затем выводить общие ребра. По моему опыту, такая "проблема поиска" не подходит для Matlab - если это возможно, я рекомендую переходить к системе, более подходящей для запросов на подключение к сетке.

Ответ 3

Другая возможность, проще, чем создание триангуляций или диаграмм voronoi, использует матрицу окрестности.

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

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

После того, как вы выполнили пространственную сортировку (есть много способов добиться этого, как по последовательным, так и параллельным алгоритмам), вы можете искать ближайшие точки данной точки P, просто посещая соседние ячейки, где точка P фактически хранится в матрица окрестности.

Вы можете прочитать более подробную информацию по этой идее в следующей статье (вы найдете ее в PDF файлах в Интернете): Моделирование сверхмассивного толпы на графическом процессоре на основе Emergent Behavior.

Шаг сортировки дает вам интересные варианты. Вы можете использовать только четный порядок переноса, описанный в документе, который очень прост в реализации (даже в CUDA). Если вы запустите только один проход, это даст вам частичный вид, который может быть уже полезен, если ваша матрица находится в сортировке. То есть, если ваши точки будут двигаться медленно, это сэкономит вам много результатов.

Если вам нужна полная сортировка, вы можете запустить такой четно-нечетный транспозиционный проход несколько раз (как описано на следующей странице Википедии):

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort