QuadEdgeSubdivision.h

Go to the documentation of this file.

/**********************************************************************
 *
 * 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
 *
 **********************************************************************/

#ifndef GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H
#define GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H

#include <memory>
#include <list>
#include <stack>
#include <unordered_set>
#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;

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;

    QuadEdge* triEdges[3];

    void prepareVisit();

    QuadEdge** 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

#endif //GEOS_TRIANGULATE_QUADEDGE_QUADEDGESUBDIVISION_H