In my work, I have to enclose some random group of points in a boundary. Convex hull was taking extra space and was not tightest shape so I modified it to relax the edges in following way:
i) Draw convex hull for the given number of points.
ii) Now for each point not on the convex hull boundary check if it can be added to the boundary (of course that changes the boundary shaping), while making sure none of the given points lies outside of the new polygon shape. (Point in Polygon algorithm)
iii) If all the points lie inside the polygon repeat step 2 for some other point.
iv) If no more point can be included on the boundary, stop.
Now, the issue is at any sample test set, all the points are getting included in the boundary. My doubts are:
i) Is this a concave hull?
ii) How is this different from, if I simply arrange the given points in anticlockwise order and draw and polygon through all of them instead of first drawing a convex hull?
iii) Is it true that for any given number of points, I can draw a non self intersection polygon through them, such that all the points lie on the boundary of the polygon?
