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

Вы можете реализовать свою первую идею выбора рёбер, середины которых попадают на пересечение с линиями Вороного, используя DelaunayTri класс и его edges< /a> и 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

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

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

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

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

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

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

Другая возможность, более простая, чем создание триангуляций или диаграмм Вороного, — это использование матрицы соседства.

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

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

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

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

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

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

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