Finding the Inner Convex Hull of a set of points (2D)

1
votes

Mostly of us are familiar with the convex hull problem,

I'm trying to solve a similar/related problem: the inner (circunscribed) convex hull, which basicaaly means finding the largest polygon to be fit inside a set of points.

In Example of the problem you can see an what I want. Given a set of points (blue dots) I want to find the largest convex polygon that can be fit inside the 'hole' in this clound of points that also contains my given arbitrary point (red dot). The result should be something similar to this.

I managed to solve this by applying a transformation in my original dataset to transform it inside-out, applying the convex-hull algorithm, and applying the counter-transformation to the result to retrieve the inner convex hull. This work as long as my hole well-behaved (i.e. convex and minor eccentricity). If I aaply it to a non-convex hole, it gives me very weird results.

What I am looking for is any literature that can help me with this problem.

1
computational-geometryconvex
I’m voting to close this question because it's not about programming – Software Engineer
I beg you pardon, how is it not about programming? This convex hull problem is a classic programming problem, and this is nothing but a variation of the problem. – Antonio Ribeiro
Where is the code you're having a problem with? What have you tried? Can you give us a minimum verifiable complete example? Also, you're not meant to be asking for external lit/refs/tools except as proof of a solution – Software Engineer
@Antonio Ribeiro - How do you define being inside a set of points? – Armali
The big blue square is a sure sign of a BUG in your code. – Yves Daoust

1 Answers

0
votes

It is easy to show that the inversion method is wrong. The triangle defined by extending two sides is not void, hence you could enlarge the convex polygon.

enter image description here

Maybe here: Finding largest subset of points forming a convex polygon.