#include "stdafx.h"
#include "ConvexHullGen.h"

#include <cassert>
#include <limits>
#include <algorithm>



namespace lib_geo
{


using namespace std;


//! xy平面上で指定頂点列の凸包を生成する
void ConvexHullGen2d::Generate(const std::vector<lm::vec3f>& i_points, std::vector<lm::vec3f>& o_convex_hull)
{
	Generate(i_points, lm::vec3f(0.0f, 0.0f, 1.0f), lm::vec3f(0.0f, 1.0f, 0.0f), o_convex_hull);
}

void ConvexHullGen2d::Generate(const std::vector<lm::vec3f>& i_points, const lm::vec3f& normal, const lm::vec3f& up_in2d, std::vector<lm::vec3f>& o_convex_hull)
{
	lm::vec3f binormal = cross( up_in2d , normal );

	std::vector<lm::vec3f> v2d(i_points.size());
	for(size_t i = 0; i < i_points.size(); ++i)
	{
		v2d[i].x = dot(i_points[i], binormal);
		v2d[i].y = dot(i_points[i], up_in2d);
		v2d[i].z = dot(i_points[i], normal);
	}

	CalcConvexHullMain(v2d, o_convex_hull);

	for(size_t i = 0; i < o_convex_hull.size(); ++i)
	{
		lm::vec3f& v = o_convex_hull[i];

		v = normal* v.z + up_in2d * v.y + binormal * v.x;
	}
}


void ConvexHullGen2d::Sort_ax(vector<lm::vec3f>& P)
{
	// Sort points lexicographically
	struct
	{
		bool operator()(const lm::vec3f &a, const lm::vec3f &b)
		{
			if(a.x < b.x)
				return true;
			if(a.x > b.x)
				return false;

			return a.y < b.y;
		}
	} pred;
	sort(P.begin(), P.end(), pred);
}

// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
void ConvexHullGen2d::CalcConvexHullMain(vector<lm::vec3f> P, vector<lm::vec3f>& ch)
{
	int n = P.size();
	int k = 0;

	vector<lm::vec3f> H(2 * n);

	Sort_ax(P);

	// Build lower hull
	for (int i = 0; i < n; i++)
	{
		while (k >= 2 && cross(H[k-1] - H[k-2], P[i] - H[k-2]).z <= 0)
			k--;

		H[k++] = P[i];
	}

	// Build upper hull
	for (int i = n-2, t = k+1; i >= 0; i--)
	{
			while (k >= t && cross(H[k-1] - H[k-2], P[i] - H[k-2]).z <= 0)
				k--;

			H[k++] = P[i];
	}

	H.resize(k-1);
	ch.swap(H);
}


}
