geometry.c

   1 #include "geometry.h"
   2 #include "util.h"
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <math.h>
   6 #include <string.h>
   7
   8 void NormV(Vect *v){
   9         double length;
  10
  11         length = v->x*v->x+v->y*v->y;
  12         length = sqrt(length);
  13         v->x /= length;
  14         v->y /= length;
  15 }
  16
  17 void PrintVect(Vect *a){
  18         printf("[%lf, %lf]", a->x, a->y);
  19 }
  20
  21 double DotProduct(Vect *a, Vect *b){
  22         return a->x*b->x+a->y*b->y;
  23 }
  24
  25
  26 int InPoly(Poly *p, Vect *v){
  27         int i;
  28
  29         for(i=0; i<p->novec; i++){
  30                 if( DotProduct(v, &p->n[i]) >= p->a[i]) return false;
  31         }
  32
  33         return true;
  34 }
  35
  36
  37 Poly *NewPoly(){
  38         Poly *p;
  39
  40         p=malloc(sizeof(Poly));
  41         p->novec=p->alloc=0;
  42         p->a=0;
  43         p->n=0;
  44         p->v=0;
  45
  46         return p;
  47 };
  48
  49 int AddToPoly(Poly *p,Vect *v){
  50         if( p->novec > (p->alloc-1)){
  51                 if(p->alloc <1)
  52                         p->alloc=1;
  53                 Vect *tn;
  54                 double *ta;
  55                 Vect *tv;
  56                 tn = realloc(p->n, sizeof(Vect)*p->alloc*2);
  57                 tv = realloc(p->v, sizeof(Vect)*p->alloc*2);
  58                 if(tn==0 || tv == 0)
  59                         return false;
  60
  61                 p->n = tn;
  62                 p->v = tv;
  63
  64                 ta = realloc(p->a, sizeof(double)*p->alloc*2);
  65                 if(ta == 0)
  66                         return false;
  67                 p->a = ta;
  68
  69                 p->alloc *= 2;
  70         }
  71
  72         p->v[p->novec].x = v->x;
  73         p->v[p->novec].y = v->y;
  74
  75         if(p->novec){
  76                 //compute normal between actual and preceding
  77                 p->n[p->novec-1].x = -p->v[p->novec-1].y + p->v[p->novec].y;
  78                 p->n[p->novec-1].y = +p->v[p->novec-1].x - p->v[p->novec].x;
  79                 NormV(&p->n[p->novec-1]);
  80                 p->a[p->novec-1] = p->n[p->novec-1].x*v->x + p->n[p->novec-1].y*v->y;
  81
  82                 //compute normal between actual and first
  83                 p->n[p->novec].x = -p->v[p->novec].y + p->v[0].y;
  84                 p->n[p->novec].y = +p->v[p->novec].x - p->v[0].x;
  85                 NormV(&p->n[p->novec]);
  86                 p->a[p->novec] = p->n[p->novec].x*v->x + p->n[p->novec].y*v->y;
  87
  88         }
  89         p->novec++;
  90         return true;
  91 }
  92
  93 int AddToPolyXY(Poly *p, double x, double y){
  94         Vect v;
  95         v.x=x;
  96         v.y=y;
  97         return AddToPoly(p, &v);
  98 }
  99
 100 void FreePoly(Poly *p){
 101         if(p==0)return;
 102         free(p->v);
 103         p->v=0;
 104         free(p->n);
 105         p->n=0;
 106         free(p->a);
 107         p->a=0;
 108         free(p);
 109 }
 110
 111 Poly *NewRect(double x, double y, double xx, double yy){
 112         Poly *p;
 113
 114         p=NewPoly();
 115         AddToPolyXY(p, x, y);
 116         AddToPolyXY(p, x+xx, y);
 117         AddToPolyXY(p, x+xx, y+yy);
 118         AddToPolyXY(p, x, y+yy);
 119
 120         return p;
 121 }
 122
 123 int PolyInPoly(Poly *p1, Poly *p2){
 124         int cur1;
 125         int cur2;
 126
 127         //we check if any vertex of p1 is in p2
 128         for(cur1=0; cur1 < p1->novec; cur1++){
 129                 if(InPoly(p2, &p1->v[cur1])){
 130                         return true;
 131                 }
 132         }
 133
 134         //we check if any vertex of p1 is in p2
 135         for(cur2=0; cur2 < p2->novec; cur2++){
 136                 if(InPoly(p1, &p2->v[cur2])){
 137                         return true;
 138                 }
 139         }
 140
 141         return false;
 142 }
 143
 144 int PolyInPolyComp(Poly *p1, Poly *p2){
 145         int cur1;
 146         int in;
 147         int cur2;
 148
 149         //we check if every vertex of p1 is in p2
 150         in = true;
 151         for(cur1=0; cur1 < p1->novec; cur1++){
 152                 if(!InPoly(p2, &p1->v[cur1])){
 153                         in = false;
 154                 }
 155         }
 156         if(in)
 157                 return 1;
 158
 159         //we check if any vertex of p1 is in p2
 160         in = true;
 161         for(cur2=0; cur2 < p2->novec; cur2++){
 162                 if(!InPoly(p1, &p2->v[cur2])){
 163                         in = false;
 164                 }
 165         }
 166         if(in)
 167                 return 2;
 168
 169         return 0;
 170 }
 171
 172 Poly *TranslatePoly(Poly *p, Vect *v){
 173         return TranslatePolyXY(p, v->x, v->y);
 174 }
 175
 176 Poly *TranslatePolyXY(Poly *p, double x, double y){
 177         Poly *r;
 178         int i;
 179
 180         r=NewPoly();
 181         for(i=0; i< p->novec; i++){
 182                 AddToPolyXY(r, p->v[i].x+x, p->v[i].y+y);
 183         }
 184         return r;
 185 }
 186
 187 void PrintPoly(Poly *p){
 188         int i;
 189
 190         printf("NoV: %d\n", p->novec);
 191         for(i=0; i<p->novec; i++)
 192                 printf("[%lf, %lf] [%lf, %lf] %lf \n", p->v[i].x, p->v[i].y, p->n[i].x, p->n[i].y, p->a[i]);
 193 }
 194
 195 /* format for saving poly into string:
 196  * space delimited values in ascii:
 197  * novec x y x y x y ...
 198  * */
 199 #define P2SBUFSIZE 64
 200 char *Poly2String(Poly *p){
 201         int i;
 202         char *buf;
 203         char *chain, *pc;
 204         int allocated;
 205
 206         buf = malloc(P2SBUFSIZE*sizeof(char));
 207         chain = 0;
 208
 209         snprintf(buf, P2SBUFSIZE, "%d ", p->novec);
 210         allocated = strlen(buf)+2;
 211         chain = malloc(allocated*sizeof(char));
 212         strcpy(chain, buf);
 213
 214         for(i=0; i<p->novec; i++){
 215                 snprintf(buf, P2SBUFSIZE, "%lf %lf ", p->v[i].x, p->v[i].y);
 216                 allocated += strlen(buf);
 217                 chain = realloc(chain, allocated*sizeof(char)); //TODO: check return value
 218                 sprintf(&chain[strlen(chain)],"%s", buf);
 219         }
 220
 221         free(buf);
 222         return chain;
 223 }
 224
 225 void FreePoly2String(char *s){
 226         free(s);
 227 }
 228
 229 Poly *String2Poly(char *s){
 230 //TODO: return values check, use strtok
 231         char *cur;
 232         Poly *p;
 233         int novec, i;
 234         double x,y;
 235
 236         p = NewPoly();
 237         sscanf(s, "%d", &novec);
 238         cur = s;
 239
 240         for(i=0; i<novec; i++){
 241                 cur = strchr(&cur[1], ' ');
 242                 sscanf(cur, "%lf", &x);
 243                 cur = strchr(&cur[1], ' ');
 244                 sscanf(cur, "%lf", &y);
 245                 AddToPolyXY(p, x, y);
 246         }
 247
 248         return p;
 249 }
 250
 251
 252 Area *NewArea(){
 253         Area *a;
 254
 255         a = malloc(sizeof(Area));
 256         a->nopol = 0;
 257         a->p = 0;
 258
 259         return a;
 260 }
 261
 262 void FreeArea(Area *a){
 263         int i;
 264
 265         if(a == 0)
 266                 return;
 267
 268         for(i=0; i< a->nopol; i++){
 269                 FreePoly(a->p[i]);
 270         }
 271
 272         a->nopol = 0;
 273         free(a->p);
 274         a->p = 0;
 275 }
 276
 277 int AddToArea(Area *a, Poly *p){
 278 //TODO: check for return values
 279         Poly *tp;
 280         a->nopol += 1;
 281         a->p = realloc(a->p, sizeof(Poly *)*a->nopol);
 282         a->p[a->nopol-1] = TranslatePolyXY(p, 0, 0);
 283
 284         return true;
 285 }
 286
 287 int InArea(Area *a, Vect *v){
 288         int i;
 289         for(i=0; i<a->nopol; i++){
 290                 if(InPoly(a->p[i], v))
 291                         return true;
 292         }
 293         return false;
 294 }
 295
 296 int AreaInArea(Area *a1, Area *a2){
 297         int i,j;
 298
 299         if(a1 == 0 || a2==0)
 300                 return false;
 301
 302         for(i=0; i<a1->nopol; i++)
 303                 for(j=0; j<a2->nopol; j++)
 304                         if(PolyInPoly(a1->p[i], a2->p[j]))
 305                                 return true;
 306         return false;
 307 }
 308
 309 int AreaInAreaComp(Area *a1, Area *a2){
 310         //TODO: rewrite to correct behavior this is only sufficient behavior to current use in ebulanci but not correct
 311         int i,j;
 312         int aia;
 313
 314         if(a1 == 0 || a2==0)
 315                 return false;
 316
 317         aia=true;
 318         for(i=0; i<a1->nopol; i++)
 319                 for(j=0; j<a2->nopol; j++){
 320                         if(!PolyInPolyComp(a1->p[i], a2->p[j]))
 321                                 aia =false;
 322                 }
 323         return aia;
 324 }
 325
 326 Area *TranslateAreaXY(Area *a, double x, double y){
 327         Area *new;
 328         Poly *p;
 329         int i;
 330
 331         new = NewArea();
 332         for(i=0; i< a->nopol; i++){
 333                 p = TranslatePolyXY(a->p[i], x, y);
 334                 AddToArea(new, p);
 335                 FreePoly(p);
 336         }
 337
 338         return new;
 339 }
 340
 341 Area *TranslateArea(Area *a, Vect *v){
 342         return TranslateAreaXY(a, v->x, v->y);
 343 }
 344
 345 void PrintArea(Area *a){
 346         //TODO:dopsat;
 347 }
 348
 349 char *Area2String(Area *a){
 350         int i,al;
 351         char *buf, *chain;
 352         chain = 0;
 353         buf = malloc(sizeof(char)* P2SBUFSIZE);
 354         snprintf(buf, P2SBUFSIZE, "%d\n", a->nopol);
 355         chain = strdup(buf);
 356         al = strlen(chain)+1;
 357         free(buf);
 358         for(i=0; i<a->nopol; i++){
 359                 buf = Poly2String(a->p[i]);
 360                 al += strlen(buf)+2; //+2 for \n
 361                 chain = realloc(chain, al);
 362                 sprintf(&chain[strlen(chain)], "%s\n", buf);
 363                 FreePoly2String(buf);
 364         }
 365         return chain;
 366 }
 367
 368 void FreeArea2String(char *s){
 369         free(s);
 370 }
 371
 372 Area *String2Area(char *s){
 373 //TODO: return values check
 374         char *cur;
 375         Poly *tp;
 376         Area *a;
 377         int nopol, i;
 378
 379         a = NewArea();
 380         sscanf(s, "%d", &nopol);
 381         cur = s;
 382
 383         for(i=0; i<nopol; i++){
 384                 cur = strstr(&cur[strlen("\n")], "\n"); //BUG: if strlen("\n")>1 && strlen(nopol)==1
 385                 tp = String2Poly(cur);
 386                 AddToArea(a, tp);
 387                 FreePoly(tp);
 388         }
 389
 390         return a;
 391 }
 392