c# - Insert a set of vertex within a convex polygon -

i want find out correct order of set of vertex in polygon given in unordered way. issue, develop algorithm based on computational geometry concepts. first, convex hull of set of vertex sorted in counterclockwise. then, keep remaining vertices sorted polar angle, starting pivot vertex lowest x coordenate, , insert using absolute value of cross product compute between vertex want add , 2 end points of edge in convex hull. information insert corresponding vertex between 2 point lowest absolute value on cross product, same explain above.

here problem, heuristic not true , having problems sorted sequence of vertex of polygon. important keep in mind polygon complex polygon. want know if there algorithm allow me in more consistent way, or me improve algorithm explained above.

here, snippet of code, if not enough ask me more, , using c# , .net 4.5:

var ch = jarvismarch(p); // p set of unsorted vertex of polygon             var v = (from v in p !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(); // not entirely necessary                      var wlk = new list<icomparable>();                     var min = float.maxvalue;                     var succ = default(geometryvertex); // structure have x , y coordenate of vertex                      quicksortcoorx(ref c, 0, c.length - 1);  // sweep plane algorithm                      (int = 0; < c.length; i++) // build segments in 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 key of 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 step of algorithm explained above not clear , need more information me issue, feel free ask.

if have 2d convex areas without holes can easy

• (similar current approach)
• if not case use different approach in link mine comment or
• some kind of polygonize / triangulation algorithm ...

1.compute 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 points

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

• for speed not need r squared can use r^2 in same way

3.sort vertex angle

• ascending or descending decide polygon winding cw/ccw
• according coordinate system configuration

4.if there multiple points on same angle

• use 1 highest r
• remove rest

5.now have sorted vertexes

• which wanted