QuadEdgeSubdivision.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2012 Excensus LLC.
* Copyright (C) 2019 Daniel Baston
*
* This is free software; you can redistribute and/or modify it under
* the terms of the GNU Lesser General Licence as published
* by the Free Software Foundation.
* See the COPYING file for more information.
*
**********************************************************************
*
* Last port: triangulate/quadedge/QuadEdgeSubdivision.java r524
*
**********************************************************************/
#pragma once
#include <memory>
#include <list>
#include <stack>
#include <unordered_set>
#include <array>
#include <vector>
#include <geos/geom/MultiLineString.h>
#include <geos/triangulate/quadedge/QuadEdge.h>
#include <geos/triangulate/quadedge/QuadEdgeLocator.h>
#include <geos/triangulate/quadedge/QuadEdgeQuartet.h>
#include <geos/triangulate/quadedge/Vertex.h>
namespace geos {
namespace geom {
class CoordinateSequence;
class GeometryCollection;
class MultiLineString;
class GeometryFactory;
class Coordinate;
class Geometry;
class Envelope;
}
namespace triangulate { //geos.triangulate
namespace quadedge { //geos.triangulate.quadedge
class TriangleVisitor;
class GEOS_DLL QuadEdgeSubdivision {
public:
typedef std::vector<QuadEdge*> QuadEdgeList;
static void getTriangleEdges(const QuadEdge& startQE,
const QuadEdge* triEdge[3]);
private:
std::deque<QuadEdgeQuartet> quadEdges;
std::array<QuadEdge*, 3> startingEdges;
double tolerance;
double edgeCoincidenceTolerance;
std::array<Vertex, 3> frameVertex;
geom::Envelope frameEnv;
std::unique_ptr<QuadEdgeLocator> locator;
bool visit_state_clean;
public:
QuadEdgeSubdivision(const geom::Envelope& env, double tolerance);
virtual ~QuadEdgeSubdivision() = default;
private:
virtual void createFrame(const geom::Envelope& env);
virtual void initSubdiv();
public:
inline double
getTolerance() const
{
return tolerance;
}
inline const geom::Envelope&
getEnvelope() const
{
return frameEnv;
}
inline std::deque<QuadEdgeQuartet>&
getEdges()
{
return quadEdges;
}
inline void
setLocator(std::unique_ptr<QuadEdgeLocator> p_locator)
{
this->locator = std::move(p_locator);
}
virtual QuadEdge& makeEdge(const Vertex& o, const Vertex& d);
virtual QuadEdge& connect(QuadEdge& a, QuadEdge& b);
void remove(QuadEdge& e);
QuadEdge* locateFromEdge(const Vertex& v,
const QuadEdge& startEdge) const;
inline QuadEdge*
locate(const Vertex& v) const
{
return locator->locate(v);
}
inline QuadEdge*
locate(const geom::Coordinate& p)
{
return locator->locate(Vertex(p));
}
QuadEdge* locate(const geom::Coordinate& p0, const geom::Coordinate& p1);
QuadEdge& insertSite(const Vertex& v);
bool isFrameEdge(const QuadEdge& e) const;
bool isFrameBorderEdge(const QuadEdge& e) const;
bool isFrameVertex(const Vertex& v) const;
bool isOnEdge(const QuadEdge& e, const geom::Coordinate& p) const;
bool isVertexOfEdge(const QuadEdge& e, const Vertex& v) const;
std::unique_ptr<QuadEdgeList> getPrimaryEdges(bool includeFrame);
/*****************************************************************************
* Visitors
****************************************************************************/
void visitTriangles(TriangleVisitor* triVisitor, bool includeFrame);
private:
typedef std::stack<QuadEdge*> QuadEdgeStack;
typedef std::vector<std::unique_ptr<geom::CoordinateSequence>> TriList;
std::array<QuadEdge*, 3> m_triEdges;
void prepareVisit();
std::array<QuadEdge*, 3>* fetchTriangleToVisit(QuadEdge* edge, QuadEdgeStack& edgeStack, bool includeFrame);
void getTriangleCoordinates(TriList* triList, bool includeFrame);
private:
class TriangleCoordinatesVisitor;
class TriangleCircumcentreVisitor;
public:
std::unique_ptr<geom::MultiLineString> getEdges(const geom::GeometryFactory& geomFact);
std::unique_ptr<geom::GeometryCollection> getTriangles(const geom::GeometryFactory& geomFact);
std::unique_ptr<geom::GeometryCollection> getVoronoiDiagram(const geom::GeometryFactory& geomFact);
std::unique_ptr<geom::MultiLineString> getVoronoiDiagramEdges(const geom::GeometryFactory& geomFact);
std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellPolygons(const geom::GeometryFactory& geomFact);
std::vector<std::unique_ptr<geom::Geometry>> getVoronoiCellEdges(const geom::GeometryFactory& geomFact);
std::unique_ptr<QuadEdgeSubdivision::QuadEdgeList> getVertexUniqueEdges(bool includeFrame);
std::unique_ptr<geom::Geometry> getVoronoiCellPolygon(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
std::unique_ptr<geom::Geometry> getVoronoiCellEdge(const QuadEdge* qe, const geom::GeometryFactory& geomFact);
};
} //namespace geos.triangulate.quadedge
} //namespace geos.triangulate
} //namespace goes
geos::geom::CoordinateSequence
The internal representation of a list of coordinates inside a Geometry.
Definition CoordinateSequence.h:56
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::geom::GeometryCollection
Represents a collection of heterogeneous Geometry objects.
Definition GeometryCollection.h:51
geos::geom::GeometryFactory
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition GeometryFactory.h:70
geos::geom::Geometry
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition Geometry.h:196
geos::geom::MultiLineString
Models a collection of LineStrings.
Definition MultiLineString.h:49
geos::triangulate::quadedge::QuadEdgeSubdivision::locateFromEdge
QuadEdge * locateFromEdge(const Vertex &v, const QuadEdge &startEdge) const
Locates an edge of a triangle which contains a location specified by a Vertex v.
geos::triangulate::quadedge::QuadEdgeSubdivision::isFrameBorderEdge
bool isFrameBorderEdge(const QuadEdge &e) const
Tests whether a QuadEdge is an edge on the border of the frame facets and the internal facets....
geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellEdges
std::vector< std::unique_ptr< geom::Geometry > > getVoronoiCellEdges(const geom::GeometryFactory &geomFact)
Gets a List of LineStrings for the Voronoi cells of this triangulation.
geos::triangulate::quadedge::QuadEdgeSubdivision::getVertexUniqueEdges
std::unique_ptr< QuadEdgeSubdivision::QuadEdgeList > getVertexUniqueEdges(bool includeFrame)
Gets a collection of QuadEdges whose origin vertices are a unique set which includes all vertices in ...
geos::triangulate::quadedge::QuadEdgeSubdivision::insertSite
QuadEdge & insertSite(const Vertex &v)
Inserts a new site into the Subdivision, connecting it to the vertices of the containing triangle (or...
geos::triangulate::quadedge::QuadEdgeSubdivision::isFrameEdge
bool isFrameEdge(const QuadEdge &e) const
Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
geos::triangulate::quadedge::QuadEdgeSubdivision::connect
virtual QuadEdge & connect(QuadEdge &a, QuadEdge &b)
Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all thr...
geos::triangulate::quadedge::QuadEdgeSubdivision::getTriangleEdges
static void getTriangleEdges(const QuadEdge &startQE, const QuadEdge *triEdge[3])
Gets the edges for the triangle to the left of the given QuadEdge.
geos::triangulate::quadedge::QuadEdgeSubdivision::isFrameVertex
bool isFrameVertex(const Vertex &v) const
Tests whether a vertex is a vertex of the outer triangle.
geos::triangulate::quadedge::QuadEdgeSubdivision::remove
void remove(QuadEdge &e)
Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.
geos::triangulate::quadedge::QuadEdgeSubdivision::locate
QuadEdge * locate(const geom::Coordinate &p)
Finds a quadedge of a triangle containing a location specified by a geom::Coordinate,...
Definition QuadEdgeSubdivision.h:251
geos::triangulate::quadedge::QuadEdgeSubdivision::getTriangles
std::unique_ptr< geom::GeometryCollection > getTriangles(const geom::GeometryFactory &geomFact)
Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangul...
geos::triangulate::quadedge::QuadEdgeSubdivision::getEdges
std::deque< QuadEdgeQuartet > & getEdges()
Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
Definition QuadEdgeSubdivision.h:155
geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellPolygons
std::vector< std::unique_ptr< geom::Geometry > > getVoronoiCellPolygons(const geom::GeometryFactory &geomFact)
Gets a List of Polygons for the Voronoi cells of this triangulation.
geos::triangulate::quadedge::QuadEdgeSubdivision::locate
QuadEdge * locate(const geom::Coordinate &p0, const geom::Coordinate &p1)
Locates the edge between the given vertices, if it exists in the subdivision.
geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellPolygon
std::unique_ptr< geom::Geometry > getVoronoiCellPolygon(const QuadEdge *qe, const geom::GeometryFactory &geomFact)
Gets the Voronoi cell around a site specified by the origin of a QuadEdge.
geos::triangulate::quadedge::QuadEdgeSubdivision::QuadEdgeSubdivision
QuadEdgeSubdivision(const geom::Envelope &env, double tolerance)
Creates a new instance of a quad-edge subdivision based on a frame triangle that encloses a supplied ...
geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiDiagramEdges
std::unique_ptr< geom::MultiLineString > getVoronoiDiagramEdges(const geom::GeometryFactory &geomFact)
Gets the cells in the Voronoi diagram for this triangulation.
geos::triangulate::quadedge::QuadEdgeSubdivision::getTolerance
double getTolerance() const
Gets the vertex-equality tolerance value used in this subdivision.
Definition QuadEdgeSubdivision.h:132
geos::triangulate::quadedge::QuadEdgeSubdivision::makeEdge
virtual QuadEdge & makeEdge(const Vertex &o, const Vertex &d)
Creates a new quadedge, recording it in the edges list.
geos::triangulate::quadedge::QuadEdgeSubdivision::isOnEdge
bool isOnEdge(const QuadEdge &e, const geom::Coordinate &p) const
Tests whether a Coordinate lies on a QuadEdge, up to a tolerance determined by the subdivision tolera...
geos::triangulate::quadedge::QuadEdgeSubdivision::locate
QuadEdge * locate(const Vertex &v) const
Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists.
Definition QuadEdgeSubdivision.h:235
geos::triangulate::quadedge::QuadEdgeSubdivision::getPrimaryEdges
std::unique_ptr< QuadEdgeList > getPrimaryEdges(bool includeFrame)
Gets all primary quadedges in the subdivision.
geos::triangulate::quadedge::QuadEdgeSubdivision::getEnvelope
const geom::Envelope & getEnvelope() const
Gets the envelope of the Subdivision (including the frame).
Definition QuadEdgeSubdivision.h:143
geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiDiagram
std::unique_ptr< geom::GeometryCollection > getVoronoiDiagram(const geom::GeometryFactory &geomFact)
Gets the cells in the Voronoi diagram for this triangulation. The cells are returned as a GeometryCol...
geos::triangulate::quadedge::QuadEdgeSubdivision::setLocator
void setLocator(std::unique_ptr< QuadEdgeLocator > p_locator)
Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
Definition QuadEdgeSubdivision.h:168
geos::triangulate::quadedge::QuadEdgeSubdivision::isVertexOfEdge
bool isVertexOfEdge(const QuadEdge &e, const Vertex &v) const
Tests whether a Vertex is the start or end vertex of a QuadEdge, up to the subdivision tolerance dist...
geos::triangulate::quadedge::QuadEdgeSubdivision::getEdges
std::unique_ptr< geom::MultiLineString > getEdges(const geom::GeometryFactory &geomFact)
Gets the geometry for the edges in the subdivision as a MultiLineString containing 2-point lines.
geos::triangulate::quadedge::QuadEdgeSubdivision::getVoronoiCellEdge
std::unique_ptr< geom::Geometry > getVoronoiCellEdge(const QuadEdge *qe, const geom::GeometryFactory &geomFact)
Gets the Voronoi cell edge around a site specified by the origin of a QuadEdge.
geos::triangulate::quadedge::QuadEdge
A class that represents the edge data structure which implements the quadedge algebra.
Definition QuadEdge.h:53
geos::triangulate::quadedge::TriangleVisitor
An interface for algorithms which process the triangles in a QuadEdgeSubdivision.
Definition TriangleVisitor.h:33
geos::triangulate::quadedge::Vertex
Models a site (node) in a QuadEdgeSubdivision.
Definition Vertex.h:60
geos::geom
Definition Angle.h:26
geos::triangulate::quadedge
Classes to implement a topological subdivision of quadeges, to support creating triangulations and Vo...
Definition ConcaveHull.h:33
geos::triangulate
Classes to compute Delaunay triangulations.
Definition ConcaveHull.h:32
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38