---

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. { int i; ListNode<segment> *sn; segment *s; rational x1,x2,y1,y2; bool swap; // travert vertices of contour for( i = 0; i < c->nVerts; i++ ) { sn = new ListNode<segment>; segs.Append( sn ); s = &sn->el; s->l = c->lines[i]; // use existing line equation s->f[0].set_i(keyleft); s->f[1].set_i(keyright); s->m = 1; // set multiplicity to 1 x1 = c->verts[i].x; y1 = c->verts[i].y; if( i+1 == c->nVerts ) { x2 = c->verts[0].x; y2 = c->verts[0].y; } else { x2 = c->verts[i+1].x; y2 = c->verts[i+1].y; } // orient the edges as the planesweep algorithm expects them if( c->lines[i].IsVertical() ) swap = (compare( y1, y2 ) > 0); else swap = (compare( x1, x2 ) > 0); if( swap ) { Swap(x1,x2); Swap(y1,y2); Swap(s->f[0],s->f[1]); } s->B.x = x1; s->B.y = y1; s->E.x = x2; s->E.y = y2; } }

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. { int i; ListNode<segment> *sn; segment *s; rational x1,x2,y1,y2; bool swap; seg_point_info<EP> *spi; // travert vertices of contour for( i = 0; i < c->nVerts; i++ ) { sn = new ListNode<segment>; segs.Append( sn ); s = &sn->el; s->l = c->lines[i]; // use existing line equation s->f[0].set_i(keyleft); s->f[1].set_i(keyright); spi = new seg_point_info<EP>; spi->f = &F[i]; spi->n = &N[i]; spi->t = &T[i]; s->reserved[0] = spi; s->m = 1; // set multiplicity to 1 x1 = c->verts[i].x; y1 = c->verts[i].y; if( i+1 == c->nVerts ) { x2 = c->verts[0].x; y2 = c->verts[0].y; spi = new seg_point_info<EP>; spi->f = &F[0]; spi->n = &N[0]; spi->t = &T[0]; s->reserved[1] = spi; } else { x2 = c->verts[i+1].x; y2 = c->verts[i+1].y; spi = new seg_point_info<EP>; spi->f = &F[i+1]; spi->n = &N[i+1]; spi->t = &T[i+1]; s->reserved[1] = spi; } // orient the edges as the planesweep algorithm expects them if( c->lines[i].IsVertical() ) swap = (compare( y1, y2 ) > 0); else swap = (compare( x1, x2 ) > 0); if( swap ) { Swap(x1,x2); Swap(y1,y2); Swap(s->f[0],s->f[1]); Swap(s->reserved[0],s->reserved[1]); } s->B.x = x1; s->B.y = y1; s->E.x = x2; s->E.y = y2; } }

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. { Interval ix0,iy0,iz0,ix1,iy1,iz1,ix2,iy2,iz2,ibx1,iby1,ibz1,ibx2,iby2,ibz2; Interval ilen,ilen2,inx,iny,inz; double rat,rat1; int i0,i1,i2,irat0,irat1,irat2; point<T> v1,v2; irat0 = -1; rat = rtr<double>::giant(); // start with a gigantic ratio for( i0 = 0; i0 < nVerts; i0++ ) { ix0 = Verts[i0].x; iy0 = Verts[i0].y; iz0 = Verts[i0].z; i1 = i0+1; if( i1 == nVerts ) i1 = 0; i2 = i1+1; if( i2 == nVerts ) i2 = 0; // calc first basis vector ix1 = Verts[i1].x; iy1 = Verts[i1].y; iz1 = Verts[i1].z; ibx1 = ix1 - ix0; iby1 = iy1 - iy0; ibz1 = iz1 - iz0; // normalize b1 ilen2 = ibx1*ibx1 + iby1*iby1 + ibz1*ibz1; ilen = Sqrt( ilen2 ); if( Test(ilen)==0 ) continue; // avoid division by zero ibx1 = ibx1 / ilen; iby1 = iby1 / ilen; ibz1 = ibz1 / ilen; // calc second basis vector of plane ix2 = Verts[i2].x; iy2 = Verts[i2].y; iz2 = Verts[i2].z; ibx2 = ix2 - ix0; iby2 = iy2 - iy0; ibz2 = iz2 - iz0; // project vector onto b1 ilen = ibx2*ibx1 + iby2*iby1 + ibz2*ibz1; // get the component orthogonal to b1 ibx2 = ibx2 - ilen * ibx1; iby2 = iby2 - ilen * iby1; ibz2 = ibz2 - ilen * ibz1; // normalize b2 ilen2 = ibx2*ibx2 + iby2*iby2 + ibz2*ibz2; ilen = Sqrt( ilen2 ); if( Test(ilen)==0 ) continue; // avoid division by zero ibx2 = ibx2 / ilen; iby2 = iby2 / ilen; ibz2 = ibz2 / ilen; // calculate the crossproduct of b1 and b2 inx = iby1*ibz2 - ibz1*iby2; iny = ibz1*ibx2 - ibx1*ibz2; inz = ibx1*iby2 - iby1*ibx2; // normalize it (superfluous since b1 and b2 are orthonormal) ilen2 = inx*inx + iny*iny + inz*inz; ilen = Sqrt( ilen2 ); if( Test(ilen)==0 ) continue; inx = inx / ilen; iny = iny / ilen; inz = inz / ilen; rat1 = GetRatio(inx*inx + iny*iny + inz*inz); if( rat1 < rat ) { rat = rat1; irat0 = i0; irat1 = i1; irat2 = i2; } } if( (irat0 < 0) || (rat == rtr<double>::giant()) ) return false; i0 = irat0; i1 = irat1; i2 = irat2; // the same calculation as above, now with floating point arithmetic o = Verts[i0]; v1 = Verts[i1] - o; v2 = Verts[i2] - o; normalize(&b1,v1); b2 = v2 - (v2*b1)*b1; normalize(&b2,b2); b3 = cross_product(b1,b2); normalize(&b3,b3); return true; }

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. { polyline pl; Ptr< point2<T> > P2; Ptr<T> v3,v2; List< ListNode<segment> > segs,outsegs; ListNode<segment> *seg; graph_edge_list E; graph_vertex_list V; rational far_minx,far_maxx,far_miny,far_maxy; T minx,maxx,miny,maxy; T dx,dy,scale,scalei; int i,left; List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *L; graph_edge *e; List< ListNode<graph_edge *> > *Le; unsigned long *cbuf = (unsigned long *)alloca(gul::rtr<T>::mantissa_length()); if( !nP ) return false; // project vertices onto plane P2.reserve_pool(nP); v3.reserve_pool(4); v2.reserve_pool(4); for( i = 0; i < nP; i++ ) { v3[0] = P[i].x; v3[1] = P[i].y; v3[2] = P[i].z; v3[3] = (T)1; VMProduct(4,4,v3,Ti,v2); P2[i].x = v2[0]; P2[i].y = v2[1]; } CalcBoundingBoxE( nP, P2, minx, maxx, miny, maxy ); dx = maxx - minx; dy = maxy - miny; scale = dx > dy ? dx : dy; minx -= scale; miny -= scale; scalei = (T)1.0/scale; /* Dump<float>::set_transformation(minx,miny,scale,scale); */ pl.init( nP, P2, minx, miny, scalei ); AppendContour( &pl, 0, 1, segs ); IntersectSegments( segs, &E, &V, true ); /* std::cout << "EDGES AFTER INTERSECTION\n"; std::cout << "========================\n"; Dump<float>::dump_edges( E.head ); std::cout << "\n"; */ far_miny = far_minx = rational( guar::ULong(0x100000), -1 ); far_maxy = far_maxx = rational( coord2int((T)2,cbuf),cbuf) + rational( guar::ULong(0x100000) ); RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, 1, 0, outsegs ); e = E.First(); if( !e ) return false; // internal error // backpointer to the segment edge lists which contain the fist edge L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *) e->reserved[1].p; // the first backpointed List Le = L->First()->el.m_L; // find the corresponding segment for( seg = segs.First(); seg != 0; seg = seg->next ) if( &seg->el.e == Le ) break; if( !seg ) return false; // internal error if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) left = e->f[1].i; // edge orientation different else left = e->f[0].i; lefthanded = (left != 1); // check if there were self-intersections for( seg = segs.First(); seg != 0; seg = seg->next ) if( seg->el.e.nElems != 1 ) break; selfintersect = (seg != 0); // delete data which would not be automatically destructed e = E.First(); while( e ) // delete backpointer lists { L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *) e->reserved[1].p; L->DeleteElems(); delete L; e->reserved[1].p = 0; e = e->next; } return true; }

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

Definition at line 86 of file gugr_basics.h. { return i * gul::rtr<T>::epsilon() + (T)1.0; }

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

Definition at line 96 of file gugr_basics.h. { rational q,r,rd,h; T flt; f.div_mod(&q,&r); rd = r/f.denominator(); h = rational(ULong(1))/rational(ULong(2)); if( compare(rd,h) >= 0 ) q = q + rational(ULong(1)); guar::IntTo<T>(q.m->m_na,q.m->m_a,flt); *ret = cnv2coord(flt); }

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

Definition at line 45 of file gugr_split.cpp. { rational &r1 = ((cut_record *)p1)->val, &r2 = ((cut_record *)p2)->val; int sign; sign = compare( r1, r2 ); return(sign); }

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(). { graph_edge *e = (graph_edge *)p1; edge_interval *ei = (edge_interval *)p2; if( CompareEdgesBU( e, ei->l ) <= 0 ) return(-1); if( CompareEdgesBU( e, ei->r ) < 0 ) return(0); return(1); }

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(). { graph_edge *e = (graph_edge *)p1; edge_interval *ei = (edge_interval *)p2; if( CompareEdgesTD( e, ei->l ) <= 0 ) return(-1); if( CompareEdgesTD( e, ei->r ) < 0 ) return(0); return(1); }

int compare_linerec_to_linerec (  linerec *    L1, linerec *    L2 )

Definition at line 68 of file gugr_planesweep.cpp. { int sign = DetermineOrientation(L2->B, L2->E, L1->B ); if( sign == 0 ) sign = DetermineOrientation(L2->B, L2->E, L1->E ); return sign; }

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(). { int sign = compare( C->x, E->key.x ); if( sign == 0 ) sign = compare( C->y, E->key.y ); return sign; }

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

Definition at line 64 of file gugr_planesweep.cpp. { return DetermineOrientation( L->B, L->E, *P ); }

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(). { if( p1 < p2 ) return -1; else if( p1 == p2 ) return 0; return 1; }

int compare_segment_to_linerec (  segment *    S, linerec *    L )

Definition at line 81 of file gugr_planesweep.cpp. { int sign = DetermineOrientation( L->B, L->E, S->B ); if( sign == 0 ) sign = DetermineOrientation( L->B, L->E, S->E ); return sign; }

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

Definition at line 46 of file gugr_regularize.cpp. { const graph_vertex& v1 = *((graph_vertex *)p1); const graph_vertex& v2 = *((graph_vertex *)p2); int sign; sign = compare( v1.v.v().y, v2.v.v().y ); if( !sign ) sign = -compare( v1.v.v().x, v2.v.v().x ); return(sign); }

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. { const Interval& iAx = A.x.get_bounds(); const Interval& iAy = A.y.get_bounds(); const Interval& iBx = B.x.get_bounds(); const Interval& iBy = B.y.get_bounds(); const Interval& iCx = C.x.get_bounds(); const Interval& iCy = C.y.get_bounds(); const Interval& iDx = D.x.get_bounds(); const Interval& iDy = D.y.get_bounds(); Interval iABx,iABy, iACx,iACy, iADx,iADy; Interval iABcAC,iABdAC; Interval iABcAD,iABdAD; bool flag1 = false, flag2 = false; int sideC,sideD,sign; const rational& rAx = A.x; const rational& rAy = A.y; const rational& rBx = B.x; const rational& rBy = B.y; const rational& rCx = C.x; const rational& rCy = C.y; const rational& rDx = D.x; const rational& rDy = D.y; rational rABx,rABy, rACx,rACy, rADx,rADy; rational rABcAC, rABdAC; rational rABcAD, rABdAD; Interval iLambda; rational rLambda; *match = 0; *code_c = 0; *code_d = 0; iABx = iBx - iAx; iABy = iBy - iAy; iACx = iCx - iAx; iACy = iCy - iAy; iABcAC = iABx*iACy - iABy*iACx; if( iABcAC.m_low > 0.0 ) sideC = +1; else if( iABcAC.m_high < 0.0 ) sideC = -1; else { flag1 = true; rABx = rBx - rAx; rABy = rBy - rAy; rACx = rCx - rAx; rACy = rCy - rAy; rABcAC = rABx*rACy - rABy*rACx; sideC = rABcAC.test(); } *code_c = sideC + 2; if( sideC == 0 ) /* sideC == 0 => check orientation with dot product */ { iABdAC = iABx*iACx + iABy*iACy; if( iABdAC.m_low > 0.0 ) /* 0=angle(AB,AC) < angle(AB,AD) */ { *match = 1; return(-1); } else if( iABdAC.m_high >= 0.0 ) { rABdAC = rABx*rACx + rABy*rACy; if( rABdAC.test() > 0.0 ) /* 0=angle(AB,AC) < angle(AB,AD) */ { *match = 1; return(-1); } } /* now angle(AB,AC) == 180 if sideC == 0 */ } iADx = iDx - iAx; iADy = iDy - iAy; iABcAD = iABx*iADy - iABy*iADx; if( iABcAD.m_low > 0.0 ) sideD = +1; else if( iABcAD.m_high < 0.0 ) sideD = -1; else { flag2 = true; rADx = rDx - rAx; rADy = rDy - rAy; if( !flag1 ) { rABx = rBx - rAx; rABy = rBy - rAy; } rABcAD = rABx*rADy - rABy*rADx; sideD = rABcAD.test(); } *code_d = sideD + 2; if( sideD == 0 ) /* sideD == 0 => check orientation with dot product */ { if( sideC == 0 ) { *match = 2; return(+1); } iABdAD = iABx*iADx + iABy*iADy; if( iABdAD.m_low > 0.0 ) /* 0=angle(AB,AD) < angle(AB,AC) */ { *match = 2; return(+1); } else if( iABdAD.m_high >= 0.0 ) /* exact calculation if necessary */ { rABdAD = rABx*rADx + rABy*rADy; if( rABdAD.test() > 0.0 ) /* 0=angle(AB,AD) < angle(AB,AC) */ { *match = 2; return(+1); } } /* now angle(AB,AD) == 180 if sideD == 0 */ if( sideC > 0 ) return(-1); return(+1); } if( sideC == 0 ) { if( sideD > 0 ) return(+1); return(-1); } if( sideC > sideD ) return(-1); else if( sideC < sideD ) return(+1); /* intersect Line(C,AB) and Line(A,AD) */ iLambda = (iADx*iACy - iACx*iADy)/(iABx*iADy - iABy*iADx); if( iLambda.m_low > 0.0 ) { if( sideC > 0 ) return(+1); /* angle(AB,AC) > angle(AB,AD) */ return(-1); } if( iLambda.m_high < 0.0 ) { if( sideC > 0 ) return(-1); /* angle(AB,AC) < angle(AB,AD) */ return(+1); } if( !flag1 ) { rACx = rCx - rAx; rACy = rCy - rAy; } if( !flag2 ) { if( !flag1 ) { rABx = rBx - rAx; rABy = rBy - rAy; } rADx = rDx - rAx; rADy = rDy - rAy; } rLambda = (rADx*rACy - rACx*rADy)/(rABx*rADy - rABy*rADx); sign = rLambda.test(); if( sign > 0 ) { if( sideC > 0 ) return(+1); /* angle(AB,AC) > angle(AB,AD) */ return(-1); } if( sideC > 0 ) return(-1); /* angle(AB,AC) < angle(AB,AD) */ return(+1); }

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

Definition at line 179 of file gugr_regularize.cpp. { int sign; if( A == B ) return(0); if( IS_INF(*A) ) return( INF_SIGN(*A) ); if( IS_INF(*B) ) return( -INF_SIGN(*B) ); if( A->v[0] != B->v[0] ) { sign = DetermineOrientation( B->v[0]->v.v(), B->v[1]->v.v(), A->v[0]->v.v() ); } else { sign = DetermineOrientation( B->v[0]->v.v(), B->v[1]->v.v(), A->v[1]->v.v() ); } return(-sign); }

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

Definition at line 199 of file gugr_regularize.cpp. { int sign; if( A == B ) return(0); if( IS_INF(*A) ) return( INF_SIGN(*A) ); if( IS_INF(*B) ) return( -INF_SIGN(*B) ); if( A->v[1] != B->v[1] ) { sign = DetermineOrientation( B->v[0]->v.v(), B->v[1]->v.v(), A->v[1]->v.v() ); } else { sign = DetermineOrientation( B->v[0]->v.v(), B->v[1]->v.v(), A->v[0]->v.v() ); } return(-sign); }

void gugr::ConnectEdge (  graph_edge *    e, int    maxE )

Definition at line 838 of file gugr_basics.cpp. { graph_edge *left, *right, **E; graph_vertex *v0 = e->v[0], *v1 = e->v[1]; int ileft, iright, codel, coder, nE; E = (graph_edge **)alloca( sizeof(graph_edge *) * maxE ); if( E == NULL ) throw AllocError(); nE = IncidentEdges( v0, E ); if( nE > 0 ) { EdgeInsertPosition( v0->v, v1->v, nE, E, &ileft, &iright, &codel, &coder ); left = E[ileft]; right = E[iright]; if( left->v[0] == v0 ) left->e[0] = e; else left->e[1] = e; e->e[0] = right; } else { v0->e = e; e->e[0] = e; } nE = IncidentEdges( v1, E ); if( nE > 0 ) { EdgeInsertPosition( v1->v, v0->v, nE, E, &ileft, &iright, &coder, &codel ); left = E[ileft]; right = E[iright]; if( left->v[0] == v1 ) left->e[0] = e; else left->e[1] = e; e->e[1] = right; } else { v1->e = e; e->e[1] = e; } }

void ContainmentTree (  List< ListNode< segment > > &    insegs, const rational &    far_maxx, const rational &    far_maxy, gul::List< contour_node > &    contours, contour_node &    universe )

Definition at line 178 of file gugr_bool.cpp. { graph_edge_list E; graph_vertex_list V; List< ListNode<segment> > segs; contour_node *cn; graph_edge *e; int end,side,n,i; graph_edge **TE; ListNode<graph_edge *> *en; contour_node *CA,*CB; RefMap<void>::Node mn; Ptr<void *> edges; int nEdges; List<ListNode<gul::polyline<point2<rational> > > > testC; IntersectSegments( insegs, &E, &V, false ); // cout << dump_graph(&V,&E); FindContours(E,V,far_maxx,far_maxy,segs,contours); // cout << dump_graph(&V,&E); // cout << dump_segs(&segs); E.DeleteElems(); V.DeleteElems(); // travert the help lines and build the containment tree IntersectSegments( segs, &E, &V, false ); // cout << dump_graph(&V,&E); TE = (graph_edge **)alloca(sizeof(graph_edge *)*E.nElems); edges.reserve_pool(E.nElems); for( cn = contours.First(); cn != 0; cn = cn->next ) // travert contours { CA = &universe; // current open contour above (or right) of help line CB = &universe; // current open contour below (or left) of help line if( !cn->hseg ) continue; // dump_segment(cn->hseg,cout); en = cn->hseg->e.First(); if( en ) { e = en->el; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) end = 1; else end = 0; side = !end; } while( en ) { en = en->next; if( !en ) break; // the last edge is a special case n = EdgeCycle( e, e->v[end], TE ); for( i = 1; TE[i] != en->el; i++ ) // edges above help line (or left of { // vertical help line) CT_DoAboveEdge( TE[i], e->v[end], &CA, &CB ); } for( i = n-1; TE[i] != en->el; i-- ) // edges below help line (or right of { // vertical help line) CT_DoBelowEdge( TE[i], e->v[end], &CA, &CB ); } e = en->el; // next edge } // last edge, its endpoint lies on the segment of the contour which // shall be classified. it is sufficient to do the classification // with one of the edges of these segment nEdges = cn->seg->e.nElems; for( en = cn->seg->e.First(), i=0; en != 0; en = en->next, i++ ) edges[i] = en->el; heapsort( nEdges, edges ); n = EdgeCycle( e, e->v[end], TE ); for( i = 1; ; i++ ) // edges above help line until edge on segment reached { CT_DoAboveEdge( TE[i], e->v[end], &CA, &CB ); if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 ) break; } for( i = n-1; ; i-- ) // edges below help line until edge on segment reached { CT_DoBelowEdge( TE[i], e->v[end], &CA, &CB ); if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 ) break; } } // cleanup ISDeleteOwnerMaps(E); /* int j; cn = contours.First(); j = 0; while( cn ) { j++; cout << "CONTOUR #" << j << " (" << (void *)cn << ")\n"; cout << dump_vector<void*>(cn->nOwners, cn->owners); for( i = 0; i < cn->nVerts; i++ ) cout << "(" << cn->verts[i].v() << "), "; cout << "\n"; cn = cn->next; } */ // cout << "containment tree\n"; // universe.dump(0); }

template GULAPI void ConvertToFloatPoly (  List< ListNode< gul::polyline< point2< rational > > > > &    inA, double    minx, double    miny, double    scale, List< ListNode< gul::polyline< point2< double > > > > &    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<class T> GULAPI void gugr::ConvertToFloatPoly (  List< ListNode< gul::polyline< point2< rational > > > > &    inA, T    minx, T    miny, T    scale, List< ListNode< gul::polyline< point2< T > > > > &    outA )

Definition at line 659 of file gugr_bool.cpp. { ListNode<gul::polyline<point2<rational> > > *c; ListNode<gul::polyline<point2<T> > > *fc; Interval ix,iy; T x,y; int i; c = inA.First(); while( c ) { fc = new ListNode<gul::polyline<point2<T> > >; fc->el.P.reserve_pool(c->el.n); fc->el.n = c->el.n; outA.Append(fc); for( i = 0; i < c->el.n; i++ ) { ix = c->el.P[i].x.get_bounds(); iy = c->el.P[i].y.get_bounds(); x = (T)((ix.m_low+ix.m_high)/2.0); y = (T)((iy.m_low+iy.m_high)/2.0); x = gugr::cnv2coord(x)*scale + minx; y = gugr::cnv2coord(y)*scale + miny; fc->el.P[i].x = x; fc->el.P[i].y = y; } c = c->next; } }

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 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<class T> GULAPI void gugr::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 )

Definition at line 568 of file gugr_bool.cpp. { T minx,maxx,miny,maxy; T dx,dy,scale,scalei; ListNode< gugr::polyline > *pn; ListNode< gul::polyline<point2<T> > > *c; unsigned long *cbuf = (unsigned long *)alloca(gul::rtr<T>::mantissa_length()); c = A.First(); CalcBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy ); c = c->next; while( c ) { UpdateBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy ); c = c->next; } c = B.First(); while( c ) { UpdateBoundingBoxE( c->el.n, c->el.P, minx, maxx, miny, maxy ); c = c->next; } dx = maxx - minx; dy = maxy - miny; scale = dx > dy ? dx : dy; minx -= scale; miny -= scale; scalei = (T)1/scale; c = A.First(); while( c ) { pn = new ListNode<gugr::polyline>(); PA.Append( pn ); pn->el.init( c->el.n, c->el.P, minx, miny, scalei ); c = c->next; } c = B.First(); while( c ) { pn = new ListNode<gugr::polyline>(); PB.Append( pn ); pn->el.init( c->el.n, c->el.P, minx, miny, scalei ); c = c->next; } *ret_minx = minx; *ret_miny = miny; *ret_scale = scale; *ret_far_y = *ret_far_x = rational(coord2int((T)2,cbuf),cbuf) + rational(ULong(0x100000)); }

int coord2int (  float    f, unsigned long *    buf )  [inline]

Definition at line 67 of file gugr_basics.h. { unsigned long i; // gul::Assert<InternalError>( ndebug | (1.0f <= f && f <= 2.0f) ); if( f < 1.0f ) f = 1.0f; else if( f > 2.0f ) f = 2.0f; i = (unsigned long)(f * gul::rtr<float>::epsilon_inv()); i -= (unsigned long)gul::rtr<float>::epsilon_inv(); if( !i ) return 0; buf[0] = i; return 1; }

int coord2int (  double    f, unsigned long *    buf )  [inline]

Definition at line 44 of file gugr_basics.h. Referenced by gugr::polyline::init(). { gul::uint64 i; unsigned long hi,lo; // gul::Assert<gul::InternalError>( ndebug | (1.0 <= f && f <= 2.0) ); if( f < 1.0 ) f = 1.0; else if( f > 2.0 ) f = 2.0; i = (gul::uint64)(f*gul::rtr<double>::epsilon_inv()); i -= (gul::uint64)gul::rtr<double>::epsilon_inv(); hi = (unsigned long)((i >> 32) & LL(0xffffffff)); lo = (unsigned long)(i & LL(0xffffffff)); if( !hi ) { if( !lo ) return 0; buf[0] = lo; return 1; } buf[0] = lo; buf[1] = hi; return 2; }

void CT_DoAboveEdge (  graph_edge *    e, graph_vertex *    v, contour_node **    pCA, contour_node **    pCB )

Definition at line 46 of file gugr_bool.cpp. { RefMap<void> *Mout,*Min,*M; RefMap<void>::Node mn; contour_node *CA,*CB,*C,*Cout,*Cin; CA = *pCA; CB = *pCB; if( e->v[0] == v ) { Mout = (RefMap<void> *)e->f[1].p; Min = (RefMap<void> *)e->f[0].p; } else { Mout = (RefMap<void> *)e->f[0].p; Min = (RefMap<void> *)e->f[1].p; } Cout = Cin = 0; M = Mout; mn = M->First(); while( !mn.IsEmpty() ) // because of the first planesweep edge/side { // pairs can have only one owner contour if( mn.key() ) { Cout = (contour_node *)mn.key(); break; } mn = M->Successor( mn ); } M = Min; mn = M->First(); while( !mn.IsEmpty() ) { if( mn.key() ) { Cin = (contour_node *)mn.key(); break; } mn = M->Successor( mn ); } C = Cout; if( !C ) return; // ignore help lines of other contours if( C != CA ) { CA->Insert( C ); CA = C; } else CA = CA->parent; C = Cin; if( C != CA ) { CA->Insert( C ); CA = C; } else CA = CA->parent; *pCA = CA; *pCB = CB; }

void CT_DoBelowEdge (  graph_edge *    e, graph_vertex *    v, contour_node **    pCA, contour_node **    pCB )

Definition at line 112 of file gugr_bool.cpp. { RefMap<void> *Mout,*Min,*M; RefMap<void>::Node mn; contour_node *CA,*CB,*C,*Cout,*Cin; CA = *pCA; CB = *pCB; if( e->v[0] == v ) { Mout = (RefMap<void> *)e->f[0].p; Min = (RefMap<void> *)e->f[1].p; } else { Mout = (RefMap<void> *)e->f[1].p; Min = (RefMap<void> *)e->f[0].p; } Cout = Cin = 0; M = Mout; mn = M->First(); while( !mn.IsEmpty() ) // because of the first planesweep edge/side { // pairs can have only one owner contour if( mn.key() ) { Cout = (contour_node *)mn.key(); break; } mn = M->Successor( mn ); } M = Min; mn = M->First(); while( !mn.IsEmpty() ) { if( mn.key() ) { Cin = (contour_node *)mn.key(); break; } mn = M->Successor( mn ); } C = Cout; if( !C ) return; // ignore help lines of other contours if( C != CB ) { CB->Insert( C ); CB = C; } else CB = CB->parent; C = Cin; if( C != CB ) { CB->Insert( C ); CB = C; } else CB = CB->parent; *pCA = CA; *pCB = CB; }

int gugr::DetermineOrientation (  const point2< rational > &    A, const point2< rational > &    B, const point2< rational > &    C )

Definition at line 476 of file gugr_basics.cpp. { const Interval& ix1 = A.x.get_bounds(); const Interval& iy1 = A.y.get_bounds(); const Interval& ix2 = B.x.get_bounds(); const Interval& iy2 = B.y.get_bounds(); const Interval& ix = C.x.get_bounds(); const Interval& iy = C.y.get_bounds(); Interval i; i = (ix2-ix1)*(iy-iy1) - (ix-ix1)*(iy2-iy1); if( i.m_low > 0.0 ) return(+1); else if( i.m_high < 0.0 ) return(-1); const rational& x1 = A.x; const rational& y1 = A.y; const rational& x2 = B.x; const rational& y2 = B.y; const rational& x = C.x; const rational& y = C.y; rational det; det = (x2-x1)*(y-y1) - (x-x1)*(y2-y1); return( det.test() ); }

int gugr::DetermineOrientationPV (  const point2< rational > &    A, const point2< rational > &    AB, const point2< rational > &    C )

Definition at line 503 of file gugr_basics.cpp. { const Interval& ix1 = A.x.get_bounds(); const Interval& iy1 = A.y.get_bounds(); const Interval& ix1x2 = AB.x.get_bounds(); const Interval& iy1y2 = AB.y.get_bounds(); const Interval& ix = C.x.get_bounds(); const Interval& iy = C.y.get_bounds(); Interval i; i = ix1x2*(iy-iy1) - (ix-ix1)*iy1y2; if( i.m_low > 0.0 ) return(+1); else if( i.m_high < 0.0 ) return(-1); const rational& x1 = A.x; const rational& y1 = A.y; const rational& x1x2 = AB.x; const rational& y1y2 = AB.y; const rational& x = C.x; const rational& y = C.y; rational det; det = x1x2*(y-y1) - (x-x1)*y1y2; return( det.test() ); }

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 )  [inline]

Definition at line 125 of file gugr_bool.h. { T minx,miny,scale; rational far_x,far_y; gul::List<gul::ListNode<gugr::polyline> > PA,PB; gul::List<gul::ListNode<gul::polyline<gul::point2<rational> > > > PC; ConvertToRationalPolys(fPA,fPB,&minx,&miny,&scale,&far_x,&far_y,PA,PB); // DumpPS<T>::set_transformation(minx,miny,scale,scale); DoDifference(PA,PB,far_x,far_y,PC); ConvertToFloatPoly(PC,minx,miny,scale,fPC); }

void DifferenceSubTree (  contour_node *    C, int    oset, int    InA, int    OutB, List< ListNode< gul::polyline< point2< rational > > > > &    pl )

Definition at line 413 of file gugr_bool.cpp. { ListNode<gul::polyline<point2<rational> > > *pln; gul::ptr_int_union UA,UB; gul::RefMap<void>::Node cn; bool store; UA.set_i(InA); UB.set_i(OutB); store = false; if( oset == InA ) { if( C->hasOwner(UA.p) ) oset ^= InA; if( C->hasOwner(UB.p) ) oset ^= OutB; if( oset != InA ) store = true; } else { if( C->hasOwner(UA.p) ) oset ^= InA; if( C->hasOwner(UB.p) ) oset ^= OutB; if( oset == InA ) store = true; } if( store ) { pln = new ListNode<gul::polyline<point2<rational> > >(); C->get_polyline_joined( pln->el ); pl.Append(pln); } // travert children cn = C->childs.First(); while( !cn.IsEmpty() ) { DifferenceSubTree( (contour_node *)cn.key(), oset, InA, OutB, pl ); cn = C->childs.Successor( cn ); } }

int gugr::DisconnectEdge (  graph_edge *    e, int    maxE )

Definition at line 892 of file gugr_basics.cpp. { graph_edge *left, *right, **E; graph_vertex *v; int n,isolated; E = (graph_edge **)alloca( sizeof(graph_edge *) * maxE ); if( E == NULL ) throw AllocError(); isolated = 0; v = e->v[0]; n = EdgeCycle( e, v, E ); if( n > 1 ) { right = E[1]; left = E[n-1]; if( left->v[0] == v ) left->e[0] = right; else left->e[1] = right; if( v->e == e ) v->e = left; } else isolated |= 1; v = e->v[1]; n = EdgeCycle( e, v, E ); if( n > 1 ) { right = E[1]; left = E[n-1]; if( left->v[0] == v ) left->e[0] = right; else left->e[1] = right; if( v->e == e ) v->e = left; } else isolated |= 2; return isolated; }

void gugr::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 )

Definition at line 477 of file gugr_split.cpp. { graph_edge **E; cut_record *rec; int nE,L1,L2,R1,R2,match1,match2,cL1,cR1,cL2,cR2; vertex farleft,farright; graph_edge *ah,*el,*bl,*bh,*er,*al, *e, *eu, *ew; graph_vertex *v, *lva, *lvb, *vu, *vl, *delv; int fa,fb,nfa,nfb; line hori; farleft = vertex( point2<rational>(far_left,Sa->val) ); farright = vertex( point2<rational>(far_right,Sa->val) ); hori = line( farleft.v(), rational(ULong(1)), rational() ); E = (graph_edge **)alloca( sizeof(graph_edge *)*maxE ); if( E == NULL ) throw AllocError(); rec = Sa->R.head; fa=fb=nfa=nfb=0; /* new vertex for strip above cutting line*/ v = new graph_vertex( point2<rational>(minx,Sa->val), NULL ); Sa->V.Append(v); lva = *minSaV = v; /* new vertex for strip below cutting line */ v = new graph_vertex(lva->v, NULL); Sb->V.Append(v); lvb = *minSbV = v; delv = 0; while( rec != NULL ) { if( rec->v != NULL ) /* vertex on cutting line */ { nE = IncidentEdges( rec->v, E ); match1 = EdgeInsertPosition( rec->v->v, farleft, nE, E, &L1, &R1, &cL1, &cR1 ); cL1 = 2-(cL1-2); cR1 = 2-(cR1-2); if( cL1 == 1 ) /* special case: E[L1] below cutting line */ { bh= E[L1]; er = al = ah = NULL; if( cR1 == 2 ) { el = E[R1]; bl = E[R1]->e[0]; } else { el = NULL; bl = E[R1]; } } else if( cL1 == 2 ) /* special case: E[L1] on cutting line */ { er = E[L1]; al = ah = NULL; if( cR1 == 2 ) { el = E[R1]; if( el->e[0] == er ) bl = NULL; else bl = el->e[0]; } else { bl = E[R1]; el = NULL; } bh = bl; if( bh != NULL ) while( bh->e[1] != er ) bh = bh->e[1]; } else /* E[L1] above cutting line */ { ah = E[L1]; if( cR1 == 3 ) /* E[R1] above cutting line */ { el = bl = bh = er = NULL; al = E[R1]; } else if( (cR1 == 2) && (!match1) ) /* E[R1] on cutting line */ { /* but different orientation */ el = bl = bh = NULL; er = E[R1]; al = E[R1]->e[1]; /* using edge orientatation and that cutting line is horizontal ! */ } else { match2 = EdgeInsertPosition( rec->v->v, farright, nE, E, &L2, &R2, &cL2, &cR2 ); if( match1 ) /* E[R1] on cutting line, same orientation */ { el = E[R1]; if( cL2 == 1 ) { bl = E[R1]->e[0]; bh = E[L2]; } else bl = bh = NULL; } else { el = NULL; bl = E[R1]; bh = E[L2]; } if( cR2 == 2 ) /* R2 on cutting line */ { er = E[R2]; al = E[R2]->e[1]; } else { er = NULL; al = E[R2]; } } } if( el != NULL ) { fb = el->f[0].i; fa = el->f[1].i; } if( al != NULL ) { /* create new vertex: */ v = new graph_vertex( ah->v[0]->v, ah ); Sa->V.Append(v); ah->e[0] = al; /* connect upper edges to new vertex */ e = al; do { e->v[0] = v; e = e->e[0]; } while( e != al ); if( el == NULL ) fa = ah->f[0].i; /* create new edge */ e = new graph_edge(); Sa->E.Append(e); e->l = hori; e->f[0].set_i(fb); e->f[1].set_i(fa); e->e[0] = al; ah->e[0] = e; if( lva->e != NULL ) { e->e[1] = lva->e->e[0]; lva->e->e[0] = e; } else { e->e[1] = e; lva->e = e; } v->e = e; e->v[0] = v; e->v[1] = lva; lva = v; nfa = nfb = al->f[1].i; } if( bl != NULL ) { /* create new vertex: */ v = new graph_vertex( bl->v[1]->v, bh ); Sb->V.Append(v); bh->e[1] = bl; /* connect edges below to new vertex */ e = bl; do { Sa->E.Remove(e); Sb->E.Append(e); e->v[1] = v; e = e->e[1]; } while( e != bl ); if( el == NULL ) fb = bl->f[0].i; /* create new edge */ e = new graph_edge(); Sb->E.Append(e); e->l = hori; e->f[0].set_i(fb); e->f[1].set_i(fa); e->e[0] = bl; bh->e[1] = e; if( lvb->e != NULL ) { e->e[1] = lvb->e->e[1]; lvb->e->e[1] = e; } else { e->e[1] = e; lvb->e = e; } e->v[0] = v; e->v[1] = lvb; lvb = v; nfa = nfb = bh->f[1].i; } if( er != NULL ) { fa = er->f[1].i; fb = er->f[0].i; } else { fa = nfa; fb = nfb; } Sa->V.Remove( rec->v ); /* remove original vertex */ delete delv; /* delayed deletion of vertex from original graph */ delv = rec->v; if( el != NULL ) { /* remove original horizontal edge */ Sa->E.Remove(el); delete el; } } else /* cutting line intersects edge */ { ew = rec->e; /* new vertex for strip above cutting line */ vu = new graph_vertex( point2<rational>(rec->val,Sa->val), NULL ); Sa->V.Append(vu); /* new vertex for strip below cutting line */ vl = new graph_vertex( vu->v, NULL ); Sb->V.Append(vl); /* new edge for upper halve of intersecting edge */ eu = new graph_edge(); Sa->E.Append(eu); eu->l = ew->l; eu->f[0] = ew->f[0]; eu->f[1] = ew->f[1]; eu->v[0] = vu; eu->v[1] = ew->v[1]; eu->e[0] = NULL; if( ew->e[1] != ew ) { eu->e[1] = ew->e[1]; nE = EdgeCycle( ew, ew->v[1], E ); e = E[nE-1]; if( e->e[0] == ew ) e->e[0] = eu; else e->e[1] = eu; } else eu->e[1] = eu; ew->v[1]->e = eu; /* shorten intersecting edge and add it to lower strip */ Sa->E.Remove(ew); Sb->E.Append(ew); ew->v[1] = vl; ew->e[1] = NULL; vu->e = eu; /* set vertex pointers to an incident edge */ vl->e = ew; /* create new horizontal edge for upper strip */ e = new graph_edge(); Sa->E.Append(e); e->l = hori; e->f[0] = e->f[1] = ew->f[0]; /* same face below and above */ e->e[0] = eu; eu->e[0] = e; if( lva->e != NULL ) { e->e[1] = lva->e->e[0]; lva->e->e[0] = e; } else { e->e[1] = e; lva->e = e; } vu->e = e; e->v[0] = vu; e->v[1] = lva; /* create new horizontal edge for lower strip */ e = new graph_edge(); Sb->E.Append(e); e->l = hori; e->f[0] = e->f[1] = ew->f[0]; /* same face below and above */ e->e[0] = ew; ew->e[1] = e; if( lvb->e != NULL ) { e->e[1] = lvb->e->e[1]; lvb->e->e[1] = e; } else { e->e[1] = e; lvb->e = e; } vl->e = ew; e->v[0] = vl; e->v[1] = lvb; lva = vu; lvb = vl; fa = fb = ew->f[1].i; } rec = rec->next; } delete delv; /* new vertex for strip above cutting line */ v = new graph_vertex( point2<rational>(maxx,Sa->val), NULL ); *maxSaV = v; Sa->V.Append(v); /* create new horizontal edge for upper strip */ e = new graph_edge(); Sa->E.Append(e); e->l = hori; e->f[0].set_i(fb); e->f[1].set_i(fa); e->e[0] = e; if( lva->e != NULL ) { e->e[1] = lva->e->e[0]; lva->e->e[0] = e; } else { e->e[1] = e; lva->e = e; } v->e = e; e->v[0] = v; e->v[1] = lva; /* new vertex for strip below cutting line */ v = new graph_vertex( v->v, NULL ); *maxSbV = v; Sb->V.Append(v); /* create new horizontal edge for lower strip */ e = new graph_edge(); Sb->E.Append(e); e->l = hori; e->f[0].set_i(fb); e->f[1].set_i(fa); e->e[0] = e; if( lvb->e != NULL ) { e->e[1] = lvb->e->e[1]; lvb->e->e[1] = e; } else { e->e[1] = e; lvb->e = e; } v->e = e; e->v[0] = v; e->v[1] = lvb; }

void gugr::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 )

Definition at line 1009 of file gugr_split.cpp. { graph_edge **E; cut_record *rec; int nE,L1,L2,R1,R2,match1,match2,cL1,cR1,cL2,cR2,iv,sign,ew_ori; vertex farbottom,fartop; graph_edge *ah,*el,*bl,*bh,*er,*al, *e, *eu, *ew; graph_vertex *v, *lva, *lvb, *vu, *vl, *delv; int fa,fb,nfa,nfb; line verti; farbottom = vertex( point2<rational>(Sb->val,far_bottom) ); fartop = vertex( point2<rational>(Sb->val,far_top) ); verti = line( farbottom.v(), rational(), rational(ULong(1)) ); E = (graph_edge **)alloca( sizeof(graph_edge *)*maxE ); if( E == NULL ) throw AllocError(); rec = Sb->R.head; fa=fb=nfa=nfb=0; /* new vertex for strip left from cutting line*/ v = *minSaV = new graph_vertex( point2<rational>(Sb->val,miny), NULL ); Sa->V.Append(v); lva = v; /* new vertex for strip right from cutting line */ v = *minSbV = new graph_vertex(lva->v, NULL); Sb->V.Append(v); lvb = v; delv = 0; while( rec != NULL ) { if( rec->v != NULL ) /* vertex on cutting line */ { nE = IncidentEdges( rec->v, E ); match1 = EdgeInsertPosition( rec->v->v, farbottom, nE, E, &L1, &R1, &cL1, &cR1 ); cL1 = 2-(cL1-2); cR1 = 2-(cR1-2); if( cL1 == 1 ) /* special case: E[L1] left from cutting line */ { bh = E[L1]; er = al = ah = NULL; if( cR1 == 2 ) { el = E[R1]; bl = E[R1]->e[1]; } else { el = NULL; bl = E[R1]; } } else if( cL1 == 2 ) /* special case: E[L1] on cutting line */ { er = E[L1]; al = ah = NULL; if( cR1 == 2 ) { el = E[R1]; if( el->e[1] == er ) bl = NULL; else bl = el->e[1]; } else { bl = E[R1]; el = NULL; } bh = bl; if( bh != NULL ) { e = (bh->v[0] == rec->v ? bh->e[0] : bh->e[1]); while( e != er ) { bh = e; e = (bh->v[0] == rec->v ? bh->e[0] : bh->e[1]); } } } else /* E[L1] right from cutting line */ { ah = E[L1]; if( cR1 == 3 ) /* E[R1] right from cutting line */ { el = bl = bh = er = NULL; al = E[R1]; } else if( (cR1 == 2) && (!match1) ) /* E[R1] on cutting line */ { /* but different orientation */ el = bl = bh = NULL; er = E[R1]; al = E[R1]->e[0]; /* using edge orientatation and that cutting line is vertical ! */ } else { match2 = EdgeInsertPosition( rec->v->v, fartop, nE, E, &L2, &R2, &cL2, &cR2 ); if( match1 ) /* E[R1] on cutting line, same orientation */ { el = E[R1]; if( cL2 == 1 ) { bl = E[R1]->e[1]; bh = E[L2]; } else bl = bh = NULL; } else { el = NULL; bl = E[R1]; bh = E[L2]; } if( cR2 == 2 ) /* R2 on cutting line */ { er = E[R2]; al = E[R2]->e[0]; } else { er = NULL; al = E[R2]; } } } if( el != NULL ) { fb = el->f[1].i; fa = el->f[0].i; } if( al != NULL ) { /* create new vertex: */ iv = (ah->v[0] == rec->v ? 0 : 1); v = new graph_vertex( rec->v->v, ah ); Sa->V.Append(v); ah->e[iv] = al; /* connect edges to the left to new vertex */ e = al; do { Sb->E.Remove(e); Sa->E.Append(e); if( e->v[0] == rec->v ) { e->v[0] = v; e = e->e[0]; } else { e->v[1] = v; e = e->e[1]; } } while( e != al ); if( el == NULL ) fa = ah->f[iv].i; /* create new edge */ e = new graph_edge(); Sa->E.Append(e); e->l = verti; e->f[0].set_i(fa); e->f[1].set_i(fb); e->e[1] = al; ah->e[iv] = e; if( lva->e != NULL ) { if( lva->e->v[0] == lva ) { e->e[0] = lva->e->e[0]; lva->e->e[0] = e; } else { e->e[0] = lva->e->e[1]; lva->e->e[1] = e; } } else { e->e[0] = e; lva->e = e; } v->e = e; e->v[1] = v; e->v[0] = lva; lva = v; nfa = nfb = (al->v[0] == v ? al->f[1].i : al->f[0].i); } if( bl != NULL ) { /* create new vertex: */ v = new graph_vertex( rec->v->v, bh ); Sb->V.Append(v); /* connect edges on the right to new vertex */ if( bh->v[0] == rec->v ) bh->e[0] = bl; else bh->e[1] = bl; e = bl; do { if( e->v[0] == rec->v ) { e->v[0] = v; e = e->e[0]; } else { e->v[1] = v; e = e->e[1]; } } while( e != bl ); if( el == NULL ) if( bl->v[1] == v ) fb = bl->f[0].i; else fb = bl->f[1].i; /* create new edge */ e = new graph_edge(); Sb->E.Append(e); e->l = verti; e->f[0].set_i(fa); e->f[1].set_i(fb); e->e[1] = bl; if( bh->v[0] == v ) bh->e[0] = e; else bh->e[1] = e; if( lvb->e != NULL ) { if( lvb->e->v[0] == lvb ) { e->e[0] = lvb->e->e[0]; lvb->e->e[0] = e; } else { e->e[0] = lvb->e->e[1]; lvb->e->e[1] = e; } } else { e->e[0] = e; lvb->e = e; } e->v[1] = v; e->v[0] = lvb; lvb = v; nfa = nfb = (bh->v[1] == v ? bh->f[1].i : bh->f[0].i); } Sb->V.Remove( rec->v ); /* remove original vertex */ delete delv; /* delayed deletion of vertex from original graph */ delv = rec->v; if( er != NULL ) { fa = er->f[0].i; fb = er->f[1].i; } else { fa = nfa; fb = nfb; } if( el != NULL ) { /* remove original vertical edge */ Sb->E.Remove(el); delete el; } } else /* cutting line intersects edge */ { ew = rec->e; /* new vertex for strip right from cutting line */ vu = new graph_vertex( point2<rational>(Sb->val,rec->val), NULL ); Sb->V.Append(vu); /* new vertex for strip left from cutting line */ vl = new graph_vertex( vu->v, NULL ); Sa->V.Append(vl); /* new edge for right halve of intersecting edge */ eu = new graph_edge(); Sb->E.Append(eu); eu->l = ew->l; eu->f[0] = ew->f[0]; eu->f[1] = ew->f[1]; sign = compare(ew->v[1]->v.v().x, ew->v[0]->v.v().x); if( sign > 0 ) ew_ori = 1; else ew_ori = 0; if( ew_ori ) /*** ew oriented from left to right ***/ { eu->v[0] = vu; eu->v[1] = ew->v[1]; eu->e[0] = NULL; if( ew->e[1] != ew ) { eu->e[1] = ew->e[1]; nE = EdgeCycle( ew, ew->v[1], E ); e = E[nE-1]; if( e->e[0] == ew ) e->e[0] = eu; else e->e[1] = eu; } else eu->e[1] = eu; ew->v[1]->e = eu; /* shorten intersecting edge and add it to left strip */ Sb->E.Remove(ew); Sa->E.Append(ew); ew->v[1] = vl; ew->e[1] = NULL; vu->e = eu; /* set vertex pointers to an incident edge */ vl->e = ew; /* create new vertical edge for right strip */ e = new graph_edge(); Sb->E.Append(e); e->l = verti; e->f[0] = e->f[1] = ew->f[1]; /* same face on left and right side */ /* of edge */ eu->e[0] = e; } else /*** ew oriented from right to left ***/ { eu->v[1] = vu; eu->v[0] = ew->v[0]; eu->e[1] = NULL; if( ew->e[0] != ew ) { eu->e[0] = ew->e[0]; nE = EdgeCycle( ew, ew->v[0], E ); e = E[nE-1]; if( e->e[0] == ew ) e->e[0] = eu; else e->e[1] = eu; } else eu->e[0] = eu; ew->v[0]->e = eu; /* shorten intersecting edge and add it to lower strip */ Sb->E.Remove(ew); Sa->E.Append(ew); ew->v[0] = vl; ew->e[0] = NULL; vu->e = eu; /* set vertex pointers to an incident edge */ vl->e = ew; /* create new vertical edge for right strip */ e = new graph_edge(); Sb->E.Append(e); e->l = verti; e->f[0] = e->f[1] = ew->f[0]; /* same face on left and right side */ /* of edge */ eu->e[1] = e; } e->e[1] = eu; if( lvb->e != NULL ) { if( lvb->e->v[0] == lvb ) { e->e[0] = lvb->e->e[0]; lvb->e->e[0] = e; } else { e->e[0] = lvb->e->e[1]; lvb->e->e[1] = e; } } else { e->e[0] = e; lvb->e = e; } vu->e = eu; e->v[1] = vu; e->v[0] = lvb; /* create new vertical edge for left strip */ e = new graph_edge(); Sa->E.Append(e); e->l = verti; if( ew_ori ) /*** ew oriented from left to right ***/ { e->f[0] = e->f[1] = ew->f[1]; /* same face on left and right side */ e->e[1] = ew; ew->e[1] = e; fa = fb = ew->f[0].i; /* for next intersection */ } else /*** ew oriented from left to right ***/ { e->f[0] = e->f[1] = ew->f[0]; /* same face on left and right side */ e->e[1] = ew; ew->e[0] = e; fa = fb = ew->f[1].i; /* for next intersection */ } if( lva->e != NULL ) { if( lva->e->v[0] == lva ) { e->e[0] = lva->e->e[0]; lva->e->e[0] = e; } else { e->e[0] = lva->e->e[1]; lva->e->e[1] = e; } } else { e->e[0] = e; lva->e = e; } vl->e = e; e->v[1] = vl; e->v[0] = lva; lvb = vu; lva = vl; } rec = rec->next; } delete delv; /* new vertex for strip left from cutting line */ v = new graph_vertex( point2<rational>(Sb->val,maxy), NULL ); *maxSaV = v; Sa->V.Append(v); /* create new vertical edge for left strip */ e = new graph_edge(); Sa->E.Append(e); e->l = verti; e->f[0].set_i(fa); e->f[1].set_i(fb); e->e[1] = e; if( lva->e != NULL ) { if( lva->e->v[0] == lva ) { e->e[0] = lva->e->e[0]; lva->e->e[0] = e; } else { e->e[0] = lva->e->e[1]; lva->e->e[1] = e; } } else { e->e[0] = e; lva->e = e; } v->e = e; e->v[1] = v; e->v[0] = lva; /* new vertex for strip right from cutting line */ v = new graph_vertex( v->v, NULL ); *maxSbV = v; Sb->V.Append(v); /* create new vertical edge for right strip */ e = new graph_edge(); Sb->E.Append(e); e->l = verti; e->f[0].set_i(fa); e->f[1].set_i(fb); e->e[1] = e; if( lvb->e != NULL ) { if( lvb->e->v[0] == lvb ) { e->e[0] = lvb->e->e[0]; lvb->e->e[0] = e; } else { e->e[0] = lvb->e->e[1]; lvb->e->e[1] = e; } } else { e->e[0] = e; lvb->e = e; } v->e = e; e->v[1] = v; e->v[0] = lvb; }

GULAPI void gugr::DoDifference (  List< ListNode< polyline > > &    PA, List< ListNode< polyline > > &    PB, const rational &    far_x, const rational &    far_y, List< ListNode< gul::polyline< point2< rational > > > > &    C )

Definition at line 533 of file gugr_bool.cpp. { const int OutA = 1; const int InA = 2; const int OutB = 4; const int InB = 8; graph_edge_list E; graph_vertex_list V; segment_list S,Stmp; List<contour_node> contours; contour_node universe(0); // pseudo contour which contains everything // get the segments of both polygons and mark them with // InA,OutA,InB,OutB OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S ); OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp ); S += Stmp; // find all contours and build their containment tree ContainmentTree( S, far_x, far_y, contours, universe ); // universe.dump(0); DifferenceSubTree( &universe, 0, InA, OutB, C ); }

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 )

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 )

Definition at line 467 of file gugr_bool.cpp. { const int OutA = 1; const int InA = 2; const int OutB = 4; const int InB = 8; graph_edge_list E; graph_vertex_list V; segment_list S,Stmp; List<contour_node> contours; contour_node universe(0); // pseudo contour which contains everything // get the segments of both polygons and mark them with // InA,OutA,InB,OutB OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S ); OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp ); S += Stmp; // find all contours and build their containment tree ContainmentTree( S, far_x, far_y, contours, universe ); // universe.dump(0); IntersectionSubTree( &universe, 0, InA, InB, C ); }

void gugr::DoIntersectSegments (  int    nsegs, Map< eventrec > &    EvQ, gugr::graph_edge_list *    E, gugr::graph_vertex_list *    V )

Definition at line 754 of file gugr_planesweep.cpp. { Map<eventrec>::Node enode,evnode,evnode1; int side,sign; ListNode<segment *> *begseg; Map<linerec> SwS; segment *seg; ListNode<Map<linerec>::Node> *lrefnode,*lstnode; Map<linerec>::Node lnode,lnodelo,lnodehi,lnode1,lnode2; linerec *vlin = 0, *lin; bool addvend,iflag,iexflag,checkneighbors; RefMap<intersection>::Node irnode, irnode1; intersection *irec; ListNode<linepair> *lpnode; linepair lpair; List<intersection> Ipts; List<intersectionseg> Isegs; int maxE; maxE = nsegs*4; /*--- loop until event queue empty ---*/ for(;;) { enode = EvQ.First(); if( enode.IsEmpty() ) break; // queue empty /*--- process starting vertical segments ---*/ while( enode.key()->BV.nElems > 0 ) { begseg = enode.key()->BV.First(); enode.key()->BV.Remove( begseg ); /* cout << "[processing starting vertical line segment]: "; DumpPS<float>::dump_segment( begseg->el ); */ addvend = false; if( vlin == 0 ) { vlin = new linerec( begseg->el ); delete begseg; addvend = true; } else { vlin->S.Append( begseg ); // add line-segment (using ex. list node) sign = compare( begseg->el->E.y, vlin->E.y ); if( sign > 0 ) { vlin->E = begseg->el->E; /* remove old vertical-line-end event */ vlin->endev.key()->EV = 0; if( (vlin->endev.key()->IsEmpty()) && (vlin->endev.key() != enode.key()) ) { EvQ.RemoveNode( vlin->endev ); EvQ.FreeNode( vlin->endev ); } addvend = true; } } if( addvend ) { /* add new vertical-line-end event */ side = EvQ.SearchNode( &vlin->E, compare_point_to_eventrec, &evnode ); if( side != 0 ) { evnode1 = EvQ.NewNode( vlin->E ); EvQ.InsertNode( evnode1, evnode, side ); evnode = evnode1; } evnode.key()->EV = vlin; vlin->endev = evnode; } } /* check if current event point is a intersection point */ if( enode.key()->I.nElems > 0 ) iexflag = true; else iexflag = false; if( iexflag || ((vlin != 0) && (enode.key()->B.nElems > 0)) || ((vlin != 0) && (!enode.key()->E.IsEmpty())) || ((enode.key()->B.nElems > 0) && (!enode.key()->E.IsEmpty())) ) { iflag = true; if( iexflag ) { /* get the intersection record from one of two intersecting lines */ lin = enode.key()->I.First()->el.L1.key(); side = lin->I.SearchNode( &enode.key()->key, hcompare_point_to_intersection, &irnode ); gul::Assert<InternalError>( ndebug || (side == 0) ); irec = irnode.key(); } else { /* create a new intersection record */ irec = new intersection( enode.key()->key ); Ipts.Append(irec); } } else iflag = false; /* --- add intersection to vertical line --- */ if( vlin && iflag ) { side = vlin->I.SearchNode( &irec->I, vcompare_point_to_intersection, &irnode1 ); if( side != 0 ) { irnode = vlin->I.NewNode(irec); vlin->I.InsertNode( irnode, irnode1, side ); } } /*--- process ending lines ---*/ lrefnode = enode.key()->E.First(); while( lrefnode != 0 ) { /* first element in list of lines ending in current event point */ lnode = lrefnode->el; lrefnode = lrefnode->next; if( iflag ) { /* add intersection record (if not already existing) */ side = lnode.key()->I.SearchNode( &irec->I, hcompare_point_to_intersection, &irnode ); if( side != 0 ) { irnode1 = lnode.key()->I.NewNode(irec); lnode.key()->I.InsertNode( irnode1, irnode, side ); } } lnodelo = SwS.Predecessor( lnode ); /* get neighbors in symetric order */ lnodehi = SwS.Successor( lnode ); SwS.RemoveNode( lnode ); /* remove ending line from symmetric order */ /* intersect neighbors */ if( !lnodelo.IsEmpty() && !lnodehi.IsEmpty() ) intersect( lnodelo, lnodehi, enode.key()->key.x, &EvQ, &Ipts ); } /* process intersecting lines */ while( enode.key()->I.nElems > 0 ) { lpnode = enode.key()->I.First(); enode.key()->I.Remove( lpnode ); lpair = lpnode->el; delete lpnode; // free list node lnode1 = lpair.L1; lnode2 = lpair.L2; if( !SwS.IsRemoved(lnode1) && !SwS.IsRemoved(lnode2) ) { SwS.RemoveNode( lnode1 ); SwS.RemoveNode( lnode2 ); lnode1.key()->B = enode.key()->key; lnode2.key()->B = enode.key()->key; side = SwS.SearchNode( lnode1.key(), compare_linerec_to_linerec, &lnode ); gul::Assert<InternalError>(ndebug | (side!=0) ); SwS.InsertNode(lnode1,lnode,side); // reinsert lnodelo = SwS.Predecessor( lnode1 ); /* get neighbors in order */ lnodehi = SwS.Successor( lnode1 ); if( !lnodelo.IsEmpty() ) intersect( lnodelo, lnode1, enode.key()->key.x, &EvQ, &Ipts ); if( !lnodehi.IsEmpty() ) intersect( lnodehi, lnode1, enode.key()->key.x, &EvQ, &Ipts ); side = SwS.SearchNode( lnode2.key(), compare_linerec_to_linerec, &lnode ); gul::Assert<InternalError>(ndebug | (side!=0) ); SwS.InsertNode(lnode2,lnode,side); // reinsert lnodelo = SwS.Predecessor( lnode2 ); /* get neighbors in order */ lnodehi = SwS.Successor( lnode2 ); if( !lnodelo.IsEmpty() ) intersect( lnodelo, lnode2, enode.key()->key.x, &EvQ, &Ipts ); if( !lnodehi.IsEmpty() ) intersect( lnodehi, lnode2, enode.key()->key.x, &EvQ, &Ipts ); } } /* process beginning lines */ while( enode.key()->B.nElems > 0 ) { begseg = enode.key()->B.First(); enode.key()->B.Remove( begseg ); seg = begseg->el; side = SwS.SearchNode( seg, compare_segment_to_linerec, &lnode ); if( side == 0 ) // colinear with existing line { lnode.key()->S.Append( begseg ); // add line-segment (using list node) sign = compare( begseg->el->E.x, lnode.key()->E.x ); if( sign > 0 ) { lnode.key()->E = begseg->el->E; /* remove old line-end event */ lnode.key()->endev.key()->E.Remove( lnode.key()->endev_node ); delete lnode.key()->endev_node; // delete line-end lstnode if( lnode.key()->endev.key()->IsEmpty() ) { EvQ.RemoveNode( lnode.key()->endev ); EvQ.FreeNode( lnode.key()->endev ); } checkneighbors = true; } else { checkneighbors = false; } } else { delete begseg; // delete list node; lnode1 = SwS.NewNode( seg ); SwS.InsertNode( lnode1, lnode, side ); lnode = lnode1; checkneighbors = true; } if( checkneighbors ) { lnodelo = SwS.Predecessor( lnode ); /* get neighbors in order */ lnodehi = SwS.Successor( lnode ); lstnode = new ListNode< Map<linerec>::Node >(lnode); side = EvQ.SearchNode( &seg->E, compare_point_to_eventrec, &evnode ); if( side != 0 ) { evnode1 = EvQ.NewNode( seg->E ); EvQ.InsertNode( evnode1, evnode, side ); evnode = evnode1; } evnode.key()->E.Append( lstnode ); lnode.key()->endev = evnode; lnode.key()->endev_node = lstnode; if( !lnodelo.IsEmpty() ) intersect( lnodelo, lnode, enode.key()->key.x, &EvQ, &Ipts ); if( !lnodehi.IsEmpty() ) intersect( lnodehi, lnode, enode.key()->key.x, &EvQ, &Ipts ); } if( iflag ) { /* add intersection record (if not already existing) */ side = lnode.key()->I.SearchNode( &irec->I, hcompare_point_to_intersection, &irnode ); if( side != 0 ) { irnode1 = lnode.key()->I.NewNode(irec); lnode.key()->I.InsertNode( irnode1, irnode, side ); } } } /* --- process end of vertical line --- */ if( enode.key()->EV != 0 ) { /* find linerecs passing between start and end of vertical line */ if( !SwS.IsEmpty() ) { side = SwS.SearchNode( &enode.key()->EV->B, compare_point_to_linerec, &lnode ); if( side > 0 ) lnode = SwS.Successor( lnode ); do { if( !lnode.IsEmpty() ) { irec = intersect_vert( vlin, lnode, &Ipts ); lnode = SwS.Successor( lnode ); } } while( !lnode.IsEmpty() && (irec != 0) ); } // cout << "[before finish_vertline]: "; // DumpPS<float>::dump_linerec( enode.key()->EV ); finish_vertline( vlin, E, V, maxE, &Ipts, &Isegs ); delete vlin; vlin = 0; } /* --- process finished lines --- */ while( (lrefnode = enode.key()->E.First()) != 0 ) { enode.key()->E.Remove( lrefnode ); lnode = lrefnode->el; delete lrefnode; /* cout << "[before finish_line]: "; DumpPS<float>::dump_linerec( lnode.key() ); */ finish_line( lnode.key(), E, V, maxE, &Ipts, &Isegs ); SwS.FreeNode(lnode); // already removed, see above } EvQ.RemoveNode( enode ); EvQ.FreeNode(enode); } /* gugr::Dump<float>::dump_vertices( V.head ); gugr::Dump<float>::dump_edges( E.head ); */ /* cout << "\nINTERSECTIONS\n"; cout << "=============\n"; DumpPS<float>::dump_intersections( Ipts ); cout << "\n"; DumpPS<float>::dump_intersectionsegs( Isegs ); */ Ipts.DeleteElems(); Isegs.DeleteElems(); }

GULAPI void gugr::DoUnion (  List< ListNode< polyline > > &    PA, List< ListNode< polyline > > &    PB, const rational &    far_x, const rational &    far_y, List< ListNode< gul::polyline< point2< rational > > > > &    C )

Definition at line 500 of file gugr_bool.cpp. { const int OutA = 1; const int InA = 2; const int OutB = 4; const int InB = 8; graph_edge_list E; graph_vertex_list V; segment_list S,Stmp; List<contour_node> contours; contour_node universe(0); // pseudo contour which contains everything // get the segments of both polygons and mark them with // InA,OutA,InB,OutB OddEvenRule( PA, far_x, far_y, InA, OutA, E, V, S ); OddEvenRule( PB, far_x, far_y, InB, OutB, E, V, Stmp ); S += Stmp; // find all contours and build their containment tree ContainmentTree( S, far_x, far_y, contours, universe ); // universe.dump(0); UnionSubTree( &universe, 0, OutA, OutB, C ); }

void dump_segment (  segment *    S, std::ostream &    s )  [inline]

Definition at line 255 of file gugr_io.h. { s << "[" << S->f[0].i << ", " << S->f[1].i << "] B=(" << S->B << "), (" << S->E << ")\n"; }

int gugr::EdgeCycle (  graph_edge *    e, graph_vertex *    v, graph_edge **    A )

Definition at line 373 of file gugr_basics.cpp. { graph_edge *a0,*a; int i; A[0] = a0 = a = e; if( a->v[0] == v ) a = a->e[0]; else a = a->e[1]; i = 1; while( a != a0 ) { A[i] = a; i++; if( a->v[0] == v ) a = a->e[0]; else a = a->e[1]; } return(i); }

void EdgeInsert (  graph_edge *    e, int    maxE )

Definition at line 245 of file gugr_regularize.cpp. { graph_edge *left, *right, **E; graph_vertex *v0 = e->v[0], *v1 = e->v[1]; int ileft, iright, codel, coder, nE; E = (graph_edge **)alloca( sizeof(graph_edge *) * maxE ); if( E == NULL ) throw AllocError(); nE = IncidentEdges( v0, E ); EdgeInsertPosition( v0->v, v1->v, nE, E, &ileft, &iright, &codel, &coder ); left = E[ileft]; right = E[iright]; if( left->v[0] == v0 ) left->e[0] = e; else left->e[1] = e; e->e[0] = right; if( left->v[0] == v0 ) e->f[1] = left->f[0]; else e->f[1] = left->f[1]; if( right->v[0] == v0 ) e->f[0] = right->f[1]; else e->f[0] = right->f[0]; nE = IncidentEdges( v1, E ); EdgeInsertPosition( v1->v, v0->v, nE, E, &ileft, &iright, &coder, &codel ); left = E[ileft]; right = E[iright]; if( left->v[0] == v1 ) left->e[0] = e; else left->e[1] = e; e->e[1] = right; }

int gugr::EdgeInsertPosition (  const vertex &    a, const vertex &    b, int    nE, graph_edge **    E, int *    eleft, int *    eright, int *    code_left, int *    code_right )

Definition at line 725 of file gugr_basics.cpp. { vertex v1,v2,v3; int left,right,mid,sign,s1,s2,s3,tmp; int match = 0; left = 0; right = nE-1; if( right > 0 ) { if( E[left]->v[0]->v == a ) v1 = E[left]->v[1]->v; else v1 = E[left]->v[0]->v; if( E[right]->v[0]->v == a ) v2 = E[right]->v[1]->v; else v2 = E[right]->v[0]->v; sign = CompareAngles( a.v(), b.v(), v1.v(), v2.v(), &match, &s1, &s2 ); if( sign > 0 ) { if( match ) { if( right-1 != left ) s1 = 0; left = right-1; } else { mid = (left+right)/2; while( mid != left ) { if( E[mid]->v[0]->v == a ) v3 = E[mid]->v[1]->v; else v3 = E[mid]->v[0]->v; sign = CompareAngles( a.v(), b.v(), v1.v(), v3.v(), &match, &s1, &s3 ); if( match ) { right = mid; s2 = s3; if( mid-1 != left ) s1 = 0; left = mid-1; break; } if( sign > 0 ) { right = mid; s2 = s3; } else if( sign < 0 ) { left = mid; v1 = v3; s1 = s3; } else throw InternalError(); /* this cannot be */ mid = (left+right)/2; } } } else { gul::Assert< gul::InternalError >( ndebug || ((sign != 0) && (left == 0) && (right == nE-1)) ); tmp = left; left = right; right = tmp; tmp = s1; s1 = s2; s2 = tmp; } } else { right = left; s1 = s2 = 0; } if( s1 == 0 ) { if( E[left]->v[0]->v == a ) v1 = E[left]->v[1]->v; else v1 = E[left]->v[0]->v; s1 = DetermineOrientation( a.v(), b.v(), v1.v() ) + 2; } if( s2 == 0 ) { if( right != left ) { if( E[right]->v[0]->v == a ) v2 = E[right]->v[1]->v; else v2 = E[right]->v[0]->v; s2 = DetermineOrientation( a.v(), b.v(), v2.v() ) + 2; } else s2 = s1; } *eleft = left; *eright = right; *code_left = s1; *code_right = s2; return(match); }

void gugr::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 )

Definition at line 489 of file gugr_contour.cpp. { graph_edge *e,*laste; ListNode<segment> *sn; contour_node *cn; ListNode<segment> *hn; segment *h,*lastseg; outsegs.DeleteElems(); // reserve a new segment struct for each edge (needed later for the // classification of the formed regions with the odd/even winding rule) e = E.First(); while( e ) { sn = new ListNode<segment>; outsegs.Append(sn); // orient the segments as the planesweep algorithm expects them if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) { sn->el.B = e->v[1]->v.v(); sn->el.E = e->v[0]->v.v(); } else { sn->el.B = e->v[0]->v.v(); sn->el.E = e->v[1]->v.v(); } sn->el.l = e->l; sn->el.m = e->reserved[0].i; // multiplicity of edge (for winding rule) e->reserved[2].p = &sn->el; // back pointer edge -> new segment e = e->next; } // find the non-intersecting regions e = E.First(); laste = 0; lastseg = 0; while( e ) { /* cout << "processing edge " << (void *)e << "\n"; */ if( e->f[0].p ) { cn = new contour_node(0); // new contour contours.Append(cn); cn->seg = (segment *)e->reserved[2].p; LeftSideContour( e, E, cn ); if( e != laste ) { // construct a help line for each contour for classifying it // later with an odd/even winding rule hn = new ListNode<segment>; outsegs.Append(hn); h = &hn->el; if( !e->l.IsHorizontal() ) // horizontal help line { h->E.y = (e->v[0]->v.v().y + e->v[1]->v.v().y)/rational(ULong(2)); h->E.x = far_maxx; intersect_horiz( h->E.y, e->l, h->B ); h->f[0].p = h->f[1].p = 0; // edge/side pairs belong to no contour h->l = line( h->E, rational(ULong(1)), rational(ULong(0)) ); } else // vertical help line { h->E.x = (e->v[0]->v.v().x + e->v[1]->v.v().x)/rational(ULong(2)); h->E.y = far_maxy; intersect_vert( h->E.x, e->l, h->B ); h->f[0].p = h->f[1].p = 0; // edge/side pairs belong to no contour h->l = line( h->E, rational(ULong(0)), rational(ULong(1)) ); } cn->hseg = h; // remember the address of the created help line cn->hseg_firstref = true; /* DumpPS<float>::dump_segment( h ); */ laste = e; lastseg = h; } else { cn->hseg = lastseg; // remember the address of the created help line cn->hseg_firstref = false; /* DumpPS<float>::dump_segment( lastseg ); */ } } if( e->f[1].p ) { cn = new contour_node(0); // new contour contours.Append(cn); cn->seg = (segment *)e->reserved[2].p; RightSideContour( e, E, cn ); if( e != laste ) { // construct a help line for each contour for classifying it // later with an odd/even winding rule hn = new ListNode<segment>; outsegs.Append(hn); h = &hn->el; if( !e->l.IsHorizontal() ) // horizontal help line { h->E.y = (e->v[0]->v.v().y + e->v[1]->v.v().y)/rational(ULong(2)); h->E.x = far_maxx; intersect_horiz( h->E.y, e->l, h->B ); h->f[0].p = h->f[1].p = 0; // edge/side pairs belong to no contour h->l = line( h->E, rational(ULong(1)), rational(ULong(0)) ); } else // vertical help line { h->E.x = (e->v[0]->v.v().x + e->v[1]->v.v().x)/rational(ULong(2)); h->E.y = far_maxy; intersect_vert( h->E.x, e->l, h->B ); h->f[0].p = h->f[1].p = 0; // edge/side pairs belong to no contour h->l = line( h->E, rational(ULong(0)), rational(ULong(1)) ); } cn->hseg = h; // remember the address of the created help line cn->hseg_firstref = true; /* DumpPS<float>::dump_segment( h ); */ laste = e; lastseg = h; } else { cn->hseg = lastseg; // remember the address of the created help line cn->hseg_firstref = false; /* DumpPS<float>::dump_segment( lastseg ); */ } } e = e->next; } }

int FindCutInfo (  rational &    x, int    nA, const Ptr< cut_info > &    A, bool &    found )

Definition at line 332 of file gugr_split.cpp. { int mid,right,left,sign; if( nA == 0 ) {found = false; return -1;} sign = compare( A[0].val, x ); if( sign >= 0 ) { if( sign > 0 ) {found = false; return -1;} found = true; return 0; } sign = compare( A[nA-1].val, x ); if( sign <= 0 ) { if( sign < 0 ) {found = false; return nA-1;} found = true; return nA-1; } left = 0; right = nA; mid = (left+right)/2; while( (mid!=left) && (mid!=right) ) { sign = compare( A[mid].val, x ); if( sign == 0 ) break; else if( sign > 0 ) { right = mid; mid = (left+right)>>1; } else { left = mid; mid = (left+right)>>1; } } found = (sign == 0); return mid; }

void finish_line (  linerec *    L, graph_edge_list *    E, graph_vertex_list *    V, int    maxE, List< intersection > *    Ipts, List< intersectionseg > *    Isegs )

Definition at line 246 of file gugr_planesweep.cpp. { ListNode<segment *> *segref = L->S.First(); segment *seg; int side; intersection *i,*i1,*i2; intersectionseg *is; RefMap<intersection>::Node irnode,irnode1; Ptr<intersection *> I; int nI,j; segtree SegTr; int left,right,mid,iB,iE,sign,nLf; Ptr<segnode *> Lf; segnode *snode; RefMap<segment>::Node segnod; graph_edge *e; RefMap<void>::Node leftowner,rightowner,leftowner1,rightowner1; RefMap<void> *leftowners,*rightowners; List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *ownerrecs; ListNode< ListNodeInfo< ListNode<graph_edge *> > > *orec; ListNode<graph_edge *> *erec; while( segref != 0 ) { seg = segref->el; /* --- add segment endpoints as intersections --- */ side = L->I.SearchNode( &seg->B, hcompare_point_to_intersection, &irnode ); if( side != 0 ) { i = new intersection( seg->B ); Ipts->Append(i); irnode1 = L->I.NewNode(i); L->I.InsertNode( irnode1, irnode, side ); } side = L->I.SearchNode( &seg->E, hcompare_point_to_intersection, &irnode ); if( side != 0 ) { i = new intersection( seg->E ); Ipts->Append(i); irnode1 = L->I.NewNode(i); L->I.InsertNode( irnode1, irnode, side ); } segref = segref->next; } nI = L->I.ConvertToArray( &I ); SegTr.init( nI, I ); segref = L->S.First(); while( segref != 0 ) { seg = segref->el; left = 0; right = nI; mid = (left+right)/2; for(;;) { sign = compare( seg->B.x, I[mid]->I.x ); if( sign == 0 ) break; else if( sign < 0 ) { right = mid; mid = (left+right)/2; } else { left = mid; mid = (left+right)/2; } } iB = mid; left = 0; right = nI; mid = (left+right)/2; for(;;) { sign = compare( seg->E.x, I[mid]->I.x ); if( sign == 0 ) break; else if( sign < 0 ) { right = mid; mid = (left+right)/2; } else { left = mid; mid = (left+right)/2; } } iE = mid; SegTr.insert( iB, iE, seg ); segref = segref->next; } nLf = SegTr.leaves_to_array( &Lf ); for( j = 0; j < nLf; j++ ) { e = new graph_edge; E->Append(e); i1 = SegTr.m_absz[Lf[j]->m_il]; if( i1->v == 0 ) { i1->v = new graph_vertex( i1->I, 0 ); V->Append(i1->v); } i2 = SegTr.m_absz[Lf[j]->m_ir]; if( i2->v == 0 ) { i2->v = new graph_vertex( i2->I, 0 ); V->Append(i2->v); } e->v[0] = i1->v; e->v[1] = i2->v; e->l = L->l; /* --- set owner lists of intersections --- */ is = new intersectionseg(e); Isegs->Append(is); /* initialize sets of owners of left and right side of the edge */ leftowners = new RefMap<void>; rightowners = new RefMap<void>; e->f[0].p = leftowners; e->f[1].p = rightowners; e->reserved[0].set_i(0); ownerrecs = new List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > >; e->reserved[1].p = ownerrecs; snode = Lf[j]; while( snode ) { segnod = snode->m_segs.First(); while( !segnod.IsEmpty() ) { // increment number of owners by the multiplicity of the segments // which contain the edge e->reserved[0].i += segnod.key()->m; /* add owner to the set of owners of the left side of the edge */ side = leftowners->SearchNode( (void *)segnod.key()->f[0].p, compare_pointer_to_pointer, &leftowner ); if( side != 0 ) { leftowner1 = leftowners->NewNode((void *)segnod.key()->f[0].p); leftowners->InsertNode( leftowner1, leftowner, side ); } /* add owner to the set of owners of the right side of the edge */ side = rightowners->SearchNode( (void *)segnod.key()->f[1].p, compare_pointer_to_pointer, &rightowner ); if( side != 0 ) { rightowner1 = rightowners->NewNode((void *)segnod.key()->f[1].p); rightowners->InsertNode( rightowner1, rightowner, side ); } /* add edge to the list of edges for the original input segment */ erec = new ListNode<graph_edge *>(e); segnod.key()->e.Append( erec ); /* add a backpointer to the corresponding edge record in the edge list of the input segment; this makes it later possible to remove all references to an edge from all input segments */ orec = new ListNode< ListNodeInfo< ListNode<graph_edge *> > >( ListNodeInfo< ListNode<graph_edge *> >(&segnod.key()->e, erec) ); ownerrecs->Append(orec); /* the owner lists of the intersection records are only for debugging */ /* owner = new ListNode<segment *>(segnod.key()); i1->S.Append(owner); owner = new ListNode<segment *>(segnod.key()); is->S.Append(owner); */ segnod = snode->m_segs.Successor(segnod); } snode = snode->m_parent; } OrientEdge( e ); ConnectEdge( e, maxE ); } /* --- set owner list of endpoint - intersection --- */ /* if( (j=nLf-1) >= 0 ) { snode = Lf[j]; while( snode ) { segnod = snode->m_segs.First(); while( !segnod.IsEmpty() ) { owner = new ListNode<segment *>(segnod.key()); i2->S.Append(owner); segnod = snode->m_segs.Successor(segnod); } snode = snode->m_parent; } } */ }

void finish_vertline (  linerec *    L, graph_edge_list *    E, graph_vertex_list *    V, int    maxE, List< intersection > *    Ipts, List< intersectionseg > *    Isegs )

Definition at line 489 of file gugr_planesweep.cpp. { ListNode<segment *> *segref = L->S.First(); segment *seg; int side; intersection *i,*i1,*i2; intersectionseg *is; RefMap<intersection>::Node irnode,irnode1; Ptr<intersection *> I; int nI,j; segtree SegTr; int left,right,mid,iB,iE,sign,nLf; Ptr<segnode *> Lf; segnode *snode; RefMap<segment>::Node segnod; graph_edge *e; RefMap<void>::Node leftowner,rightowner,leftowner1,rightowner1; RefMap<void> *leftowners,*rightowners; List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *ownerrecs; ListNode< ListNodeInfo< ListNode<graph_edge *> > > *orec; ListNode<graph_edge *> *erec; while( segref != 0 ) { seg = segref->el; /* --- add segment endpoints as intersections --- */ side = L->I.SearchNode( &seg->B, vcompare_point_to_intersection, &irnode ); if( side != 0 ) { i = new intersection( seg->B ); Ipts->Append(i); irnode1 = L->I.NewNode(i); L->I.InsertNode( irnode1, irnode, side ); } side = L->I.SearchNode( &seg->E, vcompare_point_to_intersection, &irnode ); if( side != 0 ) { i = new intersection( seg->E ); Ipts->Append(i); irnode1 = L->I.NewNode(i); L->I.InsertNode( irnode1, irnode, side ); } segref = segref->next; } nI = L->I.ConvertToArray( &I ); SegTr.init( nI, I ); segref = L->S.First(); while( segref != 0 ) { seg = segref->el; left = 0; right = nI; mid = (left+right)/2; for(;;) { sign = compare( seg->B.y, I[mid]->I.y ); if( sign == 0 ) break; else if( sign < 0 ) { right = mid; mid = (left+right)/2; } else { left = mid; mid = (left+right)/2; } } iB = mid; left = 0; right = nI; mid = (left+right)/2; for(;;) { sign = compare( seg->E.y, I[mid]->I.y ); if( sign == 0 ) break; else if( sign < 0 ) { right = mid; mid = (left+right)/2; } else { left = mid; mid = (left+right)/2; } } iE = mid; SegTr.insert( iB, iE, seg ); segref = segref->next; } nLf = SegTr.leaves_to_array( &Lf ); for( j = 0; j < nLf; j++ ) { e = new graph_edge; E->Append(e); i1 = SegTr.m_absz[Lf[j]->m_il]; if( i1->v == 0 ) { i1->v = new graph_vertex( i1->I, 0 ); V->Append(i1->v); } i2 = SegTr.m_absz[Lf[j]->m_ir]; if( i2->v == 0 ) { i2->v = new graph_vertex( i2->I, 0 ); V->Append(i2->v); } e->v[0] = i1->v; e->v[1] = i2->v; e->l = L->l; /* --- set owner lists of intersections --- */ is = new intersectionseg(e); Isegs->Append(is); /* initialize sets of owners of left and right side of the edge */ leftowners = new RefMap<void>; rightowners = new RefMap<void>; e->f[0].p = leftowners; e->f[1].p = rightowners; e->reserved[0].set_i(0); ownerrecs = new List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > >; e->reserved[1].p = ownerrecs; snode = Lf[j]; while( snode ) { segnod = snode->m_segs.First(); while( !segnod.IsEmpty() ) { // increment number of owners by the multiplicity of the segments // which contain the edge e->reserved[0].i += segnod.key()->m; /* add owner to the set of owners of the left side of the edge */ side = leftowners->SearchNode( (void *)segnod.key()->f[0].p, compare_pointer_to_pointer, &leftowner ); if( side != 0 ) { leftowner1 = leftowners->NewNode((void *)segnod.key()->f[0].p ); leftowners->InsertNode( leftowner1, leftowner, side ); } /* add owner to the set of owners of the right side of the edge */ side = rightowners->SearchNode( (void *)segnod.key()->f[1].p, compare_pointer_to_pointer, &rightowner ); if( side != 0 ) { rightowner1 = rightowners->NewNode((void *)segnod.key()->f[1].p); rightowners->InsertNode( rightowner1, rightowner, side ); } /* add edge to the list of edges for the original input segment */ erec = new ListNode<graph_edge *>(e); segnod.key()->e.Append( erec ); /* add a backpointer to the corresponding edge record in the edge list of the input segment; this makes it later possible to remove all references to an edge from all input segments */ orec = new ListNode< ListNodeInfo< ListNode<graph_edge *> > >( ListNodeInfo< ListNode<graph_edge *> >(&segnod.key()->e, erec) ); ownerrecs->Append(orec); /* the owner lists of the intersection records are only for debugging */ /* owner = new ListNode<segment *>(segnod.key()); i1->S.Append(owner); owner = new ListNode<segment *>(segnod.key()); is->S.Append(owner); */ segnod = snode->m_segs.Successor(segnod); } snode = snode->m_parent; } OrientEdge( e ); ConnectEdge( e, maxE ); } /* --- set owner list of endpoint - intersection --- */ /* if( (j=nLf-1) >= 0 ) { snode = Lf[j]; while( snode ) { segnod = snode->m_segs.First(); while( !segnod.IsEmpty() ) { owner = new ListNode<segment *>(segnod.key()); i2->S.Append(owner); segnod = snode->m_segs.Successor(segnod); } snode = snode->m_parent; } } */ }

int hcompare_point_to_intersection (  point2< rational > *    C, intersection *    R )

Definition at line 87 of file gugr_planesweep.cpp. { return compare( C->x, R->I.x ); }

int gugr::IncidentEdges (  const graph_vertex *    v, graph_edge **    A )

Definition at line 341 of file gugr_basics.cpp. { graph_edge *a0,*a; int i; a = A[0] = a0 = v->e; if( !a ) return 0; if( a->v[0] == v ) a = a->e[0]; else a = a->e[1]; i = 1; while( a != a0 ) { A[i] = a; i++; if( a->v[0] == v ) a = a->e[0]; else a = a->e[1]; } return(i); }

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 )

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<class T> void gugr::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 )

Definition at line 1748 of file gugr_split.cpp. { graph_vertex *Vy1Sl, *Vy1Sr, *Vy2Sl, *Vy2Sr, *Vx1Sa, *Vx1Sb, *Vx2Sa, *Vx2Sb; graph_vertex *hvLeftT, *hvRightT; graph_edge *e, *el, **hE; graph_vertex *v, *v0; int nhE, nMaxE; Ptr< cut_info > CutsX, CutsY; rational& MinX = Gconv->MinX; // short aliases rational& MaxX = Gconv->MaxX; rational& FarMinX = Gconv->FarMinX; rational& FarMaxX = Gconv->FarMaxX; rational& MinY = Gconv->MinY; rational& MaxY = Gconv->MaxY; rational& FarMinY = Gconv->FarMinY; rational& FarMaxY = Gconv->FarMaxY; CutsX.reserve_place( reserve_stack(cut_info,3), 3 ); CutsY.reserve_place( reserve_stack(cut_info,3), 3 ); CutsX[1].val = X1; CutsX[2].val = X2; CutsY[1].val = Y1; CutsY[2].val = Y2; nMaxE = 10 * E->nElems; // this is a hack, but its enough even in the // worst case hE = (graph_edge **)alloca( sizeof(graph_edge *) * nMaxE ); /* cout << "input graph\n"; cout << "***********\n"; gugr::Dump<T>::dump_vertices( V->head ); gugr::Dump<T>::dump_edges( E->head ); */ // split graph into vertical strips IntersectWithVerticals( E, V, 3, CutsX ); // isolate first vertical strip and discard it DivideVerticalStrips( &CutsX[2], &CutsX[1], nMaxE, MinY, MaxY, FarMinY, FarMaxY, &Vy1Sr, &Vy1Sl, &Vy2Sr, &Vy2Sl ); /* cout << "after disconnecting X-Strip " << 2 << " and " << 1 << "\n"; cout << "*******************************************************\n"; for( int k = 2; k >= 0; k-- ) { cout << "X-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsX[k].V.head ); gugr::Dump<T>::dump_edges( CutsX[k].E.head ); } */ CutsX[2].R.DeleteElems(); CutsX[2].E.DeleteElems(); CutsX[2].V.DeleteElems(); DivideVerticalStrips( &CutsX[1], &CutsX[0], nMaxE, MinY, MaxY, FarMinY, FarMaxY, &Vy1Sr, &Vy1Sl, &Vy2Sr, &Vy2Sl ); /* cout << "after disconnecting X-Strip " << 1 << " and " << 0 << "\n"; cout << "*******************************************************\n"; for( int k = 1; k >= 0; k-- ) { cout << "X-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsX[k].V.head ); gugr::Dump<T>::dump_edges( CutsX[k].E.head ); } */ // split vertical strips into horizontal strips IntersectWithHorizontals( &CutsX[1].E, &CutsX[1].V, 3, CutsY ); // isolate first strip and discard it DivideHorizontalStrips( &CutsY[2], &CutsY[1], nMaxE, MinX, MaxX, FarMinX, FarMaxX, &Vx1Sa, &Vx1Sb, &Vx2Sa, &Vx2Sb ); /* cout << "after disconnecting Y-Strip " << 2 << " and " << 1 << "\n"; cout << "*******************************************************\n"; for( int k = 2; k >= 0; k-- ) { cout << "Y-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsY[k].V.head ); gugr::Dump<T>::dump_edges( CutsY[k].E.head ); } */ CutsY[2].R.DeleteElems(); CutsY[2].E.DeleteElems(); CutsY[2].V.DeleteElems(); hvLeftT = Vx1Sb; hvRightT = Vx2Sb; // for next strip // divide vertical strips into horizontal strips DivideHorizontalStrips( &CutsY[1], &CutsY[0], nMaxE, MinX, MaxX, FarMinX, FarMaxX, &Vx1Sa, &Vx1Sb, &Vx2Sa, &Vx2Sb ); /* cout << "after disconnecting Y-Strip " << 1 << " and " << 0 << "\n"; cout << "*******************************************************\n"; for( int k = 1; k >= 0; k-- ) { cout << "Y-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsY[k].V.head ); gugr::Dump<T>::dump_edges( CutsY[k].E.head ); } */ v0 = hvLeftT; // remove help edges from the corner edge cycles e = v0->e; G->face = e->e[0]->f[1].i; // face index of quad, if it is v = e->v[0]; // not divided G->P[1][0] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[0]; else el->e[1] = e->e[0]; v->e = el; CutsY[1].V.Remove(v0); CutsY[1].E.Remove(e); delete v0; delete e; v0 = hvRightT; e = v0->e; v = e->v[1]; G->P[1][1] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[1]; else el->e[1] = e->e[1]; v->e = el; CutsY[1].V.Remove(v0); CutsY[1].E.Remove(e); delete v0; delete e; v0 = Vx2Sa; e = v0->e; v = e->v[1]; G->P[0][1] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[1]; else el->e[1] = e->e[1]; v->e = el; CutsY[1].V.Remove(v0); CutsY[1].E.Remove(e); delete v0; delete e; v0 = Vx1Sa; e = v0->e; v = e->v[0]; G->P[0][0] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[0]; else el->e[1] = e->e[0]; v->e = el; CutsY[1].V.Remove(v0); CutsY[1].E.Remove(e); delete v0; delete e; CutsY[1].R.DeleteElems(); // free cut records only G->E += CutsY[1].E; G->V += CutsY[1].V; CutsY[0].R.DeleteElems(); CutsY[0].E.DeleteElems(); CutsY[0].V.DeleteElems(); CutsX[1].R.DeleteElems(); CutsX[1].E.DeleteElems(); CutsX[1].V.DeleteElems(); CutsX[0].R.DeleteElems(); CutsX[0].E.DeleteElems(); CutsX[0].V.DeleteElems(); }

void gugr::InsertDiagonal (  graph_edge_list *    E, graph_vertex_list *    V, graph_vertex *    P11, graph_vertex *    P22 )

Definition at line 176 of file gugr_split.cpp. { cut_record_list Recs; cut_record *rec; int nhE,L,R,match,cR,cL,ivh,ivl,maxE; graph_edge *e,*eh,*el,**hE; graph_vertex *lv; vertex *lowerleft = &P11->v; vertex *upperright = &P22->v; line lin; IntersectWithAscendant( P11->v.v(), P22->v.v(), *E, *V, lin, Recs ); maxE = 3*E->nElems + V->nElems; hE = (graph_edge **)alloca( sizeof(graph_edge *)*maxE ); if( hE == NULL ) throw AllocError(); rec = Recs.head; lv = rec->v; gul::Assert<InternalError>( ndebug || (lv == P11) ); rec = rec->next; while( rec != NULL ) { if( rec->e == NULL ) /* vertex on diagonal */ { nhE = IncidentEdges( rec->v, hE ); match = EdgeInsertPosition( rec->v->v, *lowerleft, nhE, hE, &L, &R, &cL, &cR ); if( cR != 2 ) // have to create a new edge { e = new graph_edge(); E->Append(e); e->v[0] = lv; e->v[1] = rec->v; if( hE[L]->v[0] == rec->v ) // connect upper end of new edge { e->e[1] = hE[L]->e[0]; hE[L]->e[0] = e; e->f[0] = e->f[1] = hE[L]->f[0]; } else { e->e[1] = hE[L]->e[1]; hE[L]->e[1] = e; e->f[0] = e->f[1] = hE[L]->f[1]; } nhE = IncidentEdges( lv, hE ); match = EdgeInsertPosition( lv->v, *upperright, nhE, hE, &L, &R, &cL, &cR ); if( hE[L]->v[0] == lv ) // connect lower end of new edge { e->e[0] = hE[L]->e[0]; hE[L]->e[0] = e; } else { e->e[0] = hE[L]->e[1]; hE[L]->e[1] = e; } } } else /* diagonal intersects an edge */ { el = rec->e; eh = new graph_edge(); // new edge for half of edge above diagonal E->Append(eh); rec->v->e = eh; // give new vertex an incident edge V->Append(rec->v); // append it to vertex list if( el->v[0]->reserved[1].i > 0 ) // part with v0 above diagonal { ivh = 0; ivl = 1; } else // part with v1 above diagonal { ivh = 1; ivl = 0; } eh->v[ivl] = rec->v; eh->v[ivh] = el->v[ivh]; eh->f[0] = el->f[0]; eh->f[1] = el->f[1]; nhE = EdgeCycle( el, el->v[ivh], hE ); if( nhE > 1 ) { eh->e[ivh] = el->e[ivh]; if( hE[nhE-1]->e[0] == el ) hE[nhE-1]->e[0] = eh; else hE[nhE-1]->e[1] = eh; } else eh->e[ivh] = eh; el->v[ivh]->e = eh; // eh replaces original edge in upper edge cycle el->v[ivh] = rec->v; // shorten intersecting edge to lower half /* ---- create new edge for diagonal ---- */ e = new graph_edge(); E->Append(e); e->v[0] = lv; e->v[1] = rec->v; e->f[0] = e->f[1] = el->f[ivl]; nhE = IncidentEdges( lv, hE ); match = EdgeInsertPosition( lv->v, *upperright, nhE, hE, &L, &R, &cL, &cR ); if( hE[L]->v[0] == lv ) // connect lower end of new edge { e->e[0] = hE[L]->e[0]; hE[L]->e[0] = e; } else { e->e[0] = hE[L]->e[1]; hE[L]->e[1] = e; } eh->e[ivl] = e; e->e[1] = el; el->e[ivh] = eh; } lv = rec->v; rec = rec->next; } gul::Assert<InternalError>( ndebug || (lv == P22) ); Recs.DeleteElems(); }

intersection* intersect (  Map< linerec >::Node    L1, Map< linerec >::Node    L2, const rational &    xleft, Map< eventrec > *    EvQ, List< intersection > *    Ipts )

Definition at line 112 of file gugr_planesweep.cpp. { const rational& x0 = L1.key()->l.v().x; const rational& y0 = L1.key()->l.v().y; const rational& dy = L1.key()->l.dy(); const rational& e = L1.key()->E.x; const rational& X0 = L2.key()->l.v().x; const rational& Y0 = L2.key()->l.v().y; const rational& DY = L2.key()->l.dy(); const rational& E = L2.key()->E.x; rational d; point2<rational> I; int sign,bsign,side1,side2; RefMap<intersection>::Node irnode1, irnode2, irnode; intersection *i; int side; Map<eventrec>::Node enode,enode1; d = DY - dy; sign = d.test(); if( sign == 0 ) return 0; I.x = (y0 - Y0 + X0*DY - x0*dy) / d; bsign = compare( I.x, xleft ); if( bsign < 0 ) return 0; sign = compare( I.x, e ); if( sign > 0 ) return 0; sign = compare( I.x, E ); if( sign > 0 ) return 0; I.y = y0 + (I.x-x0)*dy; side1 = L1.key()->I.SearchNode( &I, hcompare_point_to_intersection, &irnode1 ); side2 = L2.key()->I.SearchNode( &I, hcompare_point_to_intersection, &irnode2 ); if( side1 == 0 ) i = irnode1.key(); else if( side2 == 0 ) i = irnode2.key(); else { i = new intersection( I ); Ipts->Append(i); } if( side1 != 0 ) { irnode = L1.key()->I.NewNode(i); L1.key()->I.InsertNode( irnode, irnode1, side1 ); } if( side2 != 0 ) { irnode = L2.key()->I.NewNode(i); L2.key()->I.InsertNode( irnode, irnode2, side2 ); } if( bsign == 0 ) return i; side = EvQ->SearchNode( &I, compare_point_to_eventrec, &enode ); if( side != 0 ) { enode1 = EvQ->NewNode( I ); EvQ->InsertNode( enode1, enode, side ); enode = enode1; } enode.key()->I.Append( new ListNode<linepair>( linepair(L1,L2) ) ); return i; }

bool gugr::intersect (  const line &    a, const line &    b, point2< rational > &    I )

Definition at line 105 of file gugr_basics.cpp. { if( a.IsVertical() ) { if( b.IsVertical() ) return false; return intersect_vert( a.v().x, b, I ); } else if( a.IsHorizontal() ) { if( b.IsHorizontal() ) return false; return intersect_horiz( a.v().y, b, I ); } if( b.IsVertical() ) return intersect_vert( b.v().x, a, I ); else if( b.IsHorizontal() ) return intersect_horiz( b.v().y, a, I ); return intersect_nonvert( a, b, I ); }

bool gugr::intersect_horiz (  const rational &    y0, const line &    b, point2< rational > &    I )

Definition at line 89 of file gugr_basics.cpp. { const rational& X0 = b.v().x; const rational& Y0 = b.v().y; const rational& DX = b.dx(); if( b.IsHorizontal() ) return false; if( b.IsVertical() ) I.x = X0; else I.x = X0 + (y0 - Y0)*DX; I.y = y0; return true; }

bool gugr::intersect_nonvert (  const line &    a, const line &    b, point2< rational > &    I )

Definition at line 50 of file gugr_basics.cpp. { const rational& x0 = a.v().x; const rational& y0 = a.v().y; const rational& dy = a.dy(); const rational& X0 = b.v().x; const rational& Y0 = b.v().y; const rational& DY = b.dy(); rational d; int sign; if( a.IsVertical() || b.IsVertical() ) return false; d = DY - dy; sign = d.test(); if( sign == 0 ) return false; I.x = (y0 - Y0 + X0*DY - x0*dy) / d; I.y = y0 + (I.x-x0)*dy; return true; }

intersection* intersect_vert (  linerec *    vL, Map< linerec >::Node    L, List< intersection > *    Ipts )

Definition at line 187 of file gugr_planesweep.cpp. { const rational& X0 = L.key()->l.v().x; const rational& Y0 = L.key()->l.v().y; const rational& DY = L.key()->l.dy(); const rational& yleft = vL->B.y; const rational& yright = vL->E.y; const rational& x0 = vL->l.v().x; point2<rational> I; int sign,side1,side2; RefMap<intersection>::Node irnode1, irnode2, irnode; intersection *i; I.y = Y0 + (x0 - X0)*DY; sign = compare( I.y, yleft ); if( sign < 0 ) return 0; sign = compare( I.y, yright ); if( sign > 0 ) return 0; I.x = x0; side1 = vL->I.SearchNode( &I, vcompare_point_to_intersection, &irnode1 ); side2 = L.key()->I.SearchNode( &I, hcompare_point_to_intersection, &irnode2 ); if( side1 == 0 ) i = irnode1.key(); else if( side2 == 0 ) i = irnode2.key(); else { i = new intersection( I ); Ipts->Append(i); } if( side1 != 0 ) { irnode = vL->I.NewNode(i); vL->I.InsertNode( irnode, irnode1, side1 ); } if( side2 != 0 ) { irnode = L.key()->I.NewNode(i); L.key()->I.InsertNode( irnode, irnode2, side2 ); } return i; }

bool gugr::intersect_vert (  const rational &    x0, const line &    b, point2< rational > &    I )

Definition at line 73 of file gugr_basics.cpp. { const rational& X0 = b.v().x; const rational& Y0 = b.v().y; const rational& DY = b.dy(); if( b.IsVertical() ) return false; if( b.IsHorizontal() ) I.y = Y0; else I.y = Y0 + (x0 - X0)*DY; I.x = x0; return true; }

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 )  [inline]

Definition at line 87 of file gugr_bool.h. { T minx,miny,scale; rational far_x,far_y; gul::List<gul::ListNode<gugr::polyline> > PA,PB; gul::List<gul::ListNode<gul::polyline<gul::point2<rational> > > > PC; ConvertToRationalPolys(fPA,fPB,&minx,&miny,&scale,&far_x,&far_y,PA,PB); DoIntersection(PA,PB,far_x,far_y,PC); ConvertToFloatPoly(PC,minx,miny,scale,fPC); }

void IntersectionSubTree (  contour_node *    C, int    oset, int    InA, int    InB, List< ListNode< gul::polyline< point2< rational > > > > &    pl )

Definition at line 309 of file gugr_bool.cpp. { ListNode<gul::polyline<point2<rational> > > *pln; gul::ptr_int_union UA,UB; gul::RefMap<void>::Node cn; bool store; UA.set_i(InA); UB.set_i(InB); store = false; if( oset == (InA|InB) ) { if( C->hasOwner(UA.p) ) oset ^= InA; if( C->hasOwner(UB.p) ) oset ^= InB; if( oset != (InA|InB) ) store = true; } else { if( C->hasOwner(UA.p) ) oset ^= InA; if( C->hasOwner(UB.p) ) oset ^= InB; if( oset == (InA|InB) ) store = true; } if( store ) { pln = new ListNode<gul::polyline<point2<rational> > >(); C->get_polyline_joined( pln->el ); pl.Append(pln); } // travert children cn = C->childs.First(); while( !cn.IsEmpty() ) { IntersectionSubTree( (contour_node *)cn.key(), oset, InA, InB, pl ); cn = C->childs.Successor( cn ); } }

void IntersectSegments (  gul::List< gul::ListNode< segment > > &    segs, gugr::graph_edge_list *    E, gugr::graph_vertex_list *    V, bool    need_backpointers )  [inline]

Definition at line 780 of file gugr_planesweep.h. { gul::Map<eventrec> EvQ; int side; gul::Map<eventrec>::Node enode,enode1; segment *s; ListNode<segment> *sn; /*--- initialize event queue with the lines leftmost endpoints ---*/ // gugr::DumpPS<float>::dump_segments( segs ); sn = segs.First(); while( sn ) { s = &sn->el; side = EvQ.SearchNode( &s->B, compare_point_to_eventrec, &enode ); if( side != 0 ) { enode1 = EvQ.NewNode( s->B ); EvQ.InsertNode( enode1, enode, side ); enode = enode1; } if( s->l.IsVertical() ) enode.key()->BV.Append( new ListNode<segment *>(s) ); else enode.key()->B.Append( new ListNode<segment *>(s) ); sn = sn->next; } DoIntersectSegments( segs.nElems, EvQ, E, V ); if( !need_backpointers ) { ISDeleteBackpointers( *E ); } }

void IntersectSegments (  int    nsegs, Ptr< segment >    segs, gugr::graph_edge_list *    E, gugr::graph_vertex_list *    V )  [inline]

Definition at line 441 of file gugr_planesweep.h. { gul::Map<eventrec> EvQ; int i,side; gul::Map<eventrec>::Node enode,enode1; /* cout << "PLANESWEEP\n"; cout << "==========\n"; cout << "INPUT SEGMENTS\n"; for( i = 0; i < nsegs; i++ ) DumpPS<float>::dump_segment( &segs[i] ); */ /*--- initialize event queue with the lines leftmost endpoints ---*/ for( i = 0; i < nsegs; i++ ) { side = EvQ.SearchNode( &segs[i].B, compare_point_to_eventrec, &enode ); if( side != 0 ) { enode1 = EvQ.NewNode( segs[i].B ); EvQ.InsertNode( enode1, enode, side ); enode = enode1; } if( segs[i].l.IsVertical() ) enode.key()->BV.Append( new ListNode<segment *>(&segs[i]) ); else enode.key()->B.Append( new ListNode<segment *>(&segs[i]) ); } DoIntersectSegments( nsegs, EvQ, E, V ); }

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 )

Definition at line 95 of file gugr_split.cpp. { rational y; graph_edge *e; graph_vertex *v; int i,k,sign; cut_record *rec, **tmpR; point2<rational> AB,X; AB.x = B.x - A.x; AB.y = B.y - A.y; L = line(A,B); v = V.head; while( v != NULL ) { sign = DetermineOrientationPV( A, AB, v->v.v() ); v->reserved[1].set_i(sign); if( sign == 0 ) // new record, when on diagonal { rec = new cut_record(); R.Append( rec ); rec->v = v; rec->e = NULL; rec->val = v->v.v().y; } v = v->next; } e = E.head; while( e != NULL ) { i = e->v[0]->reserved[1].i; k = e->v[1]->reserved[1].i; if( k*i < 0 ) // edge intersects diagonal { if( e->l.IsNULL() ) e->CalcLine(); intersect( e->l, L, X ); rec = new cut_record(); R.Append( rec ); rec->v = new graph_vertex( X, NULL ); rec->v->reserved[1].set_i(0); // on diagonal rec->e = e; rec->val = X.y; } e = e->next; } /* --- sort cut_records (on y) ---- */ tmpR = (cut_record **)alloca( sizeof(cut_record *)*R.nElems ); if( !tmpR ) throw AllocError(); rec = R.head; for( i = 0; i < R.nElems; i++ ) { tmpR[i] = rec; rec = rec->next; } guma::PtrHeapSort( R.nElems,(void **)tmpR, compare_cut_records,NULL); R.head = tmpR[0]; tmpR[0]->prev = NULL; for( i = 1; i < R.nElems; i++ ) { tmpR[i-1]->next = tmpR[i]; tmpR[i]->prev = tmpR[i-1]; } tmpR[R.nElems-1]->next = NULL; }

void gugr::IntersectWithHorizontals (  graph_edge_list *    E, graph_vertex_list *    V, const int    nS, gul::Ptr< cut_info >    S )

Definition at line 381 of file gugr_split.cpp. { int ns = nS-1, i,j,k,nA; graph_vertex *v,*v_next; graph_edge *e, *e_next; rational y,x0,y0,x,dx; bool rz; cut_record *rec; Ptr< cut_info > A; v = V->head; nA = nS-1; A.use_pointer( &S[1], nS-1 ); // used for binary search while( v != NULL ) { v_next = v->next; y = v->v.v().y; i = FindCutInfo( y, nA, A, rz ) + 1; v->reserved[0].set_i(i); v->reserved[1].set_i(rz); V->Remove( v ); S[i].V.Append( v ); if( rz ) { rec = new cut_record(); S[i].R.Append( rec ); rec->v = v; rec->e = NULL; rec->val = v->v.v().x; } v = v_next; } e = E->head; while( e != NULL ) { e_next = e->next; i = e->v[0]->reserved[0].i; k = e->v[1]->reserved[0].i; E->Remove( e ); S[k].E.Append( e ); if( i != k ) { if( e->l.IsNULL() ) { e->CalcLine(); } x0 = e->l.v().x; y0 = e->l.v().y; dx = e->l.dx(); if( e->v[1]->reserved[1].i ) k--; for( j = i+1; j <= k; j++ ) { if( !dx.is_zero() ) x = x0 + (S[j].val-y0)*dx; else x = x0; rec = new cut_record(); S[j].R.Append( rec ); rec->v = NULL; rec->e = e; rec->val = x; } } e = e_next; } sort_cut_records( ns, S ); }

void gugr::IntersectWithVerticals (  graph_edge_list *    E, graph_vertex_list *    V, const int    nS, gul::Ptr< cut_info >    S )

Definition at line 904 of file gugr_split.cpp. { int ns = nS-1, i,j,k,ii,ik,sign,nA; graph_vertex *v,*v_next; graph_edge *e, *e_next; rational y,x0,y0,x,dx,dy; bool rz; cut_record *rec; Ptr< cut_info > A; v = V->head; nA = nS-1; A.use_pointer( &S[1], nS-1 ); // used for binary search while( v != NULL ) { v_next = v->next; x = v->v.v().x; i = FindCutInfo( x, nA, A, rz ) + 1; v->reserved[0].set_i(i); v->reserved[1].set_i(rz); V->Remove( v ); S[i].V.Append( v ); if( rz ) { rec = new cut_record(); S[i].R.Append( rec ); rec->v = v; rec->e = NULL; rec->val = v->v.v().y; } v = v_next; } e = E->head; while( e != NULL ) { e_next = e->next; sign = compare(e->v[1]->v.v().x, e->v[0]->v.v().x); if( sign >= 0 ) { ii = 0; ik = 1; } else { ii = 1; ik = 0; } i = e->v[ii]->reserved[0].i; k = e->v[ik]->reserved[0].i; E->Remove( e ); S[k].E.Append( e ); if( i != k ) { if( e->l.IsNULL() ) { e->CalcLine(); } x0 = e->l.v().x; y0 = e->l.v().y; dy = e->l.dy(); if( e->v[ik]->reserved[1].i ) k--; for( j = i+1; j <= k; j++ ) { if( !dy.is_zero() ) y = y0 + (S[j].val-x0)*dy; else y = y0; rec = new cut_record(); S[j].R.Append( rec ); rec->v = NULL; rec->e = e; rec->val = y; } } e = e_next; } sort_cut_records( ns, S ); }

void ISDeleteBackpointers (  gugr::graph_edge_list &    E )  [inline]

Definition at line 491 of file gugr_planesweep.h. { graph_edge *e; gul::List< gul::ListNode< gul::ListNodeInfo< gul::ListNode<graph_edge *> > > > *L; e = E.First(); while( e ) // delete backpointer lists { L = (gul::List< gul::ListNode< gul::ListNodeInfo< gul::ListNode<graph_edge *> > > > *)e->reserved[1].p; L->DeleteElems(); delete L; e->reserved[1].p = 0; e = e->next; } }

void ISDeleteOwnerMaps (  gugr::graph_edge_list &    E )  [inline]

Definition at line 476 of file gugr_planesweep.h. { graph_edge *e = E.First(); while( e ) { delete (gul::RefMap<void> *)e->f[0].p; e->f[0].p = 0; delete (gul::RefMap<void> *)e->f[1].p; e->f[1].p = 0; e = e->next; } }

void gugr::LeftSideContour (  graph_edge *    e, graph_edge_list &    E, contour_node *    cn )

Definition at line 193 of file gugr_contour.cpp. { graph_edge **TE; graph_vertex *v0,*v; List< ListNode<graph_vertex *> > vlist; List< ListNode<graph_edge *> > elist; ListNode<graph_vertex *> *vn,*vn_next; ListNode<graph_edge *> *en,*en_next; int curside,n,side,nVerts,i; RefMap<void> *owners,*eowners; RefMap<void>::Node eowner,parent,owner; Ptr<vertex> verts; Ptr<line> lines; segment *seg; TE = (graph_edge **)alloca(sizeof(graph_edge *)*E.nElems); v0 = e->v[0]; // first vertice of contour vn = new ListNode<graph_vertex *>(v0); vlist.Append(vn); en = new ListNode<graph_edge *>(e); elist.Append(en); v = e->v[1]; // second vertice of contour vn = new ListNode<graph_vertex *>(v); vlist.Append(vn); curside = 0; // begin with the left side of the edge/side pair owners = (RefMap<void> *)e->f[0].p; // initialize owner set e->f[0].p = 0; // mark this edge/side pair as processed // set owner of corresponding segment to current contour seg = (segment *)e->reserved[2].p; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) seg->f[1].p = cn; // segment orientation different else seg->f[0].p = cn; for(;;) { n = EdgeCycle( e, v, TE ); e = TE[n-1]; // each edge has a backpointer to a segment for the second planesweep; // the face fields of these segments are initialized here (the planesweep // algo uses another edge orientation scheme then the rest of the graph // functions do !) seg = (segment *)e->reserved[2].p; if( e->v[0] == v ) { curside = 0; // use owners on the left side of the edge v = e->v[1]; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) seg->f[1].p = cn; // segment orientation different else seg->f[0].p = cn; } else { curside = 1; // use owners on the right side of the edge v = e->v[0]; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) seg->f[0].p = cn; // segment orientation different else seg->f[1].p = cn; } // add the owners of current edge/side pair to the contour owner set eowners = (RefMap<void> *)e->f[curside].p; eowner = eowners->First(); while( !eowner.IsEmpty() ) { side = owners->SearchNode( eowner.key(), compare_pointer_to_pointer, &parent ); if( side != 0 ) // new owner { owner = owners->NewNode( eowner.key() ); owners->InsertNode( owner, parent, side ); } eowner = eowners->Successor( eowner ); } delete eowners; // edge/side owners not needed anymore e->f[curside].p = 0; // mark edge/side pair as processed en = new ListNode<graph_edge *>(e); elist.Append(en); if( v != v0 ) { vn = new ListNode<graph_vertex *>(v); vlist.Append(vn); } else break; } // convert vertex list to array and delete it nVerts = vlist.nElems; verts.reserve_pool(nVerts); lines.reserve_pool(nVerts); vn = vlist.First(); vlist.ReleaseElems(); en = elist.First(); elist.ReleaseElems(); for( i = nVerts-1; i >= 0; i-- ) { verts[i] = vn->el->v; vn_next = vn->next; delete vn; vn = vn_next; lines[i] = en->el->l; en_next = en->next; delete en; en = en_next; } // convert owner set to array and delete it cn->nOwners = owners->ConvertToArray( &cn->owners ); delete owners; cn->nVerts = nVerts; cn->verts = verts; cn->lines = lines; return; }

const graph_edge NegInf (  0   , (graph_vertex *   )(-1) )

GULAPI void gugr::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 )

Definition at line 961 of file gugr_contour.cpp. { ListNode<polyline> *inc; List< ListNode<segment> > segs; E.DeleteElems(); // clear output lists V.DeleteElems(); outsegs.DeleteElems(); inc = inC.First(); while( inc ) { AppendContour( &inc->el, 1, 2, segs ); inc = inc->next; } /* cout << "PLANESWEEP\n"; cout << "==========\n"; cout << "INPUT SEGMENTS\n"; for( hn = segs.First(); hn != 0; hn = hn->next ) DumpPS<float>::dump_segment( &hn->el ); */ IntersectSegments( segs, &E, &V, false ); // backpointers are not needed, // since 'segs' is not used /* cout << "EDGES AFTER FIRST PLANESWEEP\n"; cout << "============================\n"; DumpPS<float>::dump_edges( E ); cout << "\n"; Dump<float>::dump_edges( E.head ); cout << "\n"; */ segs.DeleteElems(); // delete input segments (not needed) RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, key_inside, key_outside, outsegs ); }

std::ostream& operator<< (  std::ostream &    s, gugr::dump_segs &    S )  [inline]

Definition at line 283 of file gugr_io.h. { S.dump(S.m_S->First(),s); return s; }

std::ostream& operator<< (  std::ostream &    s, gugr::dump_graph &    g )  [inline]

Definition at line 246 of file gugr_io.h. { g.dump_vertices(g.m_VL->First(),s); g.dump_edges(g.m_EL->First(),s); return s << "\n"; }

bool operator== (  const vertex &    a, const vertex &    b )  [inline]

Definition at line 190 of file gugr_basics.h. { return( a.m_rep == b.m_rep ); }

void gugr::OrientEdge (  graph_edge *    e )

Definition at line 404 of file gugr_basics.cpp. { graph_edge *tmpe; graph_vertex *tmpv; gul::ptr_int_union tmpf; int sign; if( e != NULL ) { sign = compare( e->v[0]->v.v().y, e->v[1]->v.v().y ); if( !sign ) sign = -compare( e->v[0]->v.v().x, e->v[1]->v.v().x ); if( sign > 0 ) /* v1 > v2 */ { tmpv = e->v[0]; e->v[0] = e->v[1]; e->v[1] = tmpv; tmpe = e->e[0]; e->e[0] = e->e[1]; e->e[1] = tmpe; tmpf = e->f[0]; e->f[0] = e->f[1]; e->f[1] = tmpf; } } }

void gugr::OrientEdges (  graph_edge *    E )

Definition at line 437 of file gugr_basics.cpp. { graph_edge *e, *tmpe; graph_vertex *tmpv; gul::ptr_int_union tmpf; int sign; e = E; while( e != NULL ) { sign = compare( e->v[0]->v.v().y, e->v[1]->v.v().y ); if( !sign ) sign = -compare( e->v[0]->v.v().x, e->v[1]->v.v().x ); if( sign > 0 ) /* v1 > v2 */ { tmpv = e->v[0]; e->v[0] = e->v[1]; e->v[1] = tmpv; tmpe = e->e[0]; e->e[0] = e->e[1]; e->e[1] = tmpe; tmpf = e->f[0]; e->f[0] = e->f[1]; e->f[1] = tmpf; } e = e->next; } }

bool parallel (  const line &    a, const line &    b )  [inline]

Definition at line 260 of file gugr_basics.h. { if( a.IsHorizontal() ) return b.IsHorizontal(); else if( a.IsVertical() ) return b.IsVertical(); if( b.IsHorizontal() || b.IsVertical() ) return false; return compare( a.dy(), b.dy() ) == 0; }

template void Polygon3dTo2d (  const List< ListNode< gul::polyline< point< double > > > > &    C3, const Ptr< Ptr< double > > &    Ti, List< ListNode< gul::polyline< point2< double > > > > &    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<class T> void Polygon3dTo2d (  const List< ListNode< gul::polyline< point< T > > > > &    C3, const Ptr< Ptr< T > > &    Ti, List< ListNode< gul::polyline< point2< T > > > > &    C2 )

Definition at line 398 of file gugr_face.cpp. { ListNode< gul::polyline< point<T> > > *c3; ListNode< gul::polyline< point2<T> > > *c2; int i; Ptr<T> v3,v2; v3.reserve_pool(4); v2.reserve_pool(4); c3 = C3.First(); while( c3 ) { c2 = new ListNode< gul::polyline< point2<T> > >; C2.Append( c2 ); c2->el.n = c3->el.n; c2->el.P.reserve_pool( c3->el.n ); for( i = 0; i < c3->el.n; i++ ) { v3[0] = c3->el.P[i].x; v3[1] = c3->el.P[i].y; v3[2] = c3->el.P[i].z; v3[3] = (T)1; VMProduct(4,4,v3,Ti,v2); c2->el.P[i].x = v2[0]; c2->el.P[i].y = v2[1]; } c3 = c3->next; } }

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 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<class T> void gugr::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 )

Definition at line 196 of file gugr_basics.cpp. { graph_vertex *v, *vend, vdummy; graph_edge *e = 0, *eend, edummy; int i; T x,y; graph_vertex_list hv; graph_edge_list he; unsigned long *cbuf = (unsigned long *)alloca(gul::rtr<T>::mantissa_length()); he.head = eend = &edummy; hv.head = vend = &vdummy; for( i=0; i<n; i++ ) { x = (P[i].x - orgx)/scalex; y = (P[i].y - orgy)/scaley; e = new graph_edge(); he.Append(e); v = new graph_vertex( point2<rational>( rational(coord2int(x,cbuf),cbuf), rational(coord2int(y,cbuf),cbuf) ), e ); hv.Append(v); e->f[0].set_i(fleft); e->f[1].set_i(fright); e->v[0] = v; e->e[0] = e->next; e->next->v[1] = v; e->next->e[1] = e; } e->v[1] = vend->prev; e->e[1] = eend->prev; eend->prev->e[0] = e; vend->prev->next = V->head; eend->prev->next = E->head; if( V->head != NULL ) V->head->prev = vend->prev; if( E->head != NULL ) E->head->prev = eend->prev; E->head = he.head; E->nElems += n; V->head = hv.head; V->nElems += n; he.ReleaseElems(); hv.ReleaseElems(); }

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 )

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<class T> void gugr::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 )  [inline]

Definition at line 267 of file gugr_basics.cpp. { graph_vertex *v, *vend, vdummy; graph_edge *e = 0, *eend, edummy; int i; T x,y; graph_vertex_list hv; graph_edge_list he; unsigned long *cbuf = (unsigned long *)alloca(gul::rtr<T>::mantissa_length()); he.head = eend = &edummy; hv.head = vend = &vdummy; for( i=0; i<n; i++ ) { x = (P[i].x - orgx)/scalex; y = (P[i].y - orgy)/scaley; e = new graph_edge(); he.Append(e); v = new graph_vertex( point2<rational>( rational(coord2int(x,cbuf),cbuf), rational(coord2int(y,cbuf),cbuf) ), e ); hv.Append(v); v->v.m_rep->reserved.i = i; // enumber vertices e->f[0].set_i(fleft); e->f[1].set_i(fright); e->v[0] = v; e->e[0] = e->next; e->next->v[1] = v; e->next->e[1] = e; } e->v[1] = vend->prev; e->e[1] = eend->prev; eend->prev->e[0] = e; vend->prev->next = V->head; eend->prev->next = E->head; if( V->head != NULL ) V->head->prev = vend->prev; if( E->head != NULL ) E->head->prev = eend->prev; E->head = he.head; E->nElems += n; V->head = hv.head; V->nElems += n; he.ReleaseElems(); hv.ReleaseElems(); }

const graph_edge PosInf (  0   , (graph_vertex *   )(+1) )

void gugr::Regularize (  graph_edge_list *    E, graph_vertex_list *    V )

Definition at line 290 of file gugr_regularize.cpp. { edge_interval_tree Status; BBTNode *node,*node1,*node2; edge_interval *I; graph_edge **TE, *edge,*a,*r; graph_vertex *v0,*vmax,*vmin,*v; int nTE,sign,regular,j,side; TE = (graph_edge **)alloca( sizeof(graph_edge *)*(3*E->nElems) ); if( !TE ) throw AllocError(); vmax = SortVertices( V ); vmin = V->head; /*--- tree of intervalls bounded by two edges for status info -------------*/ node = Status.NewNode(); I = (edge_interval *)node->key; I->l = EDGE_NEG_INF; I->r = EDGE_POS_INF; I->v = NULL; Status.InsertNode( node, &Status.root, 1 ); // Status.Dump(); Status.DumpNodes(); /****************** Top-Down Sweep **********************************/ v0 = vmax; while( v0 != NULL ) { nTE = IncidentEdges( v0, TE ); regular = 0; for( j = 0; j < nTE; j++ ) { a = TE[j]; if( a->v[0] == v0 ) /* edge starts in v0 (then v0 cannot be maximum */ { /* of graph) */ regular = 1; sign = compare( a->v[1]->v.v().y, v0->v.v().y ); if( sign == 0 ) continue; /* nothing to do for horizontal edges */ /* replace the two intervalls [l,a],[a,r] with [l,r] */ node1 = (BBTNode *)a->reserved[0].p; node2 = (BBTNode *)a->reserved[1].p; edge = ((edge_interval *)(node2->key))->r; edge->reserved[0].p = (void *)node1; ((edge_interval *)(node1->key))->r = edge; ((edge_interval *)(node1->key))->v = v0; Status.RemoveNode( node2 ); Status.FreeNode( node2 ); // Status.Dump(); Status.DumpNodes(); } } if( (!regular) && (v0 != vmax) ) { side = Status.SearchNode( (void *)(v0->e), compare_edge_to_intervalTD, &node ); if( side != 0 ) throw InternalError(); v = ((edge_interval *)node->key)->v; edge = new graph_edge(); E->Append(edge); edge->v[1] = v; edge->v[0] = v0; EdgeInsert( edge, E->nElems ); } for( j = 0; j < nTE; j++ ) { a = TE[j]; if( a->v[1] == v0 ) /* edge ends in v0 */ { side = Status.SearchNode( (void *)a, compare_edge_to_intervalTD, &node1 ); if( side != 0 ) throw InternalError(); sign = compare( a->v[0]->v.v().y, v0->v.v().y ); if( sign == 0 ) /*special case: horizontal edge */ { ((edge_interval *)(node1->key))->v = a->v[0]; } else { r = ((edge_interval *)node1->key)->r; ((edge_interval *)node1->key)->r = a; ((edge_interval *)node1->key)->v = v0; a->reserved[0].p = (void *)node1; node2 = Status.NewNode(); ((edge_interval *)node2->key)->l = a; ((edge_interval *)node2->key)->r = r; ((edge_interval *)node2->key)->v = v0; a->reserved[1].p = (void *)node2; r->reserved[0].p = (void *)node2; side = Status.SearchNode( (void *)a, compare_edge_to_intervalTD, &node ); if( side == 0 ) throw InternalError(); Status.InsertNode( node2, node, side ); // Status.Dump(); Status.DumpNodes(); } } } v0 = v0->prev; } /********* Bottom Up Sweep ****************************************/ node = Status.Head(); I = (edge_interval *)node->key; I->v = NULL; gul::Assert<InternalError>( ndebug || ((node->left == NULL) || (node->right == NULL) || (I->l == EDGE_NEG_INF) || (I->r == EDGE_POS_INF)) ); v0 = vmin; while( v0 != NULL ) { nTE = IncidentEdges( v0, TE ); regular = 0; for( j = 0; j < nTE; j++ ) { a = TE[j]; if( a->v[1] == v0 ) /* edge ends in v0 (then v0 cannot be minimum */ { /* of graph) */ regular = 1; sign = compare( a->v[0]->v.v().y, v0->v.v().y ); if( sign == 0 ) continue; /* nothing to do for horizontal edges */ /* replace the two intervalls [l,a],[a,r] with [l,r] */ node1 = (BBTNode *)a->reserved[0].p; node2 = (BBTNode *)a->reserved[1].p; edge = ((edge_interval *)(node2->key))->r; edge->reserved[0].p = (void *)node1; ((edge_interval *)(node1->key))->r = edge; ((edge_interval *)(node1->key))->v = v0; Status.RemoveNode( node2 ); Status.FreeNode( node2 ); } } if( (!regular) && (v0 != vmin) ) { side = Status.SearchNode( (void *)(v0->e), compare_edge_to_intervalBU, &node ); if( side != 0 ) throw InternalError(); v = ((edge_interval *)node->key)->v; edge = new graph_edge(); E->Append(edge); edge->v[1] = v0; edge->v[0] = v; EdgeInsert( edge, E->nElems ); } for( j = 0; j < nTE; j++ ) { a = TE[j]; if( a->v[0] == v0 ) /* edge starts in v0 */ { side = Status.SearchNode( (void *)a, compare_edge_to_intervalBU, &node1 ); if( side != 0 ) throw InternalError(); sign = compare( a->v[1]->v.v().y, v0->v.v().y ); if( sign == 0 ) /*special case: horizontal edge */ { ((edge_interval *)(node1->key))->v = a->v[1]; } else { r = ((edge_interval *)node1->key)->r; ((edge_interval *)node1->key)->r = a; ((edge_interval *)node1->key)->v = v0; a->reserved[0].p = (void *)node1; node2 = Status.NewNode(); ((edge_interval *)node2->key)->l = a; ((edge_interval *)node2->key)->r = r; ((edge_interval *)node2->key)->v = v0; a->reserved[1].p = (void *)node2; r->reserved[0].p = (void *)node2; side = Status.SearchNode( (void *)a, compare_edge_to_intervalBU, &node ); if( side == 0 ) throw InternalError(); Status.InsertNode( node2, node, side ); } } } v0 = v0->next; } node = Status.Head(); I = (edge_interval *)node->key; gul::Assert<InternalError>( ndebug || ((node->left == NULL) || (node->right == NULL) || (I->l == EDGE_NEG_INF) || (I->r == EDGE_POS_INF)) ); Status.RemoveNode( node ); Status.FreeNode( node ); }

void gugr::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 )

Definition at line 688 of file gugr_contour.cpp. { gugr::graph_edge_list E2; gugr::graph_vertex_list V2; graph_edge *e,*e_next; ListNode<segment> *sn; List<contour_node> contours; contour_node *cn,*C0,*C1; segment *seg; int m,i,n,nEdges,side; bool end; Ptr<void *> edges; graph_edge **TE; ListNode<graph_edge *> *en; RefMap<void> *M; RefMap<void>::Node parent; int left,right,isolated; List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *L; ListNode< ListNodeInfo< ListNode<graph_edge *> > > *bptr, *bptr_next; FindContours( E, V, far_maxx, far_maxy, outsegs, contours ); /* ------ second planesweep ------------------------------- */ /* cout << "PLANESWEEP\n"; cout << "==========\n"; cout << "INPUT SEGMENTS\n"; for( hn = segs.First(); hn != 0; hn = hn->next ) DumpPS<float>::dump_segment( &hn->el ); */ IntersectSegments( outsegs, &E2, &V2, false ); /* cout << "EDGES AFTER SECOND PLANESWEEP\n"; cout << "============================\n"; DumpPS<float>::dump_edges( E2 ); cout << "\n"; Dump<float>::dump_edges( E2.head ); cout << "\n"; cout.flush(); */ // travert the help lines to classify the regions as loops or holes TE = (graph_edge **)alloca(sizeof(graph_edge *)*E2.nElems); edges.reserve_pool(E2.nElems); for( cn = contours.First(); cn != 0; cn = cn->next ) // travert contours { m = 0; en = cn->hseg->e.First(); if( en ) { e = en->el; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) end = 1; else end = 0; } while( en ) { en = en->next; if( !en ) break; // special treatment for the last edge n = EdgeCycle( e, e->v[end], TE ); for( i = 1; TE[i] != en->el; i++ ) // edges above help line (or left of { // vertical help line) m += (int)TE[i]->reserved[0].i; // count the number of intersections } e = en->el; // next edge } // last edge, its endpoint lies on the segment of the contour which // shall be classified nEdges = cn->seg->e.nElems; for( en = cn->seg->e.First(), i=0; en != 0; en = en->next, i++ ) edges[i] = en->el; heapsort( nEdges, edges ); n = EdgeCycle( e, e->v[end], TE ); for( i = 1; ; i++ ) // edges above help line until edge on segment reached { if( BinarySearch( (void *)TE[i], nEdges, edges ) >= 0 ) break; m += (int)TE[i]->reserved[0].i; // count the number of intersections } // if the contour lies on the opposite site of the segment edge add its // multiplicity too if( TE[i]->v[0] == e->v[end] ) M = (RefMap<void> *)TE[i]->f[0].p; else M = (RefMap<void> *)TE[i]->f[1].p; side = M->SearchNode( (void *)cn, compare_pointer_to_pointer, &parent ); if( side == 0 ) { m += (int)TE[i]->reserved[0].i; // count the number of intersections } cn->hole = ((m & 1) == 0); } // cleanup ISDeleteOwnerMaps(E2); E2.DeleteElems(); V2.DeleteElems(); /* cn = contours.First(); i = 0; while( cn ) { i++; cout << "CONTOUR #" << i << " (" << (void *)cn << ")\n"; cout << "hole = " << cn->hole << "\n"; cout << dump_vector<int>(cn->nOwners, cn->owners); for( i = 0; i < cn->nVerts; i++ ) Dump<float>::dump_vert( cn->verts[i] ); cn = cn->next; } */ // remove unnecessary edges which have holes or loops on both sides e = E.First(); while( e ) { seg = (segment *)e->reserved[2].p; C0 = (contour_node *)seg->f[0].p; C1 = (contour_node *)seg->f[1].p; if( C0->hole == C1->hole ) { /* cout << "removing edge " << (void *)e << "\n"; */ // some dangerous pointer arithmetic to get the segment node address gul::Assert<InternalError>( ndebug || (outsegs.First() == (ListNode<segment> *)&outsegs.First()->el) ); /* cout << (void *)esegs.First() << " == " << (void *)&esegs.First()->el << "\n"; */ sn = (ListNode<segment> *)seg; outsegs.Remove( sn ); delete sn; isolated = DisconnectEdge(e,E.nElems); if( (isolated & 1) ) { V.Remove(e->v[0]); delete e->v[0]; } if( (isolated & 2) ) { V.Remove(e->v[1]); delete e->v[1]; } // remove edge from the edge lists of backpointed segments if( e->reserved[1].p ) { L = (List< ListNode< ListNodeInfo< ListNode<graph_edge *> > > > *) e->reserved[1].p; bptr = L->First(); L->ReleaseElems(); // will be deleted manually in the following delete L; while( bptr ) { bptr->el.m_L->Remove( bptr->el.m_n ); bptr_next = bptr->next; delete bptr; bptr = bptr_next; } } e_next = e->next; E.Remove(e); delete e; e = e_next; } else { // set the edge side flags. after this the graph is ready for // triangulation if( C0->hole ) { left = key_outside; right = key_inside; } else { left = key_inside; right = key_outside; } if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) { e->f[0].set_i(right); // segment orientation different e->f[1].set_i(left); } else { e->f[0].set_i(left); e->f[1].set_i(right); } // set the side flags of the segments; after this the segment list can be // used as the input for building the new contours (without the // unnecessary edges) and their containment tree for elimination of // unnecessary contours (like holes within holes) seg->f[0].set_i(left); seg->f[1].set_i(right); seg->e.DeleteElems(); // these are meaningless since they point into E2 e = e->next; } } // cleanup for( cn = contours.First(); cn != 0; cn = cn->next ) // remove help lines { if( cn->hseg_firstref ) { sn = (ListNode<segment> *)cn->hseg; outsegs.Remove( sn ); delete sn; } } /* cout << "EDGES AFTER REMOVAL\n"; cout << "===================\n"; Dump<float>::dump_edges( E.head ); cout << "\n"; cout << "SEGMENTS AFTER REMOVAL\n"; cout << "===================\n"; for( hn = esegs.First(); hn != 0; hn = hn->next ) DumpPS<float>::dump_segment( &hn->el ); */ contours.DeleteElems(); }

void gugr::RightSideContour (  graph_edge *    e, graph_edge_list &    E, contour_node *    cn )

Definition at line 328 of file gugr_contour.cpp. { graph_edge **TE; graph_vertex *v0,*v; List< ListNode<graph_vertex *> > vlist; List< ListNode<graph_edge *> > elist; ListNode<graph_vertex *> *vn,*vn_next; ListNode<graph_edge *> *en,*en_next; int curside,n,side,nVerts,i; RefMap<void> *owners,*eowners; RefMap<void>::Node eowner,parent,owner; Ptr<vertex> verts; Ptr<line> lines; segment *seg; TE = (graph_edge **)alloca(sizeof(graph_edge *)*E.nElems); v0 = e->v[0]; // first vertice of contour vn = new ListNode<graph_vertex *>(v0); vlist.Append(vn); en = new ListNode<graph_edge *>(e); elist.Append(en); v = e->v[1]; // second vertice of contour vn = new ListNode<graph_vertex *>(v); vlist.Append(vn); curside = 1; // begin with the right side of the edge/side pair owners = (RefMap<void> *)e->f[1].p; // initialize owner set e->f[1].p = 0; // mark this edge/side pair as processed // set owner of corresponding segment to current contour seg = (segment *)e->reserved[2].p; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) seg->f[0].p = cn; // segment orientation different else seg->f[1].p = cn; for(;;) { n = EdgeCycle( e, v, TE ); e = TE[1]; // each edge has a backpointer to a segment for the second planesweep; // the face fields of these segments are initialized here (the planesweep // algo uses another edge orientation scheme then the rest of the graph // functions too !) seg = (segment *)e->reserved[2].p; if( e->v[0] == v ) { curside = 1; // use owners on the right side of the edge v = e->v[1]; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) seg->f[0].p = cn; // segment orientation different else seg->f[1].p = cn; } else { curside = 0; // use owners on the left side of the edge v = e->v[0]; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) seg->f[1].p = cn; // segment orientation different else seg->f[0].p = cn; } // add the owners of current edge/side pair to the contour owner set eowners = (RefMap<void> *)e->f[curside].p; eowner = eowners->First(); while( !eowner.IsEmpty() ) { side = owners->SearchNode( eowner.key(), compare_pointer_to_pointer, &parent ); if( side != 0 ) // new owner { owner = owners->NewNode( eowner.key() ); owners->InsertNode( owner, parent, side ); } eowner = eowners->Successor( eowner ); } delete eowners; // edge/side owners not needed anymore e->f[curside].p = 0; // mark edge/side pair as processed en = new ListNode<graph_edge *>(e); elist.Append(en); if( v != v0 ) { vn = new ListNode<graph_vertex *>(v); vlist.Append(vn); } else break; } // convert vertex list to array and delete it nVerts = vlist.nElems; verts.reserve_pool(nVerts); lines.reserve_pool(nVerts); vn = vlist.First(); vlist.ReleaseElems(); en = elist.First(); elist.ReleaseElems(); for( i = nVerts-1; i >= 0; i-- ) { verts[i] = vn->el->v; vn_next = vn->next; delete vn; vn = vn_next; lines[i] = en->el->l; en_next = en->next; delete en; en = en_next; } // convert owner set to array and delete it cn->nOwners = owners->ConvertToArray( &cn->owners ); delete owners; cn->nVerts = nVerts; cn->verts = verts; cn->lines = lines; return; }

void sort_cut_records (  int    ns, Ptr< cut_info >    S )

Definition at line 54 of file gugr_split.cpp. { cut_record *rec, **tmpR; int i,j,max_nR; max_nR = 0; for( i = 1; i <= ns; i++ ) if( S[i].R.nElems > max_nR ) max_nR = S[i].R.nElems; if( max_nR > 0 ) { tmpR = (cut_record **)alloca( sizeof(cut_record *)*max_nR ); if( !tmpR ) throw AllocError(); } else tmpR = 0; // make compiler happy :) for( i = 1; i <= ns; i++ ) { if( S[i].R.nElems > 1 ) { rec = S[i].R.head; for( j = 0; j < S[i].R.nElems; j++ ) { tmpR[j] = rec; rec = rec->next; } guma::PtrHeapSort( S[i].R.nElems,(void **)tmpR, compare_cut_records,NULL); S[i].R.head = tmpR[0]; tmpR[0]->prev = NULL; for( j = 1; j < S[i].R.nElems; j++ ) { tmpR[j-1]->next = tmpR[j]; tmpR[j]->prev = tmpR[j-1]; } tmpR[S[i].R.nElems-1]->next = NULL; } } }

graph_vertex * gugr::SortVertices (  graph_vertex_list *    V )

Definition at line 58 of file gugr_regularize.cpp. { graph_vertex **tmpV,*v; int i,j; tmpV = (graph_vertex **)alloca( sizeof(graph_vertex *)*V->nElems ); if( !tmpV ) throw AllocError(); v = V->head; for( i = 0; i < V->nElems; i++ ) { tmpV[i] = v; v = v->next; } PtrHeapSort( V->nElems, (void **)tmpV, compare_vertices, NULL ); V->head = tmpV[0]; tmpV[0]->prev = NULL; for( j = 1; j < V->nElems; j++ ) { tmpV[j-1]->next = tmpV[j]; tmpV[j]->prev = tmpV[j-1]; } tmpV[V->nElems-1]->next = NULL; return(tmpV[V->nElems-1]); /* return last vertex in list */ }

template void SplitGraph (  GraphInfo *    G, double    xmed, double    ymed, GraphConvInfo< double > *    Gconv, GraphInfo4 &    sub )

template void SplitGraph (  GraphInfo *    G, float    xmed, float    ymed, GraphConvInfo< float > *    Gconv, GraphInfo4 &    sub )

template<class T> void gugr::SplitGraph (  GraphInfo *    G, T    xmed, T    ymed, GraphConvInfo< T > *    Gconv, GraphInfo4 &    sub )

Definition at line 1537 of file gugr_split.cpp. { graph_vertex *Vy1Sl, *Vy1Sr, *Vy2Sl, *Vy2Sr, *Vx1Sa, *Vx1Sb, *Vx2Sa, *Vx2Sb; graph_vertex *hvLeftT, *hvRightT; graph_edge *e, *el, **hE; graph_vertex *v, *v0; int nhE, nMaxE, i, j; rational X1,X2,X3; rational Y1,Y2,Y3; unsigned long *cbuf = (unsigned long *)alloca(gul::rtr<double>::mantissa_length()); T y2,x2; Ptr< gugr::cut_info > CutsX, CutsY; /* cout << "SPLITGRAPH: input graph\n"; cout << "**********************\n"; gugr::Dump<T>::dump_vertices( G->V.head ); gugr::Dump<T>::dump_edges( G->E.head ); */ rational& MinX = Gconv->MinX; // short aliases rational& MaxX = Gconv->MaxX; rational& FarMinX = Gconv->FarMinX; rational& FarMaxX = Gconv->FarMaxX; rational& MinY = Gconv->MinY; rational& MaxY = Gconv->MaxY; rational& FarMinY = Gconv->FarMinY; rational& FarMaxY = Gconv->FarMaxY; CutsX.reserve_place( reserve_stack(cut_info,4), 4 ); CutsY.reserve_place( reserve_stack(cut_info,4), 4 ); x2 = (xmed - Gconv->minx)/Gconv->scale; X2 = rational(coord2int(x2,cbuf),cbuf); y2 = (ymed - Gconv->miny)/Gconv->scale; Y2 = rational(coord2int(y2,cbuf),cbuf); CutsX[1].val = X1 = G->P[0][0]->v.v().x; CutsX[2].val = X2; CutsX[3].val = X3 = G->P[0][1]->v.v().x; CutsY[1].val = Y1 = G->P[0][0]->v.v().y; CutsY[2].val = Y2; CutsY[3].val = Y3 = G->P[1][0]->v.v().y; nMaxE = 10*G->E.nElems; // this is a hack, but its enough even in the // in the worst case hE = (graph_edge **)alloca( sizeof(graph_edge *) * nMaxE ); // split graph into vertical strips IntersectWithVerticals( &G->E, &G->V, 4, CutsX ); // isolate first vertical strip and discard it DivideVerticalStrips( &CutsX[3], &CutsX[2], nMaxE, MinY, MaxY, FarMinY, FarMaxY, &Vy1Sr, &Vy1Sl, &Vy2Sr, &Vy2Sl ); /* cout << "after disconnecting X-Strip " << 3 << " and " << 2 << "\n"; cout << "*******************************************************\n"; for( int k = 3; k >= 0; k-- ) { cout << "X-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsX[k].V.head ); gugr::Dump<T>::dump_edges( CutsX[k].E.head ); } */ CutsX[3].R.DeleteElems(); CutsX[3].E.DeleteElems(); CutsX[3].V.DeleteElems(); for( i = 2; i > 0; i-- ) { DivideVerticalStrips( &CutsX[i], &CutsX[i-1], nMaxE, MinY, MaxY, FarMinY, FarMaxY, &Vy1Sr, &Vy1Sl, &Vy2Sr, &Vy2Sl ); /* cout << "after disconnecting X-Strip " << i << " and " << i-1 << "\n"; cout << "*********************************************************\n"; for( int k = i; k >= 0; k-- ) { cout << "X-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsX[k].V.head ); gugr::Dump<T>::dump_edges( CutsX[k].E.head ); } */ // split vertical strips into horizontal strips IntersectWithHorizontals( &CutsX[i].E, &CutsX[i].V, 4, CutsY ); // isolate first strip and discard it DivideHorizontalStrips( &CutsY[3], &CutsY[2], nMaxE, MinX, MaxX, FarMinX, FarMaxX, &Vx1Sa, &Vx1Sb, &Vx2Sa, &Vx2Sb ); /* cout << "after disconnecting Y-Strip " << 3 << " and " << 2 << "\n"; cout << "*******************************************************\n"; for( int k = 3; k >= 0; k-- ) { cout << "Y-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsY[k].V.head ); gugr::Dump<T>::dump_edges( CutsY[k].E.head ); } */ CutsY[3].R.DeleteElems(); CutsY[3].E.DeleteElems(); CutsY[3].V.DeleteElems(); hvLeftT = Vx1Sb; hvRightT = Vx2Sb; // for next strip // divide vertical strips into horizontal strips for( j = 2; j > 0; j-- ) { DivideHorizontalStrips( &CutsY[j], &CutsY[j-1], nMaxE, MinX, MaxX, FarMinX, FarMaxX, &Vx1Sa, &Vx1Sb, &Vx2Sa, &Vx2Sb ); /* cout << "after disconnecting Y-Strip " << j << " and " << j-1 << "\n"; cout << "*********************************************************\n"; for( int k = j; k >= 0; k-- ) { cout << "Y-Strip " << k << "\n"; gugr::Dump<T>::dump_vertices( CutsY[k].V.head ); gugr::Dump<T>::dump_edges( CutsY[k].E.head ); } */ // remove help edges from the corner edge cycles v0 = hvLeftT; e = v0->e; sub[2*(j-1)+i-1]->face = e->e[0]->f[1].i; // face index of quad, if it is v = e->v[0]; // not divided sub[2*(j-1)+i-1]->P[1][0] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[0]; else el->e[1] = e->e[0]; v->e = el; CutsY[j].V.Remove(v0); CutsY[j].E.Remove(e); delete v0; delete e; v0 = hvRightT; e = v0->e; v = e->v[1]; sub[2*(j-1)+i-1]->P[1][1] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[1]; else el->e[1] = e->e[1]; v->e = el; CutsY[j].V.Remove(v0); CutsY[j].E.Remove(e); delete v0; delete e; v0 = Vx2Sa; e = v0->e; v = e->v[1]; sub[2*(j-1)+i-1]->P[0][1] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[1]; else el->e[1] = e->e[1]; v->e = el; CutsY[j].V.Remove(v0); CutsY[j].E.Remove(e); delete v0; delete e; v0 = Vx1Sa; e = v0->e; v = e->v[0]; sub[2*(j-1)+i-1]->P[0][0] = v; nhE = EdgeCycle( e, v, hE ); el = hE[nhE-1]; if( el->v[0] == v ) el->e[0] = e->e[0]; else el->e[1] = e->e[0]; v->e = el; CutsY[j].V.Remove(v0); CutsY[j].E.Remove(e); delete v0; delete e; hvLeftT = Vx1Sb; hvRightT = Vx2Sb; // for next loop CutsY[j].R.DeleteElems(); // free cut records only sub[2*(j-1)+i-1]->E += CutsY[j].E; sub[2*(j-1)+i-1]->V += CutsY[j].V; // CutsY[j].E.ReleaseElems(); // clear for next strip // CutsY[j].V.ReleaseElems(); } CutsY[0].R.DeleteElems(); CutsY[0].E.DeleteElems(); CutsY[0].V.DeleteElems(); CutsX[i].R.DeleteElems(); CutsX[i].E.DeleteElems(); CutsX[i].V.DeleteElems(); } CutsX[0].R.DeleteElems(); CutsX[0].E.DeleteElems(); CutsX[0].V.DeleteElems(); }

void gugr::Triangulate (  graph_edge_list *    E, graph_vertex_list *    V, const rational &    far_left, triangle_list *    T )

Definition at line 48 of file gugr_triangulate.cpp. { vertex farleft; graph_edge *e, *eb, *ea,*left,*right,**tmpE; graph_vertex *v; int ileft,iright,codel,coder,nE,Win,Wout,ie,iea,ieb; int nP,i; graph_edge *e1; monpoly_info *P,*tmpP; int li,ri; tmpE = (graph_edge **)alloca( sizeof(graph_edge *)*(E->nElems) ); if( !tmpE ) throw AllocError(); if( V->head != NULL ) v = V->head->next; /* second smallest vertex */ else return; if( v->next == NULL ) return; e = E->head; while( e != NULL ) /* initialize weights to 1 */ { e->reserved[0].set_i(1); e = e->next; } /* ---------- weight balancing, first pass ----------------------------- */ while( v->next != NULL ) { nE = IncidentEdges( v, tmpE ); farleft = vertex( point2<rational>(far_left,v->v.v().y) ); EdgeInsertPosition( v->v, farleft, nE, tmpE, &ileft, &iright, &codel, &coder ); left = tmpE[ileft]; right = tmpE[iright]; if( right->v[0] == v ) /* => leftwards oriented horizontal edge */ e = eb = right->e[0]; else e = eb = right; /* eb = leftmost incoming edge */ Win = 0; /* sum of weights of incoming edges of v */ while( e->v[1] == v ) { Win += e->reserved[0].i; e = e->e[1]; } Wout = 1; /* sum of weights of outgoing edges of v */ while( e->e[0] != eb ) { Wout++; e = e->e[0]; } ea = e; /* ea = leftmost outgoing edge */ if( Win > Wout ) ea->reserved[0].set_i(Win-Wout+1); v = v->next; } /***** second pass, combined with extraction of monotone polygons *********/ /* ------- initialize polygon slots at the maximum vertex -------- */ nP = 0; nE = IncidentEdges( v, tmpE ); /* edges adjacent to maximum of graph */ farleft = vertex( point2<rational>(far_left,v->v.v().y) ); EdgeInsertPosition( v->v, farleft, nE, tmpE, &ileft, &iright, &codel, &coder ); e1 = right = tmpE[iright]; do { e1->reserved[1].set_i(nP); /* store index of the polygon on the right*/ nP += e1->reserved[0].i; /* side of this edge */ e1 = e1->e[1]; } while( e1 != right ); nP--; P = tmpP = (monpoly_info *)alloca( sizeof(monpoly_info) * nP ); if( P == NULL ) throw AllocError(); // new(P) monpoly_info[nP]; for( i = 0; i < nP; i++ ) new(tmpP++) monpoly_info; /* std::cout << "number of monotone polygons = " << nP << "\n"; */ /* ------- second pass of weight balancing -------- */ v = v->prev; /* v = second largest vertex */ while( v->prev != NULL ) { nE = IncidentEdges( v, tmpE ); farleft = vertex( point2<rational>(far_left,v->v.v().y) ); EdgeInsertPosition( v->v, farleft, nE, tmpE, &ileft, &iright, &codel, &coder ); if( tmpE[iright]->v[0] == v ) /* => leftwards oriented horizontal edge */ ie = iea = iright; else ie = iea = ileft; /* iea = index of leftmost outgoing edge */ Wout = 0; /* sum of weights of outgoing edges of v */ do { Wout += tmpE[ie]->reserved[0].i; /* ----- add edge to involved polygons ---------------- */ li = tmpE[ie]->reserved[1].i-1; if( (li >= 0) && (tmpE[ie]->f[0].i > 0) ) { /* std::cout << "adding edge " << (void *)tmpE[ie] << " to polygon " << li+1 << ", right chain\n"; */ if( P[li].AppendRight(*v, *tmpE[ie]->v[1]) ) { /* std::cout << "triangulating monotone polygon #" << li+1 << "\n"; */ TriangulateMonotonePolygon( &P[li].Vl, &P[li].Vr, &P[li].E, T ); } } ri = li + tmpE[ie]->reserved[0].i; if( (ri < nP) && (tmpE[ie]->f[1].i > 0) ) { /* std::cout << "adding edge " << (void *)tmpE[ie] << " to polygon " << ri+1 << ", left chain\n"; */ if( P[ri].AppendLeft(*v, *tmpE[ie]->v[1]) ) { /* std::cout << "triangulating monotone polygon #" << ri+1 << "\n"; */ TriangulateMonotonePolygon( &P[ri].Vl, &P[ri].Vr, &P[ri].E, T ); } } /* ---------------------------------------------------- */ ie--; if(ie < 0) ie = nE-1; } while( tmpE[ie]->v[0] == v ); Win = 0; /* sum of weights of incoming edges of v */ while( tmpE[ie] != tmpE[iea] ) { Win += tmpE[ie]->reserved[0].i; ie--; if(ie < 0) ie = nE-1; } ieb = iea+1; /* ieb = index of leftmost incoming edge */ if( ieb == nE ) ieb = 0; if( Wout > Win ) tmpE[ieb]->reserved[0].i += (Wout-Win); /* -------- set polygon indices for incoming edges -------------------- */ i = tmpE[iea]->reserved[1].i; /* index of polygon to the right of */ e = tmpE[ieb]; /* leftmost edges */ e->reserved[1].set_i(i); /* give leftmost incoming edge this index */ i += e->reserved[0].i; /* add multiplicity of edge */ e = e->e[1]; /* next edge */ while( e->v[1] == v ) /* is next incoming edge */ { e->reserved[1].set_i(i); i += e->reserved[0].i; e = e->e[1]; /* next edge */ } /* -------------------------------------------------------------------- */ v = v->prev; } /* process smallest vertex */ nE = IncidentEdges( v, tmpE ); /* incident edges to smallest vertex */ farleft = vertex( point2<rational>(far_left,v->v.v().y) ); EdgeInsertPosition( v->v, farleft, nE, tmpE, &ileft, &iright, &codel, &coder ); if( tmpE[iright]->IsHorizontal() ) /* => leftwards orient horizontal edge */ ie = iea = iright; else ie = iea = ileft; /* iea = index of leftmost outgoing edge */ do /* add edges to involved polygons */ { li = tmpE[ie]->reserved[1].i-1; if( (li >= 0) && (tmpE[ie]->f[0].i > 0) ) { /* std::cout << "adding edge " << (void *)tmpE[ie] << " to polygon " << li+1 << ", right chain\n"; */ if( P[li].AppendRight(*v, *tmpE[ie]->v[1]) ) { /* std::cout << "triangulating monotone polygon #" << li+1 << "\n"; */ TriangulateMonotonePolygon( &P[li].Vl, &P[li].Vr, &P[li].E, T ); } } ri = li + tmpE[ie]->reserved[0].i; if( (ri < nP) && (tmpE[ie]->f[1].i > 0) ) { /* std::cout << "adding edge " << (void *)tmpE[ie] << " to polygon " << ri+1 << ", left chain\n"; */ if( P[ri].AppendLeft(*v, *tmpE[ie]->v[1]) ) { /* std::cout << "triangulating monotone polygon #" << ri+1 << "\n"; */ TriangulateMonotonePolygon( &P[ri].Vl, &P[ri].Vr, &P[ri].E, T ); } } ie--; if(ie < 0) ie = nE-1; } while( ie != iea ); for( i = 0; i < nP; i++ ) { P[i].Vl.DeleteElems(); P[i].Vr.DeleteElems(); P[i].E.DeleteElems(); } }

void gugr::TriangulateMonotonePolygon (  graph_vertex_list2 *    V1, graph_vertex_list2 *    V2, graph_edge_list *    E, triangle_list *    T )

Definition at line 303 of file gugr_triangulate.cpp. { graph_vertex_list2 Vq, S; graph_vertex *vh,*v1,*v2,*vi,*vi_1,*vs,*vt,*v,*vh1,*vh2; graph_edge *e; triangle *tri; int sign; graph_vertex_list V; /* cout << "Triangulation of montone polygon\n"; cout << "********************************\n"; cout << "Vertices of left chain\n"; cout << "======================\n"; gugr::Dump<float>::dump_vertices( V1->head ); cout << "Vertices of right chain\n"; cout << "======================\n"; gugr::Dump<float>::dump_vertices( V2->head ); cout << "Edges (of both chains)\n"; cout << "======================\n"; gugr::Dump<float>::dump_edges( E->head ); */ /* ----- merge together the vertices of both monotone chains ------------ */ vh1 = V1->Last(); /* first vertex of chain 1 */ V1->Remove(vh1); V.Append(vh1); vh2 = V2->Last(); /* first vertex of chain 2 */ V2->Remove(vh2); V.Append(vh2); v1 = V1->Last(); V1->Remove(v1); v1->reserved[0].set_i(-1); /* element of left chain */ v2 = V2->Last(); V2->Remove(v2); v2->reserved[0].set_i(+1); /* element of right chain */ if( (V1->Last() == NULL) && (V2->Last() == NULL) ) /* ready, no triangles */ { delete v1; delete v2; V1->DeleteElems(); V2->DeleteElems(); V.DeleteElems(); E->DeleteElems(); return; } /* make first vertex of both chains have the same address */ vh = new graph_vertex( vh2->v, NULL, vh2->reserved[1].i ); Vq.AppendRight(vh); vh->reserved[0].set_i(0); e = new graph_edge(); E->Append(e); e->l = v1->e->l; e->v[0] = v1; e->v[1] = vh; v1->e = e; e = new graph_edge(); E->Append(e); e->l = v2->e->l; e->v[0] = v2; e->v[1] = vh; v2->e = e; while( (v1 != NULL) || (v2 != NULL) ) { if( v1 != NULL ) { if( v2 != NULL ) sign = compare( v1->v.v().y, v2->v.v().y ); else sign = +1; } else sign = -1; if( sign >= 0 ) { if( v1->e->IsHorizontal() ) /* compress together horizontal edges */ { vs = v1; vt = V1->Last(); while( (vt != NULL) && (vt->e->IsHorizontal()) ) { V1->Remove(vt); delete v1; v1 = vt; vt = V1->Last(); } if( v1 != vs ) { e = new graph_edge(); E->Append(e); e->l = v1->e->l; e->v[0] = v1; e->v[1] = vh; v1->e = e; } } v1->reserved[0].set_i(-1); Vq.AppendRight(v1); vh = v1; v1 = V1->Last(); if( v1 != NULL ) V1->Remove(v1); } else { if( v2->e->IsHorizontal() ) /* compress together horizontal edges */ { vs = v2; vt = V2->Last(); while( (vt != NULL) && (vt->e->IsHorizontal()) ) { V2->Remove(vt); delete v2; v2 = vt; vt = V2->Last(); } if( v2 != vs ) { e = new graph_edge(); E->Append(e); e->l = v2->e->l; e->v[0] = v2; e->v[1] = vh; v2->e = e; } } v2->reserved[0].set_i(+1); Vq.AppendRight(v2); vh = v2; v2 = V2->Last(); if( v2 != NULL ) V2->Remove(v2); } } vh->prev->reserved[0].set_i(0); /* this is the last vertex */ Vq.Remove(vh); delete vh; /* ---- construct the triangles ------------------------------------------- */ v = Vq.First(); /* put first two vertices on stack */ Vq.Remove(v); S.AppendRight(v); v = Vq.First(); Vq.Remove(v); S.AppendRight(v); v = Vq.First(); Vq.Remove(v); while( v->reserved[0].i != 0 ) /* not the last vertex */ { vi = S.Last(); v1 = S.First(); e = v->e; if( e->v[1] == vi ) /* adjacent to top of stack */ { vi_1 = vi->prev; sign = DetermineOrientation(v->v.v(),vi->v.v(),vi_1->v.v()); sign *= v->reserved[0].i; if( (sign == 0) && (v->e->IsHorizontal()) ) /* special case */ { S.Remove(vi); V.Append(vi); S.AppendRight(v); } else { while( (sign > 0) && (S.nElems > 1) ) { tri = new triangle(); if( vi->reserved[0].i == +1 ) { tri->v[0] = v->v; tri->code0 = v->reserved[1].i; tri->v[1] = vi->v; tri->code1 = vi->reserved[1].i; tri->v[2] = vi_1->v; tri->code2 = vi_1->reserved[1].i; /* cout << "TRIANGLE\n"; Dump<float>::dump_vertice(v); Dump<float>::dump_vertice(vi); Dump<float>::dump_vertice(vi_1); */ } else { tri->v[0] = v->v; tri->code0 = v->reserved[1].i; tri->v[1] = vi_1->v; tri->code1 = vi_1->reserved[1].i; tri->v[2] = vi->v; tri->code2 = vi->reserved[1].i; /* cout << "TRIANGLE\n"; Dump<float>::dump_vertice(v); Dump<float>::dump_vertice(vi_1); Dump<float>::dump_vertice(vi); */ } T->Append(tri); S.Remove(vi); V.Append(vi); if( S.nElems > 1 ) { vi = vi_1; vi_1 = vi->prev; sign = DetermineOrientation(v->v.v(),vi->v.v(),vi_1->v.v()); sign *= v->reserved[0].i; } } S.AppendRight(v); } } else /* adjacent to bottom of stack */ { gul::Assert<gul::InternalError>( ndebug || (e->v[1] == v1) ); if( v->e->IsHorizontal() ) /* special case */ { gul::Assert<gul::InternalError>( ndebug || (S.nElems == 2) ); S.Remove(v1); V.Append(v1); S.AppendRight(v); } else { v2 = v1->next; do { tri = new triangle(); if( v2->reserved[0].i == +1 ) { tri->v[0] = v->v; tri->code0 = v->reserved[1].i; tri->v[1] = v2->v; tri->code1 = v2->reserved[1].i; tri->v[2] = v1->v; tri->code2 = v1->reserved[1].i; /* cout << "TRIANGLE\n"; Dump<float>::dump_vertice(v); Dump<float>::dump_vertice(v2); Dump<float>::dump_vertice(v1); */ } else { tri->v[0] = v->v; tri->code0 = v->reserved[1].i; tri->v[1] = v1->v; tri->code1 = v1->reserved[1].i; tri->v[2] = v2->v; tri->code2 = v2->reserved[1].i; /* cout << "TRIANGLE\n"; Dump<float>::dump_vertice(v); Dump<float>::dump_vertice(v1); Dump<float>::dump_vertice(v2); */ } T->Append(tri); S.Remove(v1); V.Append(v1); v1 = v2; v2 = v1->next; } while( v2 != NULL ); S.AppendRight(v); } } v = Vq.First(); Vq.Remove(v); } /* last vertex */ v1 = S.First(); do { v2 = v1->next; tri = new triangle(); if( (int)v2->reserved[0].i == +1 ) { tri->v[0] = v->v; tri->code0 = v->reserved[1].i; tri->v[1] = v2->v; tri->code1 = v2->reserved[1].i; tri->v[2] = v1->v; tri->code2 = v1->reserved[1].i; /* cout << "TRIANGLE\n"; Dump<float>::dump_vertice(v); Dump<float>::dump_vertice(v2); Dump<float>::dump_vertice(v1); */ } else { tri->v[0] = v->v; tri->code0 = v->reserved[1].i; tri->v[1] = v1->v; tri->code1 = v1->reserved[1].i; tri->v[2] = v2->v; tri->code2 = v2->reserved[1].i; /* cout << "TRIANGLE\n"; Dump<float>::dump_vertice(v); Dump<float>::dump_vertice(v1); Dump<float>::dump_vertice(v2); */ } T->Append(tri); S.Remove(v1); V.Append(v1); v1 = v2; v2 = v1->next; } while( v2 != NULL ); S.Remove(v1); V.Append(v1); delete v; gul::Assert<gul::InternalError>( ndebug || ((S.nElems == 0) && (Vq.nElems == 0) && (V1->nElems == 0) && (V2->nElems == 0)) ); // S.DeleteElems(); // Vq.DeleteElems(); // V1->DeleteElems(); // V2->DeleteElems(); V.DeleteElems(); E->DeleteElems(); }

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 )

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 )

Definition at line 451 of file gugr_face.cpp. { T minx,maxx,miny,maxy; T dx,dy,scale,scalei; ListNode< gugr::polyline > *pn,*inc; ListNode< gul::polyline< point<T> > > *inF,*inN,*inT; List< ListNode< gul::polyline< point2<T> > > > C2; ListNode< gul::polyline< point2<T> > > *c2; List< ListNode<polyline> > Pl; List< ListNode<segment> > segs,outsegs; ListNode<segment> *seg; graph_edge_list E; graph_vertex_list V; rational far_minx,far_maxx,far_miny,far_maxy; unsigned long *cbuf = (unsigned long *)alloca(gul::rtr<T>::mantissa_length()); int nv,i,nt; Ptr< point<T> > &sumF = F, &sumN = N, &sumT = Tx; Ptr<T> sumW; graph_vertex *vn; graph_edge *e; ListNode<graph_edge *> *en; Interval iu,iv; T u,v,u1,u2,v1,v2,su,sv,alpha,w,wi,giant; point<T> fB,nB,fE,nE,tB,tE,f,n,t; bool end; triangle_list tri; triangle *tr; if( C3.nElems == 0 ) return; giant = gul::rtr<T>::giant(); Polygon3dTo2d( C3, Ti, C2 ); c2 = C2.First(); CalcBoundingBoxE( c2->el.n, c2->el.P, minx, maxx, miny, maxy ); c2 = c2->next; while( c2 ) { UpdateBoundingBoxE( c2->el.n, c2->el.P, minx, maxx, miny, maxy ); c2 = c2->next; } dx = maxx - minx; dy = maxy - miny; scale = dx > dy ? dx : dy; minx -= scale; miny -= scale; scalei = (T)1.0/scale; c2 = C2.First(); while( c2 ) { pn = new ListNode<gugr::polyline>(); Pl.Append( pn ); pn->el.init( c2->el.n, c2->el.P, minx, miny, scalei ); c2 = c2->next; } inc = Pl.First(); inF = C3.First(); inN = N3.First(); inT = T3.First(); while( inc ) { AppendContourFNT( &inc->el, inF->el.P, inN->el.P, inT->el.P, 0, 0, segs ); inc = inc->next; inF = inF->next; inN = inN->next; inT = inT->next; } IntersectSegments( segs, &E, &V, true ); far_miny = far_minx = rational( guar::ULong(0x100000), -1 ); far_maxy = far_maxx = rational( coord2int((T)2,cbuf),cbuf) + rational( guar::ULong(0x100000) ); RemoveUnnecessaryEdges( E, V, far_maxx, far_maxy, 1, 0, outsegs ); ISDeleteBackpointers(E); // the backpointers were used to remove edge entries // from 'segs' in 'RemoveUnnecessaryEdges' outsegs.DeleteElems(); // if the contours intersect each other 3d points and normals must be // calculated at the intersections nv = V.nElems; D.reserve_pool(nv); sumF.reserve_pool(nv); sumN.reserve_pool(nv); sumT.reserve_pool(nv); sumW.reserve_pool(nv); i = 0; vn = V.First(); while( vn ) { vn->v.m_rep->reserved.i = i; // enumber vertices iu = vn->v.v().x.get_bounds(); iv = vn->v.v().y.get_bounds(); u = (T)((iu.m_low+iu.m_high)/2.0); v = (T)((iv.m_low+iv.m_high)/2.0); u = gugr::cnv2coord(u)*scale + minx; v = gugr::cnv2coord(v)*scale + miny; D[i].x = u; D[i].y = v; set( sumF[i], (T)0 ); set( sumN[i], (T)0 ); sumW[i] = (T)0; i++; vn = vn->next; } for( seg = segs.First(); seg != 0; seg = seg->next ) { // get function value and normal of start and end point of segment fB = *((seg_point_info< point<T> > *)seg->el.reserved[0])->f; nB = *((seg_point_info< point<T> > *)seg->el.reserved[0])->n; tB = *((seg_point_info< point<T> > *)seg->el.reserved[0])->t; fE = *((seg_point_info< point<T> > *)seg->el.reserved[1])->f; nE = *((seg_point_info< point<T> > *)seg->el.reserved[1])->n; tE = *((seg_point_info< point<T> > *)seg->el.reserved[1])->t; // get u,v of segment start point iu = seg->el.E.x.get_bounds(); iv = seg->el.E.y.get_bounds(); u = (T)((iu.m_low+iu.m_high)/2.0); v = (T)((iv.m_low+iv.m_high)/2.0); u2 = cnv2coord(u)*scale + minx; v2 = cnv2coord(v)*scale + miny; // get u,v of segment end point iu = seg->el.B.x.get_bounds(); iv = seg->el.B.y.get_bounds(); u = (T)((iu.m_low+iu.m_high)/2.0); v = (T)((iv.m_low+iv.m_high)/2.0); u1 = cnv2coord(u)*scale + minx; v1 = cnv2coord(v)*scale + miny; su = u2 - u1; sv = v2 - v1; // travert edges on this segment en = seg->el.e.First(); if( !en ) continue; e = en->el; if( e->l.IsHorizontal() || (e->l.dx().test() < 0) ) end = 0; else end = 1; for( ; en != 0; en = en->next ) { e = en->el; /* ---- first point of edge --------------------------- */ vn = e->v[!end]; i = vn->v.m_rep->reserved.i; u = D[i].x - u1; v = D[i].y - v1; if( su > sv ) alpha = u/su; else if( sv > (T)0 ) alpha = v/sv; else alpha = (T)0; if( (alpha == (T)0) || (alpha >= (T)1) ) { wi = giant; } else { if( alpha > (T)0.5 ) { u = u2 - D[i].x; v = v2 - D[i].y; } w = u*u + v*v; if( w > (T)0 ) wi = (T)1.0/w; else wi = giant; } f = ((T)1.0-alpha)*fB + alpha*fE; n = ((T)1.0-alpha)*nB + alpha*nE; t = ((T)1.0-alpha)*tB + alpha*tE; if( wi >= giant ) { if( sumW[i] >= (T)0 ) { sumW[i] = (T)-1.0; sumF[i] = -f; sumN[i] = -n; sumT[i] = -t; } else { sumW[i] -= (T)1.0; sumF[i] -= f; sumN[i] -= n; sumT[i] -= t; } } else { sumW[i] += wi; sumF[i] += wi*f; sumN[i] += wi*n; sumT[i] += wi*t; } /* ---- second point of edge --------------------------- */ if( en->next && (en->next->el->v[!end] == e->v[end]) ) continue; // will be processed with next edge vn = e->v[end]; i = vn->v.m_rep->reserved.i; u = D[i].x - u1; v = D[i].y - v1; if( su > sv ) alpha = u/su; else if( sv > (T)0 ) alpha = v/sv; else alpha = (T)0; if( (alpha == (T)0) || (alpha >= (T)1) ) { wi = giant; } else { if( alpha > (T)0.5 ) { u = u2 - D[i].x; v = v2 - D[i].y; } w = u*u + v*v; if( w > (T)0 ) wi = (T)1.0/w; else wi = giant; } f = ((T)1.0-alpha)*fB + alpha*fE; n = ((T)1.0-alpha)*nB + alpha*nE; t = ((T)1.0-alpha)*tB + alpha*tE; if( wi >= giant ) { if( sumW[i] >= (T)0 ) { sumW[i] = (T)-1; sumF[i] = -f; sumN[i] = -n; sumT[i] = -t; } else { sumW[i] -= (T)1; sumF[i] -= f; sumN[i] -= n; sumT[i] -= t; } } else { sumW[i] += wi; sumF[i] += wi*f; sumN[i] += wi*n; sumT[i] += wi*t; } } } for( i = 0; i < nv; i++ ) { wi = (T)1/sumW[i]; sumF[i] *= wi; sumN[i] *= wi; sumT[i] *= wi; } // delete not needed data segs.DeleteElems(); /* ---- finally, triangulate the graph ------------------- */ Regularize( &E, &V ); Triangulate( &E, &V, far_minx, &tri ); nt = tri.nElems; Tri.reserve_pool(nt); tr = tri.First(); for( i = 0; i < nt; i++ ) { Tri[i].v[0] = tr->v[0].m_rep->reserved.i; Tri[i].v[1] = tr->v[1].m_rep->reserved.i; Tri[i].v[2] = tr->v[2].m_rep->reserved.i; tr = tr->next; } *nTri = nt; }

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 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<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 )  [inline]

Definition at line 106 of file gugr_bool.h. { T minx,miny,scale; rational far_x,far_y; gul::List<gul::ListNode<gugr::polyline> > PA,PB; gul::List<gul::ListNode<gul::polyline<gul::point2<rational> > > > PC; ConvertToRationalPolys(fPA,fPB,&minx,&miny,&scale,&far_x,&far_y,PA,PB); DoUnion(PA,PB,far_x,far_y,PC); ConvertToFloatPoly(PC,minx,miny,scale,fPC); }

void UnionSubTree (  contour_node *    C, int    oset, int    OutA, int    OutB, List< ListNode< gul::polyline< point2< rational > > > > &    pl )

Definition at line 362 of file gugr_bool.cpp. { ListNode<gul::polyline<point2<rational> > > *pln; gul::ptr_int_union UA,UB; gul::RefMap<void>::Node cn; bool store; UA.set_i(OutA); UB.set_i(OutB); store = false; if( (oset & (OutA|OutB)) != 0 ) { if( C->hasOwner(UA.p) ) oset ^= OutA; if( C->hasOwner(UB.p) ) oset ^= OutB; if( (oset & (OutA|OutB)) == 0 ) store = true; } else { if( C->hasOwner(UA.p) ) oset ^= OutA; if( C->hasOwner(UB.p) ) oset ^= OutB; if( (oset & (OutA|OutB)) != 0 ) store = true; } if( store ) { pln = new ListNode<gul::polyline<point2<rational> > >(); C->get_polyline_joined( pln->el ); pl.Append(pln); } // travert children cn = C->childs.First(); while( !cn.IsEmpty() ) { UnionSubTree( (contour_node *)cn.key(), oset, OutA, OutB, pl ); cn = C->childs.Successor( cn ); } }

int vcompare_point_to_intersection (  point2< rational > *    C, intersection *    R )

Definition at line 91 of file gugr_planesweep.cpp. { return compare( C->y, R->I.y ); }

---