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


1 Answer 1


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.


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}$.

  • $\begingroup$ 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 $\endgroup$
    – John Smith
    Mar 9, 2016 at 13:38
  • $\begingroup$ @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. $\endgroup$ Mar 10, 2016 at 9:50
  • $\begingroup$ @JohnSmith, see also stackoverflow.com/questions/14263284/… $\endgroup$ Mar 10, 2016 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.