delaunay.c

this file is contain important facts aboute different programming langueges.

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  /*e->b==1.0 */
{	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);
}


static void endpoint(e, lr, s)
struct Edge *e;
int	lr;
struct Site *s;
{
e -> ep[lr] = s;
ref(s);
if(e -> ep[re-lr]== (struct Site *) NULL) return;
out_ep(e);
deref(e->reg[le]);
deref(e->reg[re]);
makefree(e, &efl);
}


static float dist(s,t)
struct Site *s,*t;
{
float dx,dy;
	dx = s->coord.x - t->coord.x;
	dy = s->coord.y - t->coord.y;
#if defined(vms) || defined(__vms__) || defined(ultrix) || defined(_WIN32)
	return( (float) sqrt((double) (dx*dx + dy*dy)) );
#else
	return(sqrtf(dx*dx + dy*dy));
#endif
}


static void makevertex(v)
struct Site *v;
{
v -> sitenbr = nvertices;
nvertices += 1;
out_vertex(v);
}


static deref(v)
struct	Site *v;
{
v -> refcnt -= 1;
if (v -> refcnt == 0 ) makefree(v, &sfl);
}

static ref(v)
struct Site *v;
{
v -> refcnt += 1;
}

/* Original file: heap.c */


static PQinsert(he, v, offset)
struct Halfedge *he;
struct Site *v;
float 	offset;
{
struct Halfedge *last, *next;

he -> vertex = v;
ref(v);
he -> ystar = v -> coord.y + offset;
last = &PQhash[PQbucket(he)];
while ((next = last -> PQnext) != (struct Halfedge *) NULL &&
      (he -> ystar  > next -> ystar  ||
      (he -> ystar == next -> ystar && v -> coord.x > next->vertex->coord.x)))
	{	last = next;};
he -> PQnext = last -> PQnext; 
last -> PQnext = he;
PQcount += 1;
}

static PQdelete(he)
struct Halfedge *he;
{
struct Halfedge *last;

if(he ->  vertex != (struct Site *) NULL)
{	last = &PQhash[PQbucket(he)];
	while (last -> PQnext != he) last = last -> PQnext;
	last -> PQnext = he -> PQnext;
	PQcount -= 1;
	deref(he -> vertex);
	he -> vertex = (struct Site *) NULL;
};
}

static int PQbucket(he)
struct Halfedge *he;
{
int bucket;

bucket = (he->ystar - ymin)/deltay * PQhashsize;
if (bucket<0) bucket = 0;
if (bucket>=PQhashsize) bucket = PQhashsize-1 ;
if (bucket < PQmin) PQmin = bucket;
return(bucket);
}



static int PQempty()
{
	return(PQcount==0);
}


static struct Point PQ_min()
{
struct Point answer;

	while(PQhash[PQmin].PQnext == (struct Halfedge *)NULL) {PQmin += 1;};
	answer.x = PQhash[PQmin].PQnext -> vertex -> coord.x;
	answer.y = PQhash[PQmin].PQnext -> ystar;
	return (answer);
}

static struct Halfedge *PQextractmin()
{
struct Halfedge *curr;

	curr = PQhash[PQmin].PQnext;
	PQhash[PQmin].PQnext = curr -> PQnext;
	PQcount -= 1;
	return(curr);
}


static PQinitialize()
{
int i; struct Point *s;

	PQcount = 0;
	PQmin = 0;
	PQhashsize = 4 * sqrt_nsites;
	PQhash = (struct Halfedge *) myalloc(PQhashsize * sizeof *PQhash);
	for(i=0; i<PQhashsize; i+=1) PQhash[i].PQnext = (struct Halfedge *)NULL;
}

/* Original file: memory.c */

static freeinit(fl, size)
struct	Freelist *fl;
int	size;
{
fl -> head = (struct Freenode *) NULL;
fl -> nodesize = size;
}

static char *getfree(fl)
struct	Freelist *fl;
{
int i; struct Freenode *t;
if(fl->head == (struct Freenode *) NULL)
{	t =  (struct Freenode *) myalloc(sqrt_nsites * fl->nodesize);
	for(i=0; i<sqrt_nsites; i+=1) 	
		makefree((struct Freenode *)((char *)t+i*fl->nodesize), fl);
};
t = fl -> head;
fl -> head = (fl -> head) -> nextfree;
return((char *)t);
}



static makefree(curr,fl)
struct Freenode *curr;
struct Freelist *fl;
{
curr -> nextfree = fl -> head;
fl -> head = curr;
}

static int total_alloc;

static char *myalloc(n)
unsigned n;
{
char *t;
if ((t=malloc(n)) == (char *) 0)
{    fprintf(stderr,"Insufficient memory processing site %d (%d bytes in use)\n",
		siteidx, total_alloc);
     exit(EXIT_FAILURE);
};
total_alloc += n;
return(t);
}

/* Original file: output.c */

static out_bisector(e)
struct Edge *e;
{
if(!triangulate & !debug)
	printf("l %f %f %f", e->a, e->b, e->c);
if(debug)
	printf("line(%d) %gx+%gy=%g, bisecting %d %d\n", e->edgenbr,
	    e->a, e->b, e->c, e->reg[le]->sitenbr, e->reg[re]->sitenbr);
}


static out_ep(e)
struct Edge *e;
{
if(!triangulate)
{	printf("e %d", e->edgenbr);
	printf(" %d ", e->ep[le] != (struct Site *)NULL ? e->ep[le]->sitenbr : -1);
	printf("%d\n", e->ep[re] != (struct Site *)NULL ? e->ep[re]->sitenbr : -1);
};
}

static out_vertex(v)
struct Site *v;
{
if(!triangulate & !debug)
	printf ("v %f %f\n", v->coord.x, v->coord.y);
if(debug)
	printf("vertex(%d) at %f %f\n", v->sitenbr, v->coord.x, v->coord.y);
}


static out_site(s)
struct Site *s;
{
if(!triangulate & !debug)
	printf("s %f %f\n", s->coord.x, s->coord.y);
if(debug)
	printf("site (%d) at %f %f\n", s->sitenbr, s->coord.x, s->coord.y);
}


static out_triple(s1, s2, s3)
struct Site *s1, *s2, *s3;
{
if(triangulate & !debug)
/*	printf("%d %d %d\n", s1->sitenbr, s2->sitenbr, s3->sitenbr); */
        if( (myntri+1) < mymaxtri ) {
	mynop[myntri].t1 = s1->sitenbr+1;
        mynop[myntri].t2 = s2->sitenbr+1;
        mynop[myntri].t3 = s3->sitenbr+1;
        myntri++;
      } else {
        /* Error: too many triangles */
        myntri = -1;
      }
if(debug)
	printf("circle through left=%d right=%d bottom=%d\n", 
		s1->sitenbr, s2->sitenbr, s3->sitenbr);
}


/* Original file: voronoi.c */

/* implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,
   deltax, deltay (can all be estimates).
   Performance suffers if they are wrong; better to make nsites,
   deltax, and deltay too big than too small.  (?) */

static voronoi(triangulate, nextsite)
int triangulate;
struct Site *(*nextsite)();
{
struct Site *newsite, *bot, *top, *temp, *p;
struct Site *v;
struct Point newintstar;
int pm;
struct Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
struct Edge *e;


PQinitialize();
bottomsite = (*nextsite)();
out_site(bottomsite);
ELinitialize();

newsite = (*nextsite)();
while(1)
{
	if(!PQempty()) newintstar = PQ_min();

	if (newsite != (struct Site *)NULL 
	   && (PQempty() 
		 || newsite -> coord.y < newintstar.y
	 	 || (newsite->coord.y == newintstar.y 
		     && newsite->coord.x < newintstar.x)))
	{/* new site is smallest */
		out_site(newsite);
		lbnd = ELleftbnd(&(newsite->coord));
		rbnd = ELright(lbnd);
		bot = rightreg(lbnd);
		e = bisect(bot, newsite);
		bisector = HEcreate(e, le);
		ELinsert(lbnd, bisector);
		if ((p = intersect(lbnd, bisector)) != (struct Site *) NULL) 
		{	PQdelete(lbnd);
			PQinsert(lbnd, p, dist(p,newsite));
		};
		lbnd = bisector;
		bisector = HEcreate(e, re);
		ELinsert(lbnd, bisector);
		if ((p = intersect(bisector, rbnd)) != (struct Site *) NULL)
		{	PQinsert(bisector, p, dist(p,newsite));	
		};
		newsite = (*nextsite)();	
	}
	else if (!PQempty()) 
	/* intersection is smallest */
	{	lbnd = PQextractmin();
		llbnd = ELleft(lbnd);
		rbnd = ELright(lbnd);
		rrbnd = ELright(rbnd);
		bot = leftreg(lbnd);
		top = rightreg(rbnd);
		out_triple(bot, top, rightreg(lbnd));
		v = lbnd->vertex;
		makevertex(v);
		endpoint(lbnd->ELedge,lbnd->ELpm,v);
		endpoint(rbnd->ELedge,rbnd->ELpm,v);
		ELdelete(lbnd); 
		PQdelete(rbnd);
		ELdelete(rbnd); 
		pm = le;
		if (bot->coord.y > top->coord.y)
		{	temp = bot; bot = top; top = temp; pm = re;}
		e = bisect(bot, top);
		bisector = HEcreate(e, pm);
		ELinsert(llbnd, bisector);
		endpoint(e, re-pm, v);
		deref(v);
		if((p = intersect(llbnd, bisector)) != (struct Site *) NULL)
		{	PQdelete(llbnd);
			PQinsert(llbnd, p, dist(p,bot));
		};
		if ((p = intersect(bisector, rrbnd)) != (struct Site *) NULL)
		{	PQinsert(bisector, p, dist(p,bot));
		};
	}
	else break;
};

for(lbnd=ELright(ELleftend); lbnd != ELrightend; lbnd=ELright(lbnd))
	{	e = lbnd -> ELedge;
		out_ep(e);
	};
}