CODEWITHSUNDEEP
c#algorithmgeometry
monk
monk

Reputation: 134

Insert a set of vertex within a convex polygon

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.

Upvotes: 1

Views: 568

Answers (2)

user1196549
user1196549

Reputation:

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.

Upvotes: 0

Spektre
Spektre

Reputation: 51845

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

Upvotes: 1

Related Questions