/*
								+----------------------------------+
								|                                  |
								|   ***  T-Junction removal  ***   |
								|                                  |
								|   Copyright © -tHE SWINe- 2013   |
								|                                  |
								|           TJunction.h            |
								|                                  |
								+----------------------------------+
*/

#pragma once
#ifndef __T_JUNCTION_REMOVAL_INCLUDED
#define __T_JUNCTION_REMOVAL_INCLUDED

/**
 *	@file lml/TJunction.h
 *	@author -tHE SWINe-
 *	@date 2013
 *	@brief T-Junction removal
 */

#include "PolyMesh.h"

/**
 *	@def __TJUNCTIONS_GENERATE_DEBUG_INFO
 *	@brief if defined, CRemove_TJunctions supports generating of
 *		a list of lines with positions of the former t-junctions
 */
#define __TJUNCTIONS_GENERATE_DEBUG_INFO

/**
 *	@brief T-Junction removal
 */
class CRemove_TJunctions {
public:
	/**
	 *	@brief edge hash configuration stored as enum
	 */
	enum {
		hash_Size = 16 /**< @brief size of edge hash table (one of its dimensions) */
	};

	typedef CPolyMesh::_TyPolygon _TyPolygon; /**< @brief specialized polygon type */

protected:
	/**
	 *	@brief structure, containing edge hashing information
	 */
	struct TEdge {
		_TyPolygon *p_polygon; /**< @brief owner of this edge */
		size_t n_polygon_edge; /**< @brief zero-based index of the first vertex of this edge (in p_polygon) */
		Vector3f p_point[2]; /**< @brief copy of positions of the edge vertices */
		Vector3i v_hash_bin; /**< @brief bin of the hash map this edge falls into */
		size_t n_hash_bin; /**< @brief bin of the hash map this edge falls into */
		size_t n_uncertainty; /**< @brief uncertainty about bin of the hash map (in bins) */

		float f_min_proj; /**< @brief temporary variable for storing minimal projection of other edges */
		float f_max_proj; /**< @brief temporary variable for storing maximal projection of other edges */
		bool b_proj_swapped; /**< @brief reverse projection direction flag */

		/**
		 *	@brief default constructor; has no effect
		 */
		inline TEdge()
			:n_polygon_edge(-1), n_hash_bin(-1), n_uncertainty(-1),
			f_min_proj(1), f_max_proj(0), b_proj_swapped(false)
		{}

		/**
		 *	@brief constructor; evaluates edge hash function
		 *
		 *	@param[in] r_poly is owner of this edge
		 *	@param[in] n_edge is zero-based index of the first vertex of this edge (in r_poly)
		 *	@param[in] n_poly_vertex_num is number of vertices of the polygon
		 *	@param[in] f_epsilon_ex is maximal edge distance epsilon
		 */
		TEdge(_TyPolygon &r_poly, size_t n_edge,
			size_t n_poly_vertex_num, float f_epsilon_ex);

		/**
		 *	@brief calculates perpendicular tangent planes for the edge
		 *		(for quick and robust distance measure)
		 *
		 *	@param[out] r_tangent is tangent plane of edge axis
		 *	@param[out] r_bitangent is bitangent plane of edge axis
		 *	@param[in] f_epsilon_ex is the epsilon the edge was created with
		 */
		void Get_Planes(Plane3f &r_tangent, Plane3f &r_bitangent, float f_epsilon_ex) const;

		/**
		 *	@brief decides whether two edges lie on the same axis (direction does not matter)
		 *
		 *	@param[in] r_edge is the other edge to compare with
		 *	@param[in] f_epsilon_ex is the epsilon the edge was created with
		 *
		 *	@return Returns true if the edges are colinear with maximum distance
		 *		of f_epsilon_ex, otherwise returns false.
		 */
		bool b_Match(const TEdge &r_edge, float f_epsilon_ex) const;
	};

	typedef std::vector<TEdge> _TyEdgeGroup;
	typedef std::vector<_TyEdgeGroup> _TyEdgeMapBin;
	typedef std::map<size_t, _TyEdgeMapBin> _TyEdgeMap; /**< @brief edge map type */
	typedef std::map<float, Vector3f> _TyEdgePointMap; /**< @brief map of (sorted) points on an edge */
	typedef std::pair<_TyPolygon*, size_t> _TyPolyEdgePair; /**< @brief a polygon-edge pair */
	typedef std::map<_TyPolyEdgePair, _TyEdgePointMap> _TyFixupMap; /**< @brief edge fixup map type */

	/**
	 *	@brief void progress indicator
	 */
	class CVoidProgressIndicator {
	public:
		/**
		 *	@brief shows progress of t-junction removal
		 *	@param[in] f_progress is progress of t-junction removal (unused)
		 */
		inline void Show(float UNUSED(f_progress))
		{}
	};

	/**
	 *	@brief void diagnostic geometry generator
	 */
	class CVoidDebugLineGenerator {
	public:
		/**
		 *	@brief adds debug information for a t-junction being fixed
		 *
		 *	@param[in] v_pos is position of the new fixup vertex (unused)
		 *	@param[in] v_dir is direction of the edge being fixed (unused)
		 *	@param[in] v_normal is normal of the polygon being fixed (unused)
		 */
		inline void Add(Vector3f UNUSED(v_pos),
			Vector3f UNUSED(v_dir), Vector3f UNUSED(v_normal))
		{}
	};

#ifdef __TJUNCTIONS_GENERATE_DEBUG_INFO

	/**
	 *	@brief diagnostic geometry generator
	 */
	class CDebugLineGenerator {
	protected:
		std::vector<Vector3f> &m_r_debug_line_list; /**< @brief reference to the output debug line list */

	public:
		/**
		 *	@brief default constructor
		 *	@param[in] r_debug_line_list is reference to the output debug line list
		 */
		inline CDebugLineGenerator(std::vector<Vector3f> &r_debug_line_list)
			:m_r_debug_line_list(r_debug_line_list)
		{}

		/**
		 *	@brief adds debug information for a t-junction being fixed
		 *
		 *	@param[in] v_pos is position of the new fixup vertex
		 *	@param[in] v_dir is direction of the edge being fixed
		 *	@param[in] v_normal is normal of the polygon being fixed
		 *
		 *	@note This function throws std::bad_alloc.
		 */
		inline void Add(Vector3f v_pos, Vector3f v_dir, Vector3f v_normal) // throw(std::bad_alloc)
		{
			Vector3f v_axis = v_dir * .3f;
			Vector3f v_tangent = v_normal.v_Cross(v_dir);
			v_tangent.Normalize(.3f);
			m_r_debug_line_list.push_back(v_pos);
			m_r_debug_line_list.push_back(v_pos + v_axis);
			m_r_debug_line_list.push_back(v_pos);
			m_r_debug_line_list.push_back(v_pos - v_axis);
			m_r_debug_line_list.push_back(v_pos);
			m_r_debug_line_list.push_back(v_pos - v_tangent);
			// make a small "T" (which is t-junction-less btw)

			//m_r_debug_line_list.push_back(v_pos);
			//m_r_debug_line_list.push_back(r_poly.v_Center());
			// an extra leg pointing to polygon center
		}
	};

#endif // __TJUNCTIONS_GENERATE_DEBUG_INFO

public:
	// t_odo make .cpp
	// t_odo put epsilons (max edge distance epsilon and min vertex distance epsilon)
	// todo doc, test (test if calling twice adds vertices)
	// t_odo test on rotated axes

#ifdef __TJUNCTIONS_GENERATE_DEBUG_INFO

	static size_t n_Remove_TJunctions(CPolyMesh &r_mesh,
		std::vector<Vector3f> &r_debug_line_list,
		float f_edge_dist_epsilon = f_epsilon,
		float f_vertex_dist_epsilon = f_epsilon); // throw(std::bad_alloc)

	template <class CProgressIndicator>
	static size_t n_Remove_TJunctions(CPolyMesh &r_mesh,
		std::vector<Vector3f> &r_debug_line_list,
		CProgressIndicator &r_progress, float f_edge_dist_epsilon = f_epsilon,
		float f_vertex_dist_epsilon = f_epsilon) // throw(std::bad_alloc)
	{
		/*CTimer timer;
		double f_start = timer.f_Time(), f_ph0, f_ph1;*/

		_TyFixupMap polygon_fixup_map;
		{
			_TyEdgeMap edge_map;
			HashEdges(edge_map, r_mesh, f_edge_dist_epsilon, r_progress);
			// build a list of all polygon edges and group them by direction
			// so that edges that are close to each other are in the same bins

			//f_ph0 = timer.f_Time();

			Fill_TJunctionFixup_Map(polygon_fixup_map, edge_map,
				f_edge_dist_epsilon, f_vertex_dist_epsilon, r_progress);
			// go through bins, calculate projections, distribute new vertices to the sorted lists

			//f_ph1 = timer.f_Time();
		}

		CDebugLineGenerator debug_gen(r_debug_line_list);
		size_t n_result = n_Fix_TJunctions(r_mesh, polygon_fixup_map,
			debug_gen, f_edge_dist_epsilon, r_progress);

		/*double f_ph2 = timer.f_Time();
		f_ph2 -= f_ph1;
		f_ph1 -= f_ph0;
		f_ph0 -= f_start;
		printf("t-junction removal phases took %f %f %f (%f %f %f)\n",
			f_ph0, f_ph1, f_ph2, f_ph0 / (f_ph0 + f_ph1 + f_ph2),
			f_ph1 / (f_ph0 + f_ph1 + f_ph2), f_ph2 / (f_ph0 + f_ph1 + f_ph2));*/
		// debug - time the phases to better normalize the progress indicator

		return n_result;
	}

#endif // __TJUNCTIONS_GENERATE_DEBUG_INFO

	static size_t n_Remove_TJunctions(CPolyMesh &r_mesh,
		float f_edge_dist_epsilon = f_epsilon,
		float f_vertex_dist_epsilon = f_epsilon); // throw(std::bad_alloc)

	template <class CProgressIndicator>
	static size_t n_Remove_TJunctions(CPolyMesh &r_mesh,
		CProgressIndicator &r_progress, float f_edge_dist_epsilon = f_epsilon,
		float f_vertex_dist_epsilon = f_epsilon) // throw(std::bad_alloc)
	{
		_TyFixupMap polygon_fixup_map;
		{
			_TyEdgeMap edge_map;
			HashEdges(edge_map, r_mesh, f_edge_dist_epsilon, r_progress);
			// build a list of all polygon edges and group them by direction
			// so that edges that are close to each other are in the same bins

			Fill_TJunctionFixup_Map(polygon_fixup_map, edge_map,
				f_edge_dist_epsilon, f_vertex_dist_epsilon, r_progress);
			// go through bins, calculate projections, distribute new vertices to the sorted lists
		}

		CVoidDebugLineGenerator dummy;
		return n_Fix_TJunctions<CVoidDebugLineGenerator, CProgressIndicator>(r_mesh, polygon_fixup_map,
			dummy, f_edge_dist_epsilon, r_progress);
	}

protected:
	/**
	 *	@brief builds a list of all polygon edges and groups them by direction
	 *
	 *	@param[out] r_edge_map is reference to the edge map (filled with edges, is overwritten)
	 *	@param[in] r_mesh is the polygonal mesh to be hashed
	 *
	 *	@note This function throws std::bad_alloc.
	 *	@note This takes 99% of all the processing.
	 */
	template <class CProgressIndicator>
	static void HashEdges(_TyEdgeMap &r_edge_map, CPolyMesh &r_mesh,
		float f_edge_dist_epsilon, CProgressIndicator &r_progress) // throw(std::bad_alloc)
	{
		r_edge_map.clear();
		// ...

		for(size_t i = 0, n = r_mesh.n_Polygon_Num(); i < n; ++ i) {
			_TyPolygon &r_poly = r_mesh.r_Polygon(i);
			if(r_poly.n_Vertex_Num() < 3)
				continue;
			// don't fix t-junctions in degenerate polygons, it will make them look legit

			r_progress.Show(float(i) / n * .9f);
			// this first phase comprises of the first 90% of the progress

			for(size_t j = 0, m = r_poly.n_Vertex_Num(); j < m; ++ j) {
				TEdge e(r_poly, j, m, f_edge_dist_epsilon);
				if(e.n_uncertainty == size_t(-1))
					continue;
				// create edges

				bool b_added = false;
				_ASSERTE(e.n_uncertainty <= INT_MAX);
				int n_search_region = int(e.n_uncertainty);
				for(int n_uncertainty_x = -n_search_region; n_uncertainty_x <=
				   n_search_region; ++ n_uncertainty_x) {
					for(int n_uncertainty_y = -n_search_region; n_uncertainty_y <=
					   n_search_region; ++ n_uncertainty_y) {
						for(int n_uncertainty_z = -n_search_region; n_uncertainty_z <=
						   n_search_region; ++ n_uncertainty_z) {
							Vector3i v_hash(n_uncertainty_x, n_uncertainty_y, n_uncertainty_z);
							v_hash += e.v_hash_bin;
							for(int k = 0; k < 3; ++ k)
								v_hash[k] = max(0, min(hash_Size, v_hash[k])); // is that correct?
							size_t n_hash = v_hash.x + hash_Size * (v_hash.y + hash_Size * v_hash.z);
							if(r_edge_map.find(n_hash) == r_edge_map.end())
								continue;
							std::vector<std::vector<TEdge> > &r_edge_groups = r_edge_map[n_hash];
							// get a non-empty list of edge groups

							for(size_t n_group = 0, n_group_num = r_edge_groups.size();
							   n_group < n_group_num; ++ n_group) {
								const TEdge &r_edge = r_edge_groups[n_group].front();
								if(r_edge.b_Match(e, f_edge_dist_epsilon)) {
									r_edge_groups[n_group].push_back(e);
									b_added = true;
									break;
								}
							}
							// try to match the edges
						}
					}
				}
				// search the surrounding cells with some uncertainty (could use a better
				// search that would start in the middle)

				if(!b_added) {
					std::vector<std::vector<TEdge> > &r_edge_groups = r_edge_map[e.n_hash_bin];
					r_edge_groups.resize(r_edge_groups.size() + 1);
					r_edge_groups.back().push_back(e);
				}
				// in case it was not added, create a new edge group
			}
		}
	}

	/**
	 *	@brief builds a list of all polygon edges and groups them by direction
	 *
	 *	@param[out] r_polygon_fixup_map is reference to polygon fixup map
	 *		(filled with sorted vertices to fix t-junctions; is overwritten)
	 *	@param[in] r_edge_map is reference to the edge map
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	template <class CProgressIndicator>
	static void Fill_TJunctionFixup_Map(_TyFixupMap &r_polygon_fixup_map,
		_TyEdgeMap &r_edge_map, float f_edge_dist_epsilon,
		float f_vertex_dist_epsilon, CProgressIndicator &r_progress) // throw(std::bad_alloc)
	{
		r_polygon_fixup_map.clear();
		// ...

		size_t n_size = r_edge_map.size(), n_progress = 0;
		for(_TyEdgeMap::iterator p_map_it = r_edge_map.begin(),
		   p_end_it = r_edge_map.end(); p_map_it != p_end_it; ++ p_map_it, ++ n_progress) {
			std::vector<std::vector<TEdge> > &r_bucket_list = (*p_map_it).second;

			r_progress.Show(float(n_progress) / n_size * .05f + .9f);
			// this second phase comprises of the second 5% of the progress

			for(std::vector<std::vector<TEdge> >::iterator p_bucket_it =
			   r_bucket_list.begin(), p_bucket_end_it = r_bucket_list.end();
			   p_bucket_it != p_bucket_end_it; ++ p_bucket_it) {
				std::vector<TEdge> &r_bucket = *p_bucket_it;
				// get a bucket of edges that are colinear after taking absolute value of the direction
				// (actually contains lines of different directions!)

				{
					_ASSERTE(!r_bucket.empty()); // otherwise it wouldn't be there
					const TEdge &r_e = r_bucket.front();
					Vector3f v_dir = r_e.p_point[1] - r_e.p_point[0];
					_ASSERTE(v_dir.f_Length() > f_edge_dist_epsilon);
					v_dir.Normalize();
					Plane3f t_plane(r_e.p_point[0], v_dir, plane::from_position_normal);
					for(size_t i = 0, n = r_bucket.size(); i < n; ++ i) {
						TEdge &r_edge = r_bucket[i];
						r_edge.f_min_proj = t_plane.f_Vector_Dist(r_edge.p_point[0]);
						r_edge.f_max_proj = t_plane.f_Vector_Dist(r_edge.p_point[1]);
						if(r_edge.f_min_proj > r_edge.f_max_proj) {
							std::swap(r_edge.f_min_proj, r_edge.f_max_proj);
							r_edge.b_proj_swapped = true;
						} else
							_ASSERTE(!r_edge.b_proj_swapped);
						// calculate minimal and maximal projection
					}
				}
				// calculate edge projections onto the axis

				std::sort(r_bucket.begin(), r_bucket.end(), CSmallerMinProj());
				// sort the projections

				for(size_t i = 0, n = r_bucket.size(); i < n; ++ i) {
					const TEdge &r_edge = r_bucket[i];
					std::vector<TEdge>::const_iterator p_last_it =
						std::upper_bound(r_bucket.begin(), // not lower, we want the equal bound in the range
						r_bucket.end(), r_edge.f_max_proj, CSmallerMinProj());
					size_t m = p_last_it - r_bucket.begin();
					// the edges are sorted by the min projection, can find all that potentially overlap r_edge
					// (need to further check if max projection is equal or greater than r_edge.f_max_proj)

					for(size_t j = 0; j < m; ++ j) {
						if(i == j)
							continue;
						// ...

						const TEdge &r_edge2 = r_bucket[j];
						_ASSERTE(r_edge2.f_min_proj <= r_edge.f_max_proj);
						if(r_edge2.f_max_proj < r_edge.f_min_proj)
							continue;
						// discard edges that are projected before the current edge

						Insert_EdgeVertices(r_edge, r_polygon_fixup_map, r_edge2,
							true, f_vertex_dist_epsilon); // first vertex
						Insert_EdgeVertices(r_edge, r_polygon_fixup_map, r_edge2,
							false, f_vertex_dist_epsilon); // second vertex
						// insert both vertices of r_edge2 to r_edge

						// note that if we added t-junctions to both edges at the same
						// time, we could set lower bound of this loop to i + 1 (right?)
					}
				}
			}
		}
	}

	/**
	 *	@brief attempts to turn polygon in such a way that if the
	 *		triangulation creates a fan with center at vertex 0,
	 *		it contains the least number of degenerate edges
	 *
	 *	@param[in,out] r_poly is polygon to turn
	 *	@param[in] r_original_vertex_indices is a list of original polygon
	 *		vertices in the polygon with the t-junctions fixed
	 *	@param[in] p_begin is iterator pointing to the first polygon edge fixup list
	 *	@param[in] p_begin is iterator pointing to the last polygon edge fixup list
	 */
	static void TurnPolygon(_TyPolygon &r_poly,
		const std::vector<size_t> &r_original_vertex_indices,
		_TyFixupMap::const_iterator p_begin, _TyFixupMap::const_iterator p_end);

	/**
	 *	@brief builds a list of all polygon edges and groups them by direction
	 *
	 *	@param[in,out] r_mesh is the polygonal mesh to be fixed
	 *	@param[in] r_polygon_fixup_map is reference to the fixup map
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	template <class CDebugLineGenerator, class CProgressIndicator>
	static size_t n_Fix_TJunctions(CPolyMesh &r_mesh, const _TyFixupMap &r_polygon_fixup_map,
		CDebugLineGenerator &r_debug_line_list, float f_edge_dist_epsilon,
		CProgressIndicator &r_progress) // throw(std::bad_alloc)
	{
		size_t n_tj_fix_num = 0; // debug
		size_t n_orig_poly_vertex_num = 0;
		size_t n_prev_edge = 0;
		std::vector<size_t> original_vertex_indices;
		_TyPolygon *p_prev_poly = 0;
		ptrdiff_t n_poly_added_point_num = 0;
		_TyFixupMap::const_iterator p_first_poly_tjunc_it;
		size_t n_size = r_polygon_fixup_map.size(), n_progress = 0;
		for(_TyFixupMap::const_iterator p_tjunc_it = r_polygon_fixup_map.begin(), p_end_it =
		   r_polygon_fixup_map.end(); p_tjunc_it != p_end_it; ++ p_tjunc_it, ++ n_progress) {
			// note that we need to iterate over the edges in reverse order, need to make another comparison op for pointer size_t pair

			r_progress.Show(float(n_progress) / n_size * .05f + .95f);
			// this last phase comprises of the last 5% of the progress

			_TyPolyEdgePair t_poly_edge = (*p_tjunc_it).first;
			const _TyEdgePointMap &r_edge_tjunc_list = (*p_tjunc_it).second;
			_ASSERTE(!r_edge_tjunc_list.empty()); // otherwise would not be added
			_TyPolygon &r_poly = *t_poly_edge.first;
			size_t n_edge = t_poly_edge.second; // the first point of the edge
			if(&r_poly != p_prev_poly) {
				if(p_prev_poly) {
					for(; n_prev_edge < n_orig_poly_vertex_num; ++ n_prev_edge)
						original_vertex_indices.push_back(n_prev_edge + n_poly_added_point_num);
					_ASSERTE(n_orig_poly_vertex_num == original_vertex_indices.size());
					TurnPolygon(*p_prev_poly, original_vertex_indices,
						p_first_poly_tjunc_it, p_tjunc_it);
				}

				original_vertex_indices.clear();
				p_first_poly_tjunc_it = p_tjunc_it;
				p_prev_poly = &r_poly;
				n_poly_added_point_num = 0; // a new polygon came up, reset the counter
				n_orig_poly_vertex_num = r_poly.n_Vertex_Num();
				n_prev_edge = 0;
			}
			// get a polygon-edge pair

			for(; n_prev_edge < n_edge; ++ n_prev_edge)
				original_vertex_indices.push_back(n_prev_edge + n_poly_added_point_num);
			++ n_prev_edge; // !!
			original_vertex_indices.push_back(n_edge + n_poly_added_point_num);
			CPolyMesh::_TyRefVertex t_vertex0 = r_poly.t_Vertex(n_edge +
				n_poly_added_point_num);
			CPolyMesh::_TyRefVertex t_vertex1 = r_poly.t_Vertex((n_edge +
				n_poly_added_point_num + 1) % r_poly.n_Vertex_Num());
			// get edge vertices (a bit messy because of the insertions)

			Vector3f v_point0 = t_vertex0;
			Vector3f v_point1 = t_vertex1;
			Vector3f v_dir = v_point1 - v_point0;
			float f_edge_length = v_dir.f_Length();
			_ASSERTE(f_edge_length > f_edge_dist_epsilon);
			v_dir /= f_edge_length;

			float f_last_t = 0;
			for(_TyEdgePointMap::const_iterator p_tj_it = r_edge_tjunc_list.begin(),
			   p_tj_end_it = r_edge_tjunc_list.end(); p_tj_it != p_tj_end_it; ++ p_tj_it) {
				float f_t = (*p_tj_it).first;
				Vector3f v_pos = (*p_tj_it).second;
				_ASSERTE(f_last_t + f_edge_dist_epsilon <= f_t); // must be sorted
				_ASSERTE(f_t >= f_edge_dist_epsilon && f_t <= f_edge_length - f_edge_dist_epsilon); // must not collide with edge vertices

				_ASSERTE(fabs(f_t - v_dir.f_Dot(v_pos - v_point0)) < f_edge_dist_epsilon); // make sure that the position along the edge is calculated correctly

				r_debug_line_list.Add(v_pos, v_dir, r_poly.t_Normal().v_normal);

				CPolyMesh::_TyVertex t_new_vertex = t_vertex1 - t_vertex0;
				t_new_vertex *= f_t / f_edge_length; // normalize to 0, 1
				t_new_vertex += t_vertex0;
				_ASSERTE((t_new_vertex.v_position - v_pos).f_Length() < f_edge_dist_epsilon);
				t_new_vertex.v_position = v_pos; // don't use interpolation for position, use exact copy of the position instead
				_ASSERTE(n_edge + 1 + n_poly_added_point_num <= r_poly.n_Vertex_Num());
				r_mesh.r_Vertex_Pool().Insert_Back(1, t_new_vertex);
				r_poly.Insert_Vertex(n_edge + 1 + n_poly_added_point_num,
					r_mesh.t_RefVertex(r_mesh.r_Vertex_Pool().n_Size() - 1)); // note no modulo here!
				// add a new vertex to fix the t-junction

				++ n_poly_added_point_num;
				f_last_t = f_t;
			}
			n_tj_fix_num += r_edge_tjunc_list.size();
		}
		// loop over all polygon - edge pairs (should be sorted)

		if(p_prev_poly) {
			for(; n_prev_edge < n_orig_poly_vertex_num; ++ n_prev_edge)
				original_vertex_indices.push_back(n_prev_edge + n_poly_added_point_num);
			TurnPolygon(*p_prev_poly, original_vertex_indices,
				p_first_poly_tjunc_it, r_polygon_fixup_map.end());
		}

		return n_tj_fix_num;
	}

	/**
	 *	@brief inserts one of edge vertices to the polygon fixup map
	 *
	 *	@param[out] r_edge_map is reference to the edge map (filled with edges, is overwritten)
	 *	@param[in] r_mesh is the polygonal mesh to be hashed
	 *
	 *	@note This function throws std::bad_alloc.
	 */
	static void Insert_EdgeVertices(const TEdge &r_receiving_edge,
		_TyFixupMap &r_polygon_fixup_map, const TEdge &r_edge2, bool b_first_vertex,
		float f_vertex_dist_epsilon); // throw(std::bad_alloc)

	/**
	 *	@brief less-than operator functor for paranoid MSVC stl
	 */
	class CSmallerMinProj {
	public:
		inline bool operator ()(const TEdge &r_edge_a, const TEdge &r_edge_b) const
		{
			return r_edge_a.f_min_proj < r_edge_b.f_min_proj;
		}

		inline bool operator ()(const TEdge &r_edge_a, float f_ref) const
		{
			return r_edge_a.f_min_proj < f_ref;
		}

		inline bool operator ()(float f_ref, const TEdge &r_edge_a) const
		{
			return f_ref < r_edge_a.f_min_proj;
		}
	};

	/**
	 *	@brief less-than operator functor for g++ (unused at the moment)
	 */
	static inline bool b_SmallerMinProj(const TEdge &r_edge_a, const TEdge &r_edge_b)
	{
		return r_edge_a.f_min_proj < r_edge_b.f_min_proj;
	}

	/**
	 *	@brief less-than operator functor for g++ (unused at the moment)
	 */
	static inline bool b_SmallerMinProj(const TEdge &r_edge_a, float f_ref)
	{
		return r_edge_a.f_min_proj < f_ref;
	}

	/**
	 *	@brief less-than operator functor for g++ (unused at the moment)
	 */
	static inline bool b_SmallerMinProj(float f_ref, const TEdge &r_edge_a)
	{
		return f_ref < r_edge_a.f_min_proj;
	}
};

#endif // !__T_JUNCTION_REMOVAL_INCLUDED
