Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

gugr Namespace Reference


Compounds

struct  gugr::_cut_info
struct  gugr::_cut_record
struct  gugr::contour_node
class  gugr::Dump
class  gugr::dump_graph
class  gugr::dump_segs
class  gugr::DumpPS
struct  gugr::edge_interval
struct  gugr::edge_interval_tree
struct  gugr::eventrec
struct  gugr::graph_edge
struct  gugr::graph_vertex
struct  gugr::GraphConvInfo
struct  gugr::GraphInfo
struct  gugr::intersection
struct  gugr::intersectionseg
struct  gugr::line
struct  gugr::line_rep
struct  gugr::linepair
struct  gugr::linerec
struct  gugr::monpoly_info
struct  gugr::polyline
struct  gugr::seg_point_info
struct  gugr::segment
struct  gugr::segnode
struct  gugr::segtree
struct  gugr::triangle
struct  gugr::vertex
struct  gugr::vertex_rep

Typedefs

typedef List< graph_vertex > graph_vertex_list
typedef List2< graph_vertex > graph_vertex_list2
typedef List< graph_edge > graph_edge_list
typedef gugr::_cut_record cut_record
typedef List< cut_record > cut_record_list
typedef gugr::_cut_info cut_info
typedef List< triangle > triangle_list
typedef gul::List< gul::ListNode<
segment > > 		segment_list
typedef GraphInfo * GraphInfo4 [4]

Functions

bool intersect_nonvert (const line &a, const line &b, point2< rational > &I)
bool intersect_vert (const rational &x0, const line &b, point2< rational > &I)
bool intersect_horiz (const rational &y0, const line &b, point2< rational > &I)
bool intersect (const line &a, const line &b, point2< rational > &I)
template<class T> void PolygonToGraph (const int n, gul::Ptr< gul::point2< T > > P, const T orgx, const T orgy, const T scalex, const T scaley, int fleft, int fright, graph_edge_list *E, graph_vertex_list *V)
template void PolygonToGraph (const int n, gul::Ptr< gul::point2< float > > P, const float orgx, const float orgy, const float scalex, const float scaley, int fleft, int fright, graph_edge_list *E, graph_vertex_list *V)
template void PolygonToGraph (const int n, gul::Ptr< gul::point2< double > > P, const double orgx, const double orgy, const double scalex, const double scaley, int fleft, int fright, graph_edge_list *E, graph_vertex_list *V)
template<class T> void PolygonToGraphNV (const int n, gul::Ptr< gul::point2< T > > P, const T orgx, const T orgy, const T scalex, const T scaley, int fleft, int fright, graph_edge_list *E, graph_vertex_list *V)
template void PolygonToGraphNV (const int n, gul::Ptr< gul::point2< float > > P, const float orgx, const float orgy, const float scalex, const float scaley, int fleft, int fright, graph_edge_list *E, graph_vertex_list *V)
template void PolygonToGraphNV (const int n, gul::Ptr< gul::point2< double > > P, const double orgx, const double orgy, const double scalex, const double scaley, int fleft, int fright, graph_edge_list *E, graph_vertex_list *V)
int IncidentEdges (const graph_vertex *v, graph_edge **A)
int EdgeCycle (graph_edge *e, graph_vertex *v, graph_edge **A)
void OrientEdge (graph_edge *e)
void OrientEdges (graph_edge *E)
int DetermineOrientation (const point2< rational > &A, const point2< rational > &B, const point2< rational > &C)
int DetermineOrientationPV (const point2< rational > &A, const point2< rational > &AB, const point2< rational > &C)
int CompareAngles (const point2< rational > &A, const point2< rational > &B, const point2< rational > &C, const point2< rational > &D, int *match, int *code_c, int *code_d)
int EdgeInsertPosition (const vertex &a, const vertex &b, int nE, graph_edge **E, int *eleft, int *eright, int *code_left, int *code_right)
void ConnectEdge (graph_edge *e, int maxE)
int DisconnectEdge (graph_edge *e, int maxE)
int coord2int (double f, unsigned long *buf)
int coord2int (float f, unsigned long *buf)
template<class T> T cnv2coord (const T &i)
template<class T> void cnv2coord_rnd (rational &f, T *ret)
bool operator== (const vertex &a, const vertex &b)
bool parallel (const line &a, const line &b)
void CT_DoAboveEdge (graph_edge *e, graph_vertex *v, contour_node **pCA, contour_node **pCB)
void CT_DoBelowEdge (graph_edge *e, graph_vertex *v, contour_node **pCA, contour_node **pCB)
void ContainmentTree (List< ListNode< segment > > &insegs, const rational &far_maxx, const rational &far_maxy, gul::List< contour_node > &contours, contour_node &universe)
void IntersectionSubTree (contour_node *C, int oset, int InA, int InB, List< ListNode< gul::polyline< point2< rational > > > > &pl)
void UnionSubTree (contour_node *C, int oset, int OutA, int OutB, List< ListNode< gul::polyline< point2< rational > > > > &pl)
void DifferenceSubTree (contour_node *C, int oset, int InA, int OutB, List< ListNode< gul::polyline< point2< rational > > > > &pl)
GULAPI void DoIntersection (List< ListNode< polyline > > &PA, List< ListNode< polyline > > &PB, const rational &far_x, const rational &far_y, List< ListNode< gul::polyline< point2< rational > > > > &C)
GULAPI void DoUnion (List< ListNode< polyline > > &PA, List< ListNode< polyline > > &PB, const rational &far_x, const rational &far_y, List< ListNode< gul::polyline< point2< rational > > > > &C)
GULAPI void DoDifference (List< ListNode< polyline > > &PA, List< ListNode< polyline > > &PB, const rational &far_x, const rational &far_y, List< ListNode< gul::polyline< point2< rational > > > > &C)
template<class T> GULAPI void ConvertToRationalPolys (List< ListNode< gul::polyline< point2< T > > > > &A, List< ListNode< gul::polyline< point2< T > > > > &B, T *ret_minx, T *ret_miny, T *ret_scale, rational *ret_far_x, rational *ret_far_y, List< ListNode< gugr::polyline > > &PA, List< ListNode< gugr::polyline > > &PB)
template GULAPI void ConvertToRationalPolys (List< ListNode< gul::polyline< point2< float > > > > &A, List< ListNode< gul::polyline< point2< float > > > > &B, float *ret_minx, float *ret_miny, float *ret_scale, rational *ret_far_x, rational *ret_far_y, List< ListNode< gugr::polyline > > &PA, List< ListNode< gugr::polyline > > &PB)
template GULAPI void ConvertToRationalPolys (List< ListNode< gul::polyline< point2< double > > > > &A, List< ListNode< gul::polyline< point2< double > > > > &B, double *ret_minx, double *ret_miny, double *ret_scale, rational *ret_far_x, rational *ret_far_y, List< ListNode< gugr::polyline > > &PA, List< ListNode< gugr::polyline > > &PB)
template<class T> GULAPI void ConvertToFloatPoly (List< ListNode< gul::polyline< point2< rational > > > > &inA, T minx, T miny, T scale, List< ListNode< gul::polyline< point2< T > > > > &outA)
template GULAPI void ConvertToFloatPoly (List< ListNode< gul::polyline< point2< rational > > > > &inA, float minx, float miny, float scale, List< ListNode< gul::polyline< point2< float > > > > &outA)
template GULAPI void ConvertToFloatPoly (List< ListNode< gul::polyline< point2< rational > > > > &inA, double minx, double miny, double scale, List< ListNode< gul::polyline< point2< double > > > > &outA)
GULAPI void DoIntersection (gul::List< gul::ListNode< gugr::polyline > > &PA, gul::List< gul::ListNode< gugr::polyline > > &PB, const rational &far_x, const rational &far_y, gul::List< gul::ListNode< gul::polyline< gul::point2< rational > > > > &C)
template<class T> void Intersection (gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPA, gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPB, gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPC)
template<class T> void Union (gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPA, gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPB, gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPC)
template<class T> void Difference (gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPA, gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPB, gul::List< gul::ListNode< gul::polyline< gul::point2< T > > > > &fPC)
void AppendContour (polyline *c, int keyleft, int keyright, List< ListNode< segment > > &segs)
template<class EP> void AppendContourFNT (polyline *c, Ptr< EP > &F, Ptr< EP > &N, Ptr< EP > &T, int keyleft, int keyright, List< ListNode< segment > > &segs)
template void AppendContourFNT (polyline *c, Ptr< point< float > > &F, Ptr< point< float > > &N, Ptr< point< float > > &T, int keyleft, int keyright, List< ListNode< segment > > &segs)
template void AppendContourFNT (polyline *c, Ptr< point< double > > &F, Ptr< point< double > > &N, Ptr< point< double > > &T, int keyleft, int keyright, List< ListNode< segment > > &segs)
void LeftSideContour (graph_edge *e, graph_edge_list &E, contour_node *cn)
void RightSideContour (graph_edge *e, graph_edge_list &E, contour_node *cn)
void FindContours (graph_edge_list &E, graph_vertex_list &V, const rational &far_maxx, const rational &far_maxy, List< ListNode< segment > > &outsegs, List< contour_node > &contours)
void RemoveUnnecessaryEdges (graph_edge_list &E, graph_vertex_list &V, const rational &far_maxx, const rational &far_maxy, int key_inside, int key_outside, List< ListNode< segment > > &outsegs)
GULAPI void OddEvenRule (List< ListNode< polyline > > &inC, const rational &far_maxx, const rational &far_maxy, int key_inside, int key_outside, graph_edge_list &E, graph_vertex_list &V, List< ListNode< segment > > &outsegs)
template<class T> GULAPI bool CalcPlane (int nVerts, const Ptr< point< T > > &Verts, point< T > &o, point< T > &b1, point< T > &b2, point< T > &b3)
template GULAPI bool CalcPlane (int nVerts, const Ptr< point< float > > &Verts, point< float > &o, point< float > &b1, point< float > &b2, point< float > &b3)
template GULAPI bool CalcPlane (int nVerts, const Ptr< point< double > > &Verts, point< double > &o, point< double > &b1, point< double > &b2, point< double > &b3)
template<class T> GULAPI bool CheckLeftHandedness (int nP, const Ptr< point< T > > &P, const Ptr< Ptr< T > > &Ti, bool &lefthanded, bool &selfintersect)
template GULAPI bool CheckLeftHandedness (int nP, const Ptr< point< float > > &P, const Ptr< Ptr< float > > &Ti, bool &lefthanded, bool &selfintersect)
template GULAPI bool CheckLeftHandedness (int nP, const Ptr< point< double > > &P, const Ptr< Ptr< double > > &Ti, bool &lefthanded, bool &selfintersect)
template<class T> void Polygon3dTo2d (const List< ListNode< gul::polyline< point< T > > > > &C3, const Ptr< Ptr< T > > &Ti, List< ListNode< gul::polyline< point2< T > > > > &C2)
template void Polygon3dTo2d (const List< ListNode< gul::polyline< point< float > > > > &C3, const Ptr< Ptr< float > > &Ti, List< ListNode< gul::polyline< point2< float > > > > &C2)
template void Polygon3dTo2d (const List< ListNode< gul::polyline< point< double > > > > &C3, const Ptr< Ptr< double > > &Ti, List< ListNode< gul::polyline< point2< double > > > > &C2)
template<class T> GULAPI void TriangulatePolygon3d (const List< ListNode< gul::polyline< point< T > > > > &C3, const List< ListNode< gul::polyline< point< T > > > > &N3, const List< ListNode< gul::polyline< point< T > > > > &T3, const Ptr< Ptr< T > > &Ti, Ptr< point2< T > > &D, Ptr< point< T > > &F, Ptr< point< T > > &N, Ptr< point< T > > &Tx, int *nTri, Ptr< itriangle > &Tri)
template GULAPI void TriangulatePolygon3d< float > (const List< ListNode< gul::polyline< point< float > > > > &C3, const List< ListNode< gul::polyline< point< float > > > > &N3, const List< ListNode< gul::polyline< point< float > > > > &T3, const Ptr< Ptr< float > > &Ti, Ptr< point2< float > > &D, Ptr< point< float > > &F, Ptr< point< float > > &N, Ptr< point< float > > &Tx, int *nTri, Ptr< itriangle > &Tri)
template GULAPI void TriangulatePolygon3d< double > (const List< ListNode< gul::polyline< point< double > > > > &C3, const List< ListNode< gul::polyline< point< double > > > > &N3, const List< ListNode< gul::polyline< point< double > > > > &T3, const Ptr< Ptr< double > > &Ti, Ptr< point2< double > > &D, Ptr< point< double > > &F, Ptr< point< double > > &N, Ptr< point< double > > &Tx, int *nTri, Ptr< itriangle > &Tri)
template<class T> GULAPI void TriangulatePolygon3d (const gul::List< gul::ListNode< gul::polyline< point< T > > > > &C3, const gul::List< gul::ListNode< gul::polyline< point< T > > > > &N3, const gul::List< gul::ListNode< gul::polyline< point< T > > > > &T3, const Ptr< Ptr< T > > &Ti, Ptr< point2< T > > &D, Ptr< point< T > > &F, Ptr< point< T > > &N, Ptr< point< T > > &Tx, int *nTri, Ptr< gul::itriangle > &Tri)
std::ostream & operator<< (std::ostream &s, gugr::dump_graph &g)
void dump_segment (segment *S, std::ostream &s)
std::ostream & operator<< (std::ostream &s, gugr::dump_segs &S)
int compare_point_to_linerec (point2< rational > *P, linerec *L)
int compare_linerec_to_linerec (linerec *L1, linerec *L2)
int compare_point_to_eventrec (point2< rational > *C, eventrec *E)
int compare_segment_to_linerec (segment *S, linerec *L)
int hcompare_point_to_intersection (point2< rational > *C, intersection *R)
int vcompare_point_to_intersection (point2< rational > *C, intersection *R)
int compare_pointer_to_pointer (void *p1, void *p2)
intersection * intersect (Map< linerec >::Node L1, Map< linerec >::Node L2, const rational &xleft, Map< eventrec > *EvQ, List< intersection > *Ipts)
intersection * intersect_vert (linerec *vL, Map< linerec >::Node L, List< intersection > *Ipts)
void finish_line (linerec *L, graph_edge_list *E, graph_vertex_list *V, int maxE, List< intersection > *Ipts, List< intersectionseg > *Isegs)
void finish_vertline (linerec *L, graph_edge_list *E, graph_vertex_list *V, int maxE, List< intersection > *Ipts, List< intersectionseg > *Isegs)
void DoIntersectSegments (int nsegs, Map< eventrec > &EvQ, gugr::graph_edge_list *E, gugr::graph_vertex_list *V)
void IntersectSegments (int nsegs, Ptr< segment > segs, gugr::graph_edge_list *E, gugr::graph_vertex_list *V)
void ISDeleteOwnerMaps (gugr::graph_edge_list &E)
void ISDeleteBackpointers (gugr::graph_edge_list &E)
void IntersectSegments (gul::List< gul::ListNode< segment > > &segs, gugr::graph_edge_list *E, gugr::graph_vertex_list *V, bool need_backpointers)
int compare_vertices (void *p1, void *p2, void *data)
graph_vertex * SortVertices (graph_vertex_list *V)
const graph_edge NegInf (0,(graph_vertex *)(-1))
const graph_edge PosInf (0,(graph_vertex *)(+1))
int CompareEdgesBU (const graph_edge *A, const graph_edge *B)
int CompareEdgesTD (const graph_edge *A, const graph_edge *B)
int compare_edge_to_intervalBU (void *p1, void *p2)
int compare_edge_to_intervalTD (void *p1, void *p2)
void EdgeInsert (graph_edge *e, int maxE)
void Regularize (graph_edge_list *E, graph_vertex_list *V)
int compare_cut_records (void *p1, void *p2, void *data)
void sort_cut_records (int ns, Ptr< cut_info > S)
void IntersectWithAscendant (const point2< rational > &A, const point2< rational > &B, const graph_edge_list &E, const graph_vertex_list &V, line &L, cut_record_list &R)
void InsertDiagonal (graph_edge_list *E, graph_vertex_list *V, graph_vertex *P11, graph_vertex *P22)
int FindCutInfo (rational &x, int nA, const Ptr< cut_info > &A, bool &found)
void IntersectWithHorizontals (graph_edge_list *E, graph_vertex_list *V, const int nS, Ptr< cut_info > S)
void DivideHorizontalStrips (cut_info *Sa, cut_info *Sb, int maxE, const rational &minx, const rational maxx, const rational &far_left, const rational &far_right, graph_vertex **minSaV, graph_vertex **minSbV, graph_vertex **maxSaV, graph_vertex **maxSbV)
void IntersectWithVerticals (graph_edge_list *E, graph_vertex_list *V, const int nS, Ptr< cut_info > S)
void DivideVerticalStrips (cut_info *Sb, cut_info *Sa, int maxE, const rational &miny, const rational maxy, const rational &far_bottom, const rational &far_top, graph_vertex **minSbV, graph_vertex **minSaV, graph_vertex **maxSbV, graph_vertex **maxSaV)
template<class T> void SplitGraph (GraphInfo *G, T xmed, T ymed, GraphConvInfo< T > *Gconv, GraphInfo4 &sub)
template void SplitGraph (GraphInfo *G, float xmed, float ymed, GraphConvInfo< float > *Gconv, GraphInfo4 &sub)
template void SplitGraph (GraphInfo *G, double xmed, double ymed, GraphConvInfo< double > *Gconv, GraphInfo4 &sub)
template<class T> void InitGraph (const rational &X1, const rational &X2, const rational &Y1, const rational &Y2, GraphConvInfo< T > *Gconv, graph_edge_list *E, graph_vertex_list *V, GraphInfo *G)
template void InitGraph (const rational &X1, const rational &X2, const rational &Y1, const rational &Y2, GraphConvInfo< float > *Gconv, graph_edge_list *E, graph_vertex_list *V, GraphInfo *G)
template void InitGraph (const rational &X1, const rational &X2, const rational &Y1, const rational &Y2, GraphConvInfo< double > *Gconv, graph_edge_list *E, graph_vertex_list *V, GraphInfo *G)
void Triangulate (graph_edge_list *E, graph_vertex_list *V, const rational &far_left, triangle_list *T)
void TriangulateMonotonePolygon (graph_vertex_list2 *V1, graph_vertex_list2 *V2, graph_edge_list *E, triangle_list *T)

Typedef Documentation

typedef struct gugr::_cut_info gugr::cut_info
 

typedef struct gugr::_cut_record gugr::cut_record
 

typedef List<cut_record> gugr::cut_record_list
 

Definition at line 408 of file gugr_basics.h.

Referenced by gugr::_cut_record::operator delete().

typedef List<graph_edge> gugr::graph_edge_list
 

Definition at line 383 of file gugr_basics.h.

Referenced by gugr::monpoly_info::AppendRight(), gugr::edge_interval_tree::dump_edge_interval(), gugr::DumpPS::dump_edges(), gugr::dump_graph::dump_graph(), gugr::GraphInfo::operator delete(), gugr::seg_point_info::operator delete(), and gugr::graph_edge::operator delete().

typedef List<graph_vertex> gugr::graph_vertex_list
 

Definition at line 332 of file gugr_basics.h.

Referenced by gugr::monpoly_info::AppendRight(), gugr::edge_interval_tree::dump_edge_interval(), gugr::dump_graph::dump_graph(), gugr::GraphInfo::operator delete(), gugr::seg_point_info::operator delete(), and gugr::graph_vertex::operator delete().

typedef List2<graph_vertex> gugr::graph_vertex_list2
 

Definition at line 333 of file gugr_basics.h.

Referenced by gugr::graph_vertex::operator delete().

typedef GraphInfo* gugr::GraphInfo4[4]
 

Definition at line 67 of file gugr_split.h.

Referenced by gugr::GraphInfo::operator delete().

typedef gul::List<gul::ListNode<segment> > gugr::segment_list
 

Definition at line 74 of file gugr_planesweep.h.

typedef List<triangle> gugr::triangle_list
 

Definition at line 442 of file gugr_basics.h.

Referenced by gugr::triangle::operator delete().

Function Documentation

void gugr::AppendContour (  polyline *    c,
int    keyleft,
int    keyright,
List< ListNode< segment > > &    segs
) 
 

Definition at line 51 of file gugr_contour.cpp. 

00053 {
00054   int i;
00055   ListNode<segment> *sn;
00056   segment *s;
00057   rational x1,x2,y1,y2;
00058   bool swap;
00059 
00060   // travert vertices of contour
00061   for( i = 0; i < c->nVerts; i++ )
00062   {
00063     sn = new ListNode<segment>;
00064     segs.Append( sn );
00065 
00066     s = &sn->el;
00067 
00068     s->l = c->lines[i];  // use existing line equation
00069     s->f[0].set_i(keyleft);
00070     s->f[1].set_i(keyright);
00071     s->m = 1;            // set multiplicity to 1
00072 
00073     x1 = c->verts[i].x;
00074     y1 = c->verts[i].y;
00075     if( i+1 == c->nVerts )
00076     {
00077       x2 = c->verts[0].x;
00078       y2 = c->verts[0].y;
00079     }
00080     else
00081     {
00082       x2 = c->verts[i+1].x;
00083       y2 = c->verts[i+1].y;
00084     }
00085 
00086     // orient the edges as the planesweep algorithm expects them
00087 
00088     if( c->lines[i].IsVertical() )
00089       swap = (compare( y1, y2 ) > 0);
00090     else
00091       swap = (compare( x1, x2 ) > 0);
00092 
00093     if( swap )
00094     {
00095       Swap(x1,x2);
00096       Swap(y1,y2);
00097       Swap(s->f[0],s->f[1]);
00098     }
00099 
00100     s->B.x = x1;
00101     s->B.y = y1;
00102     s->E.x = x2;
00103     s->E.y = y2;
00104   }
00105 }

template void AppendContourFNT (  polyline *    c,
Ptr< point< double > > &    F,
Ptr< point< double > > &    N,
Ptr< point< double > > &    T,
int    keyleft,
int    keyright,
List< ListNode< segment > > &    segs
) 
 

template void AppendContourFNT (  polyline *    c,
Ptr< point< float > > &    F,
Ptr< point< float > > &    N,
Ptr< point< float > > &    T,
int    keyleft,
int    keyright,
List< ListNode< segment > > &    segs
) 
 

template<class EP>
void gugr::AppendContourFNT (  polyline *    c,
Ptr< EP > &    F,
Ptr< EP > &    N,
Ptr< EP > &    T,
int    keyleft,
int    keyright,
List< ListNode< segment > > &    segs
) 
 

Definition at line 108 of file gugr_contour.cpp. 

00110 {
00111   int i;
00112   ListNode<segment> *sn;
00113   segment *s;
00114   rational x1,x2,y1,y2;
00115   bool swap;
00116   seg_point_info<EP> *spi;
00117 
00118   // travert vertices of contour
00119   for( i = 0; i < c->nVerts; i++ )
00120   {
00121     sn = new ListNode<segment>;
00122     segs.Append( sn );
00123 
00124     s = &sn->el;
00125 
00126     s->l = c->lines[i];  // use existing line equation
00127     s->f[0].set_i(keyleft);
00128     s->f[1].set_i(keyright);
00129     spi = new seg_point_info<EP>;
00130     spi->f = &F[i];
00131     spi->n = &N[i];
00132     spi->t = &T[i];
00133     s->reserved[0] = spi;
00134  
00135     s->m = 1;            // set multiplicity to 1
00136 
00137     x1 = c->verts[i].x;
00138     y1 = c->verts[i].y;
00139     if( i+1 == c->nVerts )
00140     {
00141       x2 = c->verts[0].x;
00142       y2 = c->verts[0].y;
00143       spi = new seg_point_info<EP>;
00144       spi->f = &F[0];
00145       spi->n = &N[0];
00146       spi->t = &T[0];
00147       s->reserved[1] = spi;
00148     }
00149     else
00150     {
00151       x2 = c->verts[i+1].x;
00152       y2 = c->verts[i+1].y;
00153       spi = new seg_point_info<EP>;
00154       spi->f = &F[i+1];
00155       spi->n = &N[i+1];
00156       spi->t = &T[i+1];
00157       s->reserved[1] = spi;
00158     }
00159 
00160     // orient the edges as the planesweep algorithm expects them
00161 
00162     if( c->lines[i].IsVertical() )
00163       swap = (compare( y1, y2 ) > 0);
00164     else
00165       swap = (compare( x1, x2 ) > 0);
00166 
00167     if( swap )
00168     {
00169       Swap(x1,x2);
00170       Swap(y1,y2);
00171       Swap(s->f[0],s->f[1]);
00172       Swap(s->reserved[0],s->reserved[1]);
00173     }
00174 
00175     s->B.x = x1;
00176     s->B.y = y1;
00177     s->E.x = x2;
00178     s->E.y = y2;
00179   }
00180 }

template GULAPI bool CalcPlane (  int    nVerts,
const Ptr< point< double > > &    Verts,
point< double > &    o,
point< double > &    b1,
point< double > &    b2,
point< double > &    b3
) 
 

template GULAPI bool CalcPlane (  int    nVerts,
const Ptr< point< float > > &    Verts,
point< float > &    o,
point< float > &    b1,
point< float > &    b2,
point< float > &    b3
) 
 

template<class T>
GULAPI bool gugr::CalcPlane (  int    nVerts,
const Ptr< point< T > > &    Verts,
point< T > &    o,
point< T > &    b1,
point< T > &    b2,
point< T > &    b3
) 
 

Definition at line 143 of file gugr_face.cpp. 

00146 {
00147   Interval ix0,iy0,iz0,ix1,iy1,iz1,ix2,iy2,iz2,ibx1,iby1,ibz1,ibx2,iby2,ibz2;
00148   Interval ilen,ilen2,inx,iny,inz;
00149   double rat,rat1;
00150   int i0,i1,i2,irat0,irat1,irat2;
00151   point<T> v1,v2;
00152 
00153   irat0 = -1;
00154   rat = rtr<double>::giant();  // start with a gigantic ratio
00155 
00156   for( i0 = 0; i0 < nVerts; i0++ )
00157   {
00158     ix0 = Verts[i0].x;
00159     iy0 = Verts[i0].y;
00160     iz0 = Verts[i0].z;
00161     
00162     i1 = i0+1; if( i1 == nVerts ) i1 = 0;
00163     i2 = i1+1; if( i2 == nVerts ) i2 = 0;
00164 
00165     // calc first basis vector
00166 
00167     ix1 = Verts[i1].x;
00168     iy1 = Verts[i1].y;
00169     iz1 = Verts[i1].z;
00170 
00171     ibx1 = ix1 - ix0;
00172     iby1 = iy1 - iy0;
00173     ibz1 = iz1 - iz0;
00174 
00175     // normalize b1
00176 
00177     ilen2 = ibx1*ibx1 + iby1*iby1 + ibz1*ibz1;
00178     ilen = Sqrt( ilen2 ); 
00179     if( Test(ilen)==0 ) continue;   // avoid division by zero
00180 
00181     ibx1 = ibx1 / ilen;
00182     iby1 = iby1 / ilen;
00183     ibz1 = ibz1 / ilen;
00184 
00185     // calc second basis vector of plane
00186 
00187     ix2 = Verts[i2].x;
00188     iy2 = Verts[i2].y;
00189     iz2 = Verts[i2].z;
00190 
00191     ibx2 = ix2 - ix0;
00192     iby2 = iy2 - iy0;
00193     ibz2 = iz2 - iz0;
00194 
00195     // project vector onto b1 
00196 
00197     ilen = ibx2*ibx1 + iby2*iby1 + ibz2*ibz1;
00198 
00199     // get the component orthogonal to b1
00200 
00201     ibx2 = ibx2 - ilen * ibx1;
00202     iby2 = iby2 - ilen * iby1;
00203     ibz2 = ibz2 - ilen * ibz1;
00204 
00205     // normalize b2
00206 
00207     ilen2 = ibx2*ibx2 + iby2*iby2 + ibz2*ibz2;
00208     ilen = Sqrt( ilen2 ); 
00209     if( Test(ilen)==0 ) continue;   // avoid division by zero
00210 
00211     ibx2 = ibx2 / ilen;
00212     iby2 = iby2 / ilen;
00213     ibz2 = ibz2 / ilen;
00214 
00215     // calculate the crossproduct of b1 and b2
00216 
00217     inx = iby1*ibz2 - ibz1*iby2;
00218     iny = ibz1*ibx2 - ibx1*ibz2;
00219     inz = ibx1*iby2 - iby1*ibx2;
00220 
00221     // normalize it (superfluous since b1 and b2 are orthonormal)
00222 
00223     ilen2 = inx*inx + iny*iny + inz*inz;
00224     ilen = Sqrt( ilen2 ); 
00225     if( Test(ilen)==0 ) continue;
00226 
00227     inx = inx / ilen;
00228     iny = iny / ilen;
00229     inz = inz / ilen;
00230 
00231     rat1 = GetRatio(inx*inx + iny*iny + inz*inz);
00232     if( rat1 < rat ) 
00233     {
00234       rat  = rat1;
00235       irat0 = i0;
00236       irat1 = i1;
00237       irat2 = i2;
00238     }
00239   }
00240   if( (irat0 < 0) || (rat == rtr<double>::giant()) ) return false;
00241   i0 = irat0;
00242   i1 = irat1;
00243   i2 = irat2;
00244  
00245   // the same calculation as above, now with floating point arithmetic
00246 
00247   o = Verts[i0];
00248   v1 = Verts[i1] - o;
00249   v2 = Verts[i2] - o;
00250   normalize(&b1,v1);
00251   b2 = v2 - (v2*b1)*b1;
00252   normalize(&b2,b2);
00253   b3 = cross_product(b1,b2);
00254   normalize(&b3,b3);
00255 
00256   return true;
00257 }

template GULAPI bool CheckLeftHandedness (  int    nP,
const Ptr< point< double > > &    P,
const Ptr< Ptr< double > > &    Ti,
bool &    lefthanded,
bool &    selfintersect
) 
 

template GULAPI bool CheckLeftHandedness (  int    nP,
const Ptr< point< float > > &    P,
const Ptr< Ptr< float > > &    Ti,
bool &    lefthanded,
bool &    selfintersect
) 
 

template<class T>
GULAPI bool gugr::CheckLeftHandedness (  int    nP,
const Ptr< point< T > > &    P,
const Ptr< Ptr< T > > &    Ti,
bool &    lefthanded,
bool &    selfintersect
) 
 

Definition at line 272 of file gugr_face.cpp. 

00275 {
00276   polyline pl;
00277   Ptr< point2<T> > P2;
00278   Ptr<T> v3,v2;
00279   List< ListNode<segment> > segs,outsegs;
00280   ListNode<segment> *seg;
00281   graph_edge_list E;
00282   graph_vertex_list V;
00283   rational far_minx,far_maxx,far_miny,far_maxy;
00284   T minx,maxx,miny,maxy;
00285   T dx,dy,scale,scalei;
00286   int i,left;
00287   List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *L;
00288   graph_edge *e;
00289   List< ListNode<graph_edge *> > *Le;
00290   unsigned long *cbuf = 
00291     (unsigned long *)alloca(gul::rtr<T>::mantissa_length());
00292   
00293   if( !nP ) return false;
00294 
00295   // project vertices onto plane
00296 
00297   P2.reserve_pool(nP);
00298   v3.reserve_pool(4);
00299   v2.reserve_pool(4);
00300 
00301   for( i = 0; i < nP; i++ )
00302   {
00303     v3[0] = P[i].x;
00304     v3[1] = P[i].y;
00305     v3[2] = P[i].z;
00306     v3[3] = (T)1;
00307 
00308     VMProduct(4,4,v3,Ti,v2);
00309 
00310     P2[i].x = v2[0];
00311     P2[i].y = v2[1];
00312   }
00313 
00314   CalcBoundingBoxE( nP, P2, minx, maxx, miny, maxy );
00315 
00316   dx = maxx - minx;
00317   dy = maxy - miny;
00318   scale = dx > dy ? dx : dy;
00319   minx -= scale;
00320   miny -= scale;
00321   scalei = (T)1.0/scale;
00322 
00323   /*
00324   Dump<float>::set_transformation(minx,miny,scale,scale);
00325   */
00326 
00327   pl.init( nP, P2, minx, miny, scalei ); 
00328 
00329   AppendContour( &pl, 0, 1, segs );
00330  
00331   IntersectSegments( segs, &E, &V, true );
00332 
00333   /*
00334   std::cout << "EDGES AFTER INTERSECTION\n";
00335   std::cout << "========================\n";
00336   Dump<float>::dump_edges( E.head );
00337   std::cout << "\n";
00338   */
00339 
00340   far_miny = far_minx = rational( guar::ULong(0x100000), -1 );
00341   far_maxy = far_maxx = rational( coord2int((T)2,cbuf),cbuf) +
00342                                       rational( guar::ULong(0x100000) );
00343 
00344   RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, 1, 0, outsegs );
00345 
00346   e = E.First(); if( !e ) return false; // internal error
00347 
00348   // backpointer to the segment edge lists which contain the fist edge
00349   L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *)
00350                                                                e->reserved[1].p;
00351   // the first backpointed List
00352   Le = L->First()->el.m_L;
00353 
00354   // find the corresponding segment 
00355   for( seg = segs.First(); seg != 0; seg = seg->next )
00356     if( &seg->el.e == Le ) break;
00357 
00358   if( !seg ) return false;  // internal error
00359   
00360   if( e->l.IsHorizontal() || (e->l.dx().test() < 0) )
00361     left = e->f[1].i;         // edge orientation different
00362   else
00363     left = e->f[0].i;
00364 
00365   lefthanded = (left != 1);
00366 
00367   // check if there were self-intersections
00368   
00369   for( seg = segs.First(); seg != 0; seg = seg->next )
00370     if( seg->el.e.nElems != 1 ) break;
00371 
00372   selfintersect = (seg != 0);
00373 
00374   // delete data which would not be automatically destructed
00375 
00376   e = E.First();
00377   while( e )         // delete backpointer lists
00378   {
00379     L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *)
00380                                                                e->reserved[1].p;
00381     L->DeleteElems();
00382     delete L; 
00383     e->reserved[1].p = 0;
00384     e = e->next;
00385   }    
00386 
00387   return true;
00388 }

template<class T>
T cnv2coord (  const T &    i ) 
 

Definition at line 86 of file gugr_basics.h. 

00087 {
00088   return i * gul::rtr<T>::epsilon() + (T)1.0;
00089 }

template<class T>
void cnv2coord_rnd (  rational &    f,
T *    ret
)  [inline]
 

Definition at line 96 of file gugr_basics.h. 

00097 {
00098   rational q,r,rd,h;
00099   T flt;
00100 
00101   f.div_mod(&q,&r);
00102 
00103   rd = r/f.denominator();
00104   h = rational(ULong(1))/rational(ULong(2));
00105 
00106   if( compare(rd,h) >= 0 )
00107     q = q + rational(ULong(1));
00108 
00109   guar::IntTo<T>(q.m->m_na,q.m->m_a,flt);
00110 
00111   *ret = cnv2coord(flt);
00112 }

int compare_cut_records (  void *    p1,
void *    p2,
void *    data
) 
 

Definition at line 45 of file gugr_split.cpp. 

00046 {
00047   rational &r1 = ((cut_record *)p1)->val, &r2 = ((cut_record *)p2)->val;
00048   int sign;
00049   
00050   sign = compare( r1, r2 );
00051   return(sign);
00052 }

int compare_edge_to_intervalBU (  void *    p1,
void *    p2
) 
 

Definition at line 220 of file gugr_regularize.cpp.

Referenced by gugr::edge_interval_tree::dump_edge_interval(). 

00221 {
00222  graph_edge *e = (graph_edge *)p1; 
00223  edge_interval *ei = (edge_interval *)p2;
00224 
00225  if( CompareEdgesBU( e, ei->l ) <= 0 )
00226    return(-1);
00227  if( CompareEdgesBU( e, ei->r ) < 0 )
00228    return(0);
00229 
00230   return(1);
00231 }

int compare_edge_to_intervalTD (  void *    p1,
void *    p2
) 
 

Definition at line 232 of file gugr_regularize.cpp.

Referenced by gugr::edge_interval_tree::dump_edge_interval(). 

00233 {
00234  graph_edge *e = (graph_edge *)p1; 
00235  edge_interval *ei = (edge_interval *)p2;
00236 
00237  if( CompareEdgesTD( e, ei->l ) <= 0 )
00238    return(-1);
00239  if( CompareEdgesTD( e, ei->r ) < 0 )
00240    return(0);
00241 
00242   return(1);
00243 }

int compare_linerec_to_linerec (  linerec *    L1,
linerec *    L2
) 
 

Definition at line 68 of file gugr_planesweep.cpp. 

00069 {
00070   int sign = DetermineOrientation(L2->B, L2->E, L1->B );
00071   if( sign == 0 )
00072     sign = DetermineOrientation(L2->B, L2->E, L1->E );
00073   return sign;
00074 }

int gugr::compare_point_to_eventrec (  point2< rational > *    C,
eventrec *    E
) 
 

Definition at line 75 of file gugr_planesweep.cpp.

Referenced by gugr::DumpPS::dump_point(), and gugr::segtree::leaves_to_array(). 

00076 {
00077   int sign = compare( C->x, E->key.x );
00078   if( sign == 0 ) sign = compare( C->y, E->key.y );
00079   return sign;
00080 }

int compare_point_to_linerec (  point2< rational > *    P,
linerec *    L
) 
 

Definition at line 64 of file gugr_planesweep.cpp. 

00065 {
00066   return DetermineOrientation( L->B, L->E, *P );
00067 }

int gugr::compare_pointer_to_pointer (  void *    p1,
void *    p2
) 
 

Definition at line 95 of file gugr_planesweep.cpp.

Referenced by gugr::segnode::insert(), gugr::contour_node::Insert(), and gugr::segnode::remove(). 

00096 {
00097   if( p1 < p2 ) return -1;
00098   else if( p1 == p2 ) return 0;
00099   return 1;
00100 }

int compare_segment_to_linerec (  segment *    S,
linerec *    L
) 
 

Definition at line 81 of file gugr_planesweep.cpp. 

00082 {
00083   int sign = DetermineOrientation( L->B, L->E, S->B );
00084   if( sign == 0 ) sign = DetermineOrientation( L->B, L->E, S->E );
00085   return sign;
00086 }

int gugr::compare_vertices (  void *    p1,
void *    p2,
void *    data
) 
 

Definition at line 46 of file gugr_regularize.cpp. 

00047 {
00048   const graph_vertex& v1 = *((graph_vertex *)p1);
00049   const graph_vertex& v2 = *((graph_vertex *)p2);
00050   int sign;
00051   
00052   sign = compare( v1.v.v().y, v2.v.v().y );
00053   if( !sign ) sign = -compare( v1.v.v().x, v2.v.v().x );
00054 
00055   return(sign);
00056 }

int gugr::CompareAngles (  const point2< rational > &    A,
const point2< rational > &    B,
const point2< rational > &    C,
const point2< rational > &    D,
int *    match,
int *    code_c,
int *    code_d
) 
 

Definition at line 545 of file gugr_basics.cpp. 

00549 {
00550   const Interval& iAx = A.x.get_bounds();
00551   const Interval& iAy = A.y.get_bounds();
00552   const Interval& iBx = B.x.get_bounds();
00553   const Interval& iBy = B.y.get_bounds();
00554   const Interval& iCx = C.x.get_bounds();
00555   const Interval& iCy = C.y.get_bounds();
00556   const Interval& iDx = D.x.get_bounds();
00557   const Interval& iDy = D.y.get_bounds();
00558   Interval iABx,iABy, iACx,iACy, iADx,iADy;
00559   Interval iABcAC,iABdAC; 
00560   Interval iABcAD,iABdAD;
00561   bool flag1 = false, flag2 = false;
00562   int sideC,sideD,sign;
00563   const rational& rAx = A.x;
00564   const rational& rAy = A.y;
00565   const rational& rBx = B.x;
00566   const rational& rBy = B.y;
00567   const rational& rCx = C.x;
00568   const rational& rCy = C.y;
00569   const rational& rDx = D.x;
00570   const rational& rDy = D.y;
00571   rational rABx,rABy, rACx,rACy, rADx,rADy;
00572   rational rABcAC, rABdAC;   
00573   rational rABcAD, rABdAD;
00574   Interval iLambda;
00575   rational rLambda;   
00576 
00577   *match = 0;
00578   *code_c = 0;
00579   *code_d = 0;
00580   
00581   iABx = iBx - iAx;
00582   iABy = iBy - iAy;
00583   iACx = iCx - iAx;
00584   iACy = iCy - iAy;
00585   
00586   iABcAC = iABx*iACy - iABy*iACx;
00587   
00588   if( iABcAC.m_low > 0.0 ) sideC = +1;
00589   else if( iABcAC.m_high < 0.0 ) sideC = -1;
00590   else
00591   {
00592     flag1 = true;
00593     rABx = rBx - rAx;
00594     rABy = rBy - rAy;
00595     rACx = rCx - rAx;
00596     rACy = rCy - rAy;
00597 
00598     rABcAC = rABx*rACy - rABy*rACx;
00599     sideC = rABcAC.test();
00600   }
00601 
00602   *code_c = sideC + 2;
00603   
00604   if( sideC == 0 )    /* sideC == 0 => check orientation with dot product */
00605   {
00606     iABdAC = iABx*iACx + iABy*iACy;
00607     if( iABdAC.m_low > 0.0 )        /* 0=angle(AB,AC) < angle(AB,AD) */
00608     { *match = 1; return(-1); }   
00609     else if( iABdAC.m_high >= 0.0 )
00610     {    
00611       rABdAC = rABx*rACx + rABy*rACy;
00612       if( rABdAC.test() > 0.0 )     /* 0=angle(AB,AC) < angle(AB,AD) */
00613       { *match = 1; return(-1); } 
00614     }
00615     /* now angle(AB,AC) == 180 if sideC == 0 */
00616   }
00617  
00618   iADx = iDx - iAx;
00619   iADy = iDy - iAy;
00620 
00621   iABcAD = iABx*iADy - iABy*iADx;
00622   
00623   if( iABcAD.m_low > 0.0 ) sideD = +1;
00624   else if( iABcAD.m_high < 0.0 ) sideD = -1;
00625   else
00626   {
00627     flag2 = true;
00628     rADx = rDx - rAx;
00629     rADy = rDy - rAy;
00630     if( !flag1 )
00631     {
00632       rABx = rBx - rAx;
00633       rABy = rBy - rAy;
00634     }
00635     rABcAD = rABx*rADy - rABy*rADx;
00636     sideD = rABcAD.test();
00637   }
00638 
00639   *code_d = sideD + 2;
00640   
00641   if( sideD == 0 ) /* sideD == 0 => check orientation with dot product */
00642   {
00643     if( sideC == 0 ) { *match = 2; return(+1); }
00644 
00645     iABdAD = iABx*iADx + iABy*iADy;
00646     if( iABdAD.m_low > 0.0 )      /* 0=angle(AB,AD) < angle(AB,AC) */
00647     { *match = 2; return(+1); }   
00648     else if( iABdAD.m_high >= 0.0 ) /* exact calculation if necessary */
00649     {    
00650       rABdAD = rABx*rADx + rABy*rADy;
00651       if( rABdAD.test() > 0.0 )     /* 0=angle(AB,AD) < angle(AB,AC) */
00652       { *match = 2; return(+1); } 
00653     }
00654     /* now angle(AB,AD) == 180 if sideD == 0 */
00655 
00656     if( sideC > 0 ) return(-1);
00657     return(+1);
00658   }
00659 
00660   if( sideC == 0 )
00661   {
00662     if( sideD > 0 ) return(+1);
00663     return(-1);
00664   }
00665   
00666   if( sideC > sideD ) return(-1);
00667   else if( sideC < sideD ) return(+1);
00668 
00669   /* intersect Line(C,AB) and Line(A,AD) */
00670   
00671   iLambda = (iADx*iACy - iACx*iADy)/(iABx*iADy - iABy*iADx);
00672   if( iLambda.m_low > 0.0 )
00673   {
00674      if( sideC > 0 ) return(+1);  /* angle(AB,AC) > angle(AB,AD) */
00675      return(-1);
00676   }
00677   if( iLambda.m_high < 0.0 )
00678   {
00679     if( sideC > 0 ) return(-1);  /* angle(AB,AC) < angle(AB,AD) */
00680     return(+1);
00681   }
00682   
00683   if( !flag1 )
00684   {
00685     rACx = rCx - rAx;
00686     rACy = rCy - rAy;
00687   }
00688   if( !flag2 )
00689   {
00690     if( !flag1 )
00691     {
00692       rABx = rBx - rAx;
00693       rABy = rBy - rAy;
00694     }
00695     rADx = rDx - rAx;
00696     rADy = rDy - rAy;
00697   }
00698   
00699   rLambda = (rADx*rACy - rACx*rADy)/(rABx*rADy - rABy*rADx);
00700   sign = rLambda.test();
00701 
00702   if( sign > 0 )
00703   {
00704      if( sideC > 0 ) return(+1);  /* angle(AB,AC) > angle(AB,AD) */
00705      return(-1);
00706   }
00707   if( sideC > 0 ) return(-1);  /* angle(AB,AC) < angle(AB,AD) */
00708   return(+1);
00709 }

int CompareEdgesBU (  const graph_edge *    A,
const graph_edge *    B
) 
 

Definition at line 179 of file gugr_regularize.cpp. 

00180 {
00181   int sign;
00182   
00183   if( A == B ) return(0);
00184   
00185   if( IS_INF(*A) )
00186     return( INF_SIGN(*A) );
00187   if( IS_INF(*B) )
00188     return( -INF_SIGN(*B) );
00189   
00190   if( A->v[0] != B->v[0] ) {
00191     sign = DetermineOrientation( B->v[0]->v.v(), B->v[1]->v.v(),
00192                                  A->v[0]->v.v() );
00193   } else {
00194     sign = DetermineOrientation( B->v[0]->v.v(), B->v[1]->v.v(),
00195                                  A->v[1]->v.v() );
00196   }
00197   return(-sign);
00198 }

int CompareEdgesTD (  const graph_edge *    A,
const graph_edge *    B
) 
 

Definition at line 199 of file gugr_regularize.cpp. 

00200 {
00201   int sign;
00202   
00203   if( A == B ) return(0);
00204   
00205   if( IS_INF(*A) )
00206     return( INF_SIGN(*A) );
00207   if( IS_INF(*B) )
00208     return( -INF_SIGN(*B) );
00209   
00210   if( A->v[1] != B-