/********************************************************************** * $Id: EdgeIntersectionList.cpp 1820 2006-09-06 16:54:23Z mloskot $ * * GEOS - Geometry Engine Open Source * http://geos.refractions.net * * Copyright (C) 2001-2002 Vivid Solutions Inc. * Copyright (C) 2005 Refractions Research 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/EdgeIntersectionList.java rev. 1.3 * **********************************************************************/ #include #include #include #include #include #include // shouldn't be using this #include #include #include #include #include // std::pair #ifndef GEOS_DEBUG #define GEOS_DEBUG 0 #endif #if GEOS_DEBUG || GEOS_DEBUG_INTERSECT #include #endif using namespace std; using namespace geos::geom; namespace geos { namespace geomgraph { // geos.geomgraph EdgeIntersectionList::EdgeIntersectionList(Edge *newEdge): edge(newEdge) { } EdgeIntersectionList::~EdgeIntersectionList() { for (EdgeIntersectionList::iterator it=nodeMap.begin(), endIt=nodeMap.end(); it!=endIt; ++it) { delete *it; } } EdgeIntersection* EdgeIntersectionList::add(const Coordinate& coord, int segmentIndex, double dist) { EdgeIntersection *eiNew=new EdgeIntersection(coord, segmentIndex, dist); pair p = nodeMap.insert(eiNew); if ( p.second ) { // new EdgeIntersection inserted return eiNew; } else { delete eiNew; return *(p.first); } } bool EdgeIntersectionList::isEmpty() const { return nodeMap.empty(); } bool EdgeIntersectionList::isIntersection(const Coordinate& pt) const { EdgeIntersectionList::const_iterator it=nodeMap.begin(), endIt=nodeMap.end(); for (; it!=endIt; ++it) { EdgeIntersection *ei=*it; if (ei->coord==pt) return true; } return false; } void EdgeIntersectionList::addEndpoints() { int maxSegIndex=edge->getNumPoints()-1; add(edge->pts->getAt(0), 0, 0.0); add(edge->pts->getAt(maxSegIndex), maxSegIndex, 0.0); } void EdgeIntersectionList::addSplitEdges(vector *edgeList) { // ensure that the list has entries for the first and last point // of the edge addEndpoints(); EdgeIntersectionList::iterator it=nodeMap.begin(); // there should always be at least two entries in the list EdgeIntersection *eiPrev=*it; ++it; while (it!=nodeMap.end()) { EdgeIntersection *ei=*it; Edge *newEdge=createSplitEdge(eiPrev,ei); edgeList->push_back(newEdge); eiPrev=ei; it++; } } Edge * EdgeIntersectionList::createSplitEdge(EdgeIntersection *ei0, EdgeIntersection *ei1) { #if GEOS_DEBUG cerr<<"["<segmentIndex-ei0->segmentIndex+2; const Coordinate& lastSegStartPt=edge->pts->getAt(ei1->segmentIndex); // if the last intersection point is not equal to the its segment // start pt, add it to the points list as well. // (This check is needed because the distance metric is not totally // reliable!). The check for point equality is 2D only - Z values // are ignored bool useIntPt1=ei1->dist>0.0 || !ei1->coord.equals2D(lastSegStartPt); if (!useIntPt1) --npts; #if GEOS_DEBUG cerr<<" npts:"< *vc=new vector(); vc->reserve(npts); vc->push_back(ei0->coord); for(int i=ei0->segmentIndex+1; i<=ei1->segmentIndex;i++) { if ( ! useIntPt1 && ei1->segmentIndex == i ) { vc->push_back(ei1->coord); } else { vc->push_back(edge->pts->getAt(i)); } } if (useIntPt1) { vc->push_back(ei1->coord); } CoordinateSequence* pts=new CoordinateArraySequence(vc); return new Edge(pts, new Label(*(edge->getLabel()))); } string EdgeIntersectionList::print() const { string out="Intersections: "; EdgeIntersectionList::const_iterator it=begin(), endIt=end(); for (; it!=endIt; ++it) { EdgeIntersection *ei=*it; out+=ei->print(); } return out; } } // namespace geos.geomgraph } // namespace /********************************************************************** * $Log$ * Revision 1.23 2006/03/23 13:31:56 strk * Fixed to allow build with GEOS_DEBUG * * Revision 1.22 2006/03/15 17:16:29 strk * streamlined headers inclusion * * Revision 1.21 2006/03/03 10:46:21 strk * Removed 'using namespace' from headers, added missing headers in .cpp files, removed useless includes in headers (bug#46) * * Revision 1.20 2006/03/02 12:12:00 strk * Renamed DEBUG macros to GEOS_DEBUG, all wrapped in #ifndef block to allow global override (bug#43) * * Revision 1.19 2006/02/19 19:46:49 strk * Packages <-> namespaces mapping for most GEOS internal code (uncomplete, but working). Dir-level libs for index/ subdirs. * * Revision 1.18 2006/01/31 19:07:34 strk * - Renamed DefaultCoordinateSequence to CoordinateArraySequence. * - Moved GetNumGeometries() and GetGeometryN() interfaces * from GeometryCollection to Geometry class. * - Added getAt(int pos, Coordinate &to) funtion to CoordinateSequence class. * - Reworked automake scripts to produce a static lib for each subdir and * then link all subsystem's libs togheter * - Moved C-API in it's own top-level dir capi/ * - Moved source/bigtest and source/test to tests/bigtest and test/xmltester * - Fixed PointLocator handling of LinearRings * - Changed CoordinateArrayFilter to reduce memory copies * - Changed UniqueCoordinateArrayFilter to reduce memory copies * - Added CGAlgorithms::isPointInRing() version working with * Coordinate::ConstVect type (faster!) * - Ported JTS-1.7 version of ConvexHull with big attention to * memory usage optimizations. * - Improved XMLTester output and user interface * - geos::geom::util namespace used for geom/util stuff * - Improved memory use in geos::geom::util::PolygonExtractor * - New ShortCircuitedGeometryVisitor class * - New operation/predicate package * * Revision 1.17 2006/01/08 15:24:40 strk * Changed container-related typedef to class-scoped STL-like typedefs. * Fixed const correctness of EdgeIntersectionList::begin() and ::end() consts; * defined M_PI when undef as suggested by Charlie Savage. * Removed include from GeometricShapeFactory.cpp. * * Revision 1.16 2005/12/08 01:11:29 strk * minor optimizations in loops * * Revision 1.15 2005/12/08 00:24:41 strk * Reduced coordinate assignments in ::createSplitEdge * * Revision 1.14 2005/11/14 18:14:04 strk * Reduced heap allocations made by TopologyLocation and Label objects. * Enforced const-correctness on GraphComponent. * Cleanups. * * Revision 1.13 2005/11/07 18:05:28 strk * Reduced set<> lookups * * Revision 1.12 2005/11/07 12:31:24 strk * Changed EdgeIntersectionList to use a set<> rathern then a vector<>, and * to avoid dynamic allocation of initial header. * Inlined short SweepLineEvent methods. * * Revision 1.11 2005/02/05 05:44:47 strk * Changed geomgraph nodeMap to use Coordinate pointers as keys, reduces * lots of other Coordinate copies. * * Revision 1.10 2004/12/08 13:54:43 strk * gcc warnings checked and fixed, general cleanups. * * Revision 1.9 2004/11/23 19:53:06 strk * Had LineIntersector compute Z by interpolation. * * Revision 1.8 2004/11/22 13:02:12 strk * Forced use if computed intersection point in ::createSplitEdge (for Z computation) * * Revision 1.7 2004/11/17 08:13:16 strk * Indentation changes. * Some Z_COMPUTATION activated by default. * * Revision 1.6 2004/11/04 19:08:06 strk * Cleanups, initializers list, profiling. * * Revision 1.5 2004/10/21 22:29:54 strk * Indentation changes and some more COMPUTE_Z rules * * Revision 1.4 2004/10/20 17:32:14 strk * Initial approach to 2.5d intersection() * * Revision 1.3 2004/07/08 19:34:49 strk * Mirrored JTS interface of CoordinateSequence, factory and * default implementations. * Added CoordinateArraySequenceFactory::instance() function. * * Revision 1.2 2004/07/02 13:28:26 strk * Fixed all #include lines to reflect headers layout change. * Added client application build tips in README. * * Revision 1.1 2004/03/19 09:48:45 ybychkov * "geomgraph" and "geomgraph/indexl" upgraded to JTS 1.4 * * Revision 1.18 2003/11/07 01:23:42 pramsey * Add standard CVS headers licence notices and copyrights to all cpp and h * files. * * Revision 1.17 2003/11/06 19:04:28 strk * removed useless Coordinate copy in ::createSplitEdge() * **********************************************************************/