Вы можете реализовать свою первую идею выбора ребер, средние точки которых находятся на пересечении с линиями Вороного, используя DelaunayTri класс и его 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
Как это работает ...
Диаграмма Вороного состоит из серии полигонов Вороного, или ячеек.На изображении выше каждая ячейка представляет область вокруг данной вершины триангуляции, которая охватывает все точки пространства, которые находятся ближе к этой вершине, чем любая другая вершина.В результате этого, когда у вас есть 2 вершины, которые не близки к другим вершинам (например, вершины 6 и 8 на вашем изображении), тогда средняя точка линии, соединяющей эти вершины, попадает на разделительную линию между ячейками Вороного длявершины.
Однако, когда есть третья вершина, которая находится близко к линии, соединяющей две заданные вершины, ячейка Вороного для третьей вершины может простираться между двумя заданными вершинами, пересекая линию, соединяющую их и заключающуюлинии середины.Поэтому эту третью вершину можно считать «ближе» к двум заданным вершинам, чем к двум вершинам друг к другу.На вашем изображении ячейка Вороного для вершины 7 простирается в область между вершинами 1 и 2 (и 1 и 3), поэтому вершина 7 считается ближе к вершине 1, чем вершина 2 (или 3).
В некоторых случаях этот алгоритм может не рассматривать две вершины как «близких» соседей, даже если их ячейки Вороного касаются.Вершины 3 и 5 на вашем изображении являются примером этого, где вершина 2 считается ближе к вершинам 3 или 5, чем вершины 3 или 5 друг к другу.