internal_poltrig Namespace Reference

Classes
class	BTreeNode
class	Linebase
class	Pointbase
class	SplayTree

Typedefs
typedef std::map< unsigned int, Pointbase * >	PointbaseMap
typedef std::map< unsigned int, Linebase * >	LineMap
typedef std::priority_queue< Pointbase >	PQueue
typedef SplayTree< Linebase *, double >	EdgeBST
typedef std::list< unsigned int >	Monopoly
typedef std::list< Monopoly >	Monopolys
typedef std::vector< unsigned int >	Triangle
typedef std::list< Triangle >	Triangles
typedef std::map< unsigned int, std::set< unsigned int > >	AdjEdgeMap

Enumerations
enum	Type {   UNKNOWN, INPUT, INSERT, START,   END, MERGE, SPLIT, REGULAR_UP,   REGULAR_DOWN }

Functions
int	fast_expansion_sum_zeroelim (const int &elen, REAL *e, const int &flen, REAL *f, REAL *h)
REAL	estimate (const int &elen, REAL *e)
REAL	orient2dadapt (REAL *pa, REAL *pb, REAL *pc, const REAL &detsum)
REAL	orient2d (REAL *pa, REAL *pb, REAL *pc)
double	orient2d (double *pa, double *pb, double *pc)
double	dist_sqr (const Pointbase &sp, const Pointbase &ep)
double	dist_sqr (double *pa, double *pb)
void	UpdateKey (BTreeNode< Linebase *, double > *node, double y)
bool	operator== (const Pointbase &pa, const Pointbase &pb)
bool	operator> (const Pointbase &pa, const Pointbase &pb)
bool	operator< (const Pointbase &pa, const Pointbase &pb)
bool	operator!= (const Pointbase &pa, const Pointbase &pb)

Typedef Documentation

AdjEdgeMap

typedef std::map<unsigned int, std::set<unsigned int> > internal_poltrig::AdjEdgeMap

Definition at line 129 of file PolygonTriangulator.cxx.

EdgeBST

typedef SplayTree<Linebase*, double> internal_poltrig::EdgeBST

Definition at line 124 of file PolygonTriangulator.cxx.

LineMap

typedef std::map<unsigned int, Linebase*> internal_poltrig::LineMap

Definition at line 122 of file PolygonTriangulator.cxx.

Monopoly

typedef std::list<unsigned int> internal_poltrig::Monopoly

Definition at line 125 of file PolygonTriangulator.cxx.

Monopolys

typedef std::list<Monopoly> internal_poltrig::Monopolys

Definition at line 126 of file PolygonTriangulator.cxx.

PointbaseMap

typedef std::map<unsigned int, Pointbase*> internal_poltrig::PointbaseMap

Definition at line 121 of file PolygonTriangulator.cxx.

PQueue

typedef std::priority_queue<Pointbase> internal_poltrig::PQueue

Definition at line 123 of file PolygonTriangulator.cxx.

Triangle

typedef std::vector<unsigned int> internal_poltrig::Triangle

Definition at line 127 of file PolygonTriangulator.cxx.

Triangles

typedef std::list<Triangle> internal_poltrig::Triangles

Definition at line 128 of file PolygonTriangulator.cxx.

Enumeration Type Documentation

Type

enum internal_poltrig::Type

Enumerator
UNKNOWN
INPUT
INSERT
START
END
MERGE
SPLIT
REGULAR_UP
REGULAR_DOWN

Definition at line 115 of file PolygonTriangulator.cxx.

{ UNKNOWN, INPUT, INSERT, START, END, MERGE, SPLIT, REGULAR_UP, REGULAR_DOWN};

Function Documentation

dist_sqr() [1/2]

double internal_poltrig::dist_sqr	(	const Pointbase &	sp,
		const Pointbase &	ep
	)

Definition at line 1312 of file PolygonTriangulator.cxx.

  {
    return sqr(sp.x-ep.x)+sqr(sp.y-ep.y);
  }

dist_sqr() [2/2]

double internal_poltrig::dist_sqr	(	double *	pa,
		double *	pb
	)

Definition at line 1320 of file PolygonTriangulator.cxx.

  {
    return sqr(pa[0]-pb[0])+sqr(pa[1]-pb[1]);
  }

estimate()

REAL internal_poltrig::estimate	(	const int &	elen,
		REAL *	e
	)

Definition at line 454 of file PolygonTriangulator.cxx.

  {
    REAL Q;
    int eindex;
 
    Q = e[0];
    for (eindex = 1; eindex < elen; ++eindex) {
      Q += e[eindex];
    }
    return Q;
  }

fast_expansion_sum_zeroelim()

int internal_poltrig::fast_expansion_sum_zeroelim	(	const int &	elen,
		REAL *	e,
		const int &	flen,
		REAL *	f,
		REAL *	h
	)

Definition at line 375 of file PolygonTriangulator.cxx.

  {
    REAL Q;
    INEXACT REAL Qnew;
    INEXACT REAL hh;
    INEXACT REAL bvirt;
    REAL avirt, bround, around;
    int eindex, findex, hindex;
    REAL enow, fnow;
 
    enow = e[0];
    fnow = f[0];
    eindex = findex = 0;
    if ((fnow > enow) == (fnow > -enow)) {
      Q = enow;
      enow = e[++eindex];
    } else {
      Q = fnow;
      fnow = f[++findex];
    }
    hindex = 0;
    if ((eindex < elen) && (findex < flen)) {
      if ((fnow > enow) == (fnow > -enow)) {
    Fast_Two_Sum(enow, Q, Qnew, hh);
    enow = e[++eindex];
      } else {
    Fast_Two_Sum(fnow, Q, Qnew, hh);
    fnow = f[++findex];
      }
      Q = Qnew;
      if (hh != 0.0) {
    h[hindex++] = hh;
      }
      while ((eindex < elen) && (findex < flen)) {
    if ((fnow > enow) == (fnow > -enow)) {
      Two_Sum(Q, enow, Qnew, hh);
      enow = e[++eindex];
    } else {
      Two_Sum(Q, fnow, Qnew, hh);
      fnow = f[++findex];
    }
    Q = Qnew;
    if (hh != 0.0) {
      h[hindex++] = hh;
    }
      }
    }
    while (eindex < elen) {
      Two_Sum(Q, enow, Qnew, hh);
      enow = e[++eindex];
      Q = Qnew;
      if (hh != 0.0) {
    h[hindex++] = hh;
      }
    }
    while (findex < flen) {
      Two_Sum(Q, fnow, Qnew, hh);
      fnow = f[++findex];
      Q = Qnew;
      if (hh != 0.0) {
    h[hindex++] = hh;
      }
    }
    if ((Q != 0.0) || (hindex == 0)) {
      h[hindex++] = Q;
    }
    return hindex;
  }

operator!=()

bool internal_poltrig::operator!=	(	const Pointbase &	pa,
		const Pointbase &	pb
	)

Definition at line 1363 of file PolygonTriangulator.cxx.

  {
    return !(pa.x==pb.x && pa.y==pb.y);
  }

operator<()

bool internal_poltrig::operator<	(	const Pointbase &	pa,
		const Pointbase &	pb
	)

Definition at line 1357 of file PolygonTriangulator.cxx.

  {
    return( (pa.y < pb.y) || ( (pa.y==pb.y) && (pa.x > pb.x)) );
  }

operator==()

bool internal_poltrig::operator==	(	const Pointbase &	pa,
		const Pointbase &	pb
	)

Definition at line 1345 of file PolygonTriangulator.cxx.

  {
    return (pa.x==pb.x && pa.y==pb.y);
  }

operator>()

bool internal_poltrig::operator>	(	const Pointbase &	pa,
		const Pointbase &	pb
	)

Definition at line 1351 of file PolygonTriangulator.cxx.

  {
    return( (pa.y > pb.y) || ( (pa.y==pb.y) && (pa.x < pb.x)) );
  }

orient2d() [1/2]

double internal_poltrig::orient2d	(	double *	pa,
		double *	pb,
		double *	pc
	)

orient2d() [2/2]

REAL internal_poltrig::orient2d	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc
	)

Definition at line 574 of file PolygonTriangulator.cxx.

  {
    REAL detleft, detright, det;
    REAL detsum, errbound;
 
    detleft = (pa[0] - pc[0]) * (pb[1] - pc[1]);
    detright = (pa[1] - pc[1]) * (pb[0] - pc[0]);
    det = detleft - detright;
 
    if (detleft > 0.0) {
      if (detright <= 0.0) {
    return det;
      } else {
    detsum = detleft + detright;
      }
    } else if (detleft < 0.0) {
      if (detright >= 0.0) {
    return det;
      } else {
    detsum = -detleft - detright;
      }
    } else {
      return det;
    }
 
    //    errbound = ccwerrboundA * detsum;
    errbound = detsum;
    if ((det >= errbound) || (-det >= errbound)) {
      return det;
    }
 
    return orient2dadapt(pa, pb, pc, detsum);
  }

orient2dadapt()

REAL internal_poltrig::orient2dadapt	(	REAL *	pa,
		REAL *	pb,
		REAL *	pc,
		const REAL &	detsum
	)

Definition at line 492 of file PolygonTriangulator.cxx.

  {
    INEXACT REAL acx, acy, bcx, bcy;
    REAL acxtail, acytail, bcxtail, bcytail;
    INEXACT REAL detleft, detright;
    REAL detlefttail, detrighttail;
    REAL det, errbound;
    REAL B[4], C1[8], C2[12], D[16];
    INEXACT REAL B3;
    int C1length, C2length, Dlength;
    REAL u[4];
    INEXACT REAL u3;
    INEXACT REAL s1, t1;
    REAL s0, t0;
 
    INEXACT REAL bvirt;
    REAL avirt, bround, around;
    INEXACT REAL c;
    INEXACT REAL abig;
    REAL ahi, alo, bhi, blo;
    REAL err1, err2, err3;
    INEXACT REAL x_i, x_j;
    REAL x_0;
 
    acx = (REAL) (pa[0] - pc[0]);
    bcx = (REAL) (pb[0] - pc[0]);
    acy = (REAL) (pa[1] - pc[1]);
    bcy = (REAL) (pb[1] - pc[1]);
 
    Two_Product(acx, bcy, detleft, detlefttail);
    Two_Product(acy, bcx, detright, detrighttail);
 
    Two_Two_Diff(detleft, detlefttail, detright, detrighttail,
         B3, B[2], B[1], B[0]);
    B[3] = B3;
 
    det = estimate(4, B);
    //    errbound = ccwerrboundB * detsum;
    errbound = detsum;
    if ((det >= errbound) || (-det >= errbound)) {
      return det;
    }
 
    Two_Diff_Tail(pa[0], pc[0], acx, acxtail);
    Two_Diff_Tail(pb[0], pc[0], bcx, bcxtail);
    Two_Diff_Tail(pa[1], pc[1], acy, acytail);
    Two_Diff_Tail(pb[1], pc[1], bcy, bcytail);
 
    if ((acxtail == 0.0) && (acytail == 0.0)
    && (bcxtail == 0.0) && (bcytail == 0.0)) {
      return det;
    }
 
    //    errbound = ccwerrboundC * detsum + resulterrbound * Absolute(det);
    errbound = detsum + Absolute(det);
    det += (acx * bcytail + bcy * acxtail)
      - (acy * bcxtail + bcx * acytail);
    if ((det >= errbound) || (-det >= errbound)) {
      return det;
    }
 
    Two_Product(acxtail, bcy, s1, s0);
    Two_Product(acytail, bcx, t1, t0);
    Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
    u[3] = u3;
    C1length = fast_expansion_sum_zeroelim(4, B, 4, u, C1);
 
    Two_Product(acx, bcytail, s1, s0);
    Two_Product(acy, bcxtail, t1, t0);
    Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
    u[3] = u3;
    C2length = fast_expansion_sum_zeroelim(C1length, C1, 4, u, C2);
 
    Two_Product(acxtail, bcytail, s1, s0);
    Two_Product(acytail, bcxtail, t1, t0);
    Two_Two_Diff(s1, s0, t1, t0, u3, u[2], u[1], u[0]);
    u[3] = u3;
    Dlength = fast_expansion_sum_zeroelim(C2length, C2, 4, u, D);
 
    return(D[Dlength - 1]);
  }

UpdateKey()

void internal_poltrig::UpdateKey	(	BTreeNode< Linebase *, double > *	node,
		double	y
	)

Definition at line 1325 of file PolygonTriangulator.cxx.

  {
    node->data()->setKeyValue(y);
  }