Projected convex hull in plane
I solved the problem with the following algorithm


Create N horizontal planes of appropriate size
For each plane


Apply the boolean modifier (intersect the plane with the target object)
Extrude the plane in the z direction, giving it some height
Apply the convex hull operator
Remove the extra plane created in step 2
Remove any vertices inside triangles

Merge planes into one object
Bridge the edge loops
Remove interior faces (they were left from the convex hull operator)


Here is the Python script with room for some improvements: https://gist.github.com/milasudril/960f5c2c4c3735f3fdea566cfdc003d9