PolygonTriangulator::Polygon Class Reference

Collaboration diagram for PolygonTriangulator::Polygon:

Public Member Functions
	Polygon (const std::vector< double > &x, const std::vector< double > &y)
	~Polygon ()
void	partition2Monotone ()
void	searchMonotones ()
void	triangulation ()
const Triangles *	triangles ()
internal_poltrig::PointbaseMap &	points ()
internal_poltrig::LineMap &	edges ()

Private Member Functions
void	set_contour (const std::vector< double > &x, const std::vector< double > &y)
void	initializate ()
unsigned int	prev (const unsigned int &i)
unsigned int	next (const unsigned int &i)
void	handleStartVertex (const unsigned int &)
void	handleEndVertex (const unsigned int &)
void	handleSplitVertex (const unsigned int &)
void	handleMergeVertex (const unsigned int &)
void	handleRegularVertexUp (const unsigned int &)
void	handleRegularVertexDown (const unsigned int &)
void	addDiagonal (const unsigned int &i, const unsigned int &j)
double	angleCosb (double *A, double *B, double *C)
unsigned int	selectNextEdge (internal_poltrig::Linebase *edge)
void	triangulateMonotone (internal_poltrig::Monopoly &mpoly)
void	init_vertices_and_lines ()

Private Attributes
long int	m_l_id
internal_poltrig::PQueue	m_qpoints
internal_poltrig::EdgeBST	m_edgebst
internal_poltrig::Monopolys	m_mpolys
Triangles	m_triangles
internal_poltrig::AdjEdgeMap	m_startAdjEdgeMap
internal_poltrig::LineMap	m_diagonals
unsigned int	m_ncontours
std::vector< unsigned int >	m_nVertices
internal_poltrig::PointbaseMap	m_points
internal_poltrig::LineMap	m_edges
double	m_xmin
double	m_xmax
double	m_ymin
double	m_ymax

Detailed Description

Definition at line 1418 of file PolygonTriangulator.cxx.

Constructor & Destructor Documentation

Polygon()

PolygonTriangulator::Polygon::Polygon	(	const std::vector< double > &	x,
		const std::vector< double > &	y
	)

Definition at line 1552 of file PolygonTriangulator.cxx.

{
  m_l_id = 0;
  m_ncontours=0;
 
  m_xmin = m_ymin = std::numeric_limits<double>::infinity();
  m_xmax = m_ymax = - std::numeric_limits<double>::infinity();
 
 
  set_contour(x,y);
  init_vertices_and_lines();
  initializate();
}

~Polygon()

PolygonTriangulator::Polygon::~Polygon

(

)

Definition at line 1569 of file PolygonTriangulator.cxx.

{
  //clear all dynamic allocated memory
  internal_poltrig::PointbaseMap::iterator itp=m_points.begin();
  for(; itp!=m_points.end(); ++itp)
    {
      delete itp->second;
    }
 
  internal_poltrig::LineMap::iterator itl=m_edges.begin();
  for(; itl!=m_edges.end(); ++itl)
    {
      delete itl->second;
    }
 
}

Member Function Documentation

addDiagonal()

void PolygonTriangulator::Polygon::addDiagonal ( const unsigned int &  i, const unsigned int &  j  )

private

Definition at line 1679 of file PolygonTriangulator.cxx.

{
  internal_poltrig::Type type=internal_poltrig::INSERT;
  internal_poltrig::Linebase* diag=new internal_poltrig::Linebase(m_points[i], m_points[j], type,m_l_id);
  m_edges[diag->id()]=diag;
 
  m_startAdjEdgeMap[i].insert(diag->id());
  m_startAdjEdgeMap[j].insert(diag->id());
 
  m_diagonals[diag->id()]=diag;
 
}

angleCosb()

double PolygonTriangulator::Polygon::angleCosb ( double *  A, double *  B, double *  C  )

private

Definition at line 1847 of file PolygonTriangulator.cxx.

{
  double dxab = pa[0] - pb[0];
  double dyab = pa[1] - pb[1];
 
  double dxcb = pc[0] - pb[0];
  double dycb = pc[1] - pb[1];
 
  double dxab2 = dxab * dxab;
  double dyab2 = dyab * dyab;
  double dxcb2 = dxcb * dxcb;
  double dycb2 = dycb * dycb;
  double ab = dxab2 + dyab2;
  double cb = dxcb2 + dycb2;
 
  double cosb = dxab * dxcb + dyab * dycb;
  double denom = sqrt( ab * cb);
 
  cosb/=denom;
 
  return cosb;
}

edges()

internal_poltrig::LineMap& PolygonTriangulator::Polygon::edges ( )

inline

Definition at line 1434 of file PolygonTriangulator.cxx.

{ return m_edges; }

handleEndVertex()

void PolygonTriangulator::Polygon::handleEndVertex ( const unsigned int &  i )

private

Definition at line 1709 of file PolygonTriangulator.cxx.

{
  double y=m_points[i]->y;
  m_edgebst.InOrder(internal_poltrig::UpdateKey, y);
 
  unsigned int previ=prev(i);
  internal_poltrig::Linebase* edge=m_edges[previ];
  unsigned int helper=m_edges[previ]->helper();
 
 
  if(m_points[helper]->type==internal_poltrig::MERGE) addDiagonal(i, helper);
  m_edgebst.Delete(edge->keyValue());
 
}

handleMergeVertex()

void PolygonTriangulator::Polygon::handleMergeVertex ( const unsigned int &  i )

private

Definition at line 1748 of file PolygonTriangulator.cxx.

{
  double x=m_points[i]->x, y=m_points[i]->y;
  m_edgebst.InOrder(internal_poltrig::UpdateKey, y);
 
  unsigned int previ=prev(i);
  unsigned int helper=m_edges[previ]->helper();
  if (m_points[helper]->type==internal_poltrig::MERGE) addDiagonal(i, helper);
  m_edgebst.Delete(m_edges[previ]->keyValue());
 
  internal_poltrig::BTreeNode<internal_poltrig::Linebase*, double>*  leftnode;
  m_edgebst.FindMaxSmallerThan(x, leftnode);
  internal_poltrig::Linebase* leftedge=leftnode->data();
 
  helper=leftedge->helper();
  if(m_points[helper]->type==internal_poltrig::MERGE) addDiagonal(i, helper);
 
  leftedge->setHelper(i);
}

handleRegularVertexDown()

void PolygonTriangulator::Polygon::handleRegularVertexDown ( const unsigned int &  i )

private

Definition at line 1771 of file PolygonTriangulator.cxx.

{
  double y=m_points[i]->y;
  m_edgebst.InOrder(internal_poltrig::UpdateKey, y);
 
  unsigned int previ=prev(i);
  unsigned int helper=m_edges[previ]->helper();
  if(m_points[helper]->type==internal_poltrig::MERGE) addDiagonal(i, helper);
 
  m_edgebst.Delete(m_edges[previ]->keyValue());
  m_edges[i]->setHelper(i);
  m_edges[i]->setKeyValue(y);
  m_edgebst.Insert(m_edges[i]);
 
}

handleRegularVertexUp()

void PolygonTriangulator::Polygon::handleRegularVertexUp ( const unsigned int &  i )

private

Definition at line 1790 of file PolygonTriangulator.cxx.

{
  double x=m_points[i]->x, y=m_points[i]->y;
  m_edgebst.InOrder(internal_poltrig::UpdateKey, y);
 
  internal_poltrig::BTreeNode<internal_poltrig::Linebase*, double>*  leftnode;
  m_edgebst.FindMaxSmallerThan(x, leftnode);
 
  internal_poltrig::Linebase* leftedge=leftnode->data();
 
  unsigned int helper=leftedge->helper();
  if(m_points[helper]->type==internal_poltrig::MERGE) addDiagonal(i, helper);
  leftedge->setHelper(i);
 
}

handleSplitVertex()

void PolygonTriangulator::Polygon::handleSplitVertex ( const unsigned int &  i )

private

Definition at line 1727 of file PolygonTriangulator.cxx.

{
  double x=m_points[i]->x, y=m_points[i]->y;
  m_edgebst.InOrder(internal_poltrig::UpdateKey, y);
 
  internal_poltrig::BTreeNode<internal_poltrig::Linebase*, double>*  leftnode;
  m_edgebst.FindMaxSmallerThan(x, leftnode);
  internal_poltrig::Linebase* leftedge=leftnode->data();
 
  unsigned int helper=leftedge->helper();
  addDiagonal(i, helper);
 
  leftedge->setHelper(i);
  m_edges[i]->setHelper(i);
  m_edges[i]->setKeyValue(y);
  m_edgebst.Insert(m_edges[i]);
}

handleStartVertex()

void PolygonTriangulator::Polygon::handleStartVertex ( const unsigned int &  i )

private

Definition at line 1695 of file PolygonTriangulator.cxx.

{
  double y=m_points[i]->y;
  m_edgebst.InOrder(internal_poltrig::UpdateKey, y);
 
  m_edges[i]->setHelper(i);
  m_edges[i]->setKeyValue(y);
  m_edgebst.Insert(m_edges[i]);
 
}

init_vertices_and_lines()

void PolygonTriangulator::Polygon::init_vertices_and_lines ( )

private

Definition at line 1488 of file PolygonTriangulator.cxx.

{
  int sid,eid;
  int num=0;
 
  internal_poltrig::Type type;
 
  for(unsigned j=0; j<m_ncontours; ++j)
    {
      for(unsigned i=1; i<=m_nVertices[j]; ++i)//fixme: 0-based?
    {
          sid=num+i;
          eid=(i==m_nVertices[j])?num+1:num+i+1;
      type = internal_poltrig::INPUT;
          internal_poltrig::Linebase* line=new internal_poltrig::Linebase(m_points[sid], m_points[eid], type,m_l_id);
      m_edges[m_l_id]=line;
        }
      num+=m_nVertices[j];
    }
 
  int sum=0;
  for(unsigned int i=0; i<m_ncontours; ++i)
    {
      sum+= m_nVertices[i];
      m_nVertices[i]=sum;
    }
 
}

initializate()

void PolygonTriangulator::Polygon::initializate ( )

private

Definition at line 1635 of file PolygonTriangulator.cxx.

{
  internal_poltrig::PointbaseMap::iterator it=m_points.begin();
  for(; it!=m_points.end(); ++it)
    {
      int id=it->first;
      int idp=prev(id);
      int idn=next(id);
      internal_poltrig::Pointbase p=*m_points[id], pnext=*m_points[idn], pprev=*m_points[idp];
 
      if( p > pnext && pprev > p )
    m_points[id]->type=internal_poltrig::REGULAR_DOWN;
      else if (p > pprev && pnext > p)
    m_points[id]->type=internal_poltrig::REGULAR_UP;
      else
    {
      double pa[2], pb[2], pc[2];
 
      pa[0]=m_points[idp]->x;
      pa[1]=m_points[idp]->y;
 
      pb[0]=m_points[id]->x;
      pb[1]=m_points[id]->y;
 
      pc[0]=m_points[idn]->x;
      pc[1]=m_points[idn]->y;
 
      double area=internal_poltrig::orient2d(pa,pb,pc);
 
      if( pprev > p && pnext > p ) m_points[id]->type=(area >0) ? internal_poltrig::END: internal_poltrig::MERGE ;
      if( pprev < p && pnext < p ) m_points[id]->type=(area >0) ? internal_poltrig::START : internal_poltrig::SPLIT;
 
    }
 
      m_qpoints.push(*(it->second));
 
      m_startAdjEdgeMap[id].insert(id);
 
    }
}

next()

unsigned int PolygonTriangulator::Polygon::next ( const unsigned int &  i )

private

Definition at line 1608 of file PolygonTriangulator.cxx.

{
  unsigned int j(0),prevLoop(0),currentLoop(0);
 
  while ( i > m_nVertices[currentLoop] )
    {
      prevLoop=currentLoop;
      ++currentLoop;
    }
 
  if( i < m_nVertices[currentLoop] ) j=i+1;
  else if ( i==m_nVertices[currentLoop] )
    {
      if( currentLoop==0) j=1;
      else j=m_nVertices[prevLoop]+1;
    }
 
  return j;
}

partition2Monotone()

void PolygonTriangulator::Polygon::partition2Monotone

(

)

Definition at line 1809 of file PolygonTriangulator.cxx.

{
 
  if(m_qpoints.top().type!=internal_poltrig::START)
    {
      std::cout<<"Please check your input polygon:\n1)orientations?\n2)duplicated points?\n";
      exit(1);
    }
 
  while(!m_qpoints.empty())
    {
      internal_poltrig::Pointbase vertex=m_qpoints.top();
      m_qpoints.pop();
      unsigned int id=vertex.id;
 
      switch(vertex.type)
    {
    case internal_poltrig::START:        handleStartVertex(id);       break;
    case internal_poltrig::END:          handleEndVertex(id);         break;
    case internal_poltrig::MERGE:        handleMergeVertex(id);       break;
    case internal_poltrig::SPLIT:        handleSplitVertex(id);       break;
    case internal_poltrig::REGULAR_UP:   handleRegularVertexUp(id);   break;
    case internal_poltrig::REGULAR_DOWN: handleRegularVertexDown(id); break;
    default:
      std::cout<<"No duplicated points please!\n";
      exit(1); break;
    }
    }
}

points()

internal_poltrig::PointbaseMap& PolygonTriangulator::Polygon::points ( )

inline

Definition at line 1433 of file PolygonTriangulator.cxx.

{ return m_points; }

prev()

unsigned int PolygonTriangulator::Polygon::prev ( const unsigned int &  i )

private

Definition at line 1589 of file PolygonTriangulator.cxx.

{
  unsigned int j(0),prevLoop(0),currentLoop(0);
 
  while ( i > m_nVertices[currentLoop] )
    {
      prevLoop=currentLoop;
      ++currentLoop;
    }
 
  if( i==1 || (i==m_nVertices[prevLoop]+1) ) j=m_nVertices[currentLoop];
  else if( i <= m_nVertices[currentLoop] ) j=i-1;
 
  return j;
}

searchMonotones()

void PolygonTriangulator::Polygon::searchMonotones

(

)

Definition at line 1916 of file PolygonTriangulator.cxx.

{
  internal_poltrig::LineMap edges=m_edges;
 
  while( edges.size() > m_diagonals.size() )
    {
      internal_poltrig::Monopoly poly;
      internal_poltrig::LineMap::iterator it=edges.begin();
      internal_poltrig::Pointbase* startp=it->second->endPoint(0);
      internal_poltrig::Pointbase* endp=0;
      internal_poltrig::Linebase*  next=it->second;
 
      poly.push_back(startp->id);
 
      for(;;)
    {
      endp=next->endPoint(1);
      if(next->type()!=internal_poltrig::INSERT)
        {
          edges.erase(next->id());
          m_startAdjEdgeMap[next->endPoint(0)->id].erase(next->id());
        }
      if(endp==startp) break;
      poly.push_back(endp->id);
 
      unsigned int nexte=selectNextEdge(next);
 
      if(nexte==0)
        {
          std::cout<<"Please check your input polygon:\n";
          std::cout<<"1)orientations?\n2)with duplicated points?\n3)is a simple one?\n";
          exit(1);
        }
      //assert( nexte > 0);
      next=edges[nexte];
      if(next->endPoint(0) !=endp ) next->reverse();
    }
 
      m_mpolys.push_back(poly);
    }
}

selectNextEdge()

unsigned int PolygonTriangulator::Polygon::selectNextEdge ( internal_poltrig::Linebase *  edge )

private

Definition at line 1874 of file PolygonTriangulator.cxx.

{
 
  unsigned int eid= edge->endPoint(1)->id;
  std::set<unsigned int> edges=m_startAdjEdgeMap[eid];
  assert(!edges.empty());
 
  unsigned int nexte=0;
  if( edges.size() == 1 )  nexte=*(edges.begin());
  else if( edges.size() > 1 )
    {
      unsigned int nexte_ccw(0), nexte_cw(0);
      double max=-2.0,min=2.0;
 
 
      std::set<unsigned int>::iterator it=edges.begin();
      for(; it!=edges.end(); ++it)
    {
      if(*it==edge->id()) continue;
      double A[2], B[2], C[2];
      A[0]=edge->endPoint(0)->x;        A[1]=edge->endPoint(0)->y;
      B[0]=edge->endPoint(1)->x;        B[1]=edge->endPoint(1)->y;
 
      if(edge->endPoint(1)!=m_edges[*it]->endPoint(0)) m_edges[*it]->reverse();
      C[0]=m_edges[*it]->endPoint(1)->x; C[1]=m_edges[*it]->endPoint(1)->y;
 
      double area=internal_poltrig::orient2d(A, B, C);
      double cosb=angleCosb(A, B, C);
 
      if( area > 0 && max < cosb ) { nexte_ccw=*it; max=cosb; }
      else if( min > cosb ) { nexte_cw=*it; min=cosb; }
    }
 
      nexte = (nexte_ccw!=0) ? nexte_ccw : nexte_cw;
    }
 
  return nexte;
}

set_contour()

void PolygonTriangulator::Polygon::set_contour ( const std::vector< double > &  x, const std::vector< double > &  y  )

private

Definition at line 1521 of file PolygonTriangulator.cxx.

{
  assert(x.size()==y.size());
 
  m_nVertices.push_back( x.size() );
  unsigned int i = m_points.size()+1/*1*/;//fixme: get rid of the +1 ?
  double xx,yy;
  internal_poltrig::Type type;
  for (unsigned int j = 0; j < m_nVertices[m_ncontours]; ++j, ++i)
    {
      xx=x.at(j);
      yy=y.at(j);
      type=internal_poltrig::INPUT;
      internal_poltrig::Pointbase* point=new internal_poltrig::Pointbase(i,xx,yy,type);
      if(xx > m_xmax ) m_xmax=xx;
      if(xx < m_xmin ) m_xmin=xx;
      if(yy > m_ymax ) m_ymax=yy;
      if(yy < m_ymin ) m_ymin=yy;
      m_points[i]=point;
    }
 
  ++m_ncontours;
 
}

triangles()

const Triangles* PolygonTriangulator::Polygon::triangles ( )

inline

Definition at line 1431 of file PolygonTriangulator.cxx.

{ return &m_triangles; }

triangulateMonotone()

void PolygonTriangulator::Polygon::triangulateMonotone ( internal_poltrig::Monopoly &  mpoly )

private

Definition at line 1962 of file PolygonTriangulator.cxx.

{
  internal_poltrig::PQueue qvertex;
  internal_poltrig::Monopoly::iterator it=mpoly.begin(), itnext;
  for(; itnext=it, it!=mpoly.end(); ++it)
    {
      ++itnext;
      if(itnext==mpoly.end()) itnext=mpoly.begin();
      internal_poltrig::Pointbase point=*m_points[*it], pointnext=*m_points[*itnext];
      point.left=(point > pointnext)? true:false;
      qvertex.push(point);
    }
 
  std::stack<internal_poltrig::Pointbase> spoint;
  for(int i=0; i<2; ++i) { spoint.push(qvertex.top()); qvertex.pop(); }
 
  while ( qvertex.size() > 1 )
    {
      internal_poltrig::Pointbase topQueuePoint=qvertex.top();
      internal_poltrig::Pointbase topStackPoint=spoint.top();
 
      if(topQueuePoint.left!=topStackPoint.left)
    {
      while ( spoint.size()  > 1 )
        {
          internal_poltrig::Pointbase p1=spoint.top();
          spoint.pop();
          internal_poltrig::Pointbase p2=spoint.top();
          Triangle v(3);
          v[0]=topQueuePoint.id;
          v[1]=p1.id;
          v[2]=p2.id;
          sort(v.begin(),v.end());//TK
          m_triangles.push_back(v);
 
        }
      spoint.pop();
      spoint.push(topStackPoint);
      spoint.push(topQueuePoint);
    }
      else
    {
      while( spoint.size() > 1 )
        {
          internal_poltrig::Pointbase stack1Point=spoint.top();
          spoint.pop();
          internal_poltrig::Pointbase stack2Point=spoint.top();
          spoint.push(stack1Point);
          double pa[2], pb[2], pc[2];
          pa[0]=topQueuePoint.x; pa[1]=topQueuePoint.y;
          pb[0]=stack2Point.x;   pb[1]=stack2Point.y;
          pc[0]=stack1Point.x;   pc[1]=stack1Point.y;
 
          double area=internal_poltrig::orient2d(pa,pb,pc);
          bool   left=stack1Point.left;
          if( (area > 0 && left) || (area < 0 && !left ) )
            {
          Triangle v(3);
          v[0]=topQueuePoint.id;
          v[1]=stack2Point.id;
          v[2]=stack1Point.id;
          sort(v.begin(),v.end());//TK
          m_triangles.push_back(v);
          spoint.pop();
            } else break;
        }
 
      spoint.push(topQueuePoint);
 
    }
 
      qvertex.pop();
 
    }
 
  internal_poltrig::Pointbase lastQueuePoint=qvertex.top();
  while( spoint.size() !=1 )
    {
      internal_poltrig::Pointbase topPoint=spoint.top();
      spoint.pop();
      internal_poltrig::Pointbase top2Point=spoint.top();
 
      Triangle v(3);
      v[0]=lastQueuePoint.id;
      v[1]=topPoint.id;
      v[2]=top2Point.id;
      sort(v.begin(),v.end());//TK
      m_triangles.push_back(v);
    }
}

triangulation()

void PolygonTriangulator::Polygon::triangulation

(

)

Definition at line 2056 of file PolygonTriangulator.cxx.

{
  partition2Monotone();
  searchMonotones();
  internal_poltrig::Monopolys::iterator it=m_mpolys.begin();
  for(; it!=m_mpolys.end(); ++it)
    triangulateMonotone(*it);
}

Member Data Documentation

m_diagonals

internal_poltrig::LineMap PolygonTriangulator::Polygon::m_diagonals

private

Definition at line 1475 of file PolygonTriangulator.cxx.

m_edgebst

internal_poltrig::EdgeBST PolygonTriangulator::Polygon::m_edgebst

private

Definition at line 1469 of file PolygonTriangulator.cxx.

m_edges

internal_poltrig::LineMap PolygonTriangulator::Polygon::m_edges

private

Definition at line 1482 of file PolygonTriangulator.cxx.

m_l_id

long int PolygonTriangulator::Polygon::m_l_id

private

Definition at line 1438 of file PolygonTriangulator.cxx.

m_mpolys

internal_poltrig::Monopolys PolygonTriangulator::Polygon::m_mpolys

private

Definition at line 1470 of file PolygonTriangulator.cxx.

m_ncontours

unsigned int PolygonTriangulator::Polygon::m_ncontours

private

Definition at line 1479 of file PolygonTriangulator.cxx.

m_nVertices

std::vector<unsigned int> PolygonTriangulator::Polygon::m_nVertices

private

Definition at line 1480 of file PolygonTriangulator.cxx.

m_points

internal_poltrig::PointbaseMap PolygonTriangulator::Polygon::m_points

private

Definition at line 1481 of file PolygonTriangulator.cxx.

m_qpoints

internal_poltrig::PQueue PolygonTriangulator::Polygon::m_qpoints

private

Definition at line 1468 of file PolygonTriangulator.cxx.

m_startAdjEdgeMap

internal_poltrig::AdjEdgeMap PolygonTriangulator::Polygon::m_startAdjEdgeMap

private

Definition at line 1474 of file PolygonTriangulator.cxx.

m_triangles

Triangles PolygonTriangulator::Polygon::m_triangles

private

Definition at line 1471 of file PolygonTriangulator.cxx.

m_xmax

double PolygonTriangulator::Polygon::m_xmax

private

Definition at line 1483 of file PolygonTriangulator.cxx.

m_xmin

double PolygonTriangulator::Polygon::m_xmin

private

Definition at line 1483 of file PolygonTriangulator.cxx.

m_ymax

double PolygonTriangulator::Polygon::m_ymax

private

Definition at line 1483 of file PolygonTriangulator.cxx.

m_ymin

double PolygonTriangulator::Polygon::m_ymin

private

Definition at line 1483 of file PolygonTriangulator.cxx.

---

The documentation for this class was generated from the following file:

• PolygonTriangulator.cxx