Enclose multiple separate sets of points using polygons which stack next to each other

Question

I am working on a data set of coordinate points(many dots in area) either (x,y) or (lat,lon) which fall into multiple categories. What I am trying to do is get polygons of areas from those points which are called concave or non-convex as far as I know, but also those polygons have to be next to each other with no gaps between them.

These are the initial points(example)

This is the approximate result I am aiming for

Real life example would be European geopolitical map, if you had all of the addresses of all countries and wanted to get area of each country as a polygon and end up with a map.

I have come across many questions related to getting polygons from set of points, but were unable to use it in my scenario. If you need any more information please let me know. Thank you for your help.

Answer 1

You could use a Voronoi tesselation of the input space. Instead of having point you have sets of points though. Basically, you take each point in space, and look at the closest point to it. It then gets the same "class" as that point. For smoother outputs you could look at a k majority out of N nearest points. It would mean working with a bitmap image rather than 2D coordinates, but you'd get something workable. You could then use simpler image manipulation tricks (edge detection, binary set operations etc to get just the edges, and then perhaps superimpose those on the image).

As an alternative, you could run a convex hull algorithm on each data set, and then try to fix the overlap areas.