Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- private List<Vertex> MakeConvexHull()
- {
- int n = Vertices.Count;
- int k = 0;
- Vertices.Sort((left, right) => (left.X.ToString() + left.Y.ToString()).CompareTo(right.X.ToString() + right.Y.ToString()));
- List<Vertex> Hull = new List<Vertex>();
- for (int i = 0; i < n; Hull[k++] = Vertices[i++])
- {
- for (; k >= 2 && Cross(Hull[k - 2], Hull[k - 1], Vertices[i]) >= 0; --k)
- ;
- }
- for (int i = n - 2, t = k; i >= 0; Hull[k++] = Vertices[i--])
- {
- for (; k > t && Cross(Hull[k - 2], Hull[k - 1], Vertices[i]) >= 0; --k)
- ;
- }
- int m = 0;
- if (Hull[0].X == Hull[1].X && Hull[0].Y == Hull[1].Y)
- m = 1;
- for (int i = 0; i < n; i++)
- {
- if (i > k - 2 - m)
- Hull[i].Should_be_deleted = true;
- }
- Hull.RemoveAll(i => i.Should_be_deleted == true);
- return Hull;
- }
Advertisement
Add Comment
Please, Sign In to add comment