
using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;

namespace XELF {

	static partial class GeometryHelper {
		/// <summary>
		/// 点群の凸包を求める。
		/// </summary>
		/// <param name="vertices">点群</param>
		/// <returns>凸包の点群</returns>
		public static List<Vector2> ConvexHull(this List<Vector2> vertices) {
			List<Vector2> hull = new List<Vector2>();
			if (vertices.Count <= 0)
				return hull;
			hull.AddRange(vertices);
			hull.Sort(delegate(Vector2 a, Vector2 b) {
				return Math.Sign(a.Y - b.Y);
			});

			int first = 0;
			var oldPoint = hull[first];
			var oldDirection = Vector2.UnitX;

			var points = hull.ToArray();
			hull.Clear();
			hull.Add(points[first]);

			for (int i = 1; i < points.Length; i++) {
				var maximumCos = float.MinValue;
				var index = 0;
				var direction = Vector2.Zero;
				for (int j = 0; j < points.Length; j++) {
					if (points[j] == oldPoint)
						continue;
					Vector2 d;
					Vector2.Subtract(ref points[j], ref oldPoint, out d);
					d.Normalize();
					float cos;
					Vector2.Dot(ref oldDirection, ref d, out cos);
					if (cos > maximumCos) {
						index = j;
						maximumCos = cos;
						direction = d;
					}
				}
				if (index == first)
					return hull;
				hull.Add(points[index]);
				oldPoint = points[index];
				oldDirection = direction;
			}
			return hull;
		}
	}

}
