src/geomgraph/Edge.cpp

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.osgeo.org
   5  *
   6  * Copyright (C) 2011 Sandro Santilli <strk@keybit.net>
   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/Edge.java r428 (JTS-1.12+)
  18  *
  19  **********************************************************************/
  20
  21 #ifdef _MSC_VER
  22 #pragma warning(disable:4355)
  23 #endif
  24
  25 #include <cassert>
  26 #include <string>
  27 #include <sstream>
  28
  29 #include <geos/geomgraph/Edge.h>
  30 #include <geos/geomgraph/Position.h>
  31 #include <geos/geomgraph/Label.h>
  32 #include <geos/geomgraph/index/MonotoneChainEdge.h>
  33 #include <geos/algorithm/LineIntersector.h>
  34 #include <geos/geom/IntersectionMatrix.h>
  35 #include <geos/geom/CoordinateSequence.h>
  36 #include <geos/geom/CoordinateArraySequence.h> // FIXME: shouldn't use
  37 #include <geos/geom/Coordinate.h>
  38
  39 //#define GEOS_DEBUG_INTERSECT 0
  40 #ifndef GEOS_DEBUG
  41 #define GEOS_DEBUG 0
  42 #endif
  43
  44 #if GEOS_DEBUG || GEOS_DEBUG_INTERSECT
  45 #include <iostream>
  46 #endif
  47
  48 using namespace std;
  49 using namespace geos::geom;
  50
  51 namespace geos {
  52 namespace geomgraph { // geos.geomgraph
  53
  54 using namespace geos::geomgraph::index;
  55 using namespace geos::algorithm;
  56
  57 /**
  58  * Updates an IM from the label for an edge.
  59  * Handles edges from both L and A geometrys.
  60  */
  61 void
  62 Edge::updateIM(const Label& lbl, IntersectionMatrix& im)
  63 {
  64         im.setAtLeastIfValid(lbl.getLocation(0,Position::ON),
  65                               lbl.getLocation(1,Position::ON),
  66                               1);
  67         if (lbl.isArea()) {
  68
  69                 im.setAtLeastIfValid(lbl.getLocation(0,Position::LEFT),
  70                                       lbl.getLocation(1,Position::LEFT),
  71                                       2);
  72
  73                 im.setAtLeastIfValid(lbl.getLocation(0,Position::RIGHT),
  74                                       lbl.getLocation(1,Position::RIGHT),
  75                                       2);
  76         }
  77 }
  78
  79 /*public*/
  80 Edge::~Edge()
  81 {
  82         //cerr<<"["<<this<<"] ~Edge()"<<endl;
  83         delete mce;
  84         delete pts;
  85         delete env;
  86 }
  87
  88 /*public*/
  89 Edge::Edge(CoordinateSequence* newPts, const Label& newLabel)
  90         :
  91         GraphComponent(newLabel),
  92         mce(NULL),
  93         env(NULL),
  94         isIsolatedVar(true),
  95         depth(),
  96         depthDelta(0),
  97         pts(newPts),
  98         eiList(this)
  99 {
 100         testInvariant();
 101 }
 102
 103 /*public*/
 104 Edge::Edge(CoordinateSequence* newPts)
 105         :
 106         GraphComponent(),
 107         mce(NULL),
 108         env(NULL),
 109         isIsolatedVar(true),
 110         depth(),
 111         depthDelta(0),
 112         pts(newPts),
 113         eiList(this)
 114 {
 115         testInvariant();
 116 }
 117
 118 /*public*/
 119 MonotoneChainEdge*
 120 Edge::getMonotoneChainEdge()
 121 {
 122         testInvariant();
 123         if (mce==NULL) mce=new MonotoneChainEdge(this);
 124         return mce;
 125 }
 126
 127
 128 /*public*/
 129 bool
 130 Edge::isCollapsed() const
 131 {
 132         testInvariant();
 133         if (!label.isArea()) return false;
 134         if (getNumPoints()!= 3) return false;
 135         if (pts->getAt(0)==pts->getAt(2) ) return true;
 136         return false;
 137 }
 138
 139 Edge*
 140 Edge::getCollapsedEdge()
 141 {
 142         testInvariant();
 143         CoordinateSequence *newPts = new CoordinateArraySequence(2);
 144         newPts->setAt(pts->getAt(0),0);
 145         newPts->setAt(pts->getAt(1),1);
 146         return new Edge(newPts, Label::toLineLabel(label));
 147 }
 148
 149 /*public*/
 150 void
 151 Edge::addIntersections(LineIntersector *li, int segmentIndex, int geomIndex)
 152 {
 153 #if GEOS_DEBUG
 154         cerr<<"["<<this<<"] Edge::addIntersections("<<li->toString()<<", "<<segmentIndex<<", "<<geomIndex<<") called"<<endl;
 155 #endif
 156         for (int i=0; i<li->getIntersectionNum();i++) {
 157                 addIntersection(li,segmentIndex,geomIndex,i);
 158         }
 159
 160         testInvariant();
 161 }
 162
 163 /*public*/
 164 void
 165 Edge::addIntersection(LineIntersector *li,
 166         int segmentIndex, int geomIndex, int intIndex)
 167 {
 168 #if GEOS_DEBUG
 169         std::cerr << "["<<this<<"] Edge::addIntersection("<<li->toString()<<", "<<segmentIndex<<", "<<geomIndex<<", "<<intIndex<<") called"<< std::endl;
 170 #endif
 171         const Coordinate& intPt=li->getIntersection(intIndex);
 172         unsigned int normalizedSegmentIndex=segmentIndex;
 173         double dist=li->getEdgeDistance(geomIndex,intIndex);
 174
 175         // normalize the intersection point location
 176         unsigned int nextSegIndex=normalizedSegmentIndex+1;
 177         unsigned int npts=getNumPoints();
 178         if (nextSegIndex<npts)
 179         {
 180                 const Coordinate& nextPt=pts->getAt(nextSegIndex);
 181         // Normalize segment index if intPt falls on vertex
 182         // The check for point equality is 2D only - Z values are ignored
 183                 if (intPt.equals2D(nextPt)) {
 184                         normalizedSegmentIndex=nextSegIndex;
 185                         dist=0.0;
 186                 }
 187         }
 188
 189         /*
 190          * Add the intersection point to edge intersection list.
 191          */
 192 #if GEOS_DEBUG
 193         cerr<<"Edge::addIntersection adding to edge intersection list point "<<intPt.toString()<<endl;
 194 #endif
 195         eiList.add(intPt,normalizedSegmentIndex,dist);
 196
 197         testInvariant();
 198 }
 199
 200 /*public*/
 201 bool
 202 Edge::equals(const Edge& e) const
 203 {
 204         testInvariant();
 205
 206         unsigned int npts1=getNumPoints();
 207         unsigned int npts2=e.getNumPoints();
 208
 209         if (npts1 != npts2 ) return false;
 210
 211         bool isEqualForward=true;
 212         bool isEqualReverse=true;
 213
 214         for (unsigned int i=0, iRev=npts1-1; i<npts1; ++i, --iRev)
 215         {
 216                 const Coordinate &e1pi=pts->getAt(i);
 217                 const Coordinate &e2pi=e.pts->getAt(i);
 218                 const Coordinate &e2piRev=e.pts->getAt(iRev);
 219
 220                 if ( !e1pi.equals2D(e2pi) ) isEqualForward=false;
 221                 if ( !e1pi.equals2D(e2piRev) ) isEqualReverse=false;
 222                 if ( !isEqualForward && !isEqualReverse ) return false;
 223         }
 224         return true;
 225 }
 226
 227 /*public*/
 228 bool
 229 Edge::isPointwiseEqual(const Edge *e) const
 230 {
 231         testInvariant();
 232
 233 #if GEOS_DEBUG > 2
 234         cerr<<"Edge::isPointwiseEqual call"<<endl;
 235 #endif
 236         unsigned int npts=getNumPoints();
 237         unsigned int enpts=e->getNumPoints();
 238         if (npts!=enpts) return false;
 239 #if GEOS_DEBUG
 240         cerr<<"Edge::isPointwiseEqual scanning "<<enpts<<"x"<<npts<<" points"<<endl;
 241 #endif
 242         for (unsigned int i=0; i<npts; ++i)
 243         {
 244                 if (!pts->getAt(i).equals2D(e->pts->getAt(i))) {
 245                         return false;
 246                 }
 247         }
 248         return true;
 249 }
 250
 251 string
 252 Edge::print() const
 253 {
 254         testInvariant();
 255
 256         std::stringstream ss;
 257         ss << *this;
 258         return ss.str();
 259 }
 260
 261 // Dunno how to implemente this in terms of operator<<
 262 string
 263 Edge::printReverse() const
 264 {
 265         testInvariant();
 266
 267         stringstream os;
 268
 269         os << "EDGE (rev)";
 270         if ( name != "" ) os << " name:" << name;
 271
 272         os << " label:" << label
 273            << " depthDelta:" << depthDelta
 274            << ":" << std::endl
 275            << "  LINESTRING(";
 276         unsigned int npts=getNumPoints();
 277         for (unsigned int i=npts; i>0; --i)
 278         {
 279                 if (i<npts) os << ", ";
 280                 os << pts->getAt(i-1).toString();
 281         }
 282         os << ")";
 283
 284         return os.str();
 285 }
 286
 287 Envelope*
 288 Edge::getEnvelope()
 289 {
 290         // compute envelope lazily
 291         if (env==NULL)
 292         {
 293                 env=new Envelope();
 294                 unsigned int npts=getNumPoints();
 295                 for (unsigned int i = 0; i<npts; ++i)
 296                 {
 297                         env->expandToInclude(pts->getAt(i));
 298                 }
 299         }
 300         testInvariant();
 301         return env;
 302 }
 303
 304 std::ostream&
 305 operator<< (std::ostream&os, const Edge& e)
 306 {
 307         os << "edge";
 308         if ( e.name != "" ) os << " " << e.name;
 309
 310         os
 311            << "  LINESTRING"
 312            << *(e.pts)
 313            << "  " << e.label
 314            << "  " << e.depthDelta
 315            ;
 316
 317         return os;
 318 }
 319
 320 } // namespace geos.geomgraph
 321 } // namespace geos
 322