PolygonHoleJoiner.h

/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
 *
 * 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.
 *
 **********************************************************************/
 
#pragma once
 
#include <geos/geom/Coordinate.h>
#include <geos/noding/SegmentSetMutualIntersector.h>
 
#include <unordered_map>
#include <vector>
 
// Forward declarations
namespace geos {
namespace geom {
class Envelope;
class Geometry;
class CoordinateSequence;
class LinearRing;
}
namespace noding {
class SegmentString;
}
}
 
using geos::geom::Coordinate;
using geos::geom::CoordinateSequence;
using geos::geom::Polygon;
using geos::geom::LinearRing;
 
 
namespace geos {
namespace triangulate {
namespace polygon {
 
 
 
class GEOS_DLL PolygonHoleJoiner {
 
private:
 
    // Members
 
    static constexpr double EPS = 1.0E-4;
 
    std::vector<Coordinate> shellCoords;
 
    // orderedCoords is a copy of shellCoords for sort purposes
    std::set<Coordinate> shellCoordsSorted;
 
    // Key: starting end of the cut; Value: list of the other end of the cut
    std::unordered_map<Coordinate, std::vector<Coordinate>, Coordinate::HashCode> cutMap;
 
    std::unique_ptr<noding::SegmentSetMutualIntersector> polygonIntersector;
    const Polygon* inputPolygon;
 
    // The segstrings allocated in createPolygonIntersector need a
    // place to hold ownership through the lifecycle of the hole joiner
    std::vector<std::unique_ptr<noding::SegmentString>> polySegStringStore;
 
    // Methods
 
    static std::vector<Coordinate> ringCoordinates(const LinearRing* ring);
 
    void joinHoles();
 
    void joinHole(const LinearRing* hole);
 
    std::size_t getShellCoordIndex(const Coordinate& shellVertex, const Coordinate& holeVertex);
 
    std::size_t getShellCoordIndexSkip(const Coordinate& coord, std::size_t numSkip);
 
    std::vector<Coordinate> findLeftShellVertices(const Coordinate& holeCoord);
 
    bool isJoinable(const Coordinate& holeCoord, const Coordinate& shellCoord) const;
 
    bool crossesPolygon(const Coordinate& p0, const Coordinate& p1) const;
 
    void addHoleToShell(std::size_t shellVertexIndex, const CoordinateSequence* holeCoords, std::size_t holeVertexIndex);
 
    static std::vector<const LinearRing*> sortHoles(const Polygon* poly);
 
    static std::vector<std::size_t> findLeftVertices(const LinearRing* ring);
 
    std::unique_ptr<noding::SegmentSetMutualIntersector> createPolygonIntersector(const Polygon* polygon);
 
 
public:
 
    PolygonHoleJoiner(const Polygon* p_inputPolygon);
 
    static std::vector<Coordinate> join(const Polygon* inputPolygon);
    static std::unique_ptr<Polygon> joinAsPolygon(const Polygon* inputPolygon);
 
    std::vector<Coordinate> compute();
 
 
};
 
 
 
} // namespace geos.triangulate.polygon
} // namespace geos.triangulate
} // namespace geos