How to delete connections to seeds in polygons whose edges open outward of a delaunay triangulation

Hi,

I have created a 2D Voronoi diagram and delaunay triagulation based on a set of pseudo-random number (code attached below). What I would like to do next is to exclude all the connections to seed points that are in boundary polygons, meaning polygons whose edges open outward. The functions freeBoundary() or convexHull() can only include the outer boundary. Is there a way to do that in Matlab? Thank you very much for your help!

Jianan

n = 100;
cre = 0.08;
rng(2);

figure(1)
x = zeros(n,1);
y = zeros(n,1);

i = 1;
while(x(n,1)==0 || y(n,1)==0)
    if (i==1)
        x(i,1) = rand;
        y(i,1) = rand;
        i = i+1;
    else
        x(i,1) = rand;
        y(i,1) = rand;
        for j=1:i-1
            dist = sqrt((x(j,1)-x(i,1))^2+(y(j,1)-y(i,1))^2);
            if dist < cre && i == length(x)
                x(i) = 0;
                y(i) = 0;
                break
            elseif dist < cre
                break
            elseif j == i-1
                i = i+1;
            end            
        end
    end
    
end
m = [x,y];
s = scatter(x,y,10,[1 0 0],'filled');

hold on
%
v = voronoi(x,y,'-k');
%
% Assign labels to the points.
nump = size(x,1);
plabels = arrayfun(@(n) {sprintf('%d', n)}, (1:nump)');
hold on
Hpl = text(x, y, plabels, 'FontWeight', ...
      'bold', 'HorizontalAlignment','center', ...
      'BackgroundColor', 'none');
 %
DT = delaunayTriangulation(x,y);
hold on
triplot(DT,'--b');

freebnd = freeBoundary(DT);
plot(x(freebnd),y(freebnd),'-r','LineWidth',2)
%
hold on
k = convexHull(DT);
xHull = DT.Points(k,1);
yHull = DT.Points(k,2);
plot(xHull,yHull,'r','LineWidth',2);
hold off

figure(2)
plot(xHull,yHull,'r','LineWidth',2); 
axis equal
xlabel('Longitude'),ylabel('Latitude')
grid on

% The convex hull topology duplicates the start and end vertex.
% Remove the duplicate entry.
k(end) = [];
% Now remove the points on the convex hull.
DT.Points(k,:) = []
% Plot the new triangulation.
hold on
triplot(DT); 
 
hold off

Answer 1

[Naga]

Hello Jianan,

To exclude connections to seed points in boundary polygons of a Voronoi diagram, you need to identify the Voronoi regions that are unbounded and then remove connections to the seeds of those regions in the Delaunay triangulation. Follow below steps to achieve the same:

1. Use the 'voronoiDiagram' function to get the Voronoi vertices and the corresponding regions. Unbounded regions will have vertices at infinity.
2. Once you have identified which regions are unbounded, you can remove the corresponding points from the Delaunay triangulation.

Here is a modified version of your code to achieve this:

n = 100;
cre = 0.08;
rng(2);

x = zeros(n,1);
y = zeros(n,1);

i = 1;
while(x(n,1)==0 || y(n,1)==0)
    if (i==1)
        x(i,1) = rand;
        y(i,1) = rand;
        i = i+1;
    else
        x(i,1) = rand;
        y(i,1) = rand;
        for j=1:i-1
            dist = sqrt((x(j,1)-x(i,1))^2+(y(j,1)-y(i,1))^2);
            if dist < cre && i == length(x)
                x(i) = 0;
                y(i) = 0;
                break
            elseif dist < cre
                break
            elseif j == i-1
                i = i+1;
            end            
        end
    end
end

% Create Delaunay Triangulation
DT = delaunayTriangulation(x, y);

% Get Voronoi diagram
[V, R] = voronoiDiagram(DT);

% Identify unbounded Voronoi regions
unbounded = cellfun(@(r) any(r == 1), R);

% Remove points with unbounded Voronoi regions
boundedPoints = DT.Points(~unbounded, :);

% Create new Delaunay triangulation with bounded points
DT_bounded = delaunayTriangulation(boundedPoints);

% Plot results
figure;
triplot(DT_bounded, 'b');
hold on;
scatter(boundedPoints(:,1), boundedPoints(:,2), 10, [1 0 0], 'filled');
title('Delaunay Triangulation Excluding Boundary Points');
xlabel('X');ylabel('Y');axis equal;grid on;

This approach efficiently removes connections to points in unbounded Voronoi regions and updates the Delaunay triangulation accordingly.