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 MultiplyPoly(Poly *p, double xm, double ym){
 188         int i;
 189         for(i=0; i< p->novec; i++){
 190                 p->v[i].x *= xm;
 191                 p->v[i].y *= ym;
 192         }
 193 }
 194
 195
 196 void PrintPoly(Poly *p){
 197         int i;
 198
 199         printf("NoV: %d\n", p->novec);
 200         for(i=0; i<p->novec; i++)
 201                 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]);
 202 }
 203
 204 /* format for saving poly into string:
 205  * space delimited values in ascii:
 206  * novec x y x y x y ...
 207  * */
 208 #define P2SBUFSIZE 64
 209 char *Poly2String(Poly *p){
 210         int i;
 211         char *buf;
 212         char *chain;
 213         int allocated;
 214
 215         buf = malloc(P2SBUFSIZE*sizeof(char));
 216         chain = 0;
 217
 218         snprintf(buf, P2SBUFSIZE, "%d ", p->novec);
 219         allocated = strlen(buf)+2;
 220         chain = malloc(allocated*sizeof(char));
 221         strcpy(chain, buf);
 222
 223         for(i=0; i<p->novec; i++){
 224                 snprintf(buf, P2SBUFSIZE, "%lf %lf ", p->v[i].x, p->v[i].y);
 225                 allocated += strlen(buf);
 226                 chain = realloc(chain, allocated*sizeof(char)); //TODO: check return value
 227                 sprintf(&chain[strlen(chain)],"%s", buf);
 228         }
 229
 230         free(buf);
 231         return chain;
 232 }
 233
 234 void FreePoly2String(char *s){
 235         free(s);
 236 }
 237
 238 Poly *String2Poly(char *s){
 239 //TODO: return values check, use strtok
 240         char *cur;
 241         Poly *p;
 242         int novec, i;
 243         double x,y;
 244
 245         p = NewPoly();
 246         sscanf(s, "%d", &novec);
 247         cur = s;
 248
 249         for(i=0; i<novec; i++){
 250                 cur = strchr(&cur[1], ' ');
 251                 sscanf(cur, "%lf", &x);
 252                 cur = strchr(&cur[1], ' ');
 253                 sscanf(cur, "%lf", &y);
 254                 AddToPolyXY(p, x, y);
 255         }
 256
 257         return p;
 258 }
 259
 260
 261 Area *NewArea(){
 262         Area *a;
 263
 264         a = malloc(sizeof(Area));
 265         a->nopol = 0;
 266         a->p = 0;
 267
 268         return a;
 269 }
 270
 271 void FreeArea(Area *a){
 272         int i;
 273
 274         if(a == 0)
 275                 return;
 276
 277         for(i=0; i< a->nopol; i++){
 278                 FreePoly(a->p[i]);
 279         }
 280
 281         a->nopol = 0;
 282         free(a->p);
 283         a->p = 0;
 284         free(a);
 285 }
 286
 287 int AddToArea(Area *a, Poly *p){
 288 //TODO: check for return values
 289         a->nopol += 1;
 290         a->p = realloc(a->p, sizeof(Poly *)*a->nopol);
 291         a->p[a->nopol-1] = TranslatePolyXY(p, 0, 0);
 292
 293         return true;
 294 }
 295
 296 int InArea(Area *a, Vect *v){
 297         int i;
 298         for(i=0; i<a->nopol; i++){
 299                 if(InPoly(a->p[i], v))
 300                         return true;
 301         }
 302         return false;
 303 }
 304
 305 int AreaInArea(Area *a1, Area *a2){
 306         int i,j;
 307
 308         if(a1 == 0 || a2==0)
 309                 return false;
 310
 311         for(i=0; i<a1->nopol; i++)
 312                 for(j=0; j<a2->nopol; j++)
 313                         if(PolyInPoly(a1->p[i], a2->p[j]))
 314                                 return true;
 315         return false;
 316 }
 317
 318 int AreaInAreaComp(Area *a1, Area *a2){
 319         //TODO: rewrite to correct behavior this is only sufficient behavior to current use in elilanci but not correct
 320         int i,j;
 321         int aia;
 322
 323         if(a1 == 0 || a2==0)
 324                 return false;
 325
 326         aia=true;
 327         for(i=0; i<a1->nopol; i++)
 328                 for(j=0; j<a2->nopol; j++){
 329                         if(!PolyInPolyComp(a1->p[i], a2->p[j]))
 330                                 aia =false;
 331                 }
 332         return aia;
 333 }
 334
 335 Area *TranslateAreaXY(Area *a, double x, double y){
 336         Area *new;
 337         Poly *p;
 338         int i;
 339
 340         new = NewArea();
 341         for(i=0; i< a->nopol; i++){
 342                 p = TranslatePolyXY(a->p[i], x, y);
 343                 AddToArea(new, p);
 344                 FreePoly(p);
 345         }
 346
 347         return new;
 348 }
 349
 350 Area *TranslateArea(Area *a, Vect *v){
 351         return TranslateAreaXY(a, v->x, v->y);
 352 }
 353
 354 void PrintArea(Area *a){
 355         //TODO:dopsat;
 356 }
 357
 358 char *Area2String(Area *a){
 359         int i,al;
 360         char *buf, *chain;
 361         chain = 0;
 362         buf = malloc(sizeof(char)* P2SBUFSIZE);
 363         snprintf(buf, P2SBUFSIZE, "%d\n", a->nopol);
 364         chain = strdup(buf);
 365         al = strlen(chain)+1;
 366         free(buf);
 367         for(i=0; i<a->nopol; i++){
 368                 buf = Poly2String(a->p[i]);
 369                 al += strlen(buf)+2; //+2 for \n
 370                 chain = realloc(chain, al);
 371                 sprintf(&chain[strlen(chain)], "%s\n", buf);
 372                 FreePoly2String(buf);
 373         }
 374         return chain;
 375 }
 376
 377 void FreeArea2String(char *s){
 378         free(s);
 379 }
 380
 381 Area *String2Area(char *s){
 382 //TODO: return values check
 383         char *cur;
 384         Poly *tp;
 385         Area *a;
 386         int nopol, i;
 387
 388         a = NewArea();
 389         sscanf(s, "%d", &nopol);
 390         cur = s;
 391
 392         for(i=0; i<nopol; i++){
 393                 cur = strstr(&cur[strlen("\n")], "\n"); //BUG: if strlen("\n")>1 && strlen(nopol)==1
 394                 tp = String2Poly(cur);
 395                 AddToArea(a, tp);
 396                 FreePoly(tp);
 397         }
 398
 399         return a;
 400 }
 401