planarity/graph_arrange.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 <math.h>
  28
  29 #include "graph.h"
  30 #include "random.h"
  31 #include "gameboard.h"
  32 #include "graph_arrange.h"
  33 #include "graph_region.h"
  34
  35 void arrange_verticies_circle(graph *g, float off1, float off2){
  36   vertex *v = g->verticies;
  37   int n = g->vertex_num;
  38   int bw=g->orig_width;
  39   int bh=g->orig_height;
  40   int radius=min(bw,bh)*.45;
  41   int i;
  42   for(i=0;i<n;i++){
  43     v->x = rint( radius * sin( i*M_PI*2./n +off1) + (bw>>1));
  44     v->y = rint( radius * -cos( i*M_PI*2./n +off2) + (bh>>1));
  45     v=v->next;
  46   }
  47 }
  48
  49 void arrange_verticies_polygon(graph *g, int sides, float angle, float rad,
  50                                int xoff, int yoff, float xstretch, float ystretch){
  51   vertex *v = g->verticies;
  52   int n = g->vertex_num;
  53   int bw=g->orig_width;
  54   int bh=g->orig_height;
  55   int radius=min(bw,bh)*rad*.45;
  56   float perleg,del,acc=0;
  57   int i;
  58
  59   for(i=0;i<sides;i++){
  60     int xA = sin(M_PI*2/sides*i+angle)*radius+bw/2+xoff;
  61     int yA = -cos(M_PI*2/sides*i+angle)*radius+bh/2+yoff;
  62     int xB = sin(M_PI*2/sides*(i+1)+angle)*radius+bw/2+xoff;
  63     int yB = -cos(M_PI*2/sides*(i+1)+angle)*radius+bh/2+yoff;
  64
  65     float xD,yD;
  66
  67     if(i==0){
  68       perleg = hypot((xA-xB),(yA-yB));
  69       del = perleg*sides / n;
  70     }
  71
  72     xD = (xB-xA) / perleg;
  73     yD = (yB-yA) / perleg;
  74
  75     while(v && acc<=perleg){
  76       v->x = rint(((xA + xD*acc) - bw/2) * xstretch + bw/2);
  77       v->y = rint(((yA + yD*acc) - bh/2) * ystretch + bh/2);
  78       v=v->next;
  79       acc+=del;
  80     }
  81     acc-=perleg;
  82   }
  83
  84 }
  85
  86 void arrange_verticies_polycircle(graph *g, int sides, float angle, float split,
  87                                   int radplus,int xoff,int yoff){
  88
  89   vertex *v = g->verticies;
  90   int n = g->vertex_num;
  91   int bw=g->orig_width;
  92   int bh=g->orig_height;
  93   int radius=min(bw,bh)*.45+radplus;
  94   float perleg,perarc,del,acc=0;
  95   int i;
  96
  97   for(i=0;i<sides;i++){
  98     float ang0 = M_PI*2/sides*i + angle;
  99     float ang1 = M_PI*2/sides*i + (M_PI/sides*split) + angle;
 100     float ang2 = M_PI*2/sides*(i+1) - (M_PI/sides*split) + angle;
 101
 102     int xA = sin(ang1)*radius+bw/2;
 103     int yA = -cos(ang1)*radius+bh/2;
 104     int xB = sin(ang2)*radius+bw/2;
 105     int yB = -cos(ang2)*radius+bh/2;
 106
 107     float xD,yD,aD;
 108
 109     if(i==0){
 110       perleg = hypot((xA-xB),(yA-yB));
 111       perarc = 2*radius*M_PI * split / sides;
 112       del = (perleg+perarc)*sides / n;
 113     }
 114
 115     // populate the first arc segment
 116     aD = (ang1-ang0)/perarc*2;
 117     while(v && acc<=perarc/2){
 118       v->x = rint( sin(ang0 + aD*acc)*radius+bw/2)+xoff;
 119       v->y = rint(-cos(ang0 + aD*acc)*radius+bh/2)+yoff;
 120       v=v->next;
 121       acc+=del;
 122     }
 123     acc-=perarc/2;
 124
 125     // populate the line segment
 126     xD = (xB-xA) / perleg;
 127     yD = (yB-yA) / perleg;
 128
 129     while(v && acc<=perleg){
 130       v->x = rint(xA + xD*acc)+xoff;
 131       v->y = rint(yA + yD*acc)+yoff;
 132       v=v->next;
 133       acc+=del;
 134     }
 135     acc-=perleg;
 136
 137     // populate the second arc segment
 138     while(v && acc<=perarc/2){
 139       v->x = rint( sin(ang2 + aD*acc)*radius+bw/2)+xoff;
 140       v->y = rint(-cos(ang2 + aD*acc)*radius+bh/2)+yoff;
 141       v=v->next;
 142       acc+=del;
 143     }
 144     acc-=perarc/2;
 145   }
 146 }
 147
 148
 149 void arrange_verticies_mesh(graph *g, int width, int height){
 150   vertex *v = g->verticies;
 151   int bw=g->orig_width;
 152   int bh=g->orig_height;
 153   int spacing=min((float)bw/width,(float)bh/height)*.9;
 154   int x,y;
 155
 156   int xpad=(bw - (width-1)*spacing)/2;
 157   int ypad=(bh - (height-1)*spacing)/2;
 158
 159   for(y=0;y<height;y++){
 160     for(x=0;x<width;x++){
 161       v->x=x*spacing+xpad;
 162       v->y=y*spacing+ypad;
 163       v=v->next;
 164     }
 165   }
 166 }
 167
 168 void arrange_verticies_nastymesh(graph *g, int w, int h, vertex **flat){
 169   int A = 0;
 170   int B = w-1;
 171   int i;
 172
 173   arrange_verticies_mesh(g,w,h);
 174
 175   while(A<B){
 176     for(i=0;i<=A;i++){
 177       flat[i]->y-=10;
 178       flat[B+i]->y-=10;
 179
 180       flat[i+(h-1)*w]->y+=10;
 181       flat[B+i+(h-1)*w]->y+=10;
 182     }
 183     A++;
 184     B--;
 185   }
 186
 187   A = 0;
 188   B = (h-1)*w;
 189
 190   while(A<B){
 191     for(i=0;i<=A;i+=w){
 192       flat[i]->x-=10;
 193       flat[B+i]->x-=10;
 194
 195       flat[i  +(w-1)]->x+=10;
 196       flat[B+i+(w-1)]->x+=10;
 197
 198     }
 199     A+=w;
 200     B-=w;
 201   }
 202 }
 203
 204 void arrange_region_star(graph *g){
 205   region_init();
 206   region_new_area(400,45,1);
 207   region_line_to(340,232);
 208   region_line_to(143,232);
 209   region_line_to(303,347);
 210   region_line_to(241,533);
 211   region_line_to(400,417);
 212   region_line_to(559,533);
 213   region_line_to(497,347);
 214   region_line_to(657,232);
 215   region_line_to(460,232);
 216   region_close_line();
 217 }
 218
 219 void arrange_region_rainbow(graph *g){
 220   region_init();
 221   region_new_area(40,500,2);
 222   region_arc_to(760,500,-M_PI);
 223   region_line_to(660,500);
 224   region_arc_to(200,500,M_PI);
 225   region_close_line();
 226 }
 227
 228 void arrange_region_dashed_circle(graph *g){
 229   int bw=g->orig_width;
 230   int bh=g->orig_height;
 231   int radius=min(bw,bh)*.45;
 232   int i;
 233
 234   region_init();
 235
 236   for(i=0;i<20;i+=2){
 237     float phi0=(M_PI*2.f/20*(i-.5));
 238     float phi1=(M_PI*2.f/20*(i+.5));
 239     int x1=  cos(phi0)*radius+bw/2;
 240     int y1= -sin(phi0)*radius+bh/2;
 241     int x2=  cos(phi1)*radius+bw/2;
 242     int y2= -sin(phi1)*radius+bh/2;
 243     region_new_area(x1,y1,3);
 244     region_arc_to(x2,y2,M_PI/10);
 245   }
 246 }
 247
 248 void arrange_region_bifur(graph *g){
 249   int bw=g->orig_width;
 250   int bh=g->orig_height;
 251
 252   region_init();
 253   region_new_area(21,60,2);
 254   region_line_to(bw/2-130,60);
 255   region_arc_to(bw/2+130,60,-M_PI*.25);
 256   region_line_to(bw-21,60);
 257
 258   region_new_area(21,bh-60,1);
 259   region_line_to(bw/2-130,bh-60);
 260   region_arc_to(bw/2+130,bh-60,M_PI*.25);
 261   region_line_to(bw-21,bh-60);
 262 }
 263
 264 void arrange_region_dairyqueen(graph *g){
 265   int bw=g->orig_width;
 266   int bh=g->orig_height;
 267   int radius=min(bw,bh)*.45;
 268
 269   float phi0=(M_PI/2 + M_PI*2.f/8);
 270   float phi1=(M_PI/2 - M_PI*2.f/8);
 271
 272   int x1=  cos(phi0)*radius+bw/2;
 273   int x2=  cos(phi1)*radius+bw/2;
 274
 275   int y1= -sin(phi0)*radius+bh/2;
 276   int y2=  sin(phi0)*radius+bh/2;
 277
 278   region_init();
 279
 280   region_new_area(x1,y1,2);
 281   region_arc_to(x2,y1,-M_PI/2);
 282   region_line_to(750,bh/2);
 283   region_line_to(x2,y2);
 284   region_arc_to(x1,y2,-M_PI/2);
 285   region_line_to(50,bh/2);
 286   region_close_line();
 287 }
 288
 289 void arrange_region_cloud(graph *g){
 290   int bw=g->orig_width;
 291   int bh=g->orig_height;
 292   int radius=min(bw,bh)*.45-20;
 293   int i=0;
 294   float phi0=(M_PI*2.f/20*(i-.5)),phi1;
 295   int x1=  cos(phi0)*radius+bw/2,x2;
 296   int y1= -sin(phi0)*radius+bh/2,y2;
 297
 298   region_init();
 299   region_new_area(x1,y1,1);
 300   for(i=0;i<19;i++){
 301     phi1=(M_PI*2.f/20*(i+.5));
 302     x2=  cos(phi1)*radius+bw/2;
 303     y2= -sin(phi1)*radius+bh/2;
 304     region_arc_to(x2,y2,M_PI*.7);
 305   }
 306   region_close_arc(M_PI*.7);
 307 }
 308
 309 void arrange_region_ring(graph *g){
 310   int bw=g->orig_width;
 311   int bh=g->orig_height;
 312   int radius=min(bw,bh)*.45;
 313
 314   region_init();
 315   region_circle(bw/2,bh/2,radius,3);
 316   region_circle(bw/2,bh/2,radius*.4,1);
 317 }
 318
 319 void arrange_region_storm(graph *g){
 320   int bw=g->orig_width;
 321   int bh=g->orig_height;
 322   int radius=min(bw,bh)*.45;
 323   int i=0;
 324
 325   region_init();
 326
 327   for(i=0;i<10;i++){
 328     float phi0=(M_PI*2.f/10*(i-.5));
 329     float phi1=(M_PI*2.f/10*(i+.5));
 330     int x1=  cos(phi0)*radius+bw/2;
 331     int y1= -sin(phi0)*radius+bh/2;
 332     int x2=  cos(phi1)*radius*.8+bw/2;
 333     int y2= -sin(phi1)*radius*.8+bh/2;
 334
 335     region_new_area(x1,y1,1);
 336     region_arc_to(x2,y2,M_PI*.2);
 337   }
 338
 339   region_circle(bw/2,bh/2,radius*.2,0);
 340 }
 341
 342 void arrange_region_target(graph *g){
 343   int bw=g->orig_width;
 344   int bh=g->orig_height;
 345   int radius=min(bw,bh)*.45;
 346
 347   region_init();
 348   region_circle(bw/2,bh/2,radius,3);
 349   region_circle(bw/2,bh/2,radius*.5,1);
 350   region_split_here();
 351   region_circle(bw/2,bh/2,radius*.35,3);
 352 }
 353
 354 void arrange_region_plus(graph *g){
 355   region_init();
 356
 357   region_new_area(316,43,2);
 358   region_arc_to(483,43,-M_PI*2/10);
 359   region_line_to(483,216);
 360   region_line_to(656,216);
 361   region_arc_to(656,384,-M_PI*2/10);
 362   region_line_to(483,384);
 363   region_line_to(483,556);
 364   region_arc_to(316,556,-M_PI*2/10);
 365   region_line_to(316,384);
 366   region_line_to(143,384);
 367   region_arc_to(143,216,-M_PI*2/10);
 368   region_line_to(316,216);
 369   region_close_line();
 370 }
 371
 372 void arrange_region_hole3(graph *g){
 373   int bw=g->orig_width;
 374   int bh=g->orig_height;
 375   int radius=min(bw,bh)*.45;
 376
 377   region_init();
 378   region_circle(bw/2,bh/2,radius,3);
 379
 380   region_new_area(400,200,2);
 381   region_line_to(313,349);
 382   region_line_to(487,349);
 383   region_close_line();
 384 }
 385
 386 void arrange_region_hole4(graph *g){
 387   int bw=g->orig_width;
 388   int bh=g->orig_height;
 389   int radius=min(bw,bh)*.45;
 390
 391   region_init();
 392   region_circle(bw/2,bh/2,radius,3);
 393
 394   region_new_area(325,225,1);
 395   region_line_to(475,225);
 396   region_line_to(475,375);
 397   region_line_to(325,375);
 398   region_close_line();
 399 }
 400
 401 void arrange_region_ovals(graph *g){
 402
 403
 404   region_init();
 405   region_new_area(270,163,2);
 406   region_arc_to(530,163,-M_PI*.99);
 407   region_line_to(530,437);
 408   region_arc_to(270,437,-M_PI*.99);
 409   region_close_line();
 410   region_split_here();
 411
 412   region_new_area(80,263,2);
 413   region_arc_to(230,263,-M_PI*.99);
 414   region_line_to(230,337);
 415   region_arc_to(80,337,-M_PI*.99);
 416   region_close_line();
 417   region_split_here();
 418
 419   region_new_area(570,263,2);
 420   region_arc_to(720,263,-M_PI*.99);
 421   region_line_to(720,337);
 422   region_arc_to(570,337,-M_PI*.99);
 423   region_close_line();
 424   region_split_here();
 425 }