Optimizer while not allowing "holes"?

[mr483]

I have a script in which outlines need to be derived for a variety of different coordinate sets, many of which are concave, which is why I switched from a simple convex hull to alpha shapes. However, I need the script to automatically determine the appropriate alpha number, hence I used the optimize method. With this method, I'm often finding lots of holes in the shapes, which won't work for more purpose. Is there any way to configure the optimizer to avoid these holes?

[panosz]

Thank you for bringing this to my attention.

Currently, the optimize method in the alpha_shapes library is designed to find the maximum alpha value where no vertices from the triangulation are left uncovered. This might sometimes result in holes, especially for concave shapes.

As of now, the library doesn't have a built-in feature to avoid holes during optimization. However, I recognize the value of such a feature, and I'll consider it for a future enhancement.

For a temporary solution, if your data sets have similar characteristics, you might try the following approach:

1. Use the optimize method on one of your datasets to get an initial alpha value.
2. Begin by decrementing this alpha value in small steps.
3. For each decreased alpha, generate the alpha shape and check if it meets your requirements without holes.

This approach is not perfect, but it might help you get closer to your desired result until we can introduce a more refined solution in the library.

[mr483]

Many thanks for the reply! Since I need everything to be automated (cannot visually check and update alpha for every calculation), I first run optimize and then reduce alpha until (1) the MultiPolygon output is reduced to a single Polygon, and (2) the resulting Polygon has len(alpha_shape.interiors) = 0.

                    alpha_opt, alpha_shape = shaper.optimize()

                    # Check if we have a single continuous polygon
                    while (alpha_shape.type == 'MultiPolygon'):
                        alpha_shape= shaper.get_shape(alpha=alpha_opt-1)
                        alpha_opt = alpha_opt-1

                    # next, check the alpha shape has no interiors
                    while len(alpha_shape.interiors)>0:
                        alpha_shape= shaper.get_shape(alpha=alpha_opt-0.2)
                        alpha_opt = alpha_opt-0.2

While naturally a bit slow, this achieves what I need. Thanks for the input!

[panosz]

Thank you for sharing your approach! It's a pragmatic way to handle the problem, especially when automation is important.

Your approach seems quite efficient given the constraints, but if you want to bypass the interior check and simply want a continuous outer boundary without any holes, you might consider using Shapely's Polygon directly from the exterior coordinates of the alpha shape:

# Check if we have a single continuous polygon
while (alpha_shape.type == 'MultiPolygon'):
    alpha_shape= shaper.get_shape(alpha=alpha_opt-1)
    alpha_opt = alpha_opt-1

from shapely import Polygon
patched_shape = Polygon(alpha_shape.exterior)

This method essentially patches up the holes by only considering the outer boundary. While it's a simpler solution, it might not be suitable for every use case. For example, if you want to use the shaper as a triangulation, it will still have holes in it.

[mr483]

Great tip, thanks @panosz!