_takumi

Untitled

Oct 13th, 2019
577
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.07 KB | None | 0 0
  1. private List<Vertex> MakeConvexHull()
  2.         {
  3.             int n = Vertices.Count;
  4.             int k = 0;
  5.             Vertices.Sort((left, right) => (left.X.ToString() + left.Y.ToString()).CompareTo(right.X.ToString() + right.Y.ToString()));
  6.             List<Vertex> Hull = new List<Vertex>();
  7.             for (int i = 0; i < n; Hull[k++] = Vertices[i++])
  8.             {
  9.                 for (; k >= 2 && Cross(Hull[k - 2], Hull[k - 1], Vertices[i]) >= 0; --k)
  10.                     ;
  11.             }
  12.             for (int i = n - 2, t = k; i >= 0; Hull[k++] = Vertices[i--])
  13.             {
  14.                 for (; k > t && Cross(Hull[k - 2], Hull[k - 1], Vertices[i]) >= 0; --k)
  15.                     ;
  16.             }
  17.             int m = 0;
  18.             if (Hull[0].X == Hull[1].X && Hull[0].Y == Hull[1].Y)
  19.                 m = 1;
  20.             for (int i = 0; i < n; i++)
  21.             {
  22.                 if (i > k - 2 - m)
  23.                     Hull[i].Should_be_deleted = true;
  24.             }
  25.             Hull.RemoveAll(i => i.Should_be_deleted == true);
  26.             return Hull;
  27.         }
Advertisement
Add Comment
Please, Sign In to add comment