home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Graphics / 2D_3D / 2DLab / Source / geometry.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-06-12  |  3.9 KB  |  191 lines
  1. #include <math.h>
  2. #include "voronoi.h"
  3.  
  4. geominit()
  5. {
  6.     struct Edge e;
  7.     float sn;
  8.  
  9.     freeinit (&efl, sizeof (struct Edge));
  10.     nvertices = 0;
  11.     nedges = 0;
  12.     sn = nsites + 4;
  13.     sqrt_nsites = sqrt(sn);
  14.     deltay = ymax - ymin;
  15.     deltax = xmax - xmin;
  16.     siteidx = 0;
  17. }
  18.  
  19. struct Edge *bisect(s1,s2)
  20. struct    Site *s1,*s2;
  21. {
  22.     float dx,dy,adx,ady;
  23.     struct Edge *newedge;
  24.  
  25.     newedge = (struct Edge *) getfree(&efl);
  26.  
  27.     newedge->reg[0] = s1;
  28.     newedge->reg[1] = s2;
  29.     ref(s1); 
  30.     ref(s2);
  31.     newedge->ep[0] = (struct Site *) NULL;
  32.     newedge->ep[1] = (struct Site *) NULL;
  33.  
  34.     dx = s2->coord.x - s1->coord.x;
  35.     dy = s2->coord.y - s1->coord.y;
  36.     adx = dx>0 ? dx : -dx;
  37.     ady = dy>0 ? dy : -dy;
  38.     newedge->c = s1->coord.x * dx + s1->coord.y * dy + (dx*dx + dy*dy)*0.5;
  39.     if (adx>ady) {    
  40.     newedge->a = 1.0; 
  41.     newedge->b = dy/dx; 
  42.     newedge->c /= dx;
  43.     } else {    
  44.     newedge->b = 1.0; 
  45.     newedge->a = dx/dy; 
  46.     newedge->c /= dy;
  47.     }
  48.     newedge->edgenbr = nedges;
  49.     out_bisector(newedge);
  50.     nedges += 1;
  51.     return(newedge);
  52. }
  53.  
  54. struct Site *intersect(el1, el2, p)
  55. struct Halfedge *el1, *el2;
  56. struct Point *p;
  57. {
  58.     struct Edge *e1,*e2, *e;
  59.     struct Halfedge *el;
  60.     float d, xint, yint;
  61.     int right_of_site;
  62.     struct Site *v;
  63.  
  64.     e1 = el1->ELedge;
  65.     e2 = el2->ELedge;
  66.     if (e1 == (struct Edge*)NULL || e2 == (struct Edge*)NULL) 
  67.     return ((struct Site *) NULL);
  68.     if (e1->reg[1] == e2->reg[1]) 
  69.     return ((struct Site *) NULL);
  70.     d = e1->a * e2->b - e1->b * e2->a;
  71.     if (-1.0e-10<d && d<1.0e-10) 
  72.     return ((struct Site *) NULL);
  73.     xint = (e1->c*e2->b - e2->c*e1->b)/d;
  74.     yint = (e2->c*e1->a - e1->c*e2->a)/d;
  75.     if ((e1->reg[1]->coord.y < e2->reg[1]->coord.y) ||
  76.         (e1->reg[1]->coord.y == e2->reg[1]->coord.y &&
  77.         e1->reg[1]->coord.x < e2->reg[1]->coord.x) ) {    
  78.     el = el1; 
  79.     e = e1;
  80.     } else {    
  81.     el = el2; 
  82.     e = e2;
  83.     }
  84.     right_of_site = xint >= e->reg[1]->coord.x;
  85.     if ((right_of_site && el->ELpm == le) ||
  86.        (!right_of_site && el->ELpm == re)) 
  87.     return ((struct Site *) NULL);
  88.     v = (struct Site *) getfree(&sfl);
  89.     v->refcnt = 0;
  90.     v->coord.x = xint;
  91.     v->coord.y = yint;
  92.     return(v);
  93. }
  94.  
  95. /* returns 1 if p is to right of halfedge e */
  96. int right_of(el, p)
  97. struct Halfedge *el;
  98. struct Point *p;
  99. {
  100.     struct Edge *e;
  101.     struct Site *topsite;
  102.     int right_of_site, above, fast;
  103.     float dxp, dyp, dxs, t1, t2, t3, yl;
  104.  
  105.     e = el->ELedge;
  106.     topsite = e->reg[1];
  107.     right_of_site = p->x > topsite->coord.x;
  108.     if (right_of_site && el->ELpm == le) 
  109.     return(1);
  110.     if (!right_of_site && el->ELpm == re) 
  111.     return (0);
  112.     if (e->a == 1.0) {    
  113.     dyp = p->y - topsite->coord.y;
  114.     dxp = p->x - topsite->coord.x;
  115.     fast = 0;
  116.     if ((!right_of_site && e->b<0.0) || (right_of_site && e->b>=0.0) ) {    
  117.         above = dyp>= e->b*dxp;    
  118.         fast = above;
  119.     } else {    
  120.         above = p->x + p->y*e->b > e->c;
  121.         if (e->b<0.0) 
  122.         above = !above;
  123.         if (!above) 
  124.         fast = 1;
  125.     }
  126.     if (!fast) {    
  127.         dxs = topsite->coord.x - (e->reg[0])->coord.x;
  128.         above = e->b * (dxp*dxp - dyp*dyp) <
  129.                     dxs*dyp*(1.0+2.0*dxp/dxs + e->b*e->b);
  130.         if (e->b<0.0) 
  131.         above = !above;
  132.     }
  133.     } else {    /*e->b==1.0 */
  134.     yl = e->c - e->a*p->x;
  135.     t1 = p->y - yl;
  136.     t2 = p->x - topsite->coord.x;
  137.     t3 = yl - topsite->coord.y;
  138.     above = t1*t1 > t2*t2 + t3*t3;
  139.     }
  140.     return (el->ELpm==le ? above : !above);
  141. }
  142.  
  143. void
  144. v_endpoint(e, lr, s)
  145. struct Edge *e;
  146. int    lr;
  147. struct Site *s;
  148. {
  149.     e->ep[lr] = s;
  150.     ref(s);
  151.     if (e->ep[re-lr]==(struct Site *)NULL) 
  152.     return;
  153.     out_ep(e);
  154.     deref(e->reg[le]);
  155.     deref(e->reg[re]);
  156.     makefree(e, &efl);
  157. }
  158.  
  159. float dist(s,t)
  160. struct Site *s,*t;
  161. {
  162.     float dx,dy;
  163.     dx = s->coord.x - t->coord.x;
  164.     dy = s->coord.y - t->coord.y;
  165.     return(sqrt(dx*dx + dy*dy));
  166. }
  167.  
  168.  
  169. int makevertex(v)
  170. struct Site *v;
  171. {
  172.     v->sitenbr = nvertices;
  173.     nvertices += 1;
  174.     out_vertex(v);
  175. }
  176.  
  177.  
  178. deref(v)
  179. struct    Site *v;
  180. {
  181.     v->refcnt -= 1;
  182.     if (v->refcnt == 0) 
  183.     makefree(v, &sfl);
  184. }
  185.  
  186. ref(v)
  187. struct Site *v;
  188. {
  189.     v->refcnt += 1;
  190. }
  191.