Clear Filters
Clear Filters

Delete point from Voronoi diagram efficiently

17 views (last 30 days)
Annika Schmidt
Annika Schmidt on 17 Feb 2020
Answered: Ronit on 23 Sep 2024 at 7:00
I have a point set and create a Delaunay triangulation and a Voronoi diagram. Then I would like to delete a point and calculate the Delaunay triangulation and Voronoi diagram again. It is easy to delete the point from the Delaunay trianglation: If I have a triangulation DT (DT = delaunayTriangulation(x,y)), I can delete a point using DT.Points(index,:) = [];. The question is how can I then create the new Voronoi diagram efficiently? I know that only the cells adjacent to the deleted point will change, so I would like to avoid computing the whole Voronoi diagram again.

Answers (1)

Ronit
Ronit on 23 Sep 2024 at 7:00
Hello Annika,
When you delete a point from a Delaunay triangulation, only the cells adjacent to the deleted point are affected in the Voronoi diagram. To efficiently update the Voronoi diagram without recomputing it entirely, you can recompute the triangulation for the affected region and recompute only the affected Voronoi cells based on the updated Delaunay triangulation. The new Voronoi edges will be formed by the perpendicular bisectors of the updated Delaunay edges.
% Identify affected points (neighbors of the point to be deleted)
affectedPoints = DT.vertexAttachments(index);
% Delete the point
DT.Points(index, :) = [];
% Update the Delaunay triangulation
% Recompute the triangulation for the affected region
% This step may require custom logic to identify and retriangulate the cavity
% Update the Voronoi diagram
% Recompute the Voronoi diagram only for the affected region
[vx, vy] = voronoi(DT.Points(:,1), DT.Points(:,2));
This approach minimizes the computational overhead by focusing on local changes, making it more efficient than recalculating the entire Voronoi diagram.
Please refer to the documentation of "vertexAttachments" for more details:
I hope it helps with your query!

Categories

Find more on Voronoi Diagram in Help Center and File Exchange

Products


Release

R2018b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!