Quadtree.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/quadtree/Quadtree.java rev. 1.16 (JTS-1.10)
*
**********************************************************************/
#pragma once
#include <geos/export.h>
#include <geos/geom/Envelope.h>
#include <geos/index/SpatialIndex.h> // for inheritance
#include <geos/index/quadtree/Root.h> // for composition
#include <memory>
#include <vector>
#include <string>
#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 quadtree {
// class Root;
}
}
}
namespace geos {
namespace index { // geos::index
namespace quadtree { // geos::index::quadtree
class GEOS_DLL Quadtree: public SpatialIndex {
private:
std::vector<std::unique_ptr<geom::Envelope>> newEnvelopes;
void collectStats(const geom::Envelope& itemEnv);
Root root;
double minExtent;
public:
static geom::Envelope* ensureExtent(const geom::Envelope* itemEnv,
double minExtent);
Quadtree()
:
root(),
minExtent(1.0)
{}
~Quadtree() override = default;
std::size_t depth();
std::size_t size();
void insert(const geom::Envelope* itemEnv, void* item) override;
void query(const geom::Envelope* searchEnv, std::vector<void*>& ret) override;
void
query(const geom::Envelope* searchEnv, ItemVisitor& visitor) override
{
/*
* the items that are matched are the items in quads which
* overlap the search envelope
*/
root.visit(searchEnv, visitor);
}
bool remove(const geom::Envelope* itemEnv, void* item) override;
std::vector<void*>* queryAll();
std::string toString() const;
Quadtree(const Quadtree&) = delete;
Quadtree& operator=(const Quadtree&) = delete;
// Move constructor
Quadtree(Quadtree&& other) noexcept :
newEnvelopes(std::move(other.newEnvelopes)),
root(other.root),
minExtent(other.minExtent)
{
// The contents of 'other' are moved to 'this'
// 'other' will be empty after the move
};
// Move assignment operator
Quadtree& operator=(Quadtree&& other) noexcept
{
if (this != &other) {
// Move the vector from 'other' to 'this'
// 'newEnvelopes.data' will be empty after this operation
newEnvelopes.clear();
newEnvelopes = std::move(other.newEnvelopes);
minExtent = other.minExtent;
root = other.root;
}
return *this;
};
};
} // namespace geos::index::quadtree
} // 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::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::quadtree::Quadtree
A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of sp...
Definition Quadtree.h:70
geos::index::quadtree::Quadtree::size
std::size_t size()
Returns the number of items in the tree.
geos::index::quadtree::Quadtree::Quadtree
Quadtree(const Quadtree &)=delete
geos::index::quadtree::Quadtree::remove
bool remove(const geom::Envelope *itemEnv, void *item) override
geos::index::quadtree::Quadtree::depth
std::size_t depth()
Returns the number of levels in the tree.
geos::index::quadtree::Quadtree::query
void query(const geom::Envelope *searchEnv, ItemVisitor &visitor) override
Queries the tree and visits items which may lie in the given search envelope.
Definition Quadtree.h:161
geos::index::quadtree::Quadtree::ensureExtent
static geom::Envelope * ensureExtent(const geom::Envelope *itemEnv, double minExtent)
Ensure that the envelope for the inserted item has non-zero extents.
geos::index::quadtree::Quadtree::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::quadtree::Quadtree::Quadtree
Quadtree()
Constructs a Quadtree with zero items.
Definition Quadtree.h:108
geos::index::quadtree::Quadtree::query
void query(const geom::Envelope *searchEnv, std::vector< void * > &ret) override
Queries the tree and returns items which may lie in the given search envelope.
geos::index::quadtree::Quadtree::queryAll
std::vector< void * > * queryAll()
Return a list of all items in the Quadtree.
geos::index::quadtree::Root
QuadRoot is the root of a single Quadtree. It is centred at the origin, and does not have a defined e...
Definition quadtree/Root.h:48
geos::index::quadtree
Contains classes that implement a Quadtree spatial index.
Definition CleanCoverage.h:40
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