2 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
\r
3 Permission is hereby granted, free of charge, to any person obtaining a copy
\r
4 of this software and associated documentation files (the "Software"), to deal
\r
5 in the Software without restriction, including without limitation the rights
\r
6 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
7 copies of the Software, and to permit persons to whom the Software is
\r
8 furnished to do so, subject to the following conditions:
\r
10 The above copyright notice and this permission notice shall be included in
\r
11 all copies or substantial portions of the Software.
\r
13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
14 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
15 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
16 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
17 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
18 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
\r
23 // csc /r:C5.dll GConvexHull.cs
\r
28 namespace GConvexHull
\r
30 // Find the convex hull of a point set in the plane
\r
32 // An implementation of Graham's (1972) point elimination algorithm,
\r
33 // as modified by Andrew (1979) to find lower and upper hull separately.
\r
35 // This implementation correctly handle duplicate points, and
\r
36 // multiple points with the same x-coordinate.
\r
38 // 1. Sort the points lexicographically by increasing (x,y), thus
\r
39 // finding also a leftmost point L and a rightmost point R.
\r
40 // 2. Partition the point set into two lists, upper and lower, according as
\r
41 // point is above or below the segment LR. The upper list begins with
\r
42 // L and ends with R; the lower list begins with R and ends with L.
\r
43 // 3. Traverse the point lists clockwise, eliminating all but the extreme
\r
44 // points (thus eliminating also duplicate points).
\r
45 // 4. Join the point lists (in clockwise order) in an array,
\r
46 // leaving out L from lower and R from upper.
\r
48 public class Convexhull
\r
50 public static Point[] ConvexHull(Point[] pts)
\r
52 // 1. Sort points lexicographically by increasing (x, y)
\r
55 Point left = pts[0], right = pts[N - 1];
\r
56 // 2. Partition into lower hull and upper hull
\r
57 IList<Point> lower = new LinkedList<Point>(),
\r
58 upper = new LinkedList<Point>();
\r
59 lower.InsertFirst(left); upper.InsertLast(left);
\r
60 for (int i = 0; i < N; i++)
\r
62 double det = Point.Area2(left, right, pts[i]);
\r
64 lower.InsertFirst(pts[i]);
\r
66 upper.InsertLast(pts[i]);
\r
68 lower.InsertFirst(right);
\r
69 upper.InsertLast(right);
\r
70 // 3. Eliminate points not on the hull
\r
73 // 4. Join the lower and upper hull, leaving out lower.Last and upper.Last
\r
74 Point[] res = new Point[lower.Count + upper.Count - 2];
\r
75 lower[0, lower.Count - 1].CopyTo(res, 0);
\r
76 upper[0, upper.Count - 1].CopyTo(res, lower.Count - 1);
\r
81 public static void Eliminate(IList<Point> lst)
\r
83 IList<Point> view = lst.View(0, 0);
\r
85 while (view.TrySlide(slide, 3))
\r
86 if (Point.Area2(view[0], view[1], view[2]) < 0) // right turn
\r
89 { // left or straight
\r
91 slide = view.Offset != 0 ? -1 : 0;
\r
96 // ------------------------------------------------------------
\r
98 // Points in the plane
\r
100 public class Point : IComparable<Point>
\r
102 private static readonly C5Random rnd = new C5Random(42);
\r
104 public readonly double x, y;
\r
106 public Point(double x, double y)
\r
108 this.x = x; this.y = y;
\r
111 public override string ToString()
\r
113 return "(" + x + ", " + y + ")";
\r
116 public static Point Random(int w, int h)
\r
118 return new Point(rnd.Next(w), rnd.Next(h));
\r
121 public bool Equals(Point p2)
\r
123 return x == p2.x && y == p2.y;
\r
126 public int CompareTo(Point p2)
\r
128 int major = x.CompareTo(p2.x);
\r
129 return major != 0 ? major : y.CompareTo(p2.y);
\r
132 // Twice the signed area of the triangle (p0, p1, p2)
\r
133 public static double Area2(Point p0, Point p1, Point p2)
\r
135 return p0.x * (p1.y - p2.y) + p1.x * (p2.y - p0.y) + p2.x * (p0.y - p1.y);
\r
139 // ------------------------------------------------------------
\r
143 static void Main(String[] args)
\r
145 if (args.Length == 1)
\r
147 string arg = args[0];
\r
148 int N = int.Parse(arg);
\r
149 Point[] pts = new Point[N];
\r
150 for (int i = 0; i < N; i++)
\r
151 pts[i] = Point.Random(500, 500);
\r
152 Point[] chpts = Convexhull.ConvexHull(pts);
\r
153 Console.WriteLine("Area is " + Area(chpts));
\r
157 Console.WriteLine("Usage: GConvexHull <pointcount>\n");
\r
160 // The area of a polygon (represented by an array of ordered vertices)
\r
161 public static double Area(Point[] pts)
\r
163 int N = pts.Length;
\r
164 Point origo = new Point(0, 0);
\r
166 for (int i = 0; i < N; i++)
\r
167 area2 += Point.Area2(origo, pts[i], pts[(i + 1) % N]);
\r
168 return Math.Abs(area2 / 2);
\r
171 public static void Print(Point[] pts)
\r
173 int N = pts.Length;
\r
174 for (int i = 0; i < N; i++)
\r
175 Console.WriteLine(pts[i]);
\r