template<typename dist_t, typename pos_t, class distfun_t>
class GeographicLib::NearestNeighbor< dist_t, pos_t, distfun_t >
Nearest-neighbor calculations.
This class solves the nearest-neighbor problm using a vantage-point tree as described in nearest.
This class is templated so that it can handle arbitrary metric spaces as follows:
- Template Parameters
-
dist_t | the type used for measuring distances; it can be a real or signed integer type; in typical geodetic applications, dist_t might be double . |
pos_t | the type for specifying the positions of points; geodetic application might bundled the latitude and longitude into a std::pair<dist_t, dist_t> . |
distfun_t | the type of a function object which takes takes two positions (of type pos_t) and returns the distance (of type dist_t); in geodetic applications, this might be a class which is constructed with a Geodesic object and which implements a member function with a signature dist_t operator() (const pos_t&, const pos_t&) const , which returns the geodesic distance between two points. |
- Note
- The distance measure must satisfy the triangle inequality, for all points a, b, c. The geodesic distance (given by Geodesic::Inverse) does, while the great ellipse distance and the rhumb line distance do not. If you use the ordinary Euclidean distance, i.e., for two dimensions, don't be tempted to leave out the square root in the interests of "efficiency"; the squared distance does not satisfy the triangle inequality!
This is a "header-only" implementation and, as such, depends in a minimal way on the rest of GeographicLib (the only dependency is through the use of GEOGRAPHICLIB_STATIC_ASSERT and GeographicLib::GeographicErr for handling run-time and compile-time exceptions). Therefore, it is easy to extract this class from the rest of GeographicLib and use it as a stand-alone facility.
The dist_t type must support numeric_limits queries (specifically: is_signed, is_integer, max(), digits).
The NearestNeighbor object is constructed with a vector of points (type pos_t) and a distance function (type distfun_t). However the object does not store the points. When querying the object with Search(), it's necessary to supply the same vector of points and the same distance function.
There's no capability in this implementation to add or remove points from the set. Instead Initialize() should be called to re-initialize the object with the modified vector of points.
Because of the overhead in constructing a NearestNeighbor object for a large set of points, functions Save() and Load() are provided to save the object to an external file. operator<<(), operator>>() and Boost serialization can also be used to save and restore a NearestNeighbor object. This is illustrated in the example.
Example of use:
#include <iostream>
#include <exception>
#include <vector>
#include <fstream>
#include <string>
#if !defined(GEOGRAPHICLIB_HAVE_BOOST_SERIALIZATION)
#define GEOGRAPHICLIB_HAVE_BOOST_SERIALIZATION 0
#endif
#if GEOGRAPHICLIB_HAVE_BOOST_SERIALIZATION
#include <boost/archive/xml_iarchive.hpp>
#include <boost/archive/xml_oarchive.hpp>
#endif
double _lat, _lon;
};
private:
public:
}
};
try {
vector<pos> locs;
string sa, sb;
{
ifstream is("locations.txt");
if (!is.good())
while (is >> sa >> sb) {
}
if (locs.size() == 0)
}
{
#if GEOGRAPHICLIB_HAVE_BOOST_SERIALIZATION
ifstream is("pointset.xml");
if (is.good()) {
boost::archive::xml_iarchive ia(is);
ia >> BOOST_SERIALIZATION_NVP(pointset);
}
#else
ifstream is("pointset.txt");
if (is.good())
is >> pointset;
#endif
}
if (pointset.
NumPoints() !=
int(locs.size())) {
#if GEOGRAPHICLIB_HAVE_BOOST_SERIALIZATION
ofstream
os(
"pointset.xml");
boost::archive::xml_oarchive oa(
os);
oa << BOOST_SERIALIZATION_NVP(pointset);
#else
ofstream
os(
"pointset.txt");
#endif
}
ifstream is("queries.txt");
int count = 0;
vector<int> k;
while (is >> sa >> sb) {
++count;
if (k.size() != 1)
cout << k[0] <<
" " <<
d <<
"\n";
}
int setupcost, numsearches, searchcost, mincost, maxcost;
pointset.
Statistics(setupcost, numsearches, searchcost,
int
totcost = setupcost + searchcost,
exhaustivecost = count * pointset.
NumPoints();
cerr
<< "Number of distance calculations = " << totcost << "\n"
<< "With an exhaustive search = " << exhaustivecost << "\n"
<< "Ratio = " << double(totcost) / exhaustivecost << "\n"
<< "Efficiency improvement = "
<< 100 * (1 - double(totcost) / exhaustivecost) << "%\n";
}
catch (
const exception&
e) {
cerr <<
"Caught exception: " <<
e.what() <<
"\n";
return 1;
}
}
Definition at line 104 of file NearestNeighbor.hpp.
template<typename dist_t , typename pos_t , class distfun_t >
dist_t GeographicLib::NearestNeighbor< dist_t, pos_t, distfun_t >::Search |
( |
const std::vector< pos_t > & |
pts, |
|
|
const distfun_t & |
dist, |
|
|
const pos_t & |
query, |
|
|
std::vector< int > & |
ind, |
|
|
int |
k = 1 , |
|
|
dist_t |
maxdist = std::numeric_limits<dist_t>::max() , |
|
|
dist_t |
mindist = -1 , |
|
|
bool |
exhaustive = true , |
|
|
dist_t |
tol = 0 |
|
) |
| const |
|
inline |
Search the NearestNeighbor.
- Parameters
-
[in] | pts | the vector of points used for initialization. |
[in] | dist | the distance function object used for initialization. |
[in] | query | the query point. |
[out] | ind | a vector of indices to the closest points found. |
[in] | k | the number of points to search for (default = 1). |
[in] | maxdist | only return points with distances of maxdist or less from query (default is the maximum dist_t). |
[in] | mindist | only return points with distances of more than mindist from query (default = −1). |
[in] | exhaustive | whether to do an exhaustive search (default true). |
[in] | tol | the tolerance on the results (default 0). |
- Returns
- the distance to the closest point found (−1 if no points are found).
- Exceptions
-
GeographicErr | if pts has a different size from that used to construct the object. |
The indices returned in ind are sorted by distance from query (closest first).
The simplest invocation is with just the 4 non-optional arguments. This returns the closest distance and the index to the closest point in ind0. If there are several points equally close, then ind0 gives the index of an arbirary one of them. If there's no closest point (because the set of points is empty), then ind is empty and −1 is returned.
With exhaustive = true and tol = 0 (their default values), this finds the indices of k closest neighbors to query whose distances to query are in (mindist, maxdist]. If mindist and maxdist have their default values, then these bounds have no effect. If query is one of the points in the tree, then set mindist = 0 to prevent this point (and other coincident points) from being returned.
If exhaustive = false, exit as soon as k results satisfying the distance criteria are found. If less than k results are returned then the search was exhaustive even if exhaustive = false.
If tol is positive, do an approximate search; in this case the results are to be interpreted as follows: if the k'th distance is dk, then all results with distances less than or equal dk − tol are correct; all others are suspect — there may be other closer results with distances greater or equal to dk − tol. If less than k results are found, then the search is exact.
mindist should be used to exclude a "small" neighborhood of the query point (relative to the average spacing of the data). If mindist is large, the efficiency of the search deteriorates.
- Note
- Only the shortest distance is returned (as as the function value). The distances to other points (indexed by indj for j > 0) can be found by invoking dist again.
- Warning
- The arguments pts and dist must be identical to those used to initialize the NearestNeighbor; if not, this function will return some meaningless result (however, if the size of pts is wrong, this function throw an exception).
-
The query point cannot be a NaN or infinite because then the metric conditions are violated.
Definition at line 259 of file NearestNeighbor.hpp.