Coverage Report

Created: 2024-07-27 06:14

/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