/src/geos/include/geos/operation/distance/IndexedFacetDistance.h
Line | Count | Source (jump to first uncovered line) |
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 | | #pragma once |
20 | | |
21 | | #include <geos/operation/distance/FacetSequenceTreeBuilder.h> |
22 | | |
23 | | namespace geos { |
24 | | namespace operation { |
25 | | namespace distance { |
26 | | |
27 | | /// \brief Computes the distance between the facets (segments and vertices) |
28 | | /// of two [Geometrys](\ref geom::Geometry) using a Branch-and-Bound algorithm. |
29 | | /// |
30 | | /// The Branch-and-Bound algorithm operates over a traversal of R-trees built |
31 | | /// on the target and the query geometries. |
32 | | /// |
33 | | /// This approach provides the following benefits: |
34 | | /// |
35 | | /// - Performance is dramatically improved due to the use of the R-tree index |
36 | | /// and the pruning due to the Branch-and-Bound approach |
37 | | /// - The spatial index on the target geometry is cached which allow reuse in |
38 | | /// an repeated query situation. |
39 | | /// |
40 | | /// Using this technique is usually much more performant than using the |
41 | | /// brute-force geom::Geometry::distance() when one |
42 | | /// or both input geometries are large, or when evaluating many distance |
43 | | /// computations against a single geometry. |
44 | | /// |
45 | | /// \author Martin Davis |
46 | | class GEOS_DLL IndexedFacetDistance { |
47 | | public: |
48 | | |
49 | | /// \brief Creates a new distance-finding instance for a given target geom::Geometry. |
50 | | /// |
51 | | /// Distances will be computed to all facets of the input geometry. |
52 | | /// The facets of the geometry are the discrete segments and points |
53 | | /// contained in its components. |
54 | | /// In the case of lineal and puntal inputs, this is equivalent to computing |
55 | | /// the conventional distance. |
56 | | /// In the case of polygonal inputs, this is equivalent to computing the |
57 | | /// distance to the polygon boundaries. |
58 | | /// |
59 | | /// \param g a Geometry, which may be of any type. |
60 | | IndexedFacetDistance(const geom::Geometry* g) : |
61 | | cachedTree(FacetSequenceTreeBuilder::build(g)), |
62 | | baseGeometry(*g) |
63 | 0 | {} |
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::unique_ptr<geom::CoordinateSequence> 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 Tests whether the base geometry lies within a specified distance of the given geometry. |
90 | | /// |
91 | | /// \param g the geometry to test |
92 | | /// \param maxDistance the maximum distance to test |
93 | | /// |
94 | | /// \return true of the geometry lies within the specified distance |
95 | | bool isWithinDistance(const geom::Geometry* g, double maxDistance) const; |
96 | | |
97 | | /// \brief Computes the nearest locations on the base geometry and the given geometry. |
98 | | /// |
99 | | /// \param g the geometry to compute the nearest location to |
100 | | /// \return the nearest locations |
101 | | std::vector<GeometryLocation> nearestLocations(const geom::Geometry* g) const; |
102 | | |
103 | | /// \brief Compute the nearest locations on the target geometry and the given geometry. |
104 | | /// |
105 | | /// \param g the geometry to compute the nearest point to |
106 | | /// \return the nearest points |
107 | | std::unique_ptr<geom::CoordinateSequence> nearestPoints(const geom::Geometry* g) const; |
108 | | |
109 | | private: |
110 | | struct FacetDistance { |
111 | | double operator()(const FacetSequence* a, const FacetSequence* b) const |
112 | 0 | { |
113 | 0 | return a->distance(*b); |
114 | 0 | } |
115 | | }; |
116 | | |
117 | | std::unique_ptr<geos::index::strtree::TemplateSTRtree<const FacetSequence*>> cachedTree; |
118 | | const geom::Geometry& baseGeometry; |
119 | | |
120 | | }; |
121 | | } |
122 | | } |
123 | | } |
124 | | |