1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2016 Shinichi SUGIYAMA (shin.sugi@gmail.com) 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: original work 16 * 17 * Developed by Shinichi SUGIYAMA (shin.sugi@gmail.com) 18 * based on http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf 19 * 20 **********************************************************************/ 21 22 #ifndef GEOS_ALGORITHM_DISTANCE_DISCRETEFRECHETDISTANCE_H 23 #define GEOS_ALGORITHM_DISTANCE_DISCRETEFRECHETDISTANCE_H 24 25 #include <geos/export.h> 26 #include <geos/algorithm/distance/PointPairDistance.h> // for composition 27 #include <geos/algorithm/distance/DistanceToPoint.h> // for composition 28 #include <geos/util/IllegalArgumentException.h> // for inlines 29 #include <geos/geom/Geometry.h> // for inlines 30 #include <geos/util/math.h> // for inlines 31 #include <geos/geom/CoordinateFilter.h> // for inheritance 32 #include <geos/geom/CoordinateSequence.h> // for inheritance 33 34 #include <cstddef> 35 #include <vector> 36 37 #ifdef _MSC_VER 38 #pragma warning(push) 39 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class 40 #endif 41 42 namespace geos { 43 namespace algorithm { 44 //class RayCrossingCounter; 45 } 46 namespace geom { 47 class Geometry; 48 class Coordinate; 49 //class CoordinateSequence; 50 } 51 namespace index { 52 namespace intervalrtree { 53 //class SortedPackedIntervalRTree; 54 } 55 } 56 } 57 58 namespace geos { 59 namespace algorithm { // geos::algorithm 60 namespace distance { // geos::algorithm::distance 61 62 /** \brief 63 * An algorithm for computing a distance metric 64 * which is an approximation to the Frechet Distance 65 * based on a discretization of the input {@link geom::Geometry}. 66 * 67 * The algorithm computes the Frechet distance restricted to discrete points 68 * for one of the geometries. 69 * The points can be either the vertices of the geometries (the default), 70 * or the geometries with line segments densified by a given fraction. 71 * Also determines two points of the Geometries which are separated by the 72 * computed distance. 73 * 74 * This algorithm is an approximation to the standard Frechet distance. 75 * Specifically, 76 * <pre> 77 * for all geometries a, b: DFD(a, b) >= FD(a, b) 78 * </pre> 79 * The approximation can be made as close as needed by densifying the 80 * input geometries. 81 * In the limit, this value will approach the true Frechet distance: 82 * <pre> 83 * DFD(A, B, densifyFactor) -> FD(A, B) as densifyFactor -> 0.0 84 * </pre> 85 * The default approximation is exact or close enough for a large subset of 86 * useful cases. 87 * 88 * The difference between DFD and FD is bounded 89 * by the length of the longest edge of the polygonal curves. 90 * 91 * Fréchet distance sweep continuously along their respective curves 92 * and the direction of curves is significant. 93 * This makes a better measure of similarity than Hausdorff distance. 94 * 95 * An example showing how different DHD and DFD are: 96 * <pre> 97 * A = LINESTRING (0 0, 50 200, 100 0, 150 200, 200 0) 98 * B = LINESTRING (0 200, 200 150, 0 100, 200 50, 0 0) 99 * B' = LINESTRING (0 0, 200 50, 0 100, 200 150, 0 200) 100 * 101 * DHD(A, B) = DHD(A, B') = 48.5071250072666 102 * DFD(A, B) = 200 103 * DFD(A, B') = 282.842712474619 104 * </pre> 105 */ 106 class GEOS_DLL DiscreteFrechetDistance { 107 public: 108 109 static double distance(const geom::Geometry& g0, 110 const geom::Geometry& g1); 111 112 static double distance(const geom::Geometry& g0, 113 const geom::Geometry& g1, double densifyFrac); 114 DiscreteFrechetDistance(const geom::Geometry & p_g0,const geom::Geometry & p_g1)115 DiscreteFrechetDistance(const geom::Geometry& p_g0, 116 const geom::Geometry& p_g1) 117 : 118 g0(p_g0), 119 g1(p_g1), 120 ptDist(), 121 densifyFrac(0.0) 122 {} 123 124 /** 125 * Sets the fraction by which to densify each segment. 126 * Each segment will be (virtually) split into a number of equal-length 127 * subsegments, whose fraction of the total length is closest 128 * to the given fraction. 129 * 130 * @param dFrac 131 */ 132 void setDensifyFraction(double dFrac)133 setDensifyFraction(double dFrac) 134 { 135 if(dFrac > 1.0 || dFrac <= 0.0) { 136 throw util::IllegalArgumentException( 137 "Fraction is not in range (0.0 - 1.0]"); 138 } 139 140 densifyFrac = dFrac; 141 } 142 143 double distance()144 distance() 145 { 146 compute(g0, g1); 147 return ptDist.getDistance(); 148 } 149 150 const std::array<geom::Coordinate, 2> getCoordinates()151 getCoordinates() const 152 { 153 return ptDist.getCoordinates(); 154 } 155 156 private: 157 geom::Coordinate getSegementAt(const geom::CoordinateSequence& seq, size_t index); 158 159 PointPairDistance& getFrecheDistance(std::vector< std::vector<PointPairDistance> >& ca, size_t i, size_t j, 160 const geom::CoordinateSequence& p, const geom::CoordinateSequence& q); 161 162 void compute(const geom::Geometry& discreteGeom, const geom::Geometry& geom); 163 164 const geom::Geometry& g0; 165 166 const geom::Geometry& g1; 167 168 PointPairDistance ptDist; 169 170 /// Value of 0.0 indicates that no densification should take place 171 double densifyFrac; // = 0.0; 172 173 // Declare type as noncopyable 174 DiscreteFrechetDistance(const DiscreteFrechetDistance& other) = delete; 175 DiscreteFrechetDistance& operator=(const DiscreteFrechetDistance& rhs) = delete; 176 }; 177 178 } // geos::algorithm::distance 179 } // geos::algorithm 180 } // geos 181 182 #ifdef _MSC_VER 183 #pragma warning(pop) 184 #endif 185 186 #endif // GEOS_ALGORITHM_DISTANCE_DISCRETEFRECHETDISTANCE_H 187