1 /********************************************************************** 2 * 3 * GEOS - Geometry Engine Open Source 4 * http://geos.osgeo.org 5 * 6 * Copyright (C) 2016 Daniel Baston 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: operation/distance/IndexedFacetDistance.java (f6187ee2 JTS-1.14) 16 * 17 **********************************************************************/ 18 19 #ifndef GEOS_INDEXEDFACETDISTANCE_H 20 #define GEOS_INDEXEDFACETDISTANCE_H 21 22 #include <geos/operation/distance/FacetSequenceTreeBuilder.h> 23 24 namespace geos { 25 namespace operation { 26 namespace distance { 27 28 /// \brief Computes the distance between the facets (segments and vertices) 29 /// of two [Geometrys](\ref geom::Geometry) using a Branch-and-Bound algorithm. 30 /// 31 /// The Branch-and-Bound algorithm operates over a traversal of R-trees built 32 /// on the target and the query geometries. 33 /// 34 /// This approach provides the following benefits: 35 /// 36 /// - Performance is dramatically improved due to the use of the R-tree index 37 /// and the pruning due to the Branch-and-Bound approach 38 /// - The spatial index on the target geometry is cached which allow reuse in 39 /// an repeated query situation. 40 /// 41 /// Using this technique is usually much more performant than using the 42 /// brute-force \ref geom::Geometry::distance(const Geometry* g) const when one 43 /// or both input geometries are large, or when evaluating many distance 44 /// computations against a single geometry. 45 /// 46 /// \author Martin Davis 47 class GEOS_DLL IndexedFacetDistance { 48 public: 49 50 /// \brief Creates a new distance-finding instance for a given target geom::Geometry. 51 /// 52 /// Distances will be computed to all facets of the input geometry. 53 /// The facets of the geometry are the discrete segments and points 54 /// contained in its components. 55 /// In the case of lineal and puntal inputs, this is equivalent to computing 56 /// the conventional distance. 57 /// In the case of polygonal inputs, this is equivalent to computing the 58 /// distance to the polygon boundaries. 59 /// 60 /// \param g a Geometry, which may be of any type. IndexedFacetDistance(const geom::Geometry * g)61 IndexedFacetDistance(const geom::Geometry* g) : 62 cachedTree(FacetSequenceTreeBuilder::build(g)) 63 {} 64 65 /// \brief Computes the distance between facets of two geometries. 66 /// 67 /// For geometries with many segments or points, this can be faster than 68 /// using a simple distance algorithm. 69 /// 70 /// \param g1 a geometry 71 /// \param g2 a geometry 72 /// \return the distance between facets of the geometries 73 static double distance(const geom::Geometry* g1, const geom::Geometry* g2); 74 75 /// \brief Computes the nearest points of the facets of two geometries. 76 /// 77 /// \param g1 a geometry 78 /// \param g2 a geometry 79 /// \return the nearest points on the facets of the geometries 80 static std::vector<geom::Coordinate> nearestPoints(const geom::Geometry* g1, const geom::Geometry* g2); 81 82 /// \brief Computes the distance from the base geometry to the given geometry. 83 /// 84 /// \param g the geometry to compute the distance to 85 /// 86 /// \return the computed distance 87 double distance(const geom::Geometry* g) const; 88 89 /// \brief Computes the nearest locations on the base geometry and the given geometry. 90 /// 91 /// \param g the geometry to compute the nearest location to 92 /// \return the nearest locations 93 std::vector<GeometryLocation> nearestLocations(const geom::Geometry* g) const; 94 95 /// \brief Compute the nearest locations on the target geometry and the given geometry. 96 /// 97 /// \param g the geometry to compute the nearest point to 98 /// \return the nearest points 99 std::vector<geom::Coordinate> nearestPoints(const geom::Geometry* g) const; 100 101 private: 102 std::unique_ptr<geos::index::strtree::STRtree> cachedTree; 103 104 }; 105 } 106 } 107 } 108 109 #endif //GEOS_INDEXEDFACETDISTANCE_H 110