triangulate_impl.h

一个开源的Flash 播放器,可以在Windows/Linux 上运行

	a_in_b_sum += vertex_left_test(cone_b[1], cone_b[2], cone_a[2]);

	int	b_in_a_sum = 0;
	b_in_a_sum += vertex_left_test(cone_a[0], cone_a[1], cone_b[0]);
	b_in_a_sum += vertex_left_test(cone_a[1], cone_a[2], cone_b[0]);
	b_in_a_sum += vertex_left_test(cone_a[0], cone_a[1], cone_b[2]);
	b_in_a_sum += vertex_left_test(cone_a[1], cone_a[2], cone_b[2]);

	// Eeek!  Need a better way of doing this...
	bool	a_in_b = false;
	if (a_in_b_sum >= 4)
	{
		assert(b_in_a_sum <= -2);
		a_in_b = true;
	}
	else if (a_in_b_sum == 3)
	{
		assert(b_in_a_sum <= 3);

		if (b_in_a_sum >= 3)
		{
			// Inconsistent (crossing cones).  No good.
			return false;
		}
		a_in_b = true;
	}
	else if (a_in_b_sum <= -4)
	{
		assert(b_in_a_sum >= 2);
		a_in_b = false;
	}
	else if (a_in_b_sum == -3)
	{
		assert(b_in_a_sum >= -3);

		if (b_in_a_sum <= -3)
		{
			// Inconsistent (crossing cones).  No good.
			return false;
		}
		a_in_b = false;
	}
	else
	{
		if (b_in_a_sum >= 4)
		{
			assert(a_in_b_sum <= -2);
			a_in_b = false;
		}
		else if (b_in_a_sum == 3)
		{
			a_in_b = false;
		}
		else if (b_in_a_sum <= -4)
		{
			assert(a_in_b_sum >= 2);
			a_in_b = true;
		}
		else if (b_in_a_sum == -3)
		{
			a_in_b = true;
		}
		else
		{
			// Inconsistent or coincident.  No good.
			return false;
		}
	}

	if (a_in_b)
	{
		assert(a_in_b);

		bool	v_in_a =
			(vertex_left_test(cone_a[0], cone_a[1], sorted_verts[v].m_v) > 0)
			&& (vertex_left_test(cone_a[1], cone_a[2], sorted_verts[v].m_v) > 0);
		if (v_in_a)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	else
	{
		bool	v_in_b =
			(vertex_left_test(cone_b[0], cone_b[1], sorted_verts[v].m_v) > 0)
			&& (vertex_left_test(cone_b[1], cone_b[2], sorted_verts[v].m_v) > 0);
		if (v_in_b)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
}


template<class coord_t>
bool	poly<coord_t>::any_edge_intersection(const array<vert_t>& sorted_verts, int external_vert, int my_vert)
// Return true if edge (external_vert,my_vert) intersects any edge in our poly.
{
	// Check the edge index for potentially overlapping edges.

	const vert_t*	pmv = &sorted_verts[my_vert];
	const vert_t*	pev = &sorted_verts[external_vert];

	assert(m_edge_index);

 	index_box<coord_t>	query_box(pmv->get_index_point());
	query_box.expand_to_enclose(pev->get_index_point());

	for (ib_iterator it = m_edge_index->begin(query_box);
	     ! it.at_end();
	     ++it)
	{
		int	vi = it->value;
		int	v_next = sorted_verts[vi].m_next;

		if (vi != my_vert)
		{
			if (sorted_verts[vi].m_v == sorted_verts[my_vert].m_v)
			{
				// Coincident verts.
				if (vert_can_see_cone_a(sorted_verts, external_vert, my_vert, vi) == false)
				{
					// Logical edge crossing.
					return true;
				}
			}
			else if (edges_intersect(sorted_verts, vi, v_next, external_vert, my_vert))
			{
				return true;
			}
		}
	}

	return false;
}


template<class coord_t>
bool	poly<coord_t>::ear_contains_reflex_vertex(const array<vert_t>& sorted_verts, int v0, int v1, int v2)
// Return true if any of this poly's reflex verts are inside the
// specified ear.  The definition of inside is: a reflex vertex in the
// interior of the triangle (v0,v1,v2), or on the segments [v1,v0) or
// [v1,v2).
{
	// Compute the bounding box of reflex verts we want to check.
	index_box<coord_t>	query_bound(sorted_verts[v0].get_index_point());
	query_bound.expand_to_enclose(index_point<coord_t>(sorted_verts[v1].m_v.x, sorted_verts[v1].m_v.y));
	query_bound.expand_to_enclose(index_point<coord_t>(sorted_verts[v2].m_v.x, sorted_verts[v2].m_v.y));

	for (ip_iterator it = m_reflex_point_index->begin(query_bound);
	     ! it.at_end();
	     ++it)
	{
		int	vk = it->value;

		const vert_t*	pvk = &sorted_verts[vk];
		if (pvk->m_poly_owner != this)
		{
			// Not part of this poly; ignore it.
			continue;
		}

		if (vk != v0 && vk != v1 && vk != v2
		    && query_bound.contains_point(index_point<coord_t>(pvk->m_v.x, pvk->m_v.y)))
		{
#if 0
			//xxxxxx debug hook
			if (v1 == 131 && vk == 132)
			{
				vk = vk;//xxxxx breakpoint here
			}
#endif

			int	v_next = pvk->m_next;
			int	v_prev = pvk->m_prev;

			if (pvk->m_v == sorted_verts[v1].m_v)
			{
				// Tricky case.  See section 4.3 in FIST paper.

				// Note: I'm explicitly considering convex vk in here, unlike FIST.
				// This is to handle the triple dupe case, where a loop validly comes
				// straight through our cone.
				//
				// Note: the triple-dupe case is technically not a valid poly, since
				// it contains a twist.
				//
				// @@ Fix this back to the FIST way?

				int	v_prev_left01 = vertex_left_test(
					sorted_verts[v0].m_v,
					sorted_verts[v1].m_v,
					sorted_verts[v_prev].m_v);
				int	v_next_left01 = vertex_left_test(
					sorted_verts[v0].m_v,
					sorted_verts[v1].m_v,
					sorted_verts[v_next].m_v);
				int	v_prev_left12 = vertex_left_test(
					sorted_verts[v1].m_v,
					sorted_verts[v2].m_v,
					sorted_verts[v_prev].m_v);
				int	v_next_left12 = vertex_left_test(
					sorted_verts[v1].m_v,
					sorted_verts[v2].m_v,
					sorted_verts[v_next].m_v);

				if ((v_prev_left01 > 0 && v_prev_left12 > 0)
				    || (v_next_left01 > 0 && v_next_left12 > 0))
				{
					// Local interior near vk intersects this
					// ear; ear is clearly not valid.
					return true;
				}

				// Check colinear case, where cones of vk and v1 overlap exactly.
				if ((v_prev_left01 == 0 && v_next_left12 == 0)
				    || (v_prev_left12 == 0 && v_next_left01 == 0))
				{
					// @@ TODO: there's a somewhat complex non-local area test that tells us
					// whether vk qualifies as a contained reflex vert.
					//
					// For the moment, deny the ear.
					//
					// The question is, is this test required for correctness?  Because it
					// seems pretty expensive to compute.  If it's not required, I think it's
					// better to always assume the ear is invalidated.

					//xxx
					//fprintf(stderr, "colinear case in ear_contains_reflex_vertex; returning true\n");

					return true;
				}
			}
			else
			{
				assert(pvk->m_convex_result < 0);
				if (vertex_in_ear(
					    pvk->m_v, sorted_verts[v0].m_v, sorted_verts[v1].m_v, sorted_verts[v2].m_v))
				{
					// Found one.
					return true;
				}
			}
		}
	}

	// Didn't find any qualifying verts.
	return false;
}


template<class coord_t>
bool	poly<coord_t>::vert_in_cone(const array<vert_t>& sorted_verts, int vert, int cone_v0, int cone_v1, int cone_v2)
// Returns true if vert is within the cone defined by [v0,v1,v2].
/*
//  (out)  v0
//        /
//    v1 <   (in)
//        \
//         v2
*/
{
	bool	acute_cone = vertex_left_test(sorted_verts[cone_v0].m_v, sorted_verts[cone_v1].m_v, sorted_verts[cone_v2].m_v) > 0;

	// Include boundary in our tests.
	bool	left_of_01 =
		vertex_left_test(sorted_verts[cone_v0].m_v, sorted_verts[cone_v1].m_v, sorted_verts[vert].m_v) >= 0;
	bool	left_of_12 =
		vertex_left_test(sorted_verts[cone_v1].m_v, sorted_verts[cone_v2].m_v, sorted_verts[vert].m_v) >= 0;

	if (acute_cone)
	{
		// Acute cone.  Cone is intersection of half-planes.
		return left_of_01 && left_of_12;
	}
	else
	{
		// Obtuse cone.  Cone is union of half-planes.
		return left_of_01 || left_of_12;
	}
}


template<class coord_t>
bool	poly<coord_t>::vert_is_duplicated(const array<vert_t>& sorted_verts, int vert)
// Return true if there's another vertex in this poly, coincident with vert.
{
	// Scan backwards.
	{for (int vi = vert - 1; vi >= 0; vi--)
	{
		if ((sorted_verts[vi].m_v == sorted_verts[vert].m_v) == false)
		{
			// No more coincident verts scanning backward.
			break;
		}
		if (sorted_verts[vi].m_poly_owner == this)
		{
			// Found a dupe vert.
			return true;
		}
	}}

	// Scan forwards.
	{for (int vi = vert + 1, n = sorted_verts.size(); vi < n; vi++)
	{
		if ((sorted_verts[vi].m_v == sorted_verts[vert].m_v) == false)
		{
			// No more coincident verts scanning forward.
			break;
		}
		if (sorted_verts[vi].m_poly_owner == this)
		{
			// Found a dupe vert.
			return true;
		}
	}}

	// Didn't find a dupe.
	return false;
}


//
// poly_env
//


template<class coord_t>
struct poly_env
// Struct that holds the state of a triangulation.
{
//data:
	array<poly_vert<coord_t> >	m_sorted_verts;
	array<poly<coord_t>*>	m_polys;

	index_box<coord_t>	m_bound;
	int	m_estimated_triangle_count;

//code:
	void	init(int path_count, const array<coord_t> paths[]);
	void	join_paths_into_one_poly();

	int	get_estimated_triangle_count() const { return m_estimated_triangle_count; }

	poly_env()
		:
		m_bound(index_point<coord_t>(0, 0), index_point<coord_t>(0, 0)),
		m_estimated_triangle_count(0)
	{
	}

	~poly_env()
	{
		// delete the polys that got new'd during init()
		for (int i = 0, n = m_polys.size(); i < n; i++)
		{
			delete m_polys[i];
		}
	}

private:
	// Internal helpers.
	void	join_paths_with_bridge(
		poly<coord_t>* main_poly,
		poly<coord_t>* sub_poly,
		int vert_on_main_poly,
		int vert_on_sub_poly);
	void	dupe_two_verts(int v0, int v1);
};


template<class coord_t>
void	poly_env<coord_t>::init(int path_count, const array<coord_t> paths[])
// Initialize our state, from the given set of paths.  Sort vertices
// and component polys.
{
	// Only call this on a fresh poly_env
	assert(m_sorted_verts.size() == 0);
	assert(m_polys.size() == 0);

	// Count total verts.
	int	vert_count = 0;
	for (int i = 0; i < path_count; i++)
	{
		vert_count += paths[i].size();
	}

	// Slight over-estimate; the true number depends on how many
	// of the paths are actually islands.
	m_estimated_triangle_count = vert_count /* - 2 * path_count */;

	// Collect the input verts and create polys for the input paths.
	m_sorted_verts.reserve(vert_count + (path_count - 1) * 2);	// verts, plus two duped verts for each path, for bridges
	m_polys.reserve(path_count);

	for (int i = 0; i < path_count; i++)
	{
		// Create a poly for this path.
		const array<coord_t>&	path = paths[i];

		if (path.size() < 3)
		{
			// Degenerate path, ignore it.
			continue;
		}

		poly<coord_t>*	p = new poly<coord_t>;
		m_polys.push_back(p);

		// Add this path's verts to our list.
		int	path_size = path.size();
		if (path.size() & 1)
		{
			// Bad input, odd number of coords.
			assert(0);
			fprintf(stderr, "path[%d] has odd number of coords (%d), dropping last value\n", i, path.size());//xxxx
			path_size--;
		}
		for (int j = 0; j < path_size; j += 2)	// vertex coords come in pairs.
		{
			int	prev_point = j - 2;
			if (j == 0) prev_point = path_size - 2;

			if (path[j] == path[prev_point] && path[j + 1] == path[prev_point + 1])
			{
				// Duplicate point; drop it.
				continue;
			}

			// Insert point.
			int	vert_index = m_sorted_verts.size();

			poly_vert<coord_t>	vert(path[j], path[j+1], p, vert_index);
			m_sorted_verts.push_back(vert);

			p->append_vert(&m_sorted_verts, vert_index);

			index_point<coord_t>	ip(vert.m_v.x, vert.m_v.y);
			if (vert_index == 0)
			{
				// Initialize the bounding box.
				m_bound.min = ip;
				m_bound.max = ip;
			}
			else
			{
				// Expand the bounding box.
				m_bound.expand_to_enclose(ip);
			}
			assert(m_bound.contains_point(ip));
		}
		assert(p->is_valid(m_sorted_verts));

		if (p->m_vertex_count == 0)
		{
			// This path was degenerate; kill it.
			delete p;
			m_polys.pop_back();
		}
	}

	// Sort the vertices.
	qsort(&m_sorted_verts[0], m_sorted_verts.size(), sizeof(m_sorted_verts[0]), compare_vertices<coord_t>);
	assert(m_sorted_verts.size() <= 1
	       || compare_vertices<coord_t>((void*) &m_sorted_verts[0], (void*) &m_sorted_verts[1]) <= 0);	// check order

	// Remap the vertex indices, so that the polys and the
	// sorted_verts have the correct, sorted, indices.  We can
	// then use vert indices to judge the left/right relationship
	// of two verts.
	array<int>	vert_remap;	// vert_remap[i] == new index of original vert[i]
	vert_remap.resize(m_sorted_verts.size());
	for (int i = 0, n = m_sorted_verts.size(); i < n; i++)
	{
		int	new_index = i;