How to extract the boundaries of Shapely MultiPoint? [closed]

Question

I have a shapely MultiPoint object but need to extract the boundaries into a Polygon object.

I'm currently using the convex_hull of the MultiPoint object but my MultiPoint sets can have sharp inward angles (e.g. L X or U shaped) this solution is not ideal.

I'm looking for a function which would convert this MultiPoint:

 . . . . . . .
 . . . . . . .
 . . .   . . .
 . . .     . . 

into a polygon with these coordinates:

 .           .
     . .      
              
 .   .     . . 

The point data is fixed on grid with 0.25 meter between each point.

My naive approach would be to loop over all points and checking whether the point is fully enclosed by neighbors in all directions. If no, the point must be on an edge. Once I have the edges I could simplify those lines further by removing points in between start and end.

Is there a solution available in Python to do this, preferably in Shapely?

Answer 1

For a grid-like multipoint, you can use buffer method to get the boundary of points as a polygon. For a multipoint geometry with 100 meters between each point as in the image, the following script returns the boundary.

import shapely
from shapely.geometry import CAP_STYLE, JOIN_STYLE

# sample geometry
wkt = 'MultiPoint ((284536 4149243),(284536 4149143),(284536 4149043),(284536 4148943),(284536 4148843),(284536 4148743),(284636 4149243),(284636 4149143),(284636 4149043),(284636 4148943),(284636 4148843),(284636 4148743),(284736 4149243),(284736 4149143),(284736 4149043),(284836 4149243),(284836 4149143),(284836 4149043),(284836 4148943),(284836 4148843),(284936 4149243),(284936 4149143),(284936 4149043),(284936 4148943),(284936 4148843),(285036 4149243),(285036 4149143),(285036 4149043),(285036 4148943),(285036 4148843),(285136 4149243),(285136 4149143),(285136 4149043),(285136 4148943),(285136 4148843),(285236 4149243),(285236 4149143),(285236 4149043),(285236 4148943),(285236 4148843),(285236 4148743),(285336 4149243),(285336 4149143),(285336 4149043),(285336 4148943),(285336 4148843),(285336 4148743))'
multi_point = shapely.wkt.loads(wkt)

interval = 100    
kwargs = {"cap_style": CAP_STYLE.square, "join_style": JOIN_STYLE.mitre}
boundary = multi_point.buffer(interval/2, **kwargs).buffer(-interval/2, **kwargs)

Vertices of boundary: