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