Non intersecting polygon from set of points. Given a random set of points, how do I generate non-intersecting polygon. I want to use every and each of those points.
I already have one solution to this problem using Graham's scan however this is not quite what I want. Using Graham's scan method I get a polygon with a point from which I can reach each and every other point. How could I modify this method or use another one to get more irregular shaped polygon(example below).
Polygon example
 A: Say you have set of random points, $S$.
The algorithm:


*

*$i = 1$

*calculate $C = Hull(S)$

*$P_i = S \cap C$

*$S = S \setminus C$

*$i = i + 1$

*if $S \ne \varnothing$ go to 2


After that you have the sequence of concentrated non-intersecting polygons $P_i, i = 1, \ldots, n$.
Take some point $A$ inside $P_n$ (the smallest polygon). Let $l$ be a line passing through point $A$. Let $e_1, \ldots, e_{2 n}$ be edges of polygons that intersect with $l$.
Now it's possible to replace some of these edges with other edges incident to their corners so that to obtain the appropriate polygon.
UPDATE:
Here it the algorithm to do that:
Let's move from entire polygon $P_n$ to the outer one $P_1$.
If $P_n$ is a point: create $P^*_{n-1}$ from $P_n$ and $P_{n-1}$ by creating a triangle on one of sides of $P_{n-1}$ and with vertice on $P_n$.
If $P_n$ is a segment or a set of segments that lie on the same line (this is all that's possible except polygon in this case): create $P^*_{n-1}$ from $P_n$ and $P_{n-1}$ by creating qudrangle from one segment on $P_{n-1}$ and segment containing the $P_n$.
If $P_n$ is a regular polygon, do usual step with it.
Usual step:
Suppose we have already merged $P_k, \ldots, P_n$ into some non-intersecting polygon $P^*_k$. Then we can create polygon $P^*_{k - 1} = (P_{k - 1} \setminus P^*_{k}) \setminus {Q_{k - 1}}$ where $Q_{k - 1}$ is some quadrangle that contains one segment on $P^*_{k}$ and one quadrangle on $P_{k - 1}$.
