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, Apr 06 '14 at 16:06
Yes in deed, could be a way of arise the problem, but still need the vertices in sorted way — monk, Apr 06 '14 at 16:11
would your problem be like this one ? http://en.wikipedia.org/wiki/Hamiltonian_cycle It looks like a rather geometric problem more than just a programming issue. — xavigonza, Apr 06 '14 at 16:25
look here http://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, Apr 06 '14 at 16:57

score 1 · Accepted Answer · answered Apr 06 '14 at 17:11

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

@monk I see you are new user so ... if the question is answered check the check sign near the correct answer (it will give the author points and mark the solution for others to see it quickly) if it is only helpful in some way you can vote up by clicking on the upper triangle or if it is wrong harm-full abusive ... then you can vote down by that lower triangle (can cast only 1 vote per question or answer) also this will award you some badges I think ... also you can vote the comments if you have enough points. als all votes are undo-able so do not worry — Spektre, Apr 06 '14 at 18:39

score 0 · Answer 2 · 2014-04-07T06:27:42.257

0

If your vertices are guaranteed to form a convex polygon, this alternative approach will spare angle computation:

sort on X; check for possible ties at both extremes and sort them on Y;
draw the line through the two extreme points and partition the points in two subsets, on either side of it; you will separate upper and lower outline parts;
keep the points below the line in the same order and reverse the others. You are done.

Note that if your polygon is not convex, the same process with lexicographical sorting and Graham scan of the two subsequences will compute the convex hull.

edited Apr 07 '14 at 06:27

answered Apr 07 '14 at 06:02

My approach use a Jarvis's March, that is similar to the procedure that you discribe above, but my polygon not always are convex, that's is the problem. Compute the centroid of the set of points and sort them using this point as pivot is solved my problem. Instead use the angle value, I used cross product for obtain the sorted sequence of points, this more efficient computationally. I appreciate your comment. – monk Apr 07 '14 at 20:08

Insert a set of vertex within a convex polygon

2 Answers2