KdTree.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
*
* 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.
*
**********************************************************************/
#pragma once
#include <geos/export.h>
#include <geos/geom/Envelope.h>
#include <geos/index/kdtree/KdNodeVisitor.h>
#include <geos/index/kdtree/KdNode.h>
#include <memory>
#include <vector>
#include <string>
#include <deque>
#ifdef _MSC_VER
#pragma warning(push)
#pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class
#endif
namespace geos {
namespace index { // geos::index
namespace kdtree { // geos::index::kdtree
class GEOS_DLL KdTree {
private:
std::deque<KdNode> nodeQue;
KdNode *root;
std::size_t numberOfNodes;
double tolerance;
KdNode* findBestMatchNode(const geom::Coordinate& p);
KdNode* insertExact(const geom::Coordinate& p, void* data);
void queryNode(KdNode* currentNode, const geom::Envelope& queryEnv, bool odd, KdNodeVisitor& visitor);
KdNode* queryNodePoint(KdNode* currentNode, const geom::Coordinate& queryPt, bool odd);
KdNode* createNode(const geom::Coordinate& p, void* data);
class BestMatchVisitor : public KdNodeVisitor {
public:
BestMatchVisitor(const geom::Coordinate& p_p, double p_tolerance);
geom::Envelope queryEnvelope();
KdNode* getNode();
void visit(KdNode* node) override;
private:
// Members
double tolerance;
KdNode* matchNode;
double matchDist;
const geom::Coordinate& p;
// Declare type as noncopyable
BestMatchVisitor(const BestMatchVisitor& other);
BestMatchVisitor& operator=(const BestMatchVisitor& rhs);
};
class AccumulatingVisitor : public KdNodeVisitor {
public:
AccumulatingVisitor(std::vector<KdNode*>& p_nodeList) :
nodeList(p_nodeList) {};
void visit(KdNode* node) override { nodeList.push_back(node); }
private:
// Members
std::vector<KdNode*>& nodeList;
// Declare type as noncopyable
AccumulatingVisitor(const AccumulatingVisitor& other);
AccumulatingVisitor& operator=(const AccumulatingVisitor& rhs);
};
public:
static std::unique_ptr<std::vector<geom::Coordinate>> toCoordinates(std::vector<KdNode*>& kdnodes);
static std::unique_ptr<std::vector<geom::Coordinate>> toCoordinates(std::vector<KdNode*>& kdnodes, bool includeRepeated);
KdTree() :
root(nullptr),
numberOfNodes(0),
tolerance(0.0)
{};
KdTree(double p_tolerance) :
root(nullptr),
numberOfNodes(0),
tolerance(p_tolerance)
{};
bool isEmpty() { return root == nullptr; }
KdNode* insert(const geom::Coordinate& p);
KdNode* insert(const geom::Coordinate& p, void* data);
void query(const geom::Envelope& queryEnv, KdNodeVisitor& visitor);
std::unique_ptr<std::vector<KdNode*>> query(const geom::Envelope& queryEnv);
void query(const geom::Envelope& queryEnv, std::vector<KdNode*>& result);
KdNode* query(const geom::Coordinate& queryPt);
};
} // namespace geos::index::kdtree
} // namespace geos::index
} // namespace geos
#ifdef _MSC_VER
#pragma warning(pop)
#endif
geos::geom::Coordinate
Coordinate is the lightweight class used to store coordinates.
Definition Coordinate.h:217
geos::geom::Envelope
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition Envelope.h:59
geos::index::kdtree::KdNode
Definition KdNode.h:30
geos::index::kdtree::KdTree
Definition KdTree.h:55
geos::index::kdtree::KdTree::query
KdNode * query(const geom::Coordinate &queryPt)
geos::index::kdtree::KdTree::toCoordinates
static std::unique_ptr< std::vector< geom::Coordinate > > toCoordinates(std::vector< KdNode * > &kdnodes, bool includeRepeated)
geos::index::kdtree::KdTree::query
std::unique_ptr< std::vector< KdNode * > > query(const geom::Envelope &queryEnv)
geos::index::kdtree::KdTree::toCoordinates
static std::unique_ptr< std::vector< geom::Coordinate > > toCoordinates(std::vector< KdNode * > &kdnodes)
geos::index::kdtree::KdTree::insert
KdNode * insert(const geom::Coordinate &p)
geos::index::kdtree::KdTree::query
void query(const geom::Envelope &queryEnv, KdNodeVisitor &visitor)
geos::index::kdtree::KdTree::query
void query(const geom::Envelope &queryEnv, std::vector< KdNode * > &result)
geos::index
Provides classes for various kinds of spatial indexes.
Definition CleanCoverage.h:39
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38