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;
 
const double EDGE_COINCIDENCE_TOL_FACTOR = 1000;
 
//-- Frame size factor for initializing subdivision frame.  Larger is more robust
const double FRAME_SIZE_FACTOR = 100;
 
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