STRtree.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2006 Refractions Research Inc.
*
* 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: index/strtree/STRtree.java rev. 1.11
*
**********************************************************************/
#pragma once
#include <geos/export.h>
#include <geos/index/strtree/ItemDistance.h>
#include <geos/index/strtree/BoundablePair.h>
#include <geos/index/strtree/AbstractSTRtree.h> // for inheritance
#include <geos/index/SpatialIndex.h> // for inheritance
#include <geos/geom/Envelope.h> // for inlines
#include <vector>
#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
// Forward declarations
namespace geos {
namespace index {
namespace strtree {
class Boundable;
}
}
}
namespace geos {
namespace index { // geos::index
namespace strtree { // geos::index::strtree
class GEOS_DLL STRtree: public AbstractSTRtree, public SpatialIndex {
using AbstractSTRtree::insert;
using AbstractSTRtree::query;
private:
class GEOS_DLL STRIntersectsOp: public AbstractSTRtree::IntersectsOp {
public:
bool intersects(const void* aBounds, const void* bBounds) override;
};
std::unique_ptr<BoundableList> createParentBoundables(BoundableList* childBoundables, int newLevel) override;
std::unique_ptr<BoundableList> createParentBoundablesFromVerticalSlices(std::vector<BoundableList*>* verticalSlices,
int newLevel);
STRIntersectsOp intersectsOp;
std::unique_ptr<BoundableList> sortBoundablesY(const BoundableList* input);
std::unique_ptr<BoundableList> sortBoundablesX(const BoundableList* input);
std::unique_ptr<BoundableList> createParentBoundablesFromVerticalSlice(
BoundableList* childBoundables,
int newLevel);
std::vector<BoundableList*>* verticalSlices(
BoundableList* childBoundables,
std::size_t sliceCount);
bool isWithinDistance(BoundablePair* initBndPair, double maxDistance);
protected:
AbstractNode* createNode(int level) override;
IntersectsOp*
getIntersectsOp() override
{
return &intersectsOp;
}
public:
~STRtree() override = default;
STRtree(std::size_t nodeCapacity = 10);
void insert(const geom::Envelope* itemEnv, void* item) override;
//static double centreX(const geom::Envelope *e);
static double
avg(double a, double b)
{
return (a + b) / 2.0;
}
static double
centreY(const geom::Envelope* e)
{
return STRtree::avg(e->getMinY(), e->getMaxY());
}
void
query(const geom::Envelope* searchEnv, std::vector<void*>& matches) override
{
AbstractSTRtree::query(searchEnv, matches);
}
void
query(const geom::Envelope* searchEnv, ItemVisitor& visitor) override
{
return AbstractSTRtree::query(searchEnv, visitor);
}
std::pair<const void*, const void*> nearestNeighbour(ItemDistance* itemDist);
const void* nearestNeighbour(const geom::Envelope* env, const void* item, ItemDistance* itemDist);
std::pair<const void*, const void*> nearestNeighbour(STRtree* tree, ItemDistance* itemDist);
std::pair<const void*, const void*> nearestNeighbour(BoundablePair* initBndPair);
std::pair<const void*, const void*> nearestNeighbour(BoundablePair* initBndPair, double maxDistance);
bool
remove(const geom::Envelope* itemEnv, void* item) override
{
return AbstractSTRtree::remove(itemEnv, item);
}
bool isWithinDistance(STRtree* tree, ItemDistance* itemDist, double maxDistance);
};
} // namespace geos::index::strtree
} // namespace geos::index
} // namespace geos
#ifdef _MSC_VER
#pragma warning(pop)
#endif
geos::geom::Envelope
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition Envelope.h:59
geos::geom::Envelope::getMaxY
double getMaxY() const
Returns the Envelope maximum y-value. Null envelopes do not have maximum values.
Definition Envelope.h:320
geos::geom::Envelope::getMinY
double getMinY() const
Returns the Envelope minimum y-value. Null envelopes do not have maximum values.
Definition Envelope.h:340
geos::index::ItemVisitor
A visitor for items in an index.
Definition ItemVisitor.h:28
geos::index::SpatialIndex
Abstract class defines basic insertion and query operations supported by classes implementing spatial...
Definition SpatialIndex.h:46
geos::index::strtree::AbstractNode
A node of the STR tree.
Definition AbstractNode.h:43
geos::index::strtree::AbstractSTRtree::IntersectsOp
A test for intersection between two bounds, necessary because subclasses of AbstractSTRtree have diff...
Definition AbstractSTRtree.h:175
geos::index::strtree::AbstractSTRtree::insert
virtual void insert(const void *bounds, void *item)
Also builds the tree, if necessary.
geos::index::strtree::AbstractSTRtree::query
void query(const void *searchBounds, std::vector< void * > &foundItems)
Also builds the tree, if necessary.
geos::index::strtree::BoundablePair
A pair of Boundables, whose leaf items support a distance metric between them.
Definition BoundablePair.h:43
geos::index::strtree::Boundable
A spatial object in an AbstractSTRtree.
Definition Boundable.h:24
geos::index::strtree::ItemDistance
A function method which computes the distance between two ItemBoundables in an STRtree....
Definition ItemDistance.h:33
geos::index::strtree::STRtree
A query-only R-tree created using the Sort-Tile-Recursive (STR) algorithm. For two-dimensional spatia...
Definition STRtree.h:63
geos::index::strtree::STRtree::STRtree
STRtree(std::size_t nodeCapacity=10)
geos::index::strtree::STRtree::query
void query(const geom::Envelope *searchEnv, ItemVisitor &visitor) override
Queries the index for all items whose extents intersect the given search Envelope and applies an Item...
Definition STRtree.h:148
geos::index::strtree::STRtree::getIntersectsOp
IntersectsOp * getIntersectsOp() override
Definition STRtree.h:110
geos::index::strtree::STRtree::insert
void insert(const geom::Envelope *itemEnv, void *item) override
Adds a spatial item with an extent specified by the given Envelope to the index.
geos::index::strtree::STRtree::query
void query(const geom::Envelope *searchEnv, std::vector< void * > &matches) override
Queries the index for all items whose extents intersect the given search Envelope.
Definition STRtree.h:142
geos::index::strtree::STRtree::remove
bool remove(const geom::Envelope *itemEnv, void *item) override
Removes a single item from the tree.
Definition STRtree.h:160
geos::index::strtree
Contains 2-D and 1-D versions of the Sort-Tile-Recursive (STR) tree, a query-only R-tree.
Definition AbstractNode.h:31
geos::index::strtree::BoundableList
std::vector< Boundable * > BoundableList
A list of boundables. TODO: use a list.
Definition AbstractSTRtree.h:43
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