So there are several questions regarding how to compute the convex hull of a set of points. However, let's say that on inspection the set of points inscribed a star shape. A Convex hull algorithm would define a pentagon around a five-point star and call that the convex hull, but if I wanted to identify the shape as a five-pointed star that would be insufficient.
How then could I tell the computer to define a polygon that may be concave, which would contain all the points in Q and has nonzero area, but would minimize areas bounded by the shape in which there are no points from Q?
I'm thinking a simple tweak of the Graham Scan to allow right turns, but that would instead not allow lines to cross, might do it, but that's just a wild shot in the dark which I haven't tried. I'm also thinking that, given the normal application of this in computers (image pattern recognition), that I would also have a set of points R that should NOT be contained in the polygon, and after finding the "convex hull" of the points Q I can then run a variation of the algorithm that adds "right turns" at points that should lie outside the shape but currently are contained within.
So first define the subset H that define the convex hull of a set of points Q. Now, take each point X from a set R of points that must not be contained in the final polygon. Determine if that point lies within the polygon (it does if a line from any point in Q to X intersects zero or an even number of line segments defining the current polygon). If so, insert X into H between the two adjacent points M and N in H that have the lowest mean distance from X. Then, for all P in Q that are not in H, if P now lies outside the shape defined by H, add P to H between either M and X, or X and N, depending on which two points have the lowest mean distance. Repeat for all X in R.
Are there any proven algorithms that would accomplish this (and be less complex than O(N^2logN) given that Q and R are roughly equal in cardinality)?