# 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

Say you have set of random points, $S$. The algorithm:

1. $i = 1$
2. calculate $C = Hull(S)$
3. $P_i = S \cap C$
4. $S = S \setminus C$
5. $i = i + 1$
6. 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}$.

• Thank you for your answer Ilya. Is this there some paper on this method I could cite? For step 3 can't Pi just be equal to C? Now I don't quite understand the replacing of the edges where do I go from there after 6th step Mar 9 '16 at 13:38
• @JohnSmith, sorry, but I have no idea who has invented this algorithm first. I've updated the answer so that to make the idea clear. Mar 10 '16 at 9:50