Validity of algorithm for creation of a non self-intersecting polygon

Question

As an extension and partial answer to my thread I wrote a simple algorithm that given a set of points(with xy coordinates) can form a non self-intersecting polygon.

---

Claim: Given an arbitrary set of points with different coordinates it is always possible to construct a regular or irregular, non self-intersecting polygon.

The algorithm:

Assume there is a set V containing all the vertices

1) Sort all vertices in V by x-coordinate

2) Imagine a straight line (we'll call that "the divider") parallel to the x-axis which starting from the first node expands to infinity and divides/splits the vertices into two sets.

3) Now consider the two sets:

A = The set of all vertices above or on the divider line

B = The set of all remaining vertices

4) Starting at the leftmost vertex of A connect all vertices in A until you get to the rightmost

5) If the rightmost vertex of the sorted set V (the vertex with the biggest x coordinate) is not in A connect that last vertex (rightmost of A) with it.

6) Work backwards and starting from the rightmost vertex of the sorted set V (the vertex with the biggest x coordinate) connect all the vertices that are in B

7)Connect the first (leftmost vertex of B) vertex of B with the leftmost vertex of A

---

I think that the algorithm is correct and can't find a test that it would fail but maybe I'm missing something.

I would appreciate it if you could have a look and give me an example that wouldn't work if there is any(which I'm sure there must be).

Answer 1

Here is a counterexample. When step 5 does not draw a line, it is possible to self intersect.

Answer 2

I'm not sure I understand correctly what you're trying to do. In the other thread, and in the corresponding thread at math.SE (which brought me here), you said you had a polygon and were trying to find its center of gravity. Here you say you have a set of points and you want to construct a non-intersecting polygon from it. Those are two quite different things. As I mentioned at math.SE, if the polygons are not known to be convex, a set of points doesn't uniquely define a polygon -- so the algorithm you propose here may construct some arbitrary non-self-intersecting polygon (I haven't checked whether it successfully does that) but that may or may not bear any relation to the polygon you were originally interested in. Or did I misunderstand your question at math.SE and you actually only have some points and want to construct just any non-self-intersecting polygon from them and don't care that there may be several inequivalent solutions for this?