include/geos/noding/snapround/MCIndexSnapRounder.h

   1 /**********************************************************************
   2  *
   3  * GEOS - Geometry Engine Open Source
   4  * http://geos.refractions.net
   5  *
   6  * Copyright (C) 2006      Refractions Research Inc.
   7  *
   8  * This is free software; you can redistribute and/or modify it under
   9  * the terms of the GNU Lesser General Public Licence as published
  10  * by the Free Software Foundation.
  11  * See the COPYING file for more information.
  12  *
  13  **********************************************************************
  14  *
  15  * Last port: noding/snapround/MCIndexSnapRounder.java r480 (JTS-1.12)
  16  *
  17  **********************************************************************/
  18
  19 #ifndef GEOS_NODING_SNAPROUND_MCINDEXSNAPROUNDER_H
  20 #define GEOS_NODING_SNAPROUND_MCINDEXSNAPROUNDER_H
  21
  22 #include <geos/export.h>
  23
  24 #include <geos/noding/Noder.h> // for inheritance
  25 #include <geos/noding/NodedSegmentString.h> // for inlines
  26 #include <geos/noding/snapround/MCIndexPointSnapper.h> // for inines
  27 #include <geos/algorithm/LineIntersector.h> // for composition
  28 #include <geos/geom/Coordinate.h> // for use in vector
  29 #include <geos/geom/PrecisionModel.h> // for inlines
  30
  31 #include <vector>
  32
  33 #ifdef _MSC_VER
  34 #pragma warning(push)
  35 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
  36 #endif
  37
  38 // Forward declarations
  39 namespace geos {
  40         namespace algorithm {
  41                 class LineIntersector;
  42         }
  43         namespace noding {
  44                 class SegmentString;
  45                 class MCIndexNoder;
  46         }
  47 }
  48
  49 namespace geos {
  50 namespace noding { // geos::noding
  51 namespace snapround { // geos::noding::snapround
  52
  53
  54 /** \brief
  55  * Uses Snap Rounding to compute a rounded,
  56  * fully noded arrangement from a set of SegmentString
  57  *
  58  * Implements the Snap Rounding technique described in Hobby, Guibas & Marimont,
  59  * and Goodrich et al.
  60  *
  61  * Snap Rounding assumes that all vertices lie on a uniform grid
  62  * (hence the precision model of the input must be fixed precision,
  63  * and all the input vertices must be rounded to that precision).
  64  *
  65  * This implementation uses a monotone chains and a spatial index to
  66  * speed up the intersection tests.
  67  *
  68  * This implementation appears to be fully robust using an integer
  69  * precision model.
  70  *
  71  * It will function with non-integer precision models, but the
  72  * results are not 100% guaranteed to be correctly noded.
  73  */
  74 class GEOS_DLL MCIndexSnapRounder: public Noder { // implments Noder
  75
  76 public:
  77
  78         MCIndexSnapRounder(geom::PrecisionModel& nPm)
  79     :
  80                 pm(nPm),
  81                 scaleFactor(nPm.getScale()),
  82                 pointSnapper(0)
  83   {
  84     li.setPrecisionModel(&pm);
  85   }
  86
  87         std::vector<SegmentString*>* getNodedSubstrings() const {
  88           return NodedSegmentString::getNodedSubstrings(*nodedSegStrings);
  89   }
  90
  91         void computeNodes(std::vector<SegmentString*>* segStrings);
  92
  93         /**
  94          * Computes nodes introduced as a result of
  95          * snapping segments to vertices of other segments
  96          *
  97          * @param edges the list of segment strings to snap together
  98          *        NOTE: they *must* be instances of NodedSegmentString, or
  99          *                  an assertion will fail.
 100          */
 101         void computeVertexSnaps(std::vector<SegmentString*>& edges);
 102
 103 private:
 104
 105         /// externally owned
 106         geom::PrecisionModel& pm;
 107
 108         algorithm::LineIntersector li;
 109
 110         double scaleFactor;
 111
 112         std::vector<SegmentString*>* nodedSegStrings;
 113
 114         std::auto_ptr<MCIndexPointSnapper> pointSnapper;
 115
 116         void snapRound(MCIndexNoder& noder, std::vector<SegmentString*>* segStrings);
 117
 118
 119         /**
 120          * Computes all interior intersections in the collection of SegmentStrings,
 121          * and push their Coordinate to the provided vector.
 122          *
 123          * Does NOT node the segStrings.
 124          *
 125          */
 126         void findInteriorIntersections(MCIndexNoder& noder,
 127                         std::vector<SegmentString*>* segStrings,
 128                         std::vector<geom::Coordinate>& intersections);
 129
 130         /**
 131          * Computes nodes introduced as a result of snapping
 132          * segments to snap points (hot pixels)
 133          */
 134         void computeIntersectionSnaps(std::vector<geom::Coordinate>& snapPts);
 135
 136         /**
 137          * Performs a brute-force comparison of every segment in each {@link SegmentString}.
 138          * This has n^2 performance.
 139          */
 140         void computeVertexSnaps(NodedSegmentString* e);
 141
 142         void checkCorrectness(std::vector<SegmentString*>& inputSegmentStrings);
 143
 144     // Declare type as noncopyable
 145     MCIndexSnapRounder(const MCIndexSnapRounder& other);
 146     MCIndexSnapRounder& operator=(const MCIndexSnapRounder& rhs);
 147 };
 148
 149 } // namespace geos::noding::snapround
 150 } // namespace geos::noding
 151 } // namespace geos
 152
 153 #ifdef _MSC_VER
 154 #pragma warning(pop)
 155 #endif
 156
 157 #endif // GEOS_NODING_SNAPROUND_MCINDEXSNAPROUNDER_H
 158
 159 /**********************************************************************
 160  * $Log$
 161  * Revision 1.2  2006/03/24 09:52:41  strk
 162  * USE_INLINE => GEOS_INLINE
 163  *
 164  * Revision 1.1  2006/03/14 12:55:56  strk
 165  * Headers split: geomgraphindex.h, nodingSnapround.h
 166  *
 167  **********************************************************************/
 168