edgelist.c

This is edgelist.c in view mode; [Download] [Up]
#include "voronoi.h"

int ntry, totalsearch;

void ELinitialize()
{
    int i;

    freeinit(&hfl, sizeof **ELhash);
    ELhashsize = 2 * sqrt_nsites;
    ELhash = (struct Halfedge **) myalloc ( sizeof (*ELhash) * ELhashsize);
    for(i=0; i<ELhashsize; i +=1) 
	ELhash[i] = (struct Halfedge *)NULL;
    ELleftend = HEcreate( (struct Edge *)NULL, 0);
    ELrightend = HEcreate( (struct Edge *)NULL, 0);
    ELleftend->ELleft = (struct Halfedge *)NULL;
    ELleftend->ELright = ELrightend;
    ELrightend->ELleft = ELleftend;
    ELrightend->ELright = (struct Halfedge *)NULL;
    ELhash[0] = ELleftend;
    ELhash[ELhashsize-1] = ELrightend;
}

struct Halfedge *HEcreate(e, pm)
struct Edge *e;
int pm;
{
    struct Halfedge *answer;

    answer = (struct Halfedge *) getfree(&hfl);
    answer->ELedge = e;
    answer->ELpm = pm;
    answer->PQnext = (struct Halfedge *) NULL;
    answer->vertex = (struct Site *) NULL;
    answer->ELrefcnt = 0;
    return(answer);
}

ELinsert(lb, new)
struct	Halfedge *lb, *new;
{
    new->ELleft = lb;
    new->ELright = lb->ELright;
    (lb->ELright)->ELleft = new;
    lb->ELright = new;
}

/* Get entry from hash table, pruning any deleted nodes */
struct Halfedge *ELgethash(b)
int b;
{
    struct Halfedge *he;

    if(b<0 || b>=ELhashsize) 
	return((struct Halfedge *) NULL);
    he = ELhash[b]; 
    if (he == (struct Halfedge *)NULL || he->ELedge!=(struct Edge *)DELETED) 
	return (he);

/* Hash table points to deleted half edge.  Patch as necessary. */
    ELhash[b] = (struct Halfedge *) NULL;
    if ((he->ELrefcnt -= 1) == 0) makefree(he, &hfl);
	return ((struct Halfedge *) NULL);
}	

struct Halfedge *ELleftbnd(p)
struct Point *p;
{
    int i, bucket;
    struct Halfedge *he;

/* Use hash table to get close to desired halfedge */
    bucket = (p->x - xmin)/deltax * ELhashsize;
    if(bucket<0) 
	bucket =0;
    if(bucket>=ELhashsize) 
	bucket = ELhashsize - 1;
    he = ELgethash(bucket);
    if(he == (struct Halfedge *) NULL) {   
	for(i=1; 1 ; i += 1) {	
	    if ((he=ELgethash(bucket-i)) != (struct Halfedge *) NULL) 
		break;
	    if ((he=ELgethash(bucket+i)) != (struct Halfedge *) NULL) 
		break;
	}
	totalsearch += i;
    }
    ntry += 1;

/* 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) {	
	if(ELhash[bucket] != (struct Halfedge *) NULL) 
	    ELhash[bucket]->ELrefcnt -= 1;
	ELhash[bucket] = he;
	ELhash[bucket]->ELrefcnt += 1;
    }
    return (he);
}

/*
 *  This delete routine can't reclaim node, since pointers from hash
 *  table may be present.   
 */
ELdelete(he)
struct Halfedge *he;
{
    (he->ELleft)->ELright = he->ELright;
    (he->ELright)->ELleft = he->ELleft;
    he->ELedge = (struct Edge *)DELETED;
}

struct Halfedge *ELright(he)
struct Halfedge *he;
{
    return (he->ELright);
}

struct Halfedge *ELleft(he)
struct Halfedge *he;
{
    return (he->ELleft);
}

struct Site *leftreg(he)
struct Halfedge *he;
{
    if(he->ELedge == (struct Edge *)NULL) 
	return(bottomsite);
    return( he->ELpm == le ? he->ELedge->reg[le] : he->ELedge->reg[re]);
}

struct Site *rightreg(he)
struct Halfedge *he;
{
    if(he->ELedge == (struct Edge *)NULL) 
	return(bottomsite);
    return( he->ELpm == le ? he->ELedge->reg[re] : he->ELedge->reg[le]);
}
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.