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 leftreg(), and rightreg().

double EdgeList::deltax [protected]

Definition at line 234 of file VastDefs.h.

Referenced by ELleftbnd().

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().

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

EdgeList Class Reference

Public Member Functions

Public Attributes

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation