GeographicLib: GeographicLib::NearestNeighbor< dist_t, pos_t, distfun_t (original) (raw)

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 Finding nearest neighbors.

This class is templated so that it can handle arbitrary metric spaces as follows:

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.

#include

#include

#include

#include

#include

#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

using namespace std;

struct pos {

double _lat, _lon;

pos(double lat = 0, double lon = 0) : _lat(lat), _lon(lon) {}

};

class DistanceCalculator {

private:

public:

explicit DistanceCalculator(const Geodesic& geod) : _geod(geod) {}

double operator() (const pos& a, const pos& b) const {

double d;

_geod.Inverse(a._lat, a._lon, b._lat, b._lon, d);

if ( !(d >= 0) )

throw GeographicErr("distance doesn't satisfy d >= 0");

return d;

}

};

try {

vector locs;

double lat, lon;

string sa, sb;

{

ifstream is("locations.txt");

if (!is.good())

while (is >> sa >> sb) {

DMS::DecodeLatLon(sa, sb, lat, lon);

locs.push_back(pos(lat, lon));

}

if (locs.size() == 0)

}

DistanceCalculator distance(Geodesic::WGS84());

{

#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())) {

pointset.Initialize(locs, distance);

#if GEOGRAPHICLIB_HAVE_BOOST_SERIALIZATION

ofstream os("pointset.xml");

if (!os.good())

boost::archive::xml_oarchive oa(os);

oa << BOOST_SERIALIZATION_NVP(pointset);

#else

ofstream os("pointset.txt");

if (!os.good())

os << pointset << "\n";

#endif

}

ifstream is("queries.txt");

double d;

int count = 0;

vector k;

while (is >> sa >> sb) {

++count;

DMS::DecodeLatLon(sa, sb, lat, lon);

d = pointset.Search(locs, distance, pos(lat, lon), k);

if (k.size() != 1)

cout << k[0] << " " << d << "\n";

}

int setupcost, numsearches, searchcost, mincost, maxcost;

double mean, sd;

pointset.Statistics(setupcost, numsearches, searchcost,

mincost, maxcost, mean, sd);

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;

}

}

int main(int argc, const char *const argv[])

Header for GeographicLib::DMS class.

Header for GeographicLib::Geodesic class.

Header for GeographicLib::NearestNeighbor class.

Math::real Inverse(real lat1, real lon1, real lat2, real lon2, real &s12, real &azi1, real &azi2, real &m12, real &M12, real &M21, real &S12) const

Exception handling for GeographicLib.

Nearest-neighbor calculations.

void Statistics(int &setupcost, int &numsearches, int &searchcost, int &mincost, int &maxcost, double &mean, double &sd) const

dist_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

void Initialize(const std::vector< pos_t > &pts, const distfun_t &dist, int bucket=4)

Namespace for GeographicLib.