125 lines
4.5 KiB
C++
125 lines
4.5 KiB
C++
/**********************************************************************
|
|
*
|
|
* GEOS - Geometry Engine Open Source
|
|
* http://geos.osgeo.org
|
|
*
|
|
* Copyright (C) 2016 Daniel Baston
|
|
*
|
|
* This is free software; you can redistribute and/or modify it under
|
|
* the terms of the GNU Lesser General Public Licence as published
|
|
* by the Free Software Foundation.
|
|
* See the COPYING file for more information.
|
|
*
|
|
**********************************************************************
|
|
*
|
|
* Last port: operation/distance/IndexedFacetDistance.java (f6187ee2 JTS-1.14)
|
|
*
|
|
**********************************************************************/
|
|
|
|
#pragma once
|
|
|
|
#include <geos/operation/distance/FacetSequenceTreeBuilder.h>
|
|
|
|
namespace geos {
|
|
namespace operation {
|
|
namespace distance {
|
|
|
|
/// \brief Computes the distance between the facets (segments and vertices)
|
|
/// of two [Geometrys](\ref geom::Geometry) using a Branch-and-Bound algorithm.
|
|
///
|
|
/// The Branch-and-Bound algorithm operates over a traversal of R-trees built
|
|
/// on the target and the query geometries.
|
|
///
|
|
/// This approach provides the following benefits:
|
|
///
|
|
/// - Performance is dramatically improved due to the use of the R-tree index
|
|
/// and the pruning due to the Branch-and-Bound approach
|
|
/// - The spatial index on the target geometry is cached which allow reuse in
|
|
/// an repeated query situation.
|
|
///
|
|
/// Using this technique is usually much more performant than using the
|
|
/// brute-force geom::Geometry::distance() when one
|
|
/// or both input geometries are large, or when evaluating many distance
|
|
/// computations against a single geometry.
|
|
///
|
|
/// \author Martin Davis
|
|
class GEOS_DLL IndexedFacetDistance {
|
|
public:
|
|
|
|
/// \brief Creates a new distance-finding instance for a given target geom::Geometry.
|
|
///
|
|
/// Distances will be computed to all facets of the input geometry.
|
|
/// The facets of the geometry are the discrete segments and points
|
|
/// contained in its components.
|
|
/// In the case of lineal and puntal inputs, this is equivalent to computing
|
|
/// the conventional distance.
|
|
/// In the case of polygonal inputs, this is equivalent to computing the
|
|
/// distance to the polygon boundaries.
|
|
///
|
|
/// \param g a Geometry, which may be of any type.
|
|
IndexedFacetDistance(const geom::Geometry* g) :
|
|
cachedTree(FacetSequenceTreeBuilder::build(g)),
|
|
baseGeometry(*g)
|
|
{}
|
|
|
|
/// \brief Computes the distance between facets of two geometries.
|
|
///
|
|
/// For geometries with many segments or points, this can be faster than
|
|
/// using a simple distance algorithm.
|
|
///
|
|
/// \param g1 a geometry
|
|
/// \param g2 a geometry
|
|
/// \return the distance between facets of the geometries
|
|
static double distance(const geom::Geometry* g1, const geom::Geometry* g2);
|
|
|
|
/// \brief Computes the nearest points of the facets of two geometries.
|
|
///
|
|
/// \param g1 a geometry
|
|
/// \param g2 a geometry
|
|
/// \return the nearest points on the facets of the geometries
|
|
static std::unique_ptr<geom::CoordinateSequence> nearestPoints(const geom::Geometry* g1, const geom::Geometry* g2);
|
|
|
|
/// \brief Computes the distance from the base geometry to the given geometry.
|
|
///
|
|
/// \param g the geometry to compute the distance to
|
|
///
|
|
/// \return the computed distance
|
|
double distance(const geom::Geometry* g) const;
|
|
|
|
/// \brief Tests whether the base geometry lies within a specified distance of the given geometry.
|
|
///
|
|
/// \param g the geometry to test
|
|
/// \param maxDistance the maximum distance to test
|
|
///
|
|
/// \return true of the geometry lies within the specified distance
|
|
bool isWithinDistance(const geom::Geometry* g, double maxDistance) const;
|
|
|
|
/// \brief Computes the nearest locations on the base geometry and the given geometry.
|
|
///
|
|
/// \param g the geometry to compute the nearest location to
|
|
/// \return the nearest locations
|
|
std::vector<GeometryLocation> nearestLocations(const geom::Geometry* g) const;
|
|
|
|
/// \brief Compute the nearest locations on the target geometry and the given geometry.
|
|
///
|
|
/// \param g the geometry to compute the nearest point to
|
|
/// \return the nearest points
|
|
std::unique_ptr<geom::CoordinateSequence> nearestPoints(const geom::Geometry* g) const;
|
|
|
|
private:
|
|
struct FacetDistance {
|
|
double operator()(const FacetSequence* a, const FacetSequence* b) const
|
|
{
|
|
return a->distance(*b);
|
|
}
|
|
};
|
|
|
|
std::unique_ptr<geos::index::strtree::TemplateSTRtree<const FacetSequence*>> cachedTree;
|
|
const geom::Geometry& baseGeometry;
|
|
|
|
};
|
|
}
|
|
}
|
|
}
|
|
|