A set of 2D Points are scattered randomly (i.e., no specified pattern), we are interested in finding all inner-convex-hulls (ICH) in an order of largest in area to a minimum until the entire study area to be covered by set of ICHs, if possible.
As shown in the following figure, it appears that the green convex-hull is the largest possible inner one. We mean inner implying that no point can be inside in the desired convex-hull. The boundary condition for the region can be a normal (i.e., conventionally recognised) convex-hull for all points. In Figure for the first largest in area inner-convex-hull #1 is selected first. The area covered by #1 is then excluded to avoid overlapping problem of the next generations. It seems a bit confusing and hard, hope Figure helps. We guess may be the concept of largest enclosed ellipse could help. It is however a starting guess.
Well the result of our implementation of the idea given below by
Uffe Kousgaard is here:
Numbers are ranks i.e., smaller number, larger area. It shows working, however, we noticed several cases the result is not correct. It may be due to bugs in our implementation or the method as noted by
whuber below as comment.
Here is result of the method mentioned by
Uffe applied on
Apparently something does NOT work well!
The correct complete solution is as follows (for
whuber's example data):
There are three stages, therefore, to complete the solution. We apply the method fully on each stage. That is, at stage one when all triangles were visited for possible largest inner convex-hull, the selected ICH is stored and the obsolete associated edges/points are removed from data. The procedure starts again for the remaining data. Found a solution, the steps just mentioned above apply. After exhausting all iterations (in a lucky situation as here) the area is fully covered by ICHs (here by 3 ICH) which is our ultimate goal. Note that the given answers so far are only one iteration.
Here we show our understanding of
He was correct that greedy approach won't work as demonstrated above. This disqualifies
Uffes idea as a fully correct solution, unfortunately. It looks more challenging thus compared to the initial thoughts.