source/algorithm/RobustLineIntersector.cpp

   1 /**********************************************************************
   2  * $Id$
   3  *
   4  * GEOS - Geometry Engine Open Source
   5  * http://geos.refractions.net
   6  *
   7  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   8  *
   9  * This is free software; you can redistribute and/or modify it under
  10  * the terms of the GNU Lesser General Public Licence as published
  11  * by the Free Software Foundation.
  12  * See the COPYING file for more information.
  13  *
  14  **********************************************************************/
  15
  16 #include <geos/geosAlgorithm.h>
  17 #include <geos/util.h>
  18
  19 //#define DEBUG 1
  20
  21 #ifndef COMPUTE_Z
  22 #define COMPUTE_Z 1
  23 #endif // COMPUTE_Z
  24
  25 namespace geos {
  26 namespace algorithm { // geos.algorithm
  27
  28 RobustLineIntersector::RobustLineIntersector(){}
  29 RobustLineIntersector::~RobustLineIntersector(){}
  30
  31 void
  32 RobustLineIntersector::computeIntersection(const Coordinate& p,const Coordinate& p1,const Coordinate& p2)
  33 {
  34         isProperVar=false;
  35
  36         // do between check first, since it is faster than the orientation test
  37         if(Envelope::intersects(p1,p2,p)) {
  38                 if ((CGAlgorithms::orientationIndex(p1,p2,p)==0)&&
  39                         (CGAlgorithms::orientationIndex(p2,p1,p)==0)) {
  40                         isProperVar=true;
  41                         if ((p==p1)||(p==p2)) // 2d only test
  42                         {
  43                                 isProperVar=false;
  44                         }
  45 #if COMPUTE_Z
  46                         intPt[0].setCoordinate(p);
  47 #if DEBUG
  48                         cerr<<"RobustIntersector::computeIntersection(Coordinate,Coordinate,Coordinate) calling interpolateZ"<<endl;
  49 #endif
  50                         double z = interpolateZ(p, p1, p2);
  51                         if ( !ISNAN(z) )
  52                         {
  53                                 if ( ISNAN(intPt[0].z) )
  54                                         intPt[0].z = z;
  55                                 else
  56                                         intPt[0].z = (intPt[0].z+z)/2;
  57                         }
  58 #endif // COMPUTE_Z
  59                         result=DO_INTERSECT;
  60                         return;
  61                 }
  62         }
  63         result = DONT_INTERSECT;
  64 }
  65
  66 int
  67 RobustLineIntersector::computeIntersect(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2)
  68 {
  69 #if DEBUG
  70         cerr<<"RobustLineIntersector::computeIntersect called"<<endl;
  71         cerr<<" p1:"<<p1.toString()<<" p2:"<<p2.toString()<<" q1:"<<q1.toString()<<" q2:"<<q2.toString()<<endl;
  72 #endif // DEBUG
  73
  74         isProperVar=false;
  75
  76         // first try a fast test to see if the envelopes of the lines intersect
  77         if (!Envelope::intersects(p1,p2,q1,q2))
  78         {
  79 #if DEBUG
  80                 cerr<<" DONT_INTERSECT"<<endl;
  81 #endif
  82                 return DONT_INTERSECT;
  83         }
  84
  85         // for each endpoint, compute which side of the other segment it lies
  86         // if both endpoints lie on the same side of the other segment,
  87         // the segments do not intersect
  88         int Pq1=CGAlgorithms::orientationIndex(p1,p2,q1);
  89         int Pq2=CGAlgorithms::orientationIndex(p1,p2,q2);
  90
  91         if ((Pq1>0 && Pq2>0) || (Pq1<0 && Pq2<0))
  92         {
  93 #if DEBUG
  94                 cerr<<" DONT_INTERSECT"<<endl;
  95 #endif
  96                 return DONT_INTERSECT;
  97         }
  98
  99         int Qp1=CGAlgorithms::orientationIndex(q1,q2,p1);
 100         int Qp2=CGAlgorithms::orientationIndex(q1,q2,p2);
 101
 102         if ((Qp1>0 && Qp2>0)||(Qp1<0 && Qp2<0)) {
 103 #if DEBUG
 104                 cerr<<" DONT_INTERSECT"<<endl;
 105 #endif
 106                 return DONT_INTERSECT;
 107         }
 108
 109         bool collinear=Pq1==0 && Pq2==0 && Qp1==0 && Qp2==0;
 110         if (collinear) {
 111 #if DEBUG
 112                 cerr<<" computingCollinearIntersection"<<endl;
 113 #endif
 114                 return computeCollinearIntersection(p1,p2,q1,q2);
 115         }
 116
 117         /*
 118          * Check if the intersection is an endpoint.
 119          * If it is, copy the endpoint as
 120          * the intersection point. Copying the point rather than
 121          * computing it ensures the point has the exact value,
 122          * which is important for robustness. It is sufficient to
 123          * simply check for an endpoint which is on the other line,
 124          * since at this point we know that the inputLines must
 125          *  intersect.
 126          */
 127         if (Pq1==0 || Pq2==0 || Qp1==0 || Qp2==0) {
 128 #if COMPUTE_Z
 129                 int hits=0;
 130                 double z=0.0;
 131 #endif
 132                 isProperVar=false;
 133                 if (Pq1==0) {
 134                         intPt[0].setCoordinate(q1);
 135 #if COMPUTE_Z
 136                         if ( !ISNAN(q1.z) )
 137                         {
 138                                 z += q1.z;
 139                                 hits++;
 140                         }
 141 #endif
 142                 }
 143                 if (Pq2==0) {
 144                         intPt[0].setCoordinate(q2);
 145 #if COMPUTE_Z
 146                         if ( !ISNAN(q2.z) )
 147                         {
 148                                 z += q2.z;
 149                                 hits++;
 150                         }
 151 #endif
 152                 }
 153                 if (Qp1==0) {
 154                         intPt[0].setCoordinate(p1);
 155 #if COMPUTE_Z
 156                         if ( !ISNAN(p1.z) )
 157                         {
 158                                 z += p1.z;
 159                                 hits++;
 160                         }
 161 #endif
 162                 }
 163                 if (Qp2==0) {
 164                         intPt[0].setCoordinate(p2);
 165 #if COMPUTE_Z
 166                         if ( !ISNAN(p2.z) )
 167                         {
 168                                 z += p2.z;
 169                                 hits++;
 170                         }
 171 #endif
 172                 }
 173 #if COMPUTE_Z
 174 #if DEBUG
 175                 cerr<<"RobustLineIntersector::computeIntersect: z:"<<z<<" hits:"<<hits<<endl;
 176 #endif // DEBUG
 177                 if ( hits ) intPt[0].z = z/hits;
 178 #endif // COMPUTE_Z
 179         } else {
 180                 isProperVar=true;
 181                 Coordinate *c=intersection(p1, p2, q1, q2);
 182                 intPt[0].setCoordinate(*c);
 183                 delete c;
 184         }
 185 #if DEBUG
 186         cerr<<" DO_INTERSECT; intPt[0]:"<<intPt[0].toString()<<endl;
 187 #endif // DEBUG
 188         return DO_INTERSECT;
 189 }
 190
 191 //bool RobustLineIntersector::intersectsEnvelope(Coordinate& p1,Coordinate& p2,Coordinate& q) {
 192 //      if (((q.x>=min(p1.x,p2.x)) && (q.x<=max(p1.x,p2.x))) &&
 193 //              ((q.y>=min(p1.y,p2.y)) && (q.y<=max(p1.y,p2.y)))) {
 194 //                      return true;
 195 //      } else {
 196 //              return false;
 197 //      }
 198 //}
 199
 200 int
 201 RobustLineIntersector::computeCollinearIntersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2)
 202 {
 203 #if COMPUTE_Z
 204         double ztot;
 205         int hits;
 206         double p2z;
 207         double p1z;
 208         double q1z;
 209         double q2z;
 210 #endif // COMPUTE_Z
 211
 212 #if DEBUG
 213         cerr<<"RobustLineIntersector::computeCollinearIntersection called"<<endl;
 214         cerr<<" p1:"<<p1.toString()<<" p2:"<<p2.toString()<<" q1:"<<q1.toString()<<" q2:"<<q2.toString()<<endl;
 215 #endif // DEBUG
 216
 217         bool p1q1p2=Envelope::intersects(p1,p2,q1);
 218         bool p1q2p2=Envelope::intersects(p1,p2,q2);
 219         bool q1p1q2=Envelope::intersects(q1,q2,p1);
 220         bool q1p2q2=Envelope::intersects(q1,q2,p2);
 221
 222         if (p1q1p2 && p1q2p2) {
 223 #if DEBUG
 224                 cerr<<" p1q1p2 && p1q2p2"<<endl;
 225 #endif
 226                 intPt[0].setCoordinate(q1);
 227 #if COMPUTE_Z
 228                 ztot=0;
 229                 hits=0;
 230                 q1z = interpolateZ(q1, p1, p2);
 231                 if (!ISNAN(q1z)) { ztot+=q1z; hits++; }
 232                 if (!ISNAN(q1.z)) { ztot+=q1.z; hits++; }
 233                 if ( hits ) intPt[0].z = ztot/hits;
 234 #endif
 235                 intPt[1].setCoordinate(q2);
 236 #if COMPUTE_Z
 237                 ztot=0;
 238                 hits=0;
 239                 q2z = interpolateZ(q2, p1, p2);
 240                 if (!ISNAN(q2z)) { ztot+=q2z; hits++; }
 241                 if (!ISNAN(q2.z)) { ztot+=q2.z; hits++; }
 242                 if ( hits ) intPt[1].z = ztot/hits;
 243 #endif
 244 #if DEBUG
 245                 cerr<<" intPt[0]: "<<intPt[0].toString()<<endl;
 246                 cerr<<" intPt[1]: "<<intPt[1].toString()<<endl;
 247 #endif
 248                 return COLLINEAR;
 249         }
 250         if (q1p1q2 && q1p2q2) {
 251 #if DEBUG
 252                 cerr<<" q1p1q2 && q1p2q2"<<endl;
 253 #endif
 254                 intPt[0].setCoordinate(p1);
 255 #if COMPUTE_Z
 256                 ztot=0;
 257                 hits=0;
 258                 p1z = interpolateZ(p1, q1, q2);
 259                 if (!ISNAN(p1z)) { ztot+=p1z; hits++; }
 260                 if (!ISNAN(p1.z)) { ztot+=p1.z; hits++; }
 261                 if ( hits ) intPt[0].z = ztot/hits;
 262 #endif
 263                 intPt[1].setCoordinate(p2);
 264 #if COMPUTE_Z
 265                 ztot=0;
 266                 hits=0;
 267                 p2z = interpolateZ(p2, q1, q2);
 268                 if (!ISNAN(p2z)) { ztot+=p2z; hits++; }
 269                 if (!ISNAN(p2.z)) { ztot+=p2.z; hits++; }
 270                 if ( hits ) intPt[1].z = ztot/hits;
 271 #endif
 272                 return COLLINEAR;
 273         }
 274         if (p1q1p2 && q1p1q2) {
 275 #if DEBUG
 276                 cerr<<" p1q1p2 && q1p1q2"<<endl;
 277 #endif
 278                 intPt[0].setCoordinate(q1);
 279 #if COMPUTE_Z
 280                 ztot=0;
 281                 hits=0;
 282                 q1z = interpolateZ(q1, p1, p2);
 283                 if (!ISNAN(q1z)) { ztot+=q1z; hits++; }
 284                 if (!ISNAN(q1.z)) { ztot+=q1.z; hits++; }
 285                 if ( hits ) intPt[0].z = ztot/hits;
 286 #endif
 287                 intPt[1].setCoordinate(p1);
 288 #if COMPUTE_Z
 289                 ztot=0;
 290                 hits=0;
 291                 p1z = interpolateZ(p1, q1, q2);
 292                 if (!ISNAN(p1z)) { ztot+=p1z; hits++; }
 293                 if (!ISNAN(p1.z)) { ztot+=p1.z; hits++; }
 294                 if ( hits ) intPt[1].z = ztot/hits;
 295 #endif
 296 #if DEBUG
 297                 cerr<<" intPt[0]: "<<intPt[0].toString()<<endl;
 298                 cerr<<" intPt[1]: "<<intPt[1].toString()<<endl;
 299 #endif
 300                 return (q1==p1) && !p1q2p2 && !q1p2q2 ? DO_INTERSECT : COLLINEAR;
 301         }
 302         if (p1q1p2 && q1p2q2) {
 303 #if DEBUG
 304                 cerr<<" p1q1p2 && q1p2q2"<<endl;
 305 #endif
 306                 intPt[0].setCoordinate(q1);
 307 #if COMPUTE_Z
 308                 ztot=0;
 309                 hits=0;
 310                 q1z = interpolateZ(q1, p1, p2);
 311                 if (!ISNAN(q1z)) { ztot+=q1z; hits++; }
 312                 if (!ISNAN(q1.z)) { ztot+=q1.z; hits++; }
 313                 if ( hits ) intPt[0].z = ztot/hits;
 314 #endif
 315                 intPt[1].setCoordinate(p2);
 316 #if COMPUTE_Z
 317                 ztot=0;
 318                 hits=0;
 319                 p2z = interpolateZ(p2, q1, q2);
 320                 if (!ISNAN(p2z)) { ztot+=p2z; hits++; }
 321                 if (!ISNAN(p2.z)) { ztot+=p2.z; hits++; }
 322                 if ( hits ) intPt[1].z = ztot/hits;
 323 #endif
 324 #if DEBUG
 325                 cerr<<" intPt[0]: "<<intPt[0].toString()<<endl;
 326                 cerr<<" intPt[1]: "<<intPt[1].toString()<<endl;
 327 #endif
 328                 return (q1==p2) && !p1q2p2 && !q1p1q2 ? DO_INTERSECT : COLLINEAR;
 329         }
 330         if (p1q2p2 && q1p1q2) {
 331 #if DEBUG
 332                 cerr<<" p1q2p2 && q1p1q2"<<endl;
 333 #endif
 334                 intPt[0].setCoordinate(q2);
 335 #if COMPUTE_Z
 336                 ztot=0;
 337                 hits=0;
 338                 q2z = interpolateZ(q2, p1, p2);
 339                 if (!ISNAN(q2z)) { ztot+=q2z; hits++; }
 340                 if (!ISNAN(q2.z)) { ztot+=q2.z; hits++; }
 341                 if ( hits ) intPt[0].z = ztot/hits;
 342 #endif
 343                 intPt[1].setCoordinate(p1);
 344 #if COMPUTE_Z
 345                 ztot=0;
 346                 hits=0;
 347                 p1z = interpolateZ(p1, q1, q2);
 348                 if (!ISNAN(p1z)) { ztot+=p1z; hits++; }
 349                 if (!ISNAN(p1.z)) { ztot+=p1.z; hits++; }
 350                 if ( hits ) intPt[1].z = ztot/hits;
 351 #endif
 352 #if DEBUG
 353                 cerr<<" intPt[0]: "<<intPt[0].toString()<<endl;
 354                 cerr<<" intPt[1]: "<<intPt[1].toString()<<endl;
 355 #endif
 356                 return (q2==p1) && !p1q1p2 && !q1p2q2 ? DO_INTERSECT : COLLINEAR;
 357         }
 358         if (p1q2p2 && q1p2q2) {
 359 #if DEBUG
 360                 cerr<<" p1q2p2 && q1p2q2"<<endl;
 361 #endif
 362                 intPt[0].setCoordinate(q2);
 363 #if COMPUTE_Z
 364                 ztot=0;
 365                 hits=0;
 366                 q2z = interpolateZ(q2, p1, p2);
 367                 if (!ISNAN(q2z)) { ztot+=q2z; hits++; }
 368                 if (!ISNAN(q2.z)) { ztot+=q2.z; hits++; }
 369                 if ( hits ) intPt[0].z = ztot/hits;
 370 #endif
 371                 intPt[1].setCoordinate(p2);
 372 #if COMPUTE_Z
 373                 ztot=0;
 374                 hits=0;
 375                 p2z = interpolateZ(p2, q1, q2);
 376                 if (!ISNAN(p2z)) { ztot+=p2z; hits++; }
 377                 if (!ISNAN(p2.z)) { ztot+=p2.z; hits++; }
 378                 if ( hits ) intPt[1].z = ztot/hits;
 379 #endif
 380 #if DEBUG
 381                 cerr<<" intPt[0]: "<<intPt[0].toString()<<endl;
 382                 cerr<<" intPt[1]: "<<intPt[1].toString()<<endl;
 383 #endif
 384                 return (q2==p2) && !p1q1p2 && !q1p1q2 ? DO_INTERSECT : COLLINEAR;
 385         }
 386         return DONT_INTERSECT;
 387 }
 388
 389 Coordinate*
 390 RobustLineIntersector::intersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2) const
 391 {
 392         Coordinate n1=p1;
 393         Coordinate n2=p2;
 394         Coordinate n3=q1;
 395         Coordinate n4=q2;
 396         Coordinate normPt;
 397
 398         //normalize(&n1, &n2, &n3, &n4, &normPt);
 399         normalizeToEnvCentre(n1, n2, n3, n4, normPt);
 400
 401         Coordinate *intPt=NULL;
 402
 403 #if DEBUG
 404         cerr<<"RobustIntersector::intersection(p1,p2,q1,q2) called:"<<endl;
 405         cerr<<" p1"<<p1.toString()<<endl;
 406         cerr<<" p2"<<p2.toString()<<endl;
 407         cerr<<" q1"<<q1.toString()<<endl;
 408         cerr<<" q2"<<q2.toString()<<endl;
 409
 410         cerr<<" n1"<<n1.toString()<<endl;
 411         cerr<<" n2"<<n2.toString()<<endl;
 412         cerr<<" n3"<<n3.toString()<<endl;
 413         cerr<<" n4"<<n4.toString()<<endl;
 414 #endif
 415
 416         try {
 417                 intPt=HCoordinate::intersection(n1,n2,n3,n4);
 418 #if DEBUG
 419                 cerr<<" HCoordinate found intersection h:"<<h->toString()<<endl;
 420 #endif
 421
 422         } catch (const NotRepresentableException& e) {
 423                 delete intPt;
 424                 Assert::shouldNeverReachHere("Coordinate for intersection is not calculable"+e.toString());
 425         }
 426
 427         intPt->x+=normPt.x;
 428         intPt->y+=normPt.y;
 429
 430 /**
 431  *
 432  * MD - May 4 2005 - This is still a problem.  Here is a failure case:
 433  *
 434  * LINESTRING (2089426.5233462777 1180182.3877339689,
 435  *             2085646.6891757075 1195618.7333999649)
 436  * LINESTRING (1889281.8148903656 1997547.0560044837,
 437  *             2259977.3672235999 483675.17050843034)
 438  * int point = (2097408.2633752143,1144595.8008114607)
 439  */
 440
 441 #if DEBUG
 442         if (! isInSegmentEnvelopes(intPt))
 443         {
 444                 cerr<<"Intersection outside segment envelopes: "<<
 445                         intPt->toString();
 446         }
 447 #endif
 448
 449         if (precisionModel!=NULL) precisionModel->makePrecise(intPt);
 450
 451
 452 #if COMPUTE_Z
 453         double ztot = 0;
 454         double zvals = 0;
 455         double zp = interpolateZ(*intPt, p1, p2);
 456         double zq = interpolateZ(*intPt, q1, q2);
 457         if ( !ISNAN(zp)) { ztot += zp; zvals++; }
 458         if ( !ISNAN(zq)) { ztot += zq; zvals++; }
 459         if ( zvals ) intPt->z = ztot/zvals;
 460 #endif // COMPUTE_Z
 461
 462         return intPt;
 463 }
 464
 465
 466 void
 467 RobustLineIntersector::normalize(Coordinate *n1,Coordinate *n2,Coordinate *n3,Coordinate *n4,Coordinate *normPt) const
 468 {
 469         normPt->x=smallestInAbsValue(n1->x,n2->x,n3->x,n4->x);
 470         normPt->y=smallestInAbsValue(n1->y,n2->y,n3->y,n4->y);
 471         n1->x-=normPt->x;
 472         n1->y-=normPt->y;
 473         n2->x-=normPt->x;
 474         n2->y-=normPt->y;
 475         n3->x-=normPt->x;
 476         n3->y-=normPt->y;
 477         n4->x-=normPt->x;
 478         n4->y-=normPt->y;
 479
 480 #if COMPUTE_Z
 481         normPt->z=smallestInAbsValue(n1->z,n2->z,n3->z,n4->z);
 482         n1->z-=normPt->z;
 483         n2->z-=normPt->z;
 484         n3->z-=normPt->z;
 485         n4->z-=normPt->z;
 486 #endif
 487 }
 488
 489 double
 490 RobustLineIntersector::smallestInAbsValue(double x1,double x2,double x3,double x4) const
 491 {
 492         double x=x1;
 493         double xabs=fabs(x);
 494         if(fabs(x2)<xabs) {
 495                 x=x2;
 496                 xabs=fabs(x2);
 497         }
 498         if(fabs(x3)<xabs) {
 499                 x=x3;
 500                 xabs=fabs(x3);
 501         }
 502         if(fabs(x4)<xabs) {
 503                 x=x4;
 504         }
 505         return x;
 506 }
 507
 508 /*
 509  * Test whether a point lies in the envelopes of both input segments.
 510  * A correctly computed intersection point should return <code>true</code>
 511  * for this test.
 512  * Since this test is for debugging purposes only, no attempt is
 513  * made to optimize the envelope test.
 514  *
 515  * @return <code>true</code> if the input point lies within both input
 516  *      segment envelopes
 517  */
 518 bool
 519 RobustLineIntersector::isInSegmentEnvelopes(const Coordinate& intPt)
 520 {
 521         Envelope *env0=new Envelope(*inputLines[0][0], *inputLines[0][1]);
 522         Envelope *env1=new Envelope(*inputLines[1][0], *inputLines[1][1]);
 523         return env0->contains(intPt) && env1->contains(intPt);
 524 }
 525
 526 void
 527 RobustLineIntersector::normalizeToEnvCentre(Coordinate &n00, Coordinate &n01,
 528                 Coordinate &n10, Coordinate &n11, Coordinate &normPt) const
 529 {
 530         double minX0 = n00.x < n01.x ? n00.x : n01.x;
 531         double minY0 = n00.y < n01.y ? n00.y : n01.y;
 532         double maxX0 = n00.x > n01.x ? n00.x : n01.x;
 533         double maxY0 = n00.y > n01.y ? n00.y : n01.y;
 534
 535         double minX1 = n10.x < n11.x ? n10.x : n11.x;
 536         double minY1 = n10.y < n11.y ? n10.y : n11.y;
 537         double maxX1 = n10.x > n11.x ? n10.x : n11.x;
 538         double maxY1 = n10.y > n11.y ? n10.y : n11.y;
 539
 540         double intMinX = minX0 > minX1 ? minX0 : minX1;
 541         double intMaxX = maxX0 < maxX1 ? maxX0 : maxX1;
 542         double intMinY = minY0 > minY1 ? minY0 : minY1;
 543         double intMaxY = maxY0 < maxY1 ? maxY0 : maxY1;
 544
 545         double intMidX = (intMinX + intMaxX) / 2.0;
 546         double intMidY = (intMinY + intMaxY) / 2.0;
 547
 548         normPt.x = intMidX;
 549         normPt.y = intMidY;
 550
 551         n00.x -= normPt.x;    n00.y -= normPt.y;
 552         n01.x -= normPt.x;    n01.y -= normPt.y;
 553         n10.x -= normPt.x;    n10.y -= normPt.y;
 554         n11.x -= normPt.x;    n11.y -= normPt.y;
 555
 556 #if COMPUTE_Z
 557         double minZ0 = n00.z < n01.z ? n00.z : n01.z;
 558         double minZ1 = n10.z < n11.z ? n10.z : n11.z;
 559         double maxZ0 = n00.z > n01.z ? n00.z : n01.z;
 560         double maxZ1 = n10.z > n11.z ? n10.z : n11.z;
 561         double intMinZ = minZ0 > minZ1 ? minZ0 : minZ1;
 562         double intMaxZ = maxZ0 < maxZ1 ? maxZ0 : maxZ1;
 563         double intMidZ = (intMinZ + intMaxZ) / 2.0;
 564         normPt.z = intMidZ;
 565         n00.z -= normPt.z;
 566         n01.z -= normPt.z;
 567         n10.z -= normPt.z;
 568         n11.z -= normPt.z;
 569 #endif
 570 }
 571
 572 } // namespace geos.algorithm
 573 } // namespace geos
 574
 575 /**********************************************************************
 576  * $Log$
 577  * Revision 1.36  2006/03/21 11:12:23  strk
 578  * Cleanups: headers inclusion and Log section
 579  *
 580  * Revision 1.35  2006/02/19 19:46:49  strk
 581  * Packages <-> namespaces mapping for most GEOS internal code (uncomplete, but working). Dir-level libs for index/ subdirs.
 582  **********************************************************************/