Insert a set of vertex within a convex polygon

Question

I want to find out the correct order of a set of vertex in a polygon that is given in unordered way. For this issue, I develop an algorithm based on computational geometry concepts. First, I get the convex hull of the set of vertex sorted in counterclockwise. Then, I keep with the remaining vertices sorted by its polar angle, starting for a pivot which is the vertex with the lowest X coordenate, and I will insert then using the absolute value of the cross product compute between the vertex that I want to add and the two end points of the edge in the convex hull. With this information I will insert the corresponding vertex between the two point with lowest absolute value on its cross product, same as I explain above.

Here is my problem, this heuristic not always is true and I having problems to get the sorted sequence of vertex of the polygon. Is important keep in mind that the polygon could be a complex polygon. I want to know if there is any algorithm that allow me do that in a more consistent way, or someone could help me to improve the algorithm explained above.

Here, an snippet of my code, if not enough ask me more, and using c# and .NET 4.5:

var CH = JarvisMarch(P); // P is the set of unsorted vertex of the polygon
            var V = (from v in P where !CH.Contains(v) select v).ToArray();
            var pivot = (from v in V orderby v.Y, v.X select v).FirstOrDefault();                


            if (CH.Count < P.Length)
            {
                QuickSortPolar(ref V, 0, V.Length - 1, pivot);

                foreach (var rm in V)
                {
                    var C = CH.ToArray();
                    var T = new RedBlackTree(); // this is not entirely necessary 
                    var wlk = new List<IComparable>();
                    var min = float.MaxValue;
                    var succ = default(GeometryVertex); // this structure have the X and Y coordenate of the vertex

                    QuickSortCoorX(ref C, 0, C.Length - 1);  // for the sweep plane algorithm

                    for (int i = 0; i < C.Length; i++) // this is just to build the segments in a appropriate way
                    {
                        var j = CH.IndexOf(C[i]) == CH.Count - 1 ?
                            0 : CH.IndexOf(C[i]) + 1;
                        var sgm = new GeometrySegment()
                        {
                            Start = CH[j == 0 ? CH.Count - 1 : j - 1],
                            End = CH[j]
                        };
                        var find = T.Search(sgm);

                        if (find == null || find == RedBlackTree.sentinel)
                            T.Insert(sgm);
                    }

                    T.Inorder(T.root, ref wlk);

                    foreach (var sgm in wlk) // Here is the key of the algorithm
                    {
                        var s = (GeometrySegment)sgm;
                        var curr = (float)Math.Abs(cw(s.Start, rm, s.End));

                        if (curr < min || (curr == min && s.End < succ))
                        {
                            min = curr;
                            succ = s.End;
                        }
                    }

                    CH.Insert(CH.IndexOf(succ), rm);
                }

Thanks in advanced!!

PD: If any step of the algorithm explained above is not clear and any need more information for help me with the issue, feel free to ask.

you have a set of scattered points, and want to find a ring with the minimum length, that links all these points ? — xavigonza
Yes in deed, could be a way of arise the problem, but still need the vertices in sorted way — monk
would your problem be like this one ? en.wikipedia.org/wiki/Hamiltonian_cycle It looks like a rather geometric problem more than just a programming issue. — xavigonza
look here stackoverflow.com/q/21816562/2521214 part of mine answer contains polygonize (finding the correct order of vertexes) you have to tweak it a little (invert map usage) because that code find holes and you want to find area instead... — Spektre

Spektre Spektre · Accepted Answer · 2014-04-06T17:11:51

if you have only 2D convex areas without holes then you can do this easy

(similar to your current approach)
if this is not the case use different approach like in that link from mine comment or
some kind of polygonize / triangulation algorithm ...

1.compute the center of area (your pivot)

just compute average point coordinates (your pivot)

x0 = (p1.x+p2.x+...pn.x)  / n
y0 = (p1.y+p2.y+...pn.y)  / n

2.compute polar coordinates for all points

a = atan2(p(i).x-x0,p(i).y-y0)
r = sqrt ((p(i).x-x0)^2,(p(i).y-y0)^2) // ^ is power not xor !!!

for speed you do not need r squared you can use r^2 in the same way

3.sort all vertex by angle

ascending or descending will decide polygon winding CW/CCW
according to your coordinate system configuration

4.if there are multiple points on the same angle

use one with highest r
remove the rest

5.now you have sorted vertexes

which is what you wanted

Insert a set of vertex within a convex polygon

2 Answers