planarity/graph_region.c

   1 /*
   2  *
   3  *  gPlanarity:
   4  *     The geeky little puzzle game with a big noodly crunch!
   5  *
   6  *     gPlanarity copyright (C) 2005 Monty <monty@xiph.org>
   7  *     Original Flash game by John Tantalo <john.tantalo@case.edu>
   8  *     Original game concept by Mary Radcliffe
   9  *
  10  *  gPlanarity is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2, or (at your option)
  13  *  any later version.
  14  *
  15  *  gPlanarity is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with Postfish; see the file COPYING.  If not, write to the
  22  *  Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  23  *
  24  *
  25  */
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <math.h>
  31
  32 #include "graph.h"
  33 #include "graph_region.h"
  34 #include "gettext.h"
  35
  36 /* Regions are 'electric fences' for mesh building; used in mesh2 to
  37    make non-convex shapes */
  38
  39 typedef struct region_segment {
  40   int layout; /* 0 no layout, 1 left, 2 right, 3 layout-only */
  41   int cont;   /* is this continuous from last line? */
  42   int split;  /* are we splitting the graph into interntionally
  43                  seperate regions here? */
  44
  45   float x1;
  46   float y1;
  47   float x2;
  48   float y2;
  49
  50   // arc computation cache (if arc)
  51   float cx;
  52   float cy;
  53   float radius;
  54   float phi0;
  55   float phi1;
  56   float phi;
  57
  58   float length;
  59   struct region_segment *next;
  60 } region_segment;
  61
  62 typedef struct region{
  63   int num;
  64   region_segment *l;
  65
  66   int ox,oy,x,y;
  67   int layout;
  68
  69   int cont;
  70   int split_next;
  71 } region;
  72
  73 static region r;
  74 static region layout_adj;
  75 static region_segment *segpool=0;
  76
  77 #define CHUNK 64
  78
  79 static region_segment *new_segment(region *r, int x1,int y1,int x2, int y2){
  80   region_segment *ret;
  81
  82   if(!segpool){
  83     int i;
  84     segpool = calloc(CHUNK,sizeof(*segpool));
  85     for(i=0;i<CHUNK-1;i++) /* last addition's next points to nothing */
  86       segpool[i].next=segpool+i+1;
  87   }
  88
  89   ret=segpool;
  90   segpool=ret->next;
  91
  92   memset(ret,0,sizeof(*ret));
  93   ret->next = r->l;
  94   ret->layout=r->layout;
  95   ret->x1=x1;
  96   ret->y1=y1;
  97   ret->x2=x2;
  98   ret->y2=y2;
  99   ret->cont = r->cont;
 100   ret->split = r->split_next;
 101
 102   r->l=ret;
 103   r->split_next=0;
 104
 105   return ret;
 106 }
 107
 108 /* angle convention: reversed y (1,-1 is first quadrant, ala X
 109    windows), range -PI to PI */
 110
 111 static int intersects_arc(edge *e, region_segment *r){
 112   float Ax = e->A->x - r->cx;
 113   float Ay = e->A->y - r->cy;
 114   float Bx = e->B->x - r->cx;
 115   float By = e->B->y - r->cy;
 116
 117   float dx = Bx - Ax;
 118   float dy = By - Ay;
 119   float dr2 = dx*dx + dy*dy;
 120   float D = Ax*By - Bx*Ay;
 121   float discriminant =(r->radius*r->radius)*dr2 - D*D;
 122
 123   // does it even intersect the full circle?
 124   if(discriminant<=0)return 0;
 125
 126   {
 127     float x1,y1,x2,y2;
 128
 129     float sqrtd = sqrt(discriminant);
 130     float sign = (dy>0?1.f:-1.f);
 131
 132     // finite precision required here else 0/inf slope lines will be
 133     // slighly off the secant
 134     x1 = rint((D*dy + sign*dx*sqrtd) / dr2);
 135     x2 = rint((D*dy - sign*dx*sqrtd) / dr2);
 136
 137     y1 = rint((-D*dx + fabs(dy)*sqrtd) / dr2);
 138     y2 = rint((-D*dx - fabs(dy)*sqrtd) / dr2);
 139
 140     Ax = rint(Ax);
 141     Ay = rint(Ay);
 142     Bx = rint(Bx);
 143     By = rint(By);
 144
 145     // is x1,y1 actually on the segment?
 146     if( !(x1<Ax && x1<Bx) &&
 147         !(x1>Ax && x1>Bx) &&
 148         !(y1<Ay && y1<By) &&
 149         !(y1>Ay && y1>By)){
 150       // yes. it is in the angle range we care about?
 151
 152       float ang = acos(x1 / r->radius);
 153       if(y1>0) ang = -ang;
 154
 155       if(r->phi<0){
 156         if(r->phi0 < r->phi1){
 157           if(ang <= r->phi0 || ang >= r->phi1)return 1;
 158         }else{
 159           if(ang <= r->phi0 && ang >= r->phi1)return 1;
 160         }
 161       }else{
 162         if(r->phi0 < r->phi1){
 163           if(ang >= r->phi0 && ang <= r->phi1)return 1;
 164         }else{
 165           if(ang >= r->phi0 || ang <= r->phi1)return 1;
 166         }
 167       }
 168     }
 169
 170     // is x2,y2 actually on the segment?
 171     // if so, it is in the arc range we care about?
 172     if( !(x2<Ax && x2<Bx) &&
 173         !(x2>Ax && x2>Bx) &&
 174         !(y2<Ay && y2<By) &&
 175         !(y2>Ay && y2>By)){
 176       // yes. it is in the angle range we care about?
 177
 178       float ang = acos(x2 / r->radius);
 179       if(y2>0) ang = -ang;
 180
 181       if(r->phi<0){
 182         if(r->phi0 < r->phi1){
 183           if(ang <= r->phi0 || ang >= r->phi1)return 1;
 184         }else{
 185           if(ang <= r->phi0 && ang >= r->phi1)return 1;
 186         }
 187       }else{
 188         if(r->phi0 < r->phi1){
 189           if(ang >= r->phi0 && ang <= r->phi1)return 1;
 190         }else{
 191           if(ang >= r->phi0 || ang <= r->phi1)return 1;
 192         }
 193       }
 194     }
 195   }
 196   return 0;
 197 }
 198
 199 static float line_angle(float x1, float y1, float x2, float y2){
 200   float xd = x2-x1;
 201   float yd = y2-y1;
 202
 203   if(xd == 0){
 204     if(yd>0)
 205       return -M_PI/2;
 206     else
 207       return M_PI/2;
 208   }else if(xd<0){
 209     if(yd<0)
 210       return atan(-yd/xd)+M_PI;
 211     else
 212       return  atan(-yd/xd)-M_PI;
 213   }else{
 214     return atan(-yd/xd);
 215   }
 216 }
 217
 218 static float line_mag(float x1, float y1, float x2, float y2){
 219   float xd = x2-x1;
 220   float yd = y2-y1;
 221   return hypot(xd,yd);
 222 }
 223
 224 static void compute_arc(region_segment *r,float phi){
 225   float x1=r->x1;
 226   float y1=r->y1;
 227   float x2=r->x2;
 228   float y2=r->y2;
 229   float ar,br,cr;
 230   float cx,cy,a,c,d;
 231   float xd = x2-x1;
 232   float yd = y2-y1;
 233
 234   if(phi<-M_PI){
 235     ar = phi + M_PI*2;
 236   }else if (phi<0){
 237     ar = -phi;
 238   }else if (phi<M_PI){
 239     ar = phi;
 240   }else{
 241     ar = M_PI*2 - phi;
 242   }
 243
 244   cr = line_angle(x1,y1,x2,y2);
 245   a = line_mag(x1,y1,x2,y2)/2.f;
 246   br=(M_PI/2.f)-(ar/2.f);
 247   c = tan(br)*a;
 248   d = hypot(a,c);
 249
 250   if(phi<-M_PI || (phi>0 && phi<M_PI)){
 251     cx = x1 + cos(cr+M_PI/2)*c + xd/2;
 252     cy = y1 - sin(cr+M_PI/2)*c + yd/2;
 253   }else{
 254     cx = x1 + cos(cr-M_PI/2)*c + xd/2;
 255     cy = y1 - sin(cr-M_PI/2)*c + yd/2;
 256   }
 257
 258   r->cx=cx;
 259   r->cy=cy;
 260   r->radius=d;
 261
 262   // have the center of the circle, have radius.  Determine the
 263   // portion of the arc we want.
 264   r->phi0 = acos( (x1-cx) / d);
 265   r->phi1 = acos( (x2-cx) / d);
 266   if(y1>cy) r->phi0= -r->phi0;
 267   if(y2>cy) r->phi1= -r->phi1;
 268   r->phi=phi;
 269 }
 270
 271 static region_segment *region_arc(region *re, int x1, int y1, int x2, int y2, float rad){
 272   region_segment *n=  new_segment(re,x1,y1,x2,y2);
 273   compute_arc(n,rad);
 274   return n;
 275 }
 276
 277 static region_segment *region_line(region *re,int x1, int y1, int x2, int y2){
 278   return new_segment(re,x1,y1,x2,y2);
 279 }
 280
 281 /* The overall idea here is to massage the region segments and arcs
 282    slightly so that when we layout points based on a region, the
 283    layout is slightly inside or outside (as requested) the actual
 284    region. This also reverses the path when rebuilding into the new
 285    region, putting it in the order we actually need to evaluate it in.
 286 */
 287
 288 #define ADJ 2.f
 289
 290 static void point_adj(float x1, float y1, float x2, float y2, float *Px, float *Py, int left){
 291   float xd = x2-x1;
 292   float yd = y2-y1;
 293   float M = hypot(xd,yd);
 294
 295   if(left){
 296     *Px +=  yd/M*ADJ;
 297     *Py += -xd/M*ADJ;
 298   }else{
 299     *Px += -yd/M*ADJ;
 300     *Py +=  xd/M*ADJ;
 301   }
 302 }
 303
 304 static void line_adj(float *x1, float *y1, float *x2, float *y2, int left){
 305   float xd = *x2-*x1;
 306   float yd = *y2-*y1;
 307   float M = hypot(xd,yd);
 308
 309   if(left){
 310     *x1 +=  yd/M*ADJ;
 311     *x2 +=  yd/M*ADJ;
 312     *y1 += -xd/M*ADJ;
 313     *y2 += -xd/M*ADJ;
 314   }else{
 315     *x1 += -yd/M*ADJ;
 316     *x2 += -yd/M*ADJ;
 317     *y1 +=  xd/M*ADJ;
 318     *y2 +=  xd/M*ADJ;
 319   }
 320
 321   // make sure there's an overlap!
 322   *x1-=xd/M*4.;
 323   *x2+=xd/M*4.;
 324   *y1-=yd/M*4.;
 325   *y2+=yd/M*4.;
 326 }
 327
 328
 329 static float tangent_distance_from_center(float x1, float y1, float x2, float y2,
 330                                           float cx, float cy){
 331   float xd = x2 - x1;
 332   float yd = y2 - y1;
 333   return ((x2-x1)*(cy-y1) - (y2-y1)*(cx-x1)) / hypot(xd,yd);
 334 }
 335
 336 static float radius_adjust(float r, float arc_phi, int left){
 337   if(arc_phi<0){
 338     if(left){
 339       r+=ADJ;
 340     }else{
 341       r-=ADJ;
 342     }
 343   }else{
 344     if(left){
 345       r-=ADJ;
 346     }else{
 347       r+=ADJ;
 348     }
 349   }
 350   return r;
 351 }
 352
 353 static void line_line_adj(region_segment *A, region_segment *B,
 354                           float *new_x, float *new_y, int left){
 355   double newd_x;
 356   double newd_y;
 357
 358   float Ax1=A->x1;
 359   float Ay1=A->y1;
 360   float Ax2=A->x2;
 361   float Ay2=A->y2;
 362
 363   float Bx1=B->x1;
 364   float By1=B->y1;
 365   float Bx2=B->x2;
 366   float By2=B->y2;
 367
 368   line_adj(&Ax1, &Ay1, &Ax2, &Ay2, left);
 369   line_adj(&Bx1, &By1, &Bx2, &By2, left);
 370
 371   // compute new intersection
 372   if(!intersects(Ax1,Ay1,Ax2,Ay2, Bx1,By1,Bx2,By2, &newd_x, &newd_y)){
 373     // odd; do nothing rather than fail unpredictably
 374     *new_x=Ax2;
 375     *new_y=Ay2;
 376   }else{
 377     *new_x=newd_x;
 378     *new_y=newd_y;
 379   }
 380 }
 381
 382 static void line_arc_adj(float x1, float y1, float x2, float y2,
 383                          float cx, float cy, float r, float arc_phi,
 384                          float *new_x2, float *new_y2, int lleft, int aleft){
 385   float xd = x2 - x1;
 386   float yd = y2 - y1;
 387   float c = tangent_distance_from_center(x1,y1,x2,y2,cx,cy);
 388   float a = sqrt(r*r - c*c),a2;
 389   float M = hypot(xd,yd);
 390   float ax = x2 + xd/M*a;
 391   float ay = y2 + yd/M*a;
 392
 393   float ax1 = x2 - xd/M*a;
 394   float ay1 = y2 - yd/M*a;
 395   if(hypot(ax1-cx,ay1-cy) < hypot(ax-cx,ay-cy)){
 396     ax=ax1;
 397     ay=ay1;
 398   }
 399
 400   xd = ax-x2;
 401   yd = ay-y2;
 402
 403   point_adj(x1, y1, x2, y2, &ax, &ay, lleft);
 404
 405   r = radius_adjust(r,arc_phi,aleft);
 406   c = hypot(cx-ax,cy-ay);
 407   a2 = sqrt(r*r-c*c);
 408
 409   *new_x2 = ax - xd/a*a2;
 410   *new_y2 = ay - yd/a*a2;
 411 }
 412
 413 static void arc_arc_adj(region_segment *arc, region_segment *next,
 414                          float *new_x2, float *new_y2, int left){
 415   float x2 =arc->x2;
 416   float y2 =arc->y2;
 417
 418   float cx1=arc->cx;
 419   float cy1=arc->cy;
 420   float r1 =arc->radius;
 421
 422   float cx2=next->cx;
 423   float cy2=next->cy;
 424   float r2 =next->radius;
 425
 426   float c;
 427   float xd = cx2-cx1;
 428   float yd = cy2-cy1;
 429   float d = hypot(xd,yd);
 430   float x = (d*d - r1*r1 + r2*r2) / (2*d);
 431
 432   // is the old x2/y2 to the left or right of the line connecting the
 433   // circle centers?
 434   float angle_x2y2 = line_angle(cx1,cy1,x2,y2);
 435   float angle_c1c2 = line_angle(cx1,cy1,cx2,cy2);
 436   float angle = angle_x2y2 - angle_c1c2;
 437   if(angle < -M_PI)angle += M_PI*2.f;
 438   if(angle >  M_PI)angle -= M_PI*2.f;
 439
 440   r1=radius_adjust(r1,arc->phi,left);
 441   r2=radius_adjust(r2,arc->phi,left);
 442
 443   if(r1+r2>=d){
 444     // still have a valid solution
 445     x = (d*d - r1*r1 + r2*r2) / (2*d);
 446     c = sqrt(r2*r2 - x*x);
 447
 448     if(angle>0){
 449       // left of c1,c2 segment
 450       *new_x2 = cx1+xd/d*x + yd/d*c;
 451       *new_y2 = cy1+yd/d*x - xd/d*c;
 452     }else{
 453       // right
 454       *new_x2 = cx1+xd/d*x - yd/d*c;
 455       *new_y2 = cy1+yd/d*x + xd/d*c;
 456     }
 457   }else{
 458     // circles shrunk and no longer overlap.
 459     fprintf(stderr,_("region overlap adjustment failed in arc_arc_adj; \n"
 460             "  This is an internal error that should never happen.\n"));
 461   }
 462 }
 463
 464 static float phisub(float phi0, float phi1, float arcphi){
 465   float phid = phi1-phi0;
 466   if(arcphi<0){
 467     if(phid>0) phid -= M_PI*2.f;
 468   }else{
 469     if(phid<0) phid += M_PI*2.f;
 470   }
 471   return phid;
 472 }
 473
 474 static void radius_adj_xy(region_segment *s,float *x1,float *y1, int left){
 475   float xd = *x1 - s->cx;
 476   float yd = *y1 - s->cy;
 477
 478   float r = s->radius;
 479   float new_r = radius_adjust(r,s->phi,left);
 480   float delta = new_r/r;
 481
 482   *x1 = s->cx + xd*delta;
 483   *y1 = s->cy + yd*delta;
 484 }
 485
 486 static void adjust_layout(){
 487   /* build adjustments from intersection region into layout region */
 488   region_segment *s = r.l;
 489   region_segment *endpath = 0;
 490   region_segment *endpath_adj = 0;
 491   float x2=-1,y2=-1;
 492
 493   // first, release previous layout
 494   region_segment *l=layout_adj.l;
 495   region_segment *le=l;
 496
 497   while(le && le->next)le=le->next;
 498   if(le){
 499     le->next=segpool;
 500     segpool=l;
 501   }
 502   memset(&layout_adj,0,sizeof(layout_adj));
 503
 504   while(s){
 505     float x1=0,y1=0,phi=0,radius=0;
 506
 507     if(s->cont){
 508       if(!endpath){
 509         endpath=s;
 510         endpath_adj=0;
 511       }
 512     }
 513
 514     if(s->layout){
 515       if(s->layout<3){
 516
 517         // the flags mark beginning and end of the path, but don't say
 518         // if it's closed.
 519         if(!s->cont && endpath_adj)
 520           if(endpath->x2 != s->x1 ||
 521              endpath->y2 != s->y1)
 522             endpath_adj=0;
 523
 524         /* first handle the lone-circle special case */
 525         if(s->x1==s->x2 && s->y1==s->y2){
 526           if(s->radius>0){
 527             if(s->layout == 1) radius= s->radius+2;
 528             if(s->layout == 2) radius= s->radius-2;
 529             x1=x2=s->x1;y1=y2=s->y1;
 530             phi=s->phi;
 531           }
 532         }else{
 533           region_segment *p = 0;
 534
 535           if(s->cont)
 536             p = s->next;
 537           else if(endpath_adj)
 538             p = endpath;
 539
 540           if(p){
 541             if(s->radius){
 542               if(x2==-1){
 543                 x2=s->x2;
 544                 y2=s->y2;
 545                 radius_adj_xy(s,&x2,&y2,s->layout==1);
 546               }
 547               if(p->radius){
 548                 // arc - arc case
 549                 float phi0,phi1;
 550                 arc_arc_adj(p,s,&x1,&y1,s->layout==1);
 551                 phi0=line_angle(s->cx,s->cy,x1,y1);
 552                 phi1=line_angle(s->cx,s->cy,x2,y2);
 553                 phi=phisub(phi0,phi1,s->phi);
 554               }else{
 555                 // arc-line case
 556                 float phi0,phi1;
 557                 line_arc_adj(p->x1, p->y1, p->x2, p->y2,
 558                              s->cx, s->cy, s->radius, s->phi,
 559                              &x1, &y1, s->layout==1, s->layout==1);
 560                 phi0=line_angle(s->cx,s->cy,x1,y1);
 561                 phi1=line_angle(s->cx,s->cy,x2,y2);
 562                 phi=phisub(phi0,phi1,s->phi);
 563               }
 564             }else{
 565               if(x2==-1){
 566                 x2=s->x2;
 567                 y2=s->y2;
 568                 point_adj(s->x1, s->y1, s->x2, s->y2, &x2, &y2, s->layout==1);
 569               }
 570               if(p->radius){
 571                 // line-arc case
 572                 line_arc_adj(s->x2, s->y2, s->x1, s->y1,
 573                              p->cx, p->cy, p->radius, p->phi,
 574                              &x1, &y1, s->layout==2, s->layout==1);
 575               }else{
 576                 // line-line case
 577                 line_line_adj(p, s, &x1, &y1, s->layout==1);
 578               }
 579             }
 580           }else{
 581             x1=s->x1;
 582             y1=s->y1;
 583             x2=s->x2;
 584             y2=s->y2;
 585             if(s->radius){
 586               // lone arc case; alter radius
 587               radius_adj_xy(s,&x1,&y1,s->layout==1);
 588               radius_adj_xy(s,&x2,&y2,s->layout==1);
 589               phi=s->phi;
 590             }else{
 591               // lone line segment case; offset
 592               point_adj(s->x1, s->y1, s->x2, s->y2, &x1, &y1, s->layout==1);
 593               point_adj(s->x1, s->y1, s->x2, s->y2, &x2, &y2, s->layout==1);
 594
 595             }
 596           }
 597         }
 598       }else{
 599         x1=s->x1;
 600         x2=s->x2;
 601         y1=s->y1;
 602         y2=s->y2;
 603         phi=s->phi;
 604         if(x1==x2 && y1==y2)
 605           radius = s->radius;
 606       }
 607
 608       // push the region segment
 609       {
 610         region_segment *n=new_segment(&layout_adj,rint(x1),rint(y1),rint(x2),rint(y2));
 611         n->layout=3;
 612         n->cont=(s->cont || endpath_adj);
 613         n->split = s->split;
 614
 615         if(radius){
 616           // circle; radius variable is treated as a flag
 617           n->cx=x1;
 618           n->cy=y1;
 619           n->radius=radius;
 620           n->phi0=-M_PI;
 621           n->phi1= M_PI;
 622           n->cont=1;
 623         }else if(s->radius){
 624           // arc
 625           compute_arc(n,phi);
 626         }
 627         if(s->cont && !endpath_adj)endpath_adj=n;
 628
 629       }
 630
 631       if(endpath_adj && !s->cont){
 632         // go back and clean up the endpath path member
 633         endpath_adj->x2 = rint(x1);
 634         endpath_adj->y2 = rint(y1);
 635
 636         if(endpath->radius>0){
 637           endpath_adj->phi1=line_angle(endpath->cx,endpath->cy,endpath_adj->x2,endpath_adj->y2);
 638           endpath_adj->phi=phisub(endpath_adj->phi0,endpath_adj->phi1,endpath_adj->phi);
 639         }
 640       }
 641     }
 642
 643     if(!s->cont){
 644       endpath_adj=0;
 645       endpath=0;
 646       x2=-1;
 647       y2=-1;
 648     }else{
 649       x2=x1;
 650       y2=y1;
 651     }
 652
 653     s=s->next;
 654   }
 655 }
 656
 657 void region_init(){
 658   // release any lines and arcs
 659   region_segment *l=r.l;
 660   region_segment *le=r.l;
 661   region_segment *a=layout_adj.l;
 662   region_segment *ae=layout_adj.l;
 663
 664   while(le && le->next)le=le->next;
 665   while(ae && ae->next)ae=ae->next;
 666
 667   if(le){
 668     le->next=segpool;
 669     segpool=l;
 670   }
 671   if(ae){
 672     ae->next=segpool;
 673     segpool=a;
 674   }
 675
 676   memset(&r,0,sizeof(r));
 677   memset(&layout_adj,0,sizeof(layout_adj));
 678 }
 679
 680 int region_layout(graph *g){
 681   // count up the total length of the region segments used in layout
 682   float length=0,acc=0,ldel;
 683   int num_adj=g->vertex_num;
 684   int activenum=0;
 685   region_segment *l;
 686   vertex *v = g->verticies;
 687
 688   adjust_layout();
 689
 690   l = layout_adj.l;
 691
 692   while(l){
 693     if(l->radius==0){
 694       float xd=l->x2 - l->x1;
 695       float yd=l->y2 - l->y1;
 696       length += l->length = hypot(xd,yd);
 697     }else{
 698       float diam = l->radius*2.f*M_PI;
 699       float del=phisub(l->phi0,l->phi1,l->phi);
 700       if(l->phi<0)
 701         del = -del;
 702
 703       length += l->length = diam*del*(1.f/(M_PI*2.f));
 704     }
 705     l=l->next;
 706   }
 707
 708   // non-contiguous beginnings sink a single point segment per
 709   l = layout_adj.l;
 710   while(l){
 711     if(!l->cont)
 712       num_adj--;
 713     l=l->next;
 714   }
 715
 716   /* perform layout segment by segment */
 717   l = layout_adj.l;
 718   ldel = (float)length/num_adj;
 719   while(l && v){
 720     int i;
 721     int num_placed = l->cont ? rint((l->length-acc)/ldel) :  rint((l->length-acc)/ldel)+1;
 722     float snap_del = l->cont ? l->length/num_placed : l->length/(num_placed-1);
 723     float snap_acc=l->cont?snap_del:0;
 724
 725     if(l->split)activenum++;
 726
 727     if(l->radius==0){
 728       float x1 = l->x1;
 729       float y1 = l->y1;
 730       float x2 = l->x2;
 731       float y2 = l->y2;
 732       float xd=(x2-x1)/l->length;
 733       float yd=(y2-y1)/l->length;
 734
 735       for(i=0;v && i<num_placed;i++){
 736         v->x = rint(x1+xd*snap_acc);
 737         v->y = rint(y1+yd*snap_acc);
 738
 739         if(snap_acc)
 740           acc+=ldel;
 741         snap_acc+=snap_del;
 742         v->active=activenum;
 743         v=v->next;
 744       }
 745     }else{
 746       /* next is an arc */
 747       float x = l->cx;
 748       float y = l->cy;
 749       float phid = phisub(l->phi0,l->phi1,l->phi);
 750
 751       phid /= l->length;
 752
 753       for(i=0;v && i<num_placed;i++){
 754         v->x = rint( cos(l->phi0+phid*snap_acc)*(l->radius)+x);
 755         v->y = rint( -sin(l->phi0+phid*snap_acc)*(l->radius)+y);
 756
 757         if(snap_acc)
 758           acc+=ldel;
 759         snap_acc+=snap_del;
 760         v->active=activenum;
 761         v=v->next;
 762       }
 763     }
 764
 765     acc-=l->length;
 766     l=l->next;
 767   }
 768   return activenum;
 769 }
 770
 771 void region_circle(int x,int y, float rad, int layout){
 772   region_segment *a=new_segment(&r,0,0,0,0);
 773   a->cx=a->x1=a->x2=x;
 774   a->cy=a->y1=a->y2=y;
 775   a->radius=rad;
 776   a->phi0=-M_PI;
 777   a->phi1=M_PI;
 778   a->phi=M_PI*2.f;
 779   a->layout=layout;
 780   a->cont=0; // not really necessary, just consistent
 781   r.cont=0;
 782 }
 783
 784 void region_new_area(int x, int y, int layout){
 785   r.x=r.ox=x;
 786   r.y=r.oy=y;
 787   r.layout=layout;
 788   r.cont=0;
 789 }
 790
 791 void region_line_to(int x,int y){
 792   region_line(&r,r.x,r.y,x,y);
 793   r.x=x;
 794   r.y=y;
 795   r.cont=1;
 796 }
 797
 798 void region_arc_to(int x,int y, float rad){
 799   region_arc(&r,r.x,r.y,x,y,rad);
 800   r.x=x;
 801   r.y=y;
 802   r.cont=1;
 803 }
 804
 805 void region_close_line(){
 806   region_line(&r,r.x,r.y,r.ox,r.oy);
 807   r.x=r.ox;
 808   r.y=r.oy;
 809   r.cont=0;
 810 }
 811
 812 void region_close_arc(float rad){
 813   region_arc(&r,r.x,r.y,r.ox,r.oy,rad);
 814   r.x=r.ox;
 815   r.y=r.oy;
 816   r.cont=0;
 817 }
 818
 819 void region_split_here(){
 820   r.split_next=1;
 821 }
 822
 823 int region_intersects(edge *e){
 824
 825   region_segment *s=r.l;
 826   while(s){
 827     if(s->layout<3){
 828       if(s->radius!=0){
 829         if(intersects_arc(e,s))return 1;
 830       }else{
 831         double xdummy,ydummy;
 832
 833         if(intersects(e->A->x,e->A->y,e->B->x,e->B->y,
 834                       s->x1,s->y1,s->x2,s->y2,
 835                       &xdummy,&ydummy))return 1;
 836
 837       }
 838     }
 839     s=s->next;
 840   }
 841   return 0;
 842 }
 843
 844 int have_region(){
 845   if(r.l)return 1;
 846   return 0;
 847 }