src/geomgraph/EdgeEndStar.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2011 Sandro Santilli <strk@kbt.io>
   7  * Copyright (C) 2005-2006 Refractions Research Inc.
   8  * Copyright (C) 2001-2002 Vivid Solutions Inc.
   9  *
  10  * This is free software; you can redistribute and/or modify it under
  11  * the terms of the GNU Lesser General Public Licence as published
  12  * by the Free Software Foundation.
  13  * See the COPYING file for more information.
  14  *
  15  **********************************************************************
  16  *
  17  * Last port: geomgraph/EdgeEndStar.java r428 (JTS-1.12+)
  18  *
  19  **********************************************************************/
  20
  21 #include <geos/util/TopologyException.h>
  22 #include <geos/geomgraph/EdgeEndStar.h>
  23 #include <geos/algorithm/locate/SimplePointInAreaLocator.h>
  24 #include <geos/geom/Location.h>
  25 #include <geos/geomgraph/Label.h>
  26 #include <geos/geomgraph/Position.h>
  27 #include <geos/geomgraph/GeometryGraph.h>
  28
  29 #include <cassert>
  30 #include <string>
  31 #include <vector>
  32 #include <sstream>
  33
  34 #ifndef GEOS_DEBUG
  35 #define GEOS_DEBUG 0
  36 #endif
  37
  38 //using namespace std;
  39 //using namespace geos::algorithm;
  40 using namespace geos::geom;
  41
  42 namespace geos {
  43 namespace geomgraph { // geos.geomgraph
  44
  45 /*public*/
  46 EdgeEndStar::EdgeEndStar()
  47         :
  48         edgeMap()
  49 {
  50         ptInAreaLocation[0]=Location::UNDEF;
  51         ptInAreaLocation[1]=Location::UNDEF;
  52 }
  53
  54 /*public*/
  55 Coordinate&
  56 EdgeEndStar::getCoordinate()
  57 {
  58         static Coordinate nullCoord(DoubleNotANumber, DoubleNotANumber, DoubleNotANumber);
  59         if (edgeMap.size()==0) return nullCoord;
  60
  61         EdgeEndStar::iterator it=begin();
  62         EdgeEnd *e=*it;
  63         assert(e);
  64         return e->getCoordinate();
  65 }
  66
  67 /*public*/
  68 const Coordinate&
  69 EdgeEndStar::getCoordinate() const
  70 {
  71         return const_cast<EdgeEndStar*>(this)->getCoordinate();
  72 }
  73
  74 /*public*/
  75 EdgeEnd*
  76 EdgeEndStar::getNextCW(EdgeEnd *ee)
  77 {
  78         EdgeEndStar::iterator it=find(ee);
  79         if ( it==end() ) return NULL;
  80         if ( it==begin() ) { it=end(); --it; }
  81         else --it;
  82         return *it;
  83 }
  84
  85 /*public*/
  86 void
  87 EdgeEndStar::computeLabelling(std::vector<GeometryGraph*> *geomGraph)
  88         //throw(TopologyException *)
  89 {
  90         computeEdgeEndLabels((*geomGraph)[0]->getBoundaryNodeRule());
  91
  92         // Propagate side labels  around the edges in the star
  93         // for each parent Geometry
  94         //
  95         // these calls can throw a TopologyException
  96         propagateSideLabels(0);
  97         propagateSideLabels(1);
  98
  99         /**
 100          * If there are edges that still have null labels for a geometry
 101          * this must be because there are no area edges for that geometry
 102          * incident on this node.
 103          * In this case, to label the edge for that geometry we must test
 104          * whether the edge is in the interior of the geometry.
 105          * To do this it suffices to determine whether the node for the
 106          * edge is in the interior of an area.
 107          * If so, the edge has location INTERIOR for the geometry.
 108          * In all other cases (e.g. the node is on a line, on a point, or
 109          * not on the geometry at all) the edge
 110          * has the location EXTERIOR for the geometry.
 111          *
 112          * Note that the edge cannot be on the BOUNDARY of the geometry,
 113          * since then there would have been a parallel edge from the
 114          * Geometry at this node also labelled BOUNDARY
 115          * and this edge would have been labelled in the previous step.
 116          *
 117          * This code causes a problem when dimensional collapses are present,
 118          * since it may try and determine the location of a node where a
 119          * dimensional collapse has occurred.
 120          * The point should be considered to be on the EXTERIOR
 121          * of the polygon, but locate() will return INTERIOR, since it is
 122          * passed the original Geometry, not the collapsed version.
 123          *
 124          * If there are incident edges which are Line edges labelled BOUNDARY,
 125          * then they must be edges resulting from dimensional collapses.
 126          * In this case the other edges can be labelled EXTERIOR for this
 127          * Geometry.
 128          *
 129          * MD 8/11/01 - NOT TRUE!  The collapsed edges may in fact be in the
 130          * interior of the Geometry, which means the other edges should be
 131          * labelled INTERIOR for this Geometry.
 132          * Not sure how solve this...  Possibly labelling needs to be split
 133          * into several phases:
 134          * area label propagation, symLabel merging, then finally null label
 135          * resolution.
 136          */
 137         bool hasDimensionalCollapseEdge[2]={false,false};
 138
 139         EdgeEndStar::iterator endIt=end();
 140         for (EdgeEndStar::iterator it=begin(); it!=endIt; ++it)
 141         {
 142                 EdgeEnd *e=*it;
 143                 assert(e);
 144                 const Label& label = e->getLabel();
 145                 for(int geomi=0; geomi<2; geomi++)
 146                 {
 147                         if (label.isLine(geomi) && label.getLocation(geomi) == Location::BOUNDARY)
 148                                 hasDimensionalCollapseEdge[geomi]=true;
 149                 }
 150         }
 151
 152         for (EdgeEndStar::iterator it=begin(); it!=end(); ++it)
 153         {
 154                 EdgeEnd *e=*it;
 155                 assert(e);
 156                 Label& label = e->getLabel();
 157                 for(int geomi=0; geomi<2; ++geomi)
 158                 {
 159                         if (label.isAnyNull(geomi)) {
 160                                 int loc=Location::UNDEF;
 161                                 if (hasDimensionalCollapseEdge[geomi]){
 162                                         loc=Location::EXTERIOR;
 163                                 }else {
 164                                         Coordinate& p=e->getCoordinate();
 165                                         loc = getLocation(geomi, p, geomGraph);
 166                                 }
 167                                 label.setAllLocationsIfNull(geomi, loc);
 168                         }
 169                 }
 170         }
 171 }
 172
 173 /*private*/
 174 void
 175 EdgeEndStar::computeEdgeEndLabels(
 176                 const algorithm::BoundaryNodeRule& boundaryNodeRule)
 177 {
 178         // Compute edge label for each EdgeEnd
 179         for (EdgeEndStar::iterator it=begin(); it!=end(); ++it)
 180         {
 181                 EdgeEnd *ee=*it;
 182                 assert(ee);
 183                 ee->computeLabel(boundaryNodeRule);
 184         }
 185 }
 186
 187 /*public*/
 188 int
 189 EdgeEndStar::getLocation(int geomIndex,
 190         const Coordinate& p, std::vector<GeometryGraph*> *geom)
 191 {
 192         // compute location only on demand
 193         if (ptInAreaLocation[geomIndex]==Location::UNDEF)
 194         {
 195                 ptInAreaLocation[geomIndex]=algorithm::locate::SimplePointInAreaLocator::locate(p,
 196                                 (*geom)[geomIndex]->getGeometry());
 197         }
 198         return ptInAreaLocation[geomIndex];
 199 }
 200
 201 /*public*/
 202 bool
 203 EdgeEndStar::isAreaLabelsConsistent(const GeometryGraph& geomGraph)
 204 {
 205         computeEdgeEndLabels(geomGraph.getBoundaryNodeRule());
 206         return checkAreaLabelsConsistent(0);
 207 }
 208
 209 /*private*/
 210 bool
 211 EdgeEndStar::checkAreaLabelsConsistent(int geomIndex)
 212 {
 213         // Since edges are stored in CCW order around the node,
 214         // As we move around the ring we move from the right to
 215         // the left side of the edge
 216
 217         // if no edges, trivially consistent
 218         if (edgeMap.size()==0) return true;
 219
 220         // initialize startLoc to location of last L side (if any)
 221         assert(*rbegin());
 222         const Label& startLabel = (*rbegin())->getLabel();
 223         int startLoc = startLabel.getLocation(geomIndex, Position::LEFT);
 224
 225         // Found unlabelled area edge
 226         assert(startLoc!=Location::UNDEF);
 227
 228         int currLoc=startLoc;
 229
 230         for (EdgeEndStar::iterator it=begin(), itEnd=end(); it!=itEnd; ++it)
 231         {
 232                 EdgeEnd *e=*it;
 233                 assert(e);
 234                 const Label& eLabel = e->getLabel();
 235
 236                 // we assume that we are only checking a area
 237
 238                 // Found non-area edge
 239                 assert(eLabel.isArea(geomIndex));
 240
 241                 int leftLoc=eLabel.getLocation(geomIndex, Position::LEFT);
 242                 int rightLoc=eLabel.getLocation(geomIndex, Position::RIGHT);
 243                 // check that edge is really a boundary between inside and outside!
 244                 if (leftLoc==rightLoc) {
 245                         return false;
 246                 }
 247                 // check side location conflict
 248                 //assert(rightLoc == currLoc); // "side location conflict " + locStr);
 249                 if (rightLoc!=currLoc) {
 250                         return false;
 251                 }
 252                 currLoc=leftLoc;
 253         }
 254         return true;
 255 }
 256
 257 /*public*/
 258 void
 259 EdgeEndStar::propagateSideLabels(int geomIndex)
 260         //throw(TopologyException *)
 261 {
 262         // Since edges are stored in CCW order around the node,
 263         // As we move around the ring we move from the right to the
 264         // left side of the edge
 265         int startLoc=Location::UNDEF;
 266
 267         EdgeEndStar::iterator beginIt=begin();
 268         EdgeEndStar::iterator endIt=end();
 269         EdgeEndStar::iterator it;
 270
 271         // initialize loc to location of last L side (if any)
 272         for (EdgeEndStar::iterator it=beginIt; it!=endIt; ++it)
 273         {
 274                 EdgeEnd *e=*it;
 275                 assert(e);
 276                 const Label& label = e->getLabel();
 277                 if (label.isArea(geomIndex) &&
 278                     label.getLocation(geomIndex,Position::LEFT) != Location::UNDEF)
 279                 {
 280                         startLoc = label.getLocation(geomIndex, Position::LEFT);
 281                 }
 282         }
 283
 284         // no labelled sides found, so no labels to propagate
 285         if (startLoc==Location::UNDEF) return;
 286
 287         int currLoc=startLoc;
 288         for (it=beginIt; it!=endIt; ++it)
 289         {
 290                 EdgeEnd *e=*it;
 291                 assert(e);
 292                 Label& label = e->getLabel();
 293                 // set null ON values to be in current location
 294                 if (label.getLocation(geomIndex,Position::ON) == Location::UNDEF)
 295                 {
 296                         label.setLocation(geomIndex,Position::ON,currLoc);
 297                 }
 298
 299                 // set side labels (if any)
 300                 // if (label.isArea())  //ORIGINAL
 301                 if (label.isArea(geomIndex))
 302                 {
 303                         int leftLoc=label.getLocation(geomIndex,
 304                                 Position::LEFT);
 305
 306                         int rightLoc=label.getLocation(geomIndex,
 307                                 Position::RIGHT);
 308
 309                         // if there is a right location, that is the next
 310                         // location to propagate
 311                         if (rightLoc!=Location::UNDEF) {
 312                                 if (rightLoc!=currLoc)
 313                                         throw util::TopologyException("side location conflict",
 314                                                 e->getCoordinate());
 315                                 if (leftLoc==Location::UNDEF) {
 316                                         // found single null side at e->getCoordinate()
 317                                         assert(0);
 318                                 }
 319                                 currLoc=leftLoc;
 320                         } else {
 321                                 /**
 322                                  * RHS is null - LHS must be null too.
 323                                  * This must be an edge from the other
 324                                  * geometry, which has no location
 325                                  * labelling for this geometry.
 326                                  * This edge must lie wholly inside or
 327                                  * outside the other geometry (which is
 328                                  * determined by the current location).
 329                                  * Assign both sides to be the current
 330                                  * location.
 331                                  */
 332                                 // found single null side
 333                                 assert(label.getLocation(geomIndex,
 334                                         Position::LEFT)==Location::UNDEF);
 335
 336                                 label.setLocation(geomIndex,Position::RIGHT,
 337                                         currLoc);
 338                                 label.setLocation(geomIndex,Position::LEFT,
 339                                         currLoc);
 340                         }
 341                 }
 342         }
 343 }
 344
 345 /*public*/
 346 std::string
 347 EdgeEndStar::print() const
 348 {
 349         std::ostringstream s;
 350   s << *this;
 351   return s.str();
 352 }
 353
 354 std::ostream&
 355 operator<< (std::ostream& os, const EdgeEndStar& es)
 356 {
 357         os << "EdgeEndStar:   " << es.getCoordinate() << "\n";
 358         for (EdgeEndStar::const_iterator it=es.begin(), itEnd=es.end(); it!=itEnd; ++it)
 359         {
 360                 const EdgeEnd *e=*it;
 361                 assert(e);
 362                 os << *e;
 363         }
 364         return os;
 365 }
 366
 367 } // namespace geos.geomgraph
 368 } // namespace geos
 369