feature request: finding maximum convex hull

[dhivehi]

I want find maximum convex hull of a polygon without breaking into another polygon.

[rowanwins]

You always supply good challenges @dhivehi !

Are you aware of any existing open source libraries or software that do this?

Thanks,
Rowan

[dhivehi]

Donno any library which can achieve this feature.

[dpmcmlxxvi]

@dhivehi Here is one approach using only turf functions:

https://jsfiddle.net/dpmcmlxxvi/92gvht0z

Basically, given a target polygon you want hulled (in blue), compute its convex hull then difference out the clipper polygon you want to avoid (in red), then only keep points that were in the original hull or the clipper polygon (in green). The last step removes points artificially introduced by the difference. A few things to keep in mind:

• This approach does not make any guarantees about the optimality of the final hull.
• Only the simple polygon-polygon case is considered here.
• There are edge cases and data issues to keep in mind. For example, the difference function may not always produce points exactly from the original polygons due to numerical precision issues.

[dhivehi]

Good attempt, but i need a function which works for polygons with many sides.

[dpmcmlxxvi]

@dhivehi By "sides", I assume you mean, multi-polygons. The implementation can be easily extended to cover that case.

[dhivehi]

I mean it doesnt work with complex polygons. And not optimal hull is generated in many cases

[dpmcmlxxvi]

You haven't defined optimal. I think this gets you most of the way there and can work with some tweaks. Regardless, good luck finding a solution.