# Turn disjoint polygons into tessellation

I have a set of points that have labels. These labels represent geographies; however, some of the labels are wrong. Like in the picture below

So after running some analysis, I end up with a set of disjoint polygons

I would love to be able to turn it into a tessellation similar to this

Obviously I do not need the geometries to line up exactly as above, just an approx, but I was wondering if anyone knew of an algorithm that maybe made a triangulation on the centroids of polygons to get nearest neighbor table and then used a curve smoothing alg coupled with polygon buffering (like STBuffer method on sql spatial types) to change first pic to something like the second pic

so basically I want to turn disjoint polygons into a covering of a space but can't seem to find any algorithms for it

• Delaunay en.wikipedia.org/wiki/Delaunay_triangulation or Thiessen/Voronoi wiki.gis.com/wiki/index.php/Thiessen_Polygon / en.wikipedia.org/wiki/Voronoi_diagram will cover the blank area to varying degrees; both mathematicians came up with the same idea independently so they are both credited with the method of filling space between points. What software or API do you have to work with? Commented Feb 21, 2020 at 4:18
• @MichaelStimson I am using sql spatial types at the moment and some code i have written to generate both delaunay tessellations and voronoi diagrams, so that is good to hear that they could potentially aid in my solution. i use both for outlier detection to go from the first pic to the second. i was thinking i could go from the second to something comparable to the third using voronoi diag on the centroids of the alpha shapes i generate after outlier detection Commented Feb 21, 2020 at 5:19
• You just need to decide where to decimate: a triangle that has one side greater than an arbitrary length or polygon with a perimeter greater than an arbitrary length can be removed. Delaunay will give you jagged edges and the problem exists what value does the triangle have if it is formed by points with different values.. for these reasons I would suggest Voronoi as more suitable. Another option is to rasterize the points and use raster fill then clip the raster by the concave hull of your initial polygons and convert to polygons, this will give the best results but will require more effort. Commented Feb 21, 2020 at 6:00