OverSim
Public Member Functions | Public Attributes | Protected Attributes | List of all members
EdgeList Class Reference

EdgeList class. More...

#include <VastDefs.h>

Public Member Functions

 EdgeList ()
 Standard constructor.
void initialize (int sqrt_nsites, double xmin, double deltax, Site *bottomsite)
 Initializes the list before building the diagram.
void reset ()
 Resets the list for further use.
Halfedge * HEcreate (Edge *e, int pm)
 Creates a halfedge from a given edge.
void ELinsert (Halfedge *lb, Halfedge *new_he)
 Inserts a new halfedge to the list.
Halfedge * ELgethash (int b)
 Get an entry from the list by number.
Halfedge * ELleftbnd (Vector2D *p)
 Get an entry from the list by point.
void ELdelete (Halfedge *he)
 Delete an entry from the list.
Halfedge * ELright (Halfedge *he)
 Get right neighbor of an edge.
Halfedge * ELleft (Halfedge *he)
 Get left neighbor of an edge.
Site * leftreg (Halfedge *he)
 Get site left of an edge.
Site * rightreg (Halfedge *he)
 Get site right of an edge.
int right_of (Halfedge *el, Vector2D *p)
 Determines if a point is right of an halfedge.

Public Attributes

Halfedge * ELleftend
Halfedge * ELrightend

Protected Attributes

int ELhashsize
int totalsearch
int ntry
int HEcount
double xmin
double deltax
Halfedge ** ELhash
Halfedge ** HEmemmap
Site * bottomsite

Detailed Description

EdgeList class.

Maintains the edges found while building the voronoi diagram.

Definition at line 153 of file VastDefs.h.

Constructor & Destructor Documentation

EdgeList::EdgeList ( )

Standard constructor.

Definition at line 400 of file VastDefs.cc.

{
ELhash = NULL;
}

Member Function Documentation

void EdgeList::ELdelete ( Halfedge *  he)

Delete an entry from the list.

@param he Halfedge to be removed.

Definition at line 550 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
(he->ELleft)->ELright = he->ELright;
(he->ELright)->ELleft = he->ELleft;
he->ELedge = (Edge*)DELETED;
}
Halfedge * EdgeList::ELgethash ( int  b)

Get an entry from the list by number.

@param b An integer. @return Returns halfedge number b.

Definition at line 462 of file VastDefs.cc.

Referenced by ELleftbnd().

{
Halfedge *he;
if(b < 0 || b >= ELhashsize) return NULL;
he = ELhash[b];
if(he == NULL || he->ELedge != (Edge*)DELETED) return he;
/* Hash table points to deleted half edge. */
ELhash[b] = NULL;
return NULL;
}
void EdgeList::ELinsert ( Halfedge *  lb,
Halfedge *  new_he 
)

Inserts a new halfedge to the list.

@param lb lower bound for this edge. @param new_he A new halfedge to be added to the list.

Definition at line 453 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
new_he->ELleft = lb;
new_he->ELright = lb->ELright;
(lb->ELright)->ELleft = new_he;
lb->ELright = new_he;
}
Halfedge * EdgeList::ELleft ( Halfedge *  he)

Get left neighbor of an edge.

@param he A halfedge. @return Returns left neighbor of halfedge he.

Definition at line 562 of file VastDefs.cc.

Referenced by Vast::buildVoronoi(), and ELinsert().

{
return he->ELleft;
}
Halfedge * EdgeList::ELleftbnd ( Vector2D *  p)

Get an entry from the list by point.

@param p A pointer to a point. @return Returns halfedge nearest to p.

Definition at line 518 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
int i, bucket;
Halfedge *he;
/* Use hash table to get close to desired halfedge */
bucket = (int)((p->x - xmin) / deltax) * ELhashsize;
if(bucket < 0) bucket =0;
if(bucket >= ELhashsize) bucket = ELhashsize - 1;
he = ELgethash(bucket);
if(he == NULL) {
for(i=1; 1; i++) {
if((he = ELgethash(bucket-i)) != NULL) break;
if((he = ELgethash(bucket+i)) != NULL) break;
}
totalsearch++;
}
ntry++;
/* Now search linear list of halfedges for the corect one */
if(he == ELleftend || (he != ELrightend && right_of(he, p))) {
do {he = he->ELright;} while(he != ELrightend && right_of(he, p));
he = he->ELleft;
}
else do {he = he->ELleft;} while(he != ELleftend && !right_of(he, p));
/* Update hash table and reference counts */
if(bucket > 0 && bucket < ELhashsize-1) {
ELhash[bucket] = he;
}
return he;
}
Halfedge * EdgeList::ELright ( Halfedge *  he)

Get right neighbor of an edge.

@param he A halfedge. @return Returns right neighbor of halfedge he.

Definition at line 557 of file VastDefs.cc.

Referenced by Vast::buildVoronoi(), and ELdelete().

{
return he->ELright;
}
Halfedge * EdgeList::HEcreate ( Edge *  e,
int  pm 
)

Creates a halfedge from a given edge.

@param e A pointer to an edge. @param pm Determins wether the halfedge represents the left or right "side" of the given edge (le/re). @return Returns the created halfedge.

Definition at line 437 of file VastDefs.cc.

Referenced by Vast::buildVoronoi(), and initialize().

{
Halfedge *answer = new Halfedge;
answer->ELedge = e;
answer->ELpm = pm;
HEmemmap[HEcount++] = answer;
if(HEcount%ELhashsize == 0) {
Halfedge **Temp = new Halfedge*[HEcount + ELhashsize];
for(int i=0; i<HEcount; i++) Temp[i] = HEmemmap[i];
delete[] HEmemmap;
HEmemmap = Temp;
}
return answer;
}
void EdgeList::initialize ( int  sqrt_nsites,
double  xmin,
double  deltax,
Site *  bottomsite 
)

Initializes the list before building the diagram.

@param sqrt_nsites Squareroot of the total number of sites. @param xmin Min x coordinate of all sites. @param deltax xmin+deltax is max x coordinate of all sites. @param bottomsite A pointer to the bottom site of the sites list.

Definition at line 405 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
int i;
HEcount = 0;
ELhashsize = 2 * sqrt_nsites;
HEmemmap = new Halfedge*[ELhashsize];
ELhash = new Halfedge*[ELhashsize];
for(i=0; i<ELhashsize; i++) ELhash[i] = NULL;
ELleftend = HEcreate(NULL, 0);
ELrightend = HEcreate(NULL, 0);
ELleftend->ELleft = NULL;
ELleftend->ELright = ELrightend;
ELrightend->ELleft = ELleftend;
ELrightend->ELright = NULL;
ELhash[0] = ELleftend;
ELhash[ELhashsize-1] = ELrightend;
this->xmin = xmin;
this->deltax = deltax;
this->bottomsite = bottomsite;
}
Site * EdgeList::leftreg ( Halfedge *  he)

Get site left of an edge.

@param he A halfedge. @return Returns site left of halfedge he.

Definition at line 568 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
if(he->ELedge == NULL) return(bottomsite);
return he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re];
}
void EdgeList::reset ( )

Resets the list for further use.

Definition at line 429 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
delete[] ELhash;
// free all allocated memory
for(int i=0; i<HEcount; i++) delete HEmemmap[i];
delete[] HEmemmap;
}
int EdgeList::right_of ( Halfedge *  el,
Vector2D *  p 
)

Determines if a point is right of an halfedge.

@param he A halfedge. @param p A point. @return Returns 1 if point p is right of halfedge el, 0 otherwise.

Definition at line 476 of file VastDefs.cc.

Referenced by ELleftbnd().

{
Edge *e;
Site *topsite;
int right_of_site, above, fast;
double dxp, dyp, dxs, t1, t2, t3, yl;
e = el->ELedge;
topsite = e->reg[1];
right_of_site = p->x > topsite->coord.x;
if(right_of_site && el->ELpm == le) return 1;
if(!right_of_site && el->ELpm == re) return 0;
if(e->a == 1.0) {
dyp = p->y - topsite->coord.y;
dxp = p->x - topsite->coord.x;
fast = 0;
if((!right_of_site && (e->b < 0.0)) || (right_of_site && (e->b >= 0.0))) {
above = dyp >= e->b * dxp;
fast = above;
}
else {
above = p->x + p->y * e->b > e->c;
if(e->b < 0.0) above = !above;
if(!above) fast = 1;
}
if(!fast) {
dxs = topsite->coord.x - (e->reg[0])->coord.x;
above = e->b * (dxp*dxp - dyp*dyp) < dxs * dyp * (1.0 + 2.0*dxp/dxs + e->b*e->b);
if(e->b < 0.0) above = !above;
}
}
else {
yl = e->c - e->a * p->x;
t1 = p->y - yl;
t2 = p->x - topsite->coord.x;
t3 = yl - topsite->coord.y;
above = t1*t1 > t2*t2 + t3*t3;
}
return el->ELpm == le ? above : !above;
}
Site * EdgeList::rightreg ( Halfedge *  he)

Get site right of an edge.

@param he A halfedge. @return Returns site right of halfedge he.

Definition at line 574 of file VastDefs.cc.

Referenced by Vast::buildVoronoi().

{
if(he->ELedge == NULL) return(bottomsite);
return he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le];
}

Member Data Documentation

Site* EdgeList::bottomsite
protected

Definition at line 237 of file VastDefs.h.

Referenced by initialize(), leftreg(), and rightreg().

double EdgeList::deltax
protected

Definition at line 234 of file VastDefs.h.

Referenced by ELleftbnd(), and initialize().

Halfedge** EdgeList::ELhash
protected

Definition at line 235 of file VastDefs.h.

Referenced by EdgeList(), ELgethash(), ELleftbnd(), initialize(), and reset().

int EdgeList::ELhashsize
protected

Definition at line 233 of file VastDefs.h.

Referenced by ELgethash(), ELleftbnd(), HEcreate(), and initialize().

Halfedge* EdgeList::ELleftend

Definition at line 230 of file VastDefs.h.

Referenced by Vast::buildVoronoi(), ELleftbnd(), and initialize().

Halfedge * EdgeList::ELrightend

Definition at line 230 of file VastDefs.h.

Referenced by Vast::buildVoronoi(), ELleftbnd(), and initialize().

int EdgeList::HEcount
protected

Definition at line 233 of file VastDefs.h.

Referenced by HEcreate(), initialize(), and reset().

Halfedge** EdgeList::HEmemmap
protected

Definition at line 236 of file VastDefs.h.

Referenced by HEcreate(), initialize(), and reset().

int EdgeList::ntry
protected

Definition at line 233 of file VastDefs.h.

Referenced by ELleftbnd().

int EdgeList::totalsearch
protected

Definition at line 233 of file VastDefs.h.

Referenced by ELleftbnd().

double EdgeList::xmin
protected

Definition at line 234 of file VastDefs.h.

Referenced by ELleftbnd(), and initialize().

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