src/geom/CoordinateSequence.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2006 Refractions Research Inc.
   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/profiler.h>
  17 #include <geos/geom/CoordinateSequence.h>
  18 // FIXME: we should probably not be using CoordinateArraySequenceFactory
  19 #include <geos/geom/CoordinateArraySequenceFactory.h>
  20 #include <geos/geom/Coordinate.h>
  21 #include <geos/geom/Envelope.h>
  22
  23 #include <cstdio>
  24 #include <algorithm>
  25 #include <vector>
  26 #include <cassert>
  27 #include <iterator>
  28
  29 using namespace std;
  30
  31 namespace geos {
  32 namespace geom { // geos::geom
  33
  34 #if PROFILE
  35 static Profiler *profiler = Profiler::instance();
  36 #endif
  37
  38 bool
  39 CoordinateSequence::hasRepeatedPoints() const
  40 {
  41     const std::size_t size=getSize();
  42         for(std::size_t i=1; i<size; i++) {
  43                 if (getAt(i-1)==getAt(i)) {
  44                         return true;
  45                 }
  46         }
  47         return false;
  48 }
  49
  50 /*
  51  * Returns either the given coordinate array if its length is greater than the
  52  * given amount, or an empty coordinate array.
  53  */
  54 CoordinateSequence *
  55 CoordinateSequence::atLeastNCoordinatesOrNothing(size_t n,
  56                 CoordinateSequence *c)
  57 {
  58         if ( c->getSize() >= n )
  59         {
  60                 return c;
  61         }
  62         else
  63         {
  64                 // FIXME: return NULL rather then empty coordinate array
  65                 return CoordinateArraySequenceFactory::instance()->create(NULL);
  66         }
  67 }
  68
  69
  70 bool
  71 CoordinateSequence::hasRepeatedPoints(const CoordinateSequence *cl)
  72 {
  73         const std::size_t size=cl->getSize();
  74         for(std::size_t i=1;i<size; i++) {
  75                 if (cl->getAt(i-1)==cl->getAt(i)) {
  76                         return true;
  77                 }
  78         }
  79         return false;
  80 }
  81
  82 const Coordinate*
  83 CoordinateSequence::minCoordinate() const
  84 {
  85         const Coordinate* minCoord=NULL;
  86         const std::size_t size=getSize();
  87         for(std::size_t i=0; i<size; i++) {
  88                 if(minCoord==NULL || minCoord->compareTo(getAt(i))>0) {
  89                         minCoord=&getAt(i);
  90                 }
  91         }
  92         return minCoord;
  93 }
  94
  95 const Coordinate*
  96 CoordinateSequence::minCoordinate(CoordinateSequence *cl)
  97 {
  98         const Coordinate* minCoord=NULL;
  99         const std::size_t size=cl->getSize();
 100         for(std::size_t i=0;i<size; i++) {
 101                 if(minCoord==NULL || minCoord->compareTo(cl->getAt(i))>0) {
 102                         minCoord=&(cl->getAt(i));
 103                 }
 104         }
 105         return minCoord;
 106 }
 107
 108 int
 109 CoordinateSequence::indexOf(const Coordinate *coordinate,
 110                 const CoordinateSequence *cl)
 111 {
 112         size_t size=cl->getSize();
 113         for (size_t i=0; i<size; ++i)
 114         {
 115                 if ((*coordinate)==cl->getAt(i))
 116                 {
 117                         return static_cast<int>(i); // FIXME: what if we overflow the int ?
 118                 }
 119         }
 120         return -1;
 121 }
 122
 123 void
 124 CoordinateSequence::scroll(CoordinateSequence* cl,
 125                 const Coordinate* firstCoordinate)
 126 {
 127         // FIXME: use a standard algorithm instead
 128         std::size_t i, j=0;
 129         std::size_t ind=indexOf(firstCoordinate,cl);
 130         if (ind<1)
 131         return; // not found or already first
 132
 133         const std::size_t length=cl->getSize();
 134         vector<Coordinate> v(length);
 135         for (i=ind; i<length; i++) {
 136                 v[j++]=cl->getAt(i);
 137         }
 138         for (i=0; i<ind; i++) {
 139                 v[j++]=cl->getAt(i);
 140         }
 141         cl->setPoints(v);
 142 }
 143
 144 int
 145 CoordinateSequence::increasingDirection(const CoordinateSequence& pts)
 146 {
 147         size_t ptsize = pts.size();
 148         for (size_t i=0, n=ptsize/2; i<n; ++i)
 149         {
 150                 size_t j = ptsize - 1 - i;
 151                 // skip equal points on both ends
 152                 int comp = pts[i].compareTo(pts[j]);
 153                 if (comp != 0) return comp;
 154         }
 155         // array must be a palindrome - defined to be in positive direction
 156         return 1;
 157 }
 158
 159 void
 160 CoordinateSequence::reverse(CoordinateSequence *cl)
 161 {
 162
 163         // FIXME: use a standard algorithm
 164         int last = static_cast<int>(cl->getSize()) - 1;
 165         int mid=last/2;
 166         for(int i=0;i<=mid;i++) {
 167                 const Coordinate tmp=cl->getAt(i);
 168                 cl->setAt(cl->getAt(last-i),i);
 169                 cl->setAt(tmp,last-i);
 170         }
 171 }
 172
 173 bool
 174 CoordinateSequence::equals(const CoordinateSequence *cl1,
 175                 const CoordinateSequence *cl2)
 176 {
 177         // FIXME: use std::equals()
 178
 179         if (cl1==cl2) return true;
 180         if (cl1==NULL||cl2==NULL) return false;
 181         size_t npts1=cl1->getSize();
 182         if (npts1!=cl2->getSize()) return false;
 183         for (size_t i=0; i<npts1; i++) {
 184                 if (!(cl1->getAt(i)==cl2->getAt(i))) return false;
 185         }
 186         return true;
 187 }
 188
 189 /*public*/
 190 void
 191 CoordinateSequence::add(const vector<Coordinate>* vc, bool allowRepeated)
 192 {
 193         assert(vc);
 194         for(size_t i=0; i<vc->size(); ++i)
 195         {
 196                 add((*vc)[i], allowRepeated);
 197         }
 198 }
 199
 200 /*public*/
 201 void
 202 CoordinateSequence::add(const Coordinate& c, bool allowRepeated)
 203 {
 204         if (!allowRepeated) {
 205         std::size_t npts=getSize();
 206                 if (npts>=1) {
 207                         const Coordinate& last=getAt(npts-1);
 208                         if (last.equals2D(c))
 209                 return;
 210                 }
 211         }
 212         add(c);
 213 }
 214
 215 /* Here for backward compatibility */
 216 //void
 217 //CoordinateSequence::add(CoordinateSequence *cl, bool allowRepeated,
 218 //              bool direction)
 219 //{
 220 //      add(cl, allowRepeated, direction);
 221 //}
 222
 223 /*public*/
 224 void
 225 CoordinateSequence::add(const CoordinateSequence *cl,
 226                 bool allowRepeated, bool direction)
 227 {
 228         // FIXME:  don't rely on negative values for 'j' (the reverse case)
 229
 230         const int npts = static_cast<int>(cl->getSize());
 231         if (direction) {
 232                 for (int i=0; i<npts; i++) {
 233                         add(cl->getAt(i), allowRepeated);
 234                 }
 235         } else {
 236                 for (int j=npts-1; j>=0; j--) {
 237                         add(cl->getAt(j), allowRepeated);
 238                 }
 239         }
 240 }
 241
 242
 243 /*public static*/
 244 CoordinateSequence*
 245 CoordinateSequence::removeRepeatedPoints(const CoordinateSequence *cl)
 246 {
 247 #if PROFILE
 248         static Profile *prof= profiler->get("CoordinateSequence::removeRepeatedPoints()");
 249         prof->start();
 250 #endif
 251         const vector<Coordinate> *v=cl->toVector();
 252
 253         vector<Coordinate> *nv=new vector<Coordinate>;
 254         nv->reserve(v->size());
 255         unique_copy(v->begin(), v->end(), back_inserter(*nv));
 256         CoordinateSequence* ret=CoordinateArraySequenceFactory::instance()->create(nv);
 257
 258 #if PROFILE
 259         prof->stop();
 260 #endif
 261         return ret;
 262 }
 263
 264 void
 265 CoordinateSequence::expandEnvelope(Envelope &env) const
 266 {
 267         const std::size_t size = getSize();
 268         for (std::size_t i=0; i<size; i++)
 269         env.expandToInclude(getAt(i));
 270 }
 271
 272 std::ostream& operator<< (std::ostream& os, const CoordinateSequence& cs)
 273 {
 274         os << "(";
 275         for (size_t i=0, n=cs.size(); i<n; ++i)
 276         {
 277                 const Coordinate& c = cs[i];
 278                 if ( i ) os << ", ";
 279                 os << c;
 280         }
 281         os << ")";
 282
 283         return os;
 284 }
 285
 286 bool operator== ( const CoordinateSequence& s1, const CoordinateSequence& s2)
 287 {
 288         return CoordinateSequence::equals(&s1, &s2);
 289 }
 290
 291 bool operator!= ( const CoordinateSequence& s1, const CoordinateSequence& s2)
 292 {
 293         return ! CoordinateSequence::equals(&s1, &s2);
 294 }
 295
 296 } // namespace geos::geom
 297 } // namespace geos
 298
 299 /**********************************************************************
 300  * $Log$
 301  * Revision 1.21  2006/06/12 16:51:23  strk
 302  * Added equality and inequality operators and tests
 303  *
 304  * Revision 1.20  2006/06/12 16:36:22  strk
 305  * indentation, notes about things to be fixed.
 306  *
 307  * Revision 1.19  2006/06/12 10:10:39  strk
 308  * Fixed getGeometryN() to take size_t rather then int, changed unsigned int parameters to size_t.
 309  *
 310  * Revision 1.18  2006/05/03 19:47:27  strk
 311  * added operator<< for CoordinateSequence
 312  *
 313  **********************************************************************/
 314