/********************************************************************** * * GEOS - Geometry Engine Open Source * http://geos.osgeo.org * * Copyright (C) 2011 Sandro Santilli * Copyright (C) 2005-2006 Refractions Research Inc. * Copyright (C) 2001-2002 Vivid Solutions Inc. * * This is free software; you can redistribute and/or modify it under * the terms of the GNU Lesser General Public Licence as published * by the Free Software Foundation. * See the COPYING file for more information. * ********************************************************************** * * Last port: geomgraph/EdgeEndStar.java r428 (JTS-1.12+) * **********************************************************************/ #include #include #include #include #include #include #include #include #include #include #ifndef GEOS_DEBUG #define GEOS_DEBUG 0 #endif //using namespace std; //using namespace geos::algorithm; using namespace geos::geom; namespace geos { namespace geomgraph { // geos.geomgraph /*public*/ EdgeEndStar::EdgeEndStar() : edgeMap() { ptInAreaLocation[0]=Location::UNDEF; ptInAreaLocation[1]=Location::UNDEF; } /*public*/ Coordinate& EdgeEndStar::getCoordinate() { static Coordinate nullCoord(DoubleNotANumber, DoubleNotANumber, DoubleNotANumber); if (edgeMap.size()==0) return nullCoord; EdgeEndStar::iterator it=begin(); EdgeEnd *e=*it; assert(e); return e->getCoordinate(); } /*public*/ EdgeEnd* EdgeEndStar::getNextCW(EdgeEnd *ee) { EdgeEndStar::iterator it=find(ee); if ( it==end() ) return NULL; if ( it==begin() ) { it=end(); --it; } else --it; return *it; } /*public*/ void EdgeEndStar::computeLabelling(std::vector *geomGraph) //throw(TopologyException *) { computeEdgeEndLabels((*geomGraph)[0]->getBoundaryNodeRule()); // Propagate side labels around the edges in the star // for each parent Geometry // // these calls can throw a TopologyException propagateSideLabels(0); propagateSideLabels(1); /** * If there are edges that still have null labels for a geometry * this must be because there are no area edges for that geometry * incident on this node. * In this case, to label the edge for that geometry we must test * whether the edge is in the interior of the geometry. * To do this it suffices to determine whether the node for the * edge is in the interior of an area. * If so, the edge has location INTERIOR for the geometry. * In all other cases (e.g. the node is on a line, on a point, or * not on the geometry at all) the edge * has the location EXTERIOR for the geometry. * * Note that the edge cannot be on the BOUNDARY of the geometry, * since then there would have been a parallel edge from the * Geometry at this node also labelled BOUNDARY * and this edge would have been labelled in the previous step. * * This code causes a problem when dimensional collapses are present, * since it may try and determine the location of a node where a * dimensional collapse has occurred. * The point should be considered to be on the EXTERIOR * of the polygon, but locate() will return INTERIOR, since it is * passed the original Geometry, not the collapsed version. * * If there are incident edges which are Line edges labelled BOUNDARY, * then they must be edges resulting from dimensional collapses. * In this case the other edges can be labelled EXTERIOR for this * Geometry. * * MD 8/11/01 - NOT TRUE! The collapsed edges may in fact be in the * interior of the Geometry, which means the other edges should be * labelled INTERIOR for this Geometry. * Not sure how solve this... Possibly labelling needs to be split * into several phases: * area label propagation, symLabel merging, then finally null label * resolution. */ bool hasDimensionalCollapseEdge[2]={false,false}; EdgeEndStar::iterator endIt=end(); for (EdgeEndStar::iterator it=begin(); it!=endIt; ++it) { EdgeEnd *e=*it; assert(e); const Label& label = e->getLabel(); for(int geomi=0; geomi<2; geomi++) { if (label.isLine(geomi) && label.getLocation(geomi) == Location::BOUNDARY) hasDimensionalCollapseEdge[geomi]=true; } } for (EdgeEndStar::iterator it=begin(); it!=end(); ++it) { EdgeEnd *e=*it; assert(e); Label& label = e->getLabel(); for(int geomi=0; geomi<2; ++geomi) { if (label.isAnyNull(geomi)) { int loc=Location::UNDEF; if (hasDimensionalCollapseEdge[geomi]){ loc=Location::EXTERIOR; }else { Coordinate& p=e->getCoordinate(); loc = getLocation(geomi, p, geomGraph); } label.setAllLocationsIfNull(geomi, loc); } } } } /*private*/ void EdgeEndStar::computeEdgeEndLabels( const algorithm::BoundaryNodeRule& boundaryNodeRule) { // Compute edge label for each EdgeEnd for (EdgeEndStar::iterator it=begin(); it!=end(); ++it) { EdgeEnd *ee=*it; assert(ee); ee->computeLabel(boundaryNodeRule); } } /*public*/ int EdgeEndStar::getLocation(int geomIndex, const Coordinate& p, std::vector *geom) { // compute location only on demand if (ptInAreaLocation[geomIndex]==Location::UNDEF) { ptInAreaLocation[geomIndex]=algorithm::locate::SimplePointInAreaLocator::locate(p, (*geom)[geomIndex]->getGeometry()); } return ptInAreaLocation[geomIndex]; } /*public*/ bool EdgeEndStar::isAreaLabelsConsistent(const GeometryGraph& geomGraph) { computeEdgeEndLabels(geomGraph.getBoundaryNodeRule()); return checkAreaLabelsConsistent(0); } /*private*/ bool EdgeEndStar::checkAreaLabelsConsistent(int geomIndex) { // Since edges are stored in CCW order around the node, // As we move around the ring we move from the right to // the left side of the edge // if no edges, trivially consistent if (edgeMap.size()==0) return true; // initialize startLoc to location of last L side (if any) EdgeEndStar::reverse_iterator it=rbegin(); assert(*it); const Label& startLabel = (*it)->getLabel(); int startLoc = startLabel.getLocation(geomIndex, Position::LEFT); // Found unlabelled area edge assert(startLoc!=Location::UNDEF); int currLoc=startLoc; for (EdgeEndStar::iterator it=begin(), itEnd=end(); it!=itEnd; ++it) { EdgeEnd *e=*it; assert(e); const Label& eLabel = e->getLabel(); // we assume that we are only checking a area // Found non-area edge assert(eLabel.isArea(geomIndex)); int leftLoc=eLabel.getLocation(geomIndex, Position::LEFT); int rightLoc=eLabel.getLocation(geomIndex, Position::RIGHT); // check that edge is really a boundary between inside and outside! if (leftLoc==rightLoc) { return false; } // check side location conflict //assert(rightLoc == currLoc); // "side location conflict " + locStr); if (rightLoc!=currLoc) { return false; } currLoc=leftLoc; } return true; } /*public*/ void EdgeEndStar::propagateSideLabels(int geomIndex) //throw(TopologyException *) { // Since edges are stored in CCW order around the node, // As we move around the ring we move from the right to the // left side of the edge int startLoc=Location::UNDEF; EdgeEndStar::iterator beginIt=begin(); EdgeEndStar::iterator endIt=end(); EdgeEndStar::iterator it; // initialize loc to location of last L side (if any) for (EdgeEndStar::iterator it=beginIt; it!=endIt; ++it) { EdgeEnd *e=*it; assert(e); const Label& label = e->getLabel(); if (label.isArea(geomIndex) && label.getLocation(geomIndex,Position::LEFT) != Location::UNDEF) { startLoc = label.getLocation(geomIndex, Position::LEFT); } } // no labelled sides found, so no labels to propagate if (startLoc==Location::UNDEF) return; int currLoc=startLoc; for (it=beginIt; it!=endIt; ++it) { EdgeEnd *e=*it; assert(e); Label& label = e->getLabel(); // set null ON values to be in current location if (label.getLocation(geomIndex,Position::ON) == Location::UNDEF) { label.setLocation(geomIndex,Position::ON,currLoc); } // set side labels (if any) // if (label.isArea()) //ORIGINAL if (label.isArea(geomIndex)) { int leftLoc=label.getLocation(geomIndex, Position::LEFT); int rightLoc=label.getLocation(geomIndex, Position::RIGHT); // if there is a right location, that is the next // location to propagate if (rightLoc!=Location::UNDEF) { if (rightLoc!=currLoc) throw util::TopologyException("side location conflict", e->getCoordinate()); if (leftLoc==Location::UNDEF) { // found single null side at e->getCoordinate() assert(0); } currLoc=leftLoc; } else { /** * RHS is null - LHS must be null too. * This must be an edge from the other * geometry, which has no location * labelling for this geometry. * This edge must lie wholly inside or * outside the other geometry (which is * determined by the current location). * Assign both sides to be the current * location. */ // found single null side assert(label.getLocation(geomIndex, Position::LEFT)==Location::UNDEF); label.setLocation(geomIndex,Position::RIGHT, currLoc); label.setLocation(geomIndex,Position::LEFT, currLoc); } } } } /*public*/ std::string EdgeEndStar::print() { std::string out="EdgeEndStar: " + getCoordinate().toString()+"\n"; for (EdgeEndStar::iterator it=begin(), itEnd=end(); it!=itEnd; ++it) { EdgeEnd *e=*it; assert(e); out+=e->print(); } return out; } } // namespace geos.geomgraph } // namespace geos