1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2011 Sandro Santilli <strk@kbt.io> 7 * Copyright (C) 2006 Refractions Research Inc. 8 * 9 * This is free software; you can redistribute and/or modify it under 10 * the terms of the GNU Lesser General Public Licence as published 11 * by the Free Software Foundation. 12 * See the COPYING file for more information. 13 * 14 ********************************************************************** 15 * 16 * Last port: operation/distance/DistanceOp.java r335 (JTS-1.12-) 17 * 18 **********************************************************************/ 19 20 #ifndef GEOS_OP_DISTANCE_DISTANCEOP_H 21 #define GEOS_OP_DISTANCE_DISTANCEOP_H 22 23 #include <geos/export.h> 24 25 #include <geos/algorithm/PointLocator.h> // for composition 26 #include <geos/operation/distance/GeometryLocation.h> 27 #include <geos/geom/CoordinateSequence.h> 28 29 #include <array> 30 #include <vector> 31 #include <memory> 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 geom { 41 class Coordinate; 42 class Polygon; 43 class LineString; 44 class Point; 45 class Geometry; 46 } 47 } 48 49 50 namespace geos { 51 namespace operation { // geos::operation 52 namespace distance { // geos::operation::distance 53 54 /** 55 * \brief 56 * Find two points on two {@link geom::Geometry}s which lie 57 * within a given distance, or else are the nearest points 58 * on the geometries (in which case this also 59 * provides the distance between the geometries). 60 * 61 * The distance computation also finds a pair of points in the 62 * input geometries which have the minimum distance between them. 63 * If a point lies in the interior of a line segment, 64 * the coordinate computed is a close 65 * approximation to the exact point. 66 * 67 * Empty geometry collection components are ignored. 68 * 69 * The algorithms used are straightforward O(n^2) 70 * comparisons. This worst-case performance could be improved on 71 * by using Voronoi techniques or spatial indexes. 72 * 73 */ 74 class GEOS_DLL DistanceOp { 75 public: 76 /** 77 * \brief 78 * Compute the distance between the nearest points of two geometries. 79 * 80 * @param g0 a {@link geom::Geometry} 81 * @param g1 another {@link geom::Geometry} 82 * @return the distance between the geometries 83 * @return 0 if either input geometry is empty 84 * @throws IllegalArgumentException if either input geometry is null 85 */ 86 static double distance(const geom::Geometry& g0, 87 const geom::Geometry& g1); 88 89 /// @deprecated, use the version taking references 90 static double distance(const geom::Geometry* g0, 91 const geom::Geometry* g1); 92 93 /** 94 * \brief 95 * Test whether two geometries lie within a given distance of 96 * each other. 97 * 98 * @param g0 a {@link geom::Geometry} 99 * @param g1 another {@link geom::Geometry} 100 * @param distance the distance to test 101 * @return true if g0.distance(g1) <= distance 102 */ 103 static bool isWithinDistance(const geom::Geometry& g0, 104 const geom::Geometry& g1, 105 double distance); 106 107 /** 108 * Compute the the nearest points of two geometries. 109 * 110 * The points are presented in the same order as the input Geometries. 111 * 112 * @param g0 a {@link geom::Geometry} 113 * @param g1 another {@link geom::Geometry} 114 * 115 * @return the nearest points in the geometries, ownership to caller. 116 * A NULL return means one of the geometries is empty. 117 * 118 */ 119 static std::unique_ptr<geom::CoordinateSequence> nearestPoints( 120 const geom::Geometry* g0, 121 const geom::Geometry* g1); 122 123 /// @deprecated use the one taking references 124 DistanceOp(const geom::Geometry* g0, const geom::Geometry* g1); 125 126 /** 127 * \brief 128 * Constructs a DistanceOp that computes the distance and 129 * nearest points between the two specified geometries. 130 * 131 * @param g0 a Geometry 132 * @param g1 a Geometry 133 */ 134 DistanceOp(const geom::Geometry& g0, const geom::Geometry& g1); 135 136 /** 137 * \brief 138 * Constructs a DistanceOp that computes the distance and nearest 139 * points between the two specified geometries. 140 * 141 * @param g0 a Geometry 142 * @param g1 a Geometry 143 * @param terminateDistance the distance on which to terminate 144 * the search 145 */ 146 DistanceOp(const geom::Geometry& g0, const geom::Geometry& g1, 147 double terminateDistance); 148 149 ~DistanceOp() = default; 150 151 /** 152 * Report the distance between the closest points on the input geometries. 153 * 154 * @return the distance between the geometries 155 */ 156 double distance(); 157 158 /** 159 * Report the coordinates of the nearest points in the input geometries. 160 * The points are presented in the same order as the input Geometries. 161 * 162 * @return a pair of {@link geom::Coordinate}s of the nearest points 163 * as a newly allocated object (ownership to caller) 164 * 165 */ 166 std::unique_ptr<geom::CoordinateSequence> nearestPoints(); 167 168 private: 169 170 // input 171 std::array<geom::Geometry const*, 2> geom; 172 double terminateDistance; 173 174 // working 175 algorithm::PointLocator ptLocator; 176 std::array<std::unique_ptr<GeometryLocation>, 2> minDistanceLocation; 177 double minDistance; 178 bool computed = false; 179 180 void updateMinDistance(std::array<std::unique_ptr<GeometryLocation>, 2> & locGeom, bool flip); 181 182 void computeMinDistance(); 183 184 void computeContainmentDistance(); 185 186 void computeInside(std::vector<std::unique_ptr<GeometryLocation>> & locs, 187 const std::vector<const geom::Polygon*>& polys, 188 std::array<std::unique_ptr<GeometryLocation>, 2> & locPtPoly); 189 190 191 /** 192 * Computes distance between facets (lines and points) 193 * of input geometries. 194 */ 195 void computeFacetDistance(); 196 197 void computeMinDistanceLines( 198 const std::vector<const geom::LineString*>& lines0, 199 const std::vector<const geom::LineString*>& lines1, 200 std::array<std::unique_ptr<GeometryLocation>, 2> & locGeom); 201 202 void computeMinDistancePoints( 203 const std::vector<const geom::Point*>& points0, 204 const std::vector<const geom::Point*>& points1, 205 std::array<std::unique_ptr<GeometryLocation>, 2> & locGeom); 206 207 void computeMinDistanceLinesPoints( 208 const std::vector<const geom::LineString*>& lines0, 209 const std::vector<const geom::Point*>& points1, 210 std::array<std::unique_ptr<GeometryLocation>, 2> & locGeom); 211 212 void computeMinDistance(const geom::LineString* line0, 213 const geom::LineString* line1, 214 std::array<std::unique_ptr<GeometryLocation>, 2> & locGeom); 215 216 void computeMinDistance(const geom::LineString* line, 217 const geom::Point* pt, 218 std::array<std::unique_ptr<GeometryLocation>, 2> & locGeom); 219 }; 220 221 222 } // namespace geos::operation::distance 223 } // namespace geos::operation 224 } // namespace geos 225 226 #ifdef _MSC_VER 227 #pragma warning(pop) 228 #endif 229 230 #endif // GEOS_OP_DISTANCE_DISTANCEOP_H 231 232