mmx::ssi Namespace Reference

Classes

struct dcurve
struct dim_cmp
struct sdpoint_t
struct pdpoint_t
struct sdknode
struct pdknode
struct assoc_t
struct dsearch
struct mark_t
struct lsegment
struct qnode
struct lrnode
struct qsegment
struct sample

Typedefs

typedef Interval< double, 3 > interval
typedef fxv< double, 2 > vector2
typedef fxv< double, 3 > vector3
typedef aabb< double, 3 > aabb3
typedef fxv< double, 4 > vector4
typedef igraph graph_t
typedef vector3 point3
typedef vector2 point2
typedef unsigned short coord_t
typedef short rid_t
typedef std::list< point2 > list2_t
typedef std::list< point3 > list3_t
typedef list2_t::iterator p2ref_t
typedef std::priority_queue
< assoc_t< pdpoint_t >
, std::vector< assoc_t
< pdpoint_t > >, assoc_t
< pdpoint_t >::dist_cmp > pheap_t
typedef std::priority_queue
< assoc_t< sdpoint_t >
, std::vector< assoc_t
< sdpoint_t > >, assoc_t
< sdpoint_t >::dist_cmp > sheap_t
typedef std::set< assoc_t
< pdpoint_t >, assoc_t
< pdpoint_t >::pair_cmp > pset_t
typedef assoc_t< sdpoint_t > sdassc_t
typedef assoc_t< pdpoint_t > pdassc_t
typedef std::pair< pdpoint_t
*, pdpoint_t * > ppair_t
typedef std::list< ppair_t > links_t
typedef std::map< dcurve
*, links_t > curves_links_t
typedef ordered_pair< dcurve * > cpair_t
typedef pset_t::iterator pset_iterator

Functions

void fill_quad_box (vcode_t c, aabb3 &box, const vector3 &p0, const vector3 &p1, const vector3 &p2, const vector3 &p3)
void space2prm (vector2 &pa, vector2 &pb, const vector3 &sa, const vector3 &sb, const vector3 &base, const vector3 &pu, const vector3 &pv)
template<class DP > double distance (DP *pa, DP *pb)
void append (dcurve *a, dcurve *b)
void prepend (dcurve *a, dcurve *b)
void reverse (dcurve *c)
bool empty (dcurve *c)
pdpoint_t * sibble (pdpoint_t *p)
void extremums (sdpoint_t *dst, dcurve *src)
void extremums (pdpoint_t *dst, dcurve *c)
dcurve * curve (pdpoint_t *p)
dcurve * curve (sdpoint_t *p)
bool isfirst (sdpoint_t *p)
bool islast (sdpoint_t *p)
bool isfirst (pdpoint_t *p)
bool islast (pdpoint_t *p)
bool isextrem (pdpoint_t *p)
bool isextrem (sdpoint_t *p)
void link (sdpoint_t *a, sdpoint_t *b)
void link (pdpoint_t *a, pdpoint_t *b)
void swap (dcurve *c)
bool isright (pdpoint_t *p)
template<class DPoint > void _link (DPoint *a, DPoint *b)
sdknode * make (sdpoint_t *first, sdpoint_t *last, const dim_cmp< sdpoint_t > &f)
pdknode * make (pdpoint_t **first, pdpoint_t **last, const dim_cmp< pdpoint_t > &f)
void solve_sheap (sheap_t &h)
void solve_pheap (pheap_t &h)
template<class A , class B > void container_add (A &h, const B &a)
void container_add (pset_t &s, const pdassc_t &a)
cpair_t curves (const pdassc_t &ass)
pdassc_t sibbles (const pdassc_t &ass)
void satisfy_links (curves_links_t::iterator it)
void solve_pset (curves_links_t &links, pset_t &s)
std::list< dcurve * > * reduce2 (std::vector< dcurve * > *conflicts)
void build_sheap (sheap_t &h, sdpoint_t *first, sdpoint_t *last, double prec)
template<class C , class V > std::ostream & operator<< (std::ostream &o, const qnode< C, V > &)
template<class C , class V > coord_t du (const qnode< C, V > *q)
template<class C , class V > coord_t dv (const qnode< C, V > *q)
template<class C , class V > coord_t umin (const qnode< C, V > *q)
template<class C , class V > coord_t umax (const qnode< C, V > *q)
template<class C , class V > coord_t vmin (const qnode< C, V > *q)
template<class C , class V > coord_t vmax (const qnode< C, V > *q)
template<class C , class V > bool leaf (qnode< C, V > const *const q)
template<class C , class V > bool unit (const qnode< C, V > *q)
template<class C , class V > bool inside (coord_t u, coord_t v, qnode< C, V > *q)
template<class C , class V > qnode< C, V > * search (coord_t u, coord_t v, qnode< C, V > *start)
template<class C , class V > qnode< C, V > * up (qnode< C, V > *q)
template<class C , class V > qnode< C, V > * down (qnode< C, V > *q)
template<class C , class V > qnode< C, V > * left (qnode< C, V > *q)
template<class C , class V > qnode< C, V > * right (qnode< C, V > *q)
void shiftm (vector3 *v, unsigned sz, const aabb3 &box)
void scale (vector3 *p, double s)
template<class C , class V > std::ostream & operator<< (std::ostream &o, const lrnode< C, V > &l)
template<class C , class V > void print (std::ostream &o, typename qsegment< C, V >::qtree q)
template<class Container > void search (Container &c, sdpoint_t *first, sdpoint_t *last, double epsilonn)
template<class Container > void search (Container &c, pdpoint_t *first, pdpoint_t *last, double epsilonn)
template<class Container > void search (Container &c, sdknode *curr, sdpoint_t *const query, unsigned dim, double eps)
template<class Container > void search (Container &c, pdknode *curr, pdpoint_t *const query, unsigned dim, double eps)
void build_pheap (pheap_t &h, pdpoint_t *first, pdpoint_t *last, double prec)
void build_pset (pset_t &s, pdpoint_t *first, pdpoint_t *last, double prec)

Variables

static const int up_triangle_ [] = { 0, 1, 3 }
static const int dw_triangle_ [] = { 2, 3, 1 }

Typedef Documentation

typedef aabb<double,3> aabb3

Definition at line 51 of file ssi_def.hpp.

typedef unsigned short coord_t

Definition at line 56 of file ssi_def.hpp.

typedef ordered_pair<dcurve*> cpair_t

Definition at line 264 of file ssi_dsearch.hpp.

typedef std::map< dcurve*, links_t > curves_links_t

Definition at line 263 of file ssi_dsearch.hpp.

typedef igraph graph_t

Definition at line 53 of file ssi_def.hpp.

typedef Interval<double,3> interval

Definition at line 48 of file ssi_def.hpp.

typedef std::list< ppair_t > links_t

Definition at line 262 of file ssi_dsearch.hpp.

typedef std::list< point2 > list2_t

Definition at line 84 of file ssi_dsearch.hpp.

typedef std::list< point3 > list3_t

Definition at line 85 of file ssi_dsearch.hpp.

typedef list2_t::iterator p2ref_t

Definition at line 86 of file ssi_dsearch.hpp.

typedef assoc_t<pdpoint_t> pdassc_t

Definition at line 256 of file ssi_dsearch.hpp.

typedef std::priority_queue< assoc_t<pdpoint_t>,std::vector< assoc_t<pdpoint_t> >,assoc_t< pdpoint_t>::dist_cmp > pheap_t

Definition at line 248 of file ssi_dsearch.hpp.

typedef vector2 point2

Definition at line 55 of file ssi_def.hpp.

typedef vector3 point3

Definition at line 54 of file ssi_def.hpp.

typedef std::pair<pdpoint_t*,pdpoint_t*> ppair_t

Definition at line 261 of file ssi_dsearch.hpp.

typedef pset_t::iterator pset_iterator

Definition at line 283 of file ssi_dsearch.hpp.

typedef std::set< assoc_t< pdpoint_t > , assoc_t<pdpoint_t>::pair_cmp > pset_t

Definition at line 253 of file ssi_dsearch.hpp.

typedef short rid_t

Definition at line 57 of file ssi_def.hpp.

typedef assoc_t<sdpoint_t> sdassc_t

Definition at line 255 of file ssi_dsearch.hpp.

typedef std::priority_queue< assoc_t<sdpoint_t>,std::vector< assoc_t<sdpoint_t> >,assoc_t< sdpoint_t>::dist_cmp > sheap_t

Definition at line 251 of file ssi_dsearch.hpp.

typedef fxv<double,2> vector2

Definition at line 49 of file ssi_def.hpp.

typedef fxv<double,3> vector3

Definition at line 50 of file ssi_def.hpp.

typedef fxv<double,4> vector4

Definition at line 52 of file ssi_def.hpp.

Function Documentation

void mmx::ssi::_link	(	DPoint *	a,
		DPoint *	b
	)			`[inline]`

Definition at line 206 of file ssi_dsearch.hpp.

References append(), curve(), isfirst(), islast(), prepend(), and reverse().

Referenced by link().

00207 {
00208     if ( islast(a)   )
00209     {
00210         if( islast(b) )
00211             reverse(curve(b));
00212         // last a + first b
00213         append(curve(a),curve(b));
00214     }
00215     else
00216     {
00217         if ( isfirst(b) )
00218             reverse(curve(b));
00219         // last b + first a
00220         prepend(curve(a),curve(b));
00221     };
00222 };

void append	(	dcurve *	a,
		dcurve *	b
	)

Definition at line 68 of file ssi_dsearch_dcurve.cpp.

References dcurve::inter, dcurve::left, dcurve::owner, dcurve::right, and dcurve::size.

Referenced by _link().

00069   { 
00070     a->left.splice ( a->left.end(),  b->left  );
00071     a->right.splice( a->right.end(), b->right );
00072     a->inter.splice( a->inter.end(), b->inter );
00073     b->owner = a; 
00074     a->size += b->size;
00075   };

void mmx::ssi::build_pheap	(	pheap_t &	h,
		pdpoint_t *	first,
		pdpoint_t *	last,
		double	prec
	)

Definition at line 69 of file ssi_dsearch_build.cpp.

References search().

00070 {
00071     search(h,first,last,prec);
00072 };

void mmx::ssi::build_pset	(	pset_t &	s,
		pdpoint_t *	first,
		pdpoint_t *	last,
		double	prec
	)

Definition at line 74 of file ssi_dsearch_build.cpp.

References search().

Referenced by reduce2().

00075 {
00076     search(s,first,last,prec);
00077 };

void build_sheap	(	sheap_t &	h,
		sdpoint_t *	first,
		sdpoint_t *	last,
		double	prec
	)

Definition at line 79 of file ssi_dsearch_build.cpp.

References search().

Referenced by dsearch< C, V >::reduce().

00080 {
00081     search(h,first,last,prec);
00082 };

void mmx::ssi::container_add	(	pset_t &	s,
		const pdassc_t &	a
	)			`[inline]`

Definition at line 268 of file ssi_dsearch.hpp.

00268 { s.insert(a); };

void mmx::ssi::container_add	(	A &	h,
		const B &	a
	)			`[inline]`

Definition at line 267 of file ssi_dsearch.hpp.

Referenced by search().

00267 { h.push(a); };

dcurve * curve ( sdpoint_t * p )

Definition at line 38 of file ssi_dsearch_dcurve.cpp.

References sdpoint_t::curve, and dcurve::owner.

00039   { 
00040     dcurve *  tmp      = p->curve;
00041     while( tmp->owner != tmp ) tmp = tmp->owner;
00042     p->curve->owner   = tmp;
00043     //      p->curve = tmp;
00044     return tmp;
00045   };

dcurve * curve ( pdpoint_t * p )

Definition at line 29 of file ssi_dsearch_dcurve.cpp.

References pdpoint_t::curve, and dcurve::owner.

Referenced by _link(), curves(), isfirst(), islast(), isright(), link(), satisfy_links(), search(), solve_pheap(), solve_pset(), and solve_sheap().

00030   { 
00031     dcurve * tmp      = p->curve;
00032     while( tmp->owner != tmp ) tmp = tmp->owner;
00033     p->curve->owner   = tmp;
00034     //      p->curve = tmp;
00035     return tmp;
00036   };

cpair_t mmx::ssi::curves ( const pdassc_t & ass ) [inline]

Definition at line 269 of file ssi_dsearch.hpp.

References curve(), and assoc_t< DPoint >::pp.

Referenced by solve_pset().

00269 { return cpair_t(curve(ass.pp.first),curve(ass.pp.second)); };

double mmx::ssi::distance	(	DP *	pa,
		DP *	pb
	)			`[inline]`

Definition at line 109 of file ssi_dsearch.hpp.

Referenced by search().

00110 {
00111     double acc = 0.0;
00112     for ( unsigned i = 0; i < 4; i++ )
00113         acc += ((*pa)[i]-(*pb)[i])*((*pa)[i]-(*pb)[i]);
00114     return acc;
00115 };

qnode<C,V>* mmx::ssi::down ( qnode< C, V > * q ) [inline]

Definition at line 51 of file ssi_qnode.hpp.

References search(), qnode< C, V >::umin, and qnode< C, V >::vmin.

Referenced by lsegment< C, V >::find_regions().

00051 { return search( q->umin - 1, q->vmin, q ); };

coord_t mmx::ssi::du ( const qnode< C, V > * q ) [inline]

Definition at line 33 of file ssi_qnode.hpp.

References qnode< C, V >::umax, and qnode< C, V >::umin.

Referenced by qnode< C, V >::convert(), qnode< C, V >::split(), and unit().

00033 { return q->umax-q->umin; };

coord_t mmx::ssi::dv ( const qnode< C, V > * q ) [inline]

Definition at line 34 of file ssi_qnode.hpp.

References qnode< C, V >::vmax, and qnode< C, V >::vmin.

Referenced by qnode< C, V >::convert(), qnode< C, V >::split(), and unit().

00034 { return q->vmax - q->vmin; };

bool mmx::ssi::empty ( dcurve * c ) [inline]

Definition at line 179 of file ssi_dsearch.hpp.

References dcurve::owner.

Referenced by dsearch< C, V >::reduce(), and reduce2().

00179 { return c->owner != c; };

void extremums	(	pdpoint_t *	dst,
		dcurve *	c
	)

Definition at line 58 of file ssi_dsearch_dcurve.cpp.

References pdpoint_t::a, pdpoint_t::curve, dcurve::left, pdpoint_t::ref, and dcurve::right.

00059   {
00060     dst[0].curve = dst[1].curve = dst[2].curve = dst[3].curve  = c; 
00061     dst[0].a = &(dst[1]);  dst[1].a = &(dst[0]);
00062     dst[0].ref   = c->left.begin(); dst[1].ref   = c->right.begin();
00063     dst[2].a = &(dst[3]);  dst[3].a = &(dst[2]);
00064     dst[2].ref   = --(c->left.end()); dst[3].ref   = --(c->right.end());
00065   };

void extremums	(	sdpoint_t *	dst,
		dcurve *	src
	)

Definition at line 48 of file ssi_dsearch_dcurve.cpp.

References sdpoint_t::curve, sdpoint_t::idl, sdpoint_t::idr, dcurve::left, and dcurve::right.

Referenced by dsearch< C, V >::reduce(), and reduce2().

00049   {
00050     dst[0].curve = src;
00051     dst[0].idl   = src->left.begin(); 
00052     dst[0].idr   = src->right.begin();
00053     dst[1].curve = src;
00054     dst[1].idl   = --(src->left.end()); 
00055     dst[1].idr   = --(src->right.end());
00056   };

void mmx::ssi::fill_quad_box	(	vcode_t	c,
		aabb3 &	box,
		const vector3 &	p0,
		const vector3 &	p1,
		const vector3 &	p2,
		const vector3 &	p3
	)			`[inline]`

Definition at line 63 of file ssi_def.hpp.

References fill().

00065                                                                        { fill(box,p0,p1,p2,p3); };

bool mmx::ssi::inside	(	coord_t	u,
		coord_t	v,
		qnode< C, V > *	q
	)			`[inline]`

Definition at line 41 of file ssi_qnode.hpp.

References qnode< C, V >::umax, qnode< C, V >::umin, qnode< C, V >::vmax, and qnode< C, V >::vmin.

Referenced by search().

00042   {
00043     if ( q->umin  > u ) return false;
00044     if ( q->umax <= u ) return false;
00045     if ( q->vmin  > v ) return false;
00046     if ( q->vmax <= v ) return false;
00047     return true;
00048   };

bool mmx::ssi::isextrem ( sdpoint_t * p ) [inline]

Definition at line 194 of file ssi_dsearch.hpp.

References isfirst(), and islast().

00194 { return  isfirst(p) || islast(p); };

bool mmx::ssi::isextrem ( pdpoint_t * p ) [inline]

Definition at line 193 of file ssi_dsearch.hpp.

References isfirst(), and islast().

Referenced by satisfy_links(), solve_pheap(), and solve_sheap().

00193 { return  isfirst(p) || islast(p); };

bool mmx::ssi::isfirst ( pdpoint_t * p ) [inline]

Definition at line 190 of file ssi_dsearch.hpp.

References curve(), dcurve::left, pdpoint_t::ref, and dcurve::right.

00190 { return curve(p)->left.begin() == p->ref || curve(p)->right.begin() == p->ref; };

bool mmx::ssi::isfirst ( sdpoint_t * p ) [inline]

Definition at line 187 of file ssi_dsearch.hpp.

References curve(), sdpoint_t::idl, and dcurve::left.

Referenced by _link(), isextrem(), and satisfy_links().

00187 { return curve(p)->left.begin() == p->idl;     };

bool mmx::ssi::islast ( pdpoint_t * p ) [inline]

Definition at line 191 of file ssi_dsearch.hpp.

References curve(), left(), pdpoint_t::ref, and dcurve::right.

00191 { return (--(curve(p)->left.end())) == p->ref ||(--(curve(p)->right.end())) == p->ref;};

bool mmx::ssi::islast ( sdpoint_t * p ) [inline]

Definition at line 188 of file ssi_dsearch.hpp.

References curve(), sdpoint_t::idl, and left().

Referenced by _link(), isextrem(), and satisfy_links().

00188 { return (--(curve(p)->left.end())) == p->idl; };

bool mmx::ssi::isright ( pdpoint_t * p ) [inline]

Definition at line 201 of file ssi_dsearch.hpp.

References curve(), pdpoint_t::ref, and dcurve::right.

Referenced by link().

00202 { return p->ref == curve(p)->right.begin() || p->ref == --(curve(p)->right.end());};

bool mmx::ssi::leaf ( qnode< C, V > const *const q ) [inline]

Definition at line 39 of file ssi_qnode.hpp.

References qnode< C, V >::l.

Referenced by search(), dsearch< C, V >::search(), dsearch< C, V >::search_f(), and dsearch< C, V >::search_s().

00039 { return (q->l == 0); };

qnode<C,V>* mmx::ssi::left ( qnode< C, V > * q ) [inline]

Definition at line 52 of file ssi_qnode.hpp.

References search(), qnode< C, V >::umin, and qnode< C, V >::vmin.

Referenced by islast(), voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), search(), semialgebraic2d< C, V >::subdivide(), mesher3d_shape< C, V >::subdivide(), mesher3d_algebraic_curve< C, V >::subdivide(), mesher2d< C, V >::subdivide(), cell3d_algebraic_surface< C, V >::subdivide(), bcell3d_algebraic_surface< C, V >::subdivide(), bcell3d_algebraic_curve< C, V >::subdivide(), arrangement2d< C, V >::subdivide(), and use< subdivision_def, C, default_env >::subdivide_node().

00052 { return search( q->umin, q->vmin - 1, q ); };

void link	(	pdpoint_t *	a,
		pdpoint_t *	b
	)

Definition at line 91 of file ssi_dsearch_dcurve.cpp.

References _link(), curve(), isright(), and swap().

00092   {
00093     if ( isright(a) ) swap(curve(a));
00094     if ( isright(b) ) swap(curve(b));
00095     _link(a,b);
00096   };

void link	(	sdpoint_t *	a,
		sdpoint_t *	b
	)

Definition at line 89 of file ssi_dsearch_dcurve.cpp.

References _link().

Referenced by satisfy_links(), solve_pheap(), and solve_sheap().

00089 { _link(a,b); };

pdknode * make	(	pdpoint_t **	first,
		pdpoint_t **	last,
		const dim_cmp< pdpoint_t > &	f
	)

Definition at line 129 of file ssi_dsearch_build.cpp.

References make(), and dim_cmp< DPoint >::next().

00130 {     
00131     if ( last-first >= 1 ) {
00132         if ( last-first > 1 ) {
00133             unsigned m = (last-first)>>1;
00134             std::nth_element(first, first+m,last,f);
00135             return new pdknode( *(first+m),
00136                                 make( first, first + m, f.next()),
00137                                 make( first+m+1, last,  f.next()) ); }
00138         else { return new pdknode(*first,0,0); };};
00139     return 0;
00140 };

sdknode * make	(	sdpoint_t *	first,
		sdpoint_t *	last,
		const dim_cmp< sdpoint_t > &	f
	)

Definition at line 116 of file ssi_dsearch_build.cpp.

References dim_cmp< DPoint >::next().

Referenced by make(), and search().

00117 {     
00118     if ( last-first >= 1 ) {
00119         if ( last-first > 1 ) {
00120             unsigned m = (last-first)>>1;
00121             std::nth_element(first, first+m,last,f);
00122             return new sdknode( first+m,
00123                                 make( first, first + m, f.next()),
00124                                 make( first+m+1, last,  f.next()) ); }
00125         else { return new sdknode(first,0,0); };};
00126     return 0;
00127 };

std::ostream& mmx::ssi::operator<<	(	std::ostream &	o,
		const lrnode< C, V > &	l
	)			`[inline]`

Definition at line 26 of file ssi_qsegment.hpp.

00027 {
00028   o << l.lmin << " " << l.lmax << " " << l.rmin << " " << l.rmax << std::endl;
00029   return o;
00030 };

std::ostream & operator<<	(	std::ostream &	o,
		const qnode< C, V > &	q
	)			`[inline]`

Definition at line 56 of file ssi_qnode.hpp.

00057 {
00058   o << "[ " << q.umin << ", " << q.umax << " ] x ";
00059   o << "[ " << q.vmin << ", " << q.vmax << " ]";
00060   return o;
00061 };

void prepend	(	dcurve *	a,
		dcurve *	b
	)

Definition at line 77 of file ssi_dsearch_dcurve.cpp.

References dcurve::inter, dcurve::left, dcurve::owner, dcurve::right, and dcurve::size.

Referenced by _link().

00078   { 
00079     a->left.splice( a->left.begin(), b->left );  
00080     a->right.splice( a->right.begin(), b->right );
00081     a->inter.splice( a->inter.begin(), b->inter );
00082     b->owner = a; 
00083     a->size += b->size;
00084   };

void mmx::ssi::print	(	std::ostream &	o,
		typename qsegment< C, V >::qtree	q
	)			`[inline]`

Definition at line 147 of file ssi_qsegment.hpp.

References qnode< C, V >::l, and qnode< C, V >::r.

00148 {
00149     o << *q << std::endl;
00150     if ( q->r) print( o, q->r );
00151     if ( q->l ) print( o, q->l );
00152 };

std::list< dcurve * > * reduce2 ( std::vector< dcurve * > * conflicts )

Definition at line 172 of file ssi_dsearch_build.cpp.

References build_pset(), empty(), extremums(), satisfy_links(), and solve_pset().

Referenced by dsearch< C, V >::dsearch().

00174 00175 00176 00177 00178 00179 00180     { 00181 00182 00183     }; 00184 00185 00186 00187 00188 00189 00190 00191 00192 00193 00194 00195 00196 00197 00198 00199 00200 00201     { 00202 00203 00204     }; 00205 00206 00207 };

class="fragment">00173 { if ( conflicts->size() == 0 ) return 0; unsigned i; unsigned endsize = 4*conflicts->size(); pdpoint_t * ends = new pdpoint_t[endsize]; unsigned c = 0; for ( i = 0; i < conflicts->size(); i++ ) extremums( ends + c, (*conflicts)[i] ); c+= 4; pset_t s; build_pset(s,ends, ends + endsize, 0.01 ); curves_links_t links; solve_pset(links,s); for ( curves_links_t::iterator it = links.begin(); it != links.end(); it++ ) satisfy_links( it ); delete[] ends; std::list< dcurve* > * result = new std::list< dcurve * >(); for ( i = 0; i < conflicts->size() ; i++ ) if ( empty((*conflicts)[i]) ) delete (*conflicts)[i]; else result->push_front( (*conflicts)[i] ); return result;

void reverse ( dcurve * c )

Definition at line 86 of file ssi_dsearch_dcurve.cpp.

References dcurve::inter, dcurve::left, and dcurve::right.

Referenced by _link().

00087   { c->left.reverse(); c->right.reverse(); c->inter.reverse(); };

qnode<C,V>* mmx::ssi::right ( qnode< C, V > * q ) [inline]

Definition at line 53 of file ssi_qnode.hpp.

References search(), qnode< C, V >::umin, and qnode< C, V >::vmin.

Referenced by lrnode< C, V >::make(), voronoi2dimpl< C, V >::run(), voronoi2d< C, V >::run(), search(), semialgebraic2d< C, V >::subdivide(), mesher3d_shape< C, V >::subdivide(), mesher3d_algebraic_curve< C, V >::subdivide(), mesher2d< C, V >::subdivide(), cell3d_algebraic_surface< C, V >::subdivide(), bcell3d_algebraic_surface< C, V >::subdivide(), bcell3d_algebraic_curve< C, V >::subdivide(), arrangement2d< C, V >::subdivide(), and use< subdivision_def, C, default_env >::subdivide_node().

00053 { return search( q->umin, q->vmin + 1, q );  };

void satisfy_links ( curves_links_t::iterator it )

Definition at line 98 of file ssi_dsearch_dcurve.cpp.

References curve(), isextrem(), isfirst(), islast(), and link().

Referenced by reduce2().

00099   {
00100       std::list< ppair_t > * l = &(it->second);
00101       std::vector< ppair_t > starts;
00102       std::vector< ppair_t > ends;
00103       
00104        starts.reserve(10);
00105        ends.reserve(10);
00106    
00107        for (  std::list< ppair_t >::iterator p = l->begin(); 
00108              p != l->end(); p ++ )
00109          {
00110            if ( isfirst(p->first) ) starts.push_back( *p );
00111            else if ( islast(p->first) ) ends.push_back( *p );
00112          };
00113       
00114        if ( starts.size() == 1 )
00115          {
00116            if ( isextrem( starts[0].first ) && isextrem( starts[0].second ) )
00117             if ( curve(starts[0].first) != curve(starts[0].second))
00118               link( starts[0].first, starts[0].second );
00119          };
00120       
00121        if ( ends.size() == 1 )
00122          {
00123            
00124            if ( isextrem( ends[0].first ) && isextrem( ends[0].second ) )
00125              if ( curve(ends[0].first) != curve(ends[0].second) )
00126                link( ends[0].first, ends[0].second );
00127          };
00128     };

void scale	(	vector3 *	p,
		double	s
	)

Definition at line 19 of file ssi_qsegment.cpp.

00019                                      { 
00020     for ( int i = 0; i < 4; i ++ )
00021       for ( int d = 0; d < 3; d ++ )
00022       p[i][d] *= s;
00023   };

void mmx::ssi::search	(	Container &	c,
		pdknode *	curr,
		pdpoint_t *const	query,
		unsigned	dim,
		double	eps
	)			`[inline]`

Definition at line 52 of file ssi_dsearch_build.cpp.

References container_add(), curve(), pdknode::data, distance(), pdknode::l, left(), pdknode::r, right(), and search().

00053 {
00054     if (! curr ) return;
00055 
00056     bool left  = (*query)[dim]-eps<(*(curr->data))[dim];
00057     bool right = (*query)[dim]+eps>(*(curr->data))[dim];
00058     if ( (left && right) && (query<curr->data) && (curve(query) != curve(curr->data)) )
00059     {
00060         double d = distance(curr->data,query);
00061         if ( (d<eps) )
00062             container_add(c,assoc_t<pdpoint_t>(query,curr->data,d));
00063     };
00064     if ( left  ){  search( c, curr->l, query, (dim+1)%4, eps ); };
00065     if ( right ){  search( c, curr->r, query, (dim+1)%4, eps ); };
00066 };

void mmx::ssi::search	(	Container &	c,
		sdknode *	curr,
		sdpoint_t *const	query,
		unsigned	dim,
		double	eps
	)			`[inline]`

Definition at line 34 of file ssi_dsearch_build.cpp.

References container_add(), curve(), sdknode::data, distance(), sdknode::l, left(), sdknode::r, right(), and search().

00035 {
00036     if (! curr ) return;
00037 
00038     bool left  = (*query)[dim]-eps<(*(curr->data))[dim];
00039     bool right = (*query)[dim]+eps>(*(curr->data))[dim];
00040 
00041     if ( (left && right) && (query<curr->data) && (curve(query) != curve(curr->data)) )
00042     {
00043         double d = distance(curr->data,query);
00044         if ( (d<eps) )
00045             container_add(c,assoc_t<sdpoint_t>(query,curr->data,d));
00046     };
00047     if ( left  ){  search( c, curr->l, query, (dim+1)%4, eps ); };
00048     if ( right ){  search( c, curr->r, query, (dim+1)%4, eps ); };
00049 };

void mmx::ssi::search	(	Container &	c,
		pdpoint_t *	first,
		pdpoint_t *	last,
		double	epsilonn
	)			`[inline]`

Definition at line 19 of file ssi_dsearch_build.cpp.

References make(), and search().

00020 {
00021     pdknode* root;
00022     pdpoint_t ** tmp = new pdpoint_t*[last-first];
00023     int i;
00024     for ( i = 0; i < last-first; i++ )
00025         tmp[i] = first + i;
00026     root = make(tmp,tmp + (last-first),dim_cmp<pdpoint_t>());
00027     delete[] tmp;
00028     for ( pdpoint_t * p = first; p < last; p++ )
00029         search(c,root,p,0,epsilonn);
00030     delete root;
00031 };

void mmx::ssi::search	(	Container &	c,
		sdpoint_t *	first,
		sdpoint_t *	last,
		double	epsilonn
	)			`[inline]`

Definition at line 8 of file ssi_dsearch_build.cpp.

References make(), and search().

00009 {
00010     sdknode* root;
00011     root = make(first,last,dim_cmp<sdpoint_t>());
00012     for ( sdpoint_t * p = first; p < last; p++ )
00013         search(c,root,p,0,epsilonn);
00014     delete root;
00015 };

qnode< C, V > * search	(	coord_t	u,
		coord_t	v,
		qnode< C, V > *	start
	)			`[inline]`

Definition at line 155 of file ssi_qnode.hpp.

References qnode< C, V >::father, inside(), qnode< C, V >::l, leaf(), and qnode< C, V >::r.

Referenced by build_pheap(), build_pset(), build_sheap(), down(), left(), right(), search(), and up().

00156 {
00157 qnode<C,V> * tmp = start;
00158 do { tmp=tmp->father; } while(tmp && !inside(u,v,tmp) );
00159 if ( !tmp ) return 0;
00160 while(1){
00161   if ( leaf(tmp) ) return tmp;
00162   if ( inside(u,v,tmp->l) ) { tmp = tmp->l; continue; };
00163   if ( inside(u,v,tmp->r) ) { tmp = tmp->r; continue; };
00164   return 0;
00165 };
00166 };

void shiftm	(	vector3 *	v,
		unsigned	sz,
		const aabb3 &	box
	)

Definition at line 11 of file ssi_qsegment.cpp.

00012   {
00013     //    double m,M;
00014     for ( vector3 * src = v; src != v+sz; src ++ )
00015       for ( int i = 0; i < 3; (*src)[i] -= box[i].m, i ++ );
00016   };

pdpoint_t* mmx::ssi::sibble ( pdpoint_t * p ) [inline]

Definition at line 180 of file ssi_dsearch.hpp.

References pdpoint_t::a.

Referenced by sibbles().

00180 { return p->a; };

pdassc_t mmx::ssi::sibbles ( const pdassc_t & ass ) [inline]

Definition at line 270 of file ssi_dsearch.hpp.

References assoc_t< DPoint >::pp, and sibble().

Referenced by solve_pset().

00271 {
00272     pdpoint_t * a = sibble(ass.pp.first);
00273     pdpoint_t * b = sibble(ass.pp.second);
00274     if ( a < b )
00275         return pdassc_t(a,b,0);
00276     else
00277         return pdassc_t(b,a,0);
00278 };

void solve_pheap ( pheap_t & h )

Definition at line 85 of file ssi_dsearch_build.cpp.

References curve(), isextrem(), link(), and assoc_t< DPoint >::pp.

00086 {
00087 
00088     while( !h.empty() )
00089     {
00090         pdassc_t a = h.top();
00091 
00092         if (( isextrem(a.pp.first) && isextrem(a.pp.second) ) &&
00093                 ( curve(a.pp.first) != curve(a.pp.second) ))
00094         {
00095             link(a.pp.first,a.pp.second);
00096         };
00097         h.pop();
00098     };
00099 };

void solve_pset	(	curves_links_t &	links,
		pset_t &	s
	)

Definition at line 143 of file ssi_dsearch_build.cpp.

References curve(), curves(), sibbles(), and swap().

Referenced by reduce2().

00144 {
00145     while ( !s.empty() )
00146     {
00147         pdassc_t ass(sibbles(*(s.begin())));
00148         pset_iterator it;
00149         it = s.find( ass  );
00150         if( it  != s.end() )
00151         {
00152             s.erase(s.find(ass));
00153             cpair_t tmp (curves(*(s.begin())));
00154             ppair_t p = (s.begin())->pp;
00155             if ( curve(p.first) != tmp.first )
00156             {
00157                 links[tmp.second].push_front(p);
00158                 std::swap(p.first,p.second);
00159                 links[tmp.first].push_front(p);
00160             }
00161             else
00162             {
00163                 links[tmp.first].push_front(p);
00164                 std::swap(p.first,p.second);
00165                 links[tmp.second].push_front(p);
00166             };
00167         };
00168         s.erase(s.begin());
00169     };
00170 };

void solve_sheap ( sheap_t & h )

Definition at line 101 of file ssi_dsearch_build.cpp.

References curve(), isextrem(), link(), and assoc_t< DPoint >::pp.

Referenced by dsearch< C, V >::reduce().

00102 {
00103     // dcurve * dummy_curve = new dcurve( point2(), point2(), point2(), point2(),
00104     //                           point3(), point3() );
00105     while( !h.empty() )
00106     {
00107         sdassc_t a = h.top();
00108         //        cout << a.d << endl;
00109         if (( isextrem(a.pp.first) && isextrem(a.pp.second) ) &&
00110                 ( curve(a.pp.first) != curve(a.pp.second) ))
00111             link(a.pp.first,a.pp.second);
00112         h.pop();
00113     };
00114 };

void space2prm	(	vector2 &	pa,
		vector2 &	pb,
		const vector3 &	sa,
		const vector3 &	sb,
		const vector3 &	base,
		const vector3 &	pu,
		const vector3 &	pv
	)

Definition at line 74 of file ssi_dsearch_triangle.cpp.

00081   {
00082   /* T(u,v) = base + u*bu +v*bv
00083      => 
00084      spc[0] - base[0] = delta[0]  = / bu[0] bv[0]\  / u \
00085      spc[1] - base[1] = delta[1]  = | bu[1] bv[1]|  |   |
00086      spc[2] - base[2] = delta[2]  = \ bu[2] bv[2]/  \ v /
00087   */
00088   vector3 bu;
00089   for ( int i = 0; i < 3; i ++ ) bu[i] = pu[i]-base[i];
00090   vector3 bv;
00091   for ( int i = 0; i < 3; i ++ ) bv[i] = pv[i]-base[i];
00092   double muu, mvv, muv;
00093   muu = 0;
00094   for ( int i = 0; i < 3; i ++ ) muu += bu[i]*bu[i];
00095   mvv = 0;
00096   for ( int i = 0; i < 3; i ++ ) mvv += bv[i]*bv[i];
00097   muv = 0; 
00098   for ( int i = 0; i < 3; i ++ ) muv += bu[i]*bv[i];
00099   double detm = muu*mvv - muv*muv;
00100   vector3 delta;
00101   double x, y;
00102   for ( int k = 0; k < 3; k ++ ) delta[k] = sa[k]-base[k];
00103   x = 0;
00104   for ( int k = 0; k < 3; k ++ ) x += bu[k]*delta[k];
00105   y = 0; 
00106   for ( int k = 0; k < 3; k ++ ) y += bv[k]*delta[k];
00107   pa[0] = (mvv * x - muv * y)/detm;
00108   pa[1] = (muu * y - muv * x)/detm;
00109   for ( int k = 0; k < 3; k ++ ) delta[k] = sb[k]-base[k];
00110   x = 0;
00111   for ( int k = 0; k < 3; k ++ ) x += bu[k]*delta[k];
00112   y = 0; 
00113   for ( int k = 0; k < 3; k ++ ) y += bv[k]*delta[k];
00114   pb[0] = (mvv * x - muv * y)/detm;
00115   pb[1] = (muu * y - muv * x)/detm;
00116 };

void mmx::ssi::swap ( dcurve * c ) [inline]

Definition at line 199 of file ssi_dsearch.hpp.

References dcurve::left, and dcurve::right.

Referenced by link(), and solve_pset().

00199 { c->left.swap( c->right ); };

coord_t mmx::ssi::umax ( const qnode< C, V > * q ) [inline]

Definition at line 36 of file ssi_qnode.hpp.

References qnode< C, V >::umax.

Referenced by mmx::shape::as_graphic(), and qsegment< C, V >::qsegment().

00036 { return q->umax; };

coord_t mmx::ssi::umin ( const qnode< C, V > * q ) [inline]

Definition at line 35 of file ssi_qnode.hpp.

References qnode< C, V >::umin.

Referenced by mmx::shape::as_graphic(), and qsegment< C, V >::qsegment().

00035 { return q->umin; };

bool mmx::ssi::unit ( const qnode< C, V > * q ) [inline]

Definition at line 40 of file ssi_qnode.hpp.

References du(), and dv().

00040 { return du(q)==1 && dv(q) == 1; };

qnode<C,V>* mmx::ssi::up ( qnode< C, V > * q ) [inline]

Definition at line 50 of file ssi_qnode.hpp.

References search(), qnode< C, V >::umin, and qnode< C, V >::vmin.

Referenced by solver_implicit< C, V >::common_edge_point(), solver_implicit< C, V >::edge_point(), and lsegment< C, V >::find_regions().

00050 { return search( q->umin + 1, q->vmin, q ); };

coord_t mmx::ssi::vmax ( const qnode< C, V > * q ) [inline]

Definition at line 38 of file ssi_qnode.hpp.

References qnode< C, V >::vmax.

00038 { return q->vmax; };

coord_t mmx::ssi::vmin ( const qnode< C, V > * q ) [inline]

Definition at line 37 of file ssi_qnode.hpp.

References qnode< C, V >::vmin.

00037 { return q->vmin; };

Variable Documentation

const int dw_triangle_[] = { 2, 3, 1 } [static]

Definition at line 11 of file ssi_dsearch_triangle.cpp.

const int up_triangle_[] = { 0, 1, 3 } [static]

Definition at line 10 of file ssi_dsearch_triangle.cpp.