37template <
class VertexVector,
class Polygon>
56 template <
class TriangleList>
61 typedef typename VertexVector::value_type Vector;
63 Vector eval_orientation(
const Polygon& poly)
const;
68 const typename VertexVector::value_type& a,
69 const typename VertexVector::value_type& b,
70 const typename VertexVector::value_type& c,
71 const typename VertexVector::value_type& p,
72 bool debug =
false )
const;
75 const VertexVector& m_vv;
76 mutable Vector m_orientation;
79template <
class VertexVector,
class Polygon>
85template <
class VertexVector,
class Polygon>
86template <
class TriangleList>
90 size_t poly_size = poly.size();
97 m_orientation = eval_orientation(poly);
98 typename Polygon::const_iterator pi = poly.begin();
99 typename Polygon::const_iterator pe = poly.end();
108 while ( (p_i != p_e) && (poly_size > 3)) {
109 if (is_ear(p_i, cpoly,
false)) {
111 output.push_back(
typename TriangleList::value_type(**p_i->
succ, **p_i, **p_i->
prev));
121 if ((p_i == p_e) && (poly_size > 3)) {
126 while ( (p_i != p_e) && (poly_size > 3)) {
127 if (is_ear(p_i, cpoly,
true)) {
129 output.push_back(
typename TriangleList::value_type(**p_i->
succ, **p_i, **p_i->
prev));
140 output.push_back(
typename TriangleList::value_type(**p_i->
succ, **p_i, **p_i->
prev));
146template <
class VertexVector,
class Polygon>
147typename TPolyTriangulator<VertexVector, Polygon>::Vector
150 typename VertexVector::value_type result(0, 0, 0);
151 typename Polygon::const_iterator pb = poly.begin();
152 typename Polygon::const_iterator be = poly.end();
153 typename Polygon::const_iterator c1 = pb;
155 typename Polygon::const_iterator c2 = c1;
157 typename VertexVector::value_type a = m_vv[*pb];
159 while (c1 != be && c2 != be) {
160 result += (m_vv[*c1++] - a) ^ (m_vv[*c2++] - a);
166template <
class VertexVector,
class Polygon>
169 typename VertexVector::value_type a = m_vv[ **i->prev];
170 typename VertexVector::value_type b = m_vv[ **i];
171 typename VertexVector::value_type c = m_vv[ **i->succ];
172 typename VertexVector::value_type ab = a - b;
173 typename VertexVector::value_type cb = c - b;
174 typename VertexVector::value_type
cross = ab ^ cb;
175 const bool result =
dot(
cross, m_orientation) > 0;
179template <
class VertexVector,
class Polygon>
182 if (!is_convex(p, debug)) {
183 cvdebug() <<
"corner is concave\n";
187 typename VertexVector::value_type a = m_vv[ **p->prev];
188 typename VertexVector::value_type b = m_vv[ **p];
189 typename VertexVector::value_type c = m_vv[ **p->succ];
190 cvdebug() <<
"check triangle" << a << b << c <<
" = (" << **p->prev <<
"," << **p <<
"," << **p->succ <<
"\n";
191 typename CPoly::const_iterator i = cpoly.begin();
194 while (i != cpoly.end()) {
195 if (i != p && i != p->prev && i != p->succ)
196 if (!is_convex(i, debug) && is_inside(a, b, c, m_vv[ **i], debug)) {
197 cvdebug() <<
"point " << **i <<
":" << m_vv[ **i] <<
" is concave and inside\n";
207template <
class VertexVector,
class Polygon>
209 const typename VertexVector::value_type& a,
210 const typename VertexVector::value_type& b,
211 const typename VertexVector::value_type& c,
212 const typename VertexVector::value_type& p,
215 double abc = ((a - b) ^ (c - b)).norm() * 0.5;
216 double abp = ((a - p) ^ (b - p)).norm() * 0.5;
217 double acp = ((a - p) ^ (c - p)).norm() * 0.5;
218 double bcp = ((b - p) ^ (c - p)).norm() * 0.5;
219 const bool result = (abc >= abp + acp + bcp);
T cross(const T2DVector< T > &a, const T2DVector< T > &b)
T dot(const T2DVector< T > &a, const T2DVector< T > &b)
class to make a triangle mesh from a closed polygon
bool triangulate(TriangleList &output, const Polygon &poly) const
TPolyTriangulator(const VertexVector &vv)
#define NS_MIA_BEGIN
conveniance define to start the mia namespace
#define NS_MIA_END
conveniance define to end the mia namespace