PolygonHoleJoiner.h

/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2023 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/geom/CoordinateSequence.h>
#include <geos/algorithm/LineIntersector.h>
#include <geos/noding/SegmentIntersector.h>
#include <geos/noding/BasicSegmentString.h>
#include <geos/noding/SegmentSetMutualIntersector.h>
#include <geos/constants.h>
 
#include <set>
#include <limits>
 
// Forward declarations
namespace geos {
namespace geom {
class Envelope;
class Geometry;
class LinearRing;
class Polygon;
}
namespace noding {
}
}
 
namespace geos {
namespace triangulate {
namespace polygon {
 
 

class GEOS_DLL PolygonHoleJoiner {
    using Coordinate = geos::geom::Coordinate;
    using CoordinateSequence = geos::geom::CoordinateSequence;
    using Polygon = geos::geom::Polygon;
    using LinearRing = geos::geom::LinearRing;
    using BasicSegmentString = geos::noding::BasicSegmentString;
    using SegmentSetMutualIntersector = geos::noding::SegmentSetMutualIntersector;
 
private:
 
    // Members
 
    const Polygon* inputPolygon;
 
    //-- normalized, sorted and noded polygon rings
    std::unique_ptr<CoordinateSequence> shellRing;
    std::vector<std::unique_ptr<CoordinateSequence>> holeRings;
 
    //-- indicates whether a hole should be testing for touching
    std::vector<bool> isHoleTouchingHint;
 
    CoordinateSequence joinedRing;
 
    // a sorted and searchable version of the joinedRing
    std::set<Coordinate> joinedPts;
 
    std::unique_ptr<SegmentSetMutualIntersector> boundaryIntersector;
 
    // holding place for some BasicSegmentStrings
    std::vector<std::unique_ptr<BasicSegmentString>> polySegStringStore;
 
 
    // Classes
    class InteriorIntersectionDetector;
    friend class PolygonHoleJoiner::InteriorIntersectionDetector;
 
 
    void extractOrientedRings(const Polygon* polygon);
    static std::unique_ptr<CoordinateSequence> extractOrientedRing(const LinearRing* ring, bool isCW);
    void nodeRings();
    void joinHoles();
 
    void joinHole(std::size_t index, const CoordinateSequence& holeCoords);

    bool joinTouchingHole(const CoordinateSequence& holeCoords);

    std::size_t findHoleTouchIndex(const CoordinateSequence& holeCoords);

    void joinNonTouchingHole(
        const CoordinateSequence& holeCoords);
 
    const Coordinate& findJoinableVertex(
        const Coordinate& holeJoinCoord);

    std::size_t findJoinIndex(
        const Coordinate& joinCoord,
        const Coordinate& holeJoinCoord);

    static bool isLineInterior(
        const CoordinateSequence& ring,
        std::size_t ringIndex,
        const Coordinate& linePt);
 
    static std::size_t prev(std::size_t i, std::size_t size);
    static std::size_t next(std::size_t i, std::size_t size);

    void addJoinedHole(
        std::size_t joinIndex,
        const CoordinateSequence& holeCoords,
        std::size_t holeJoinIndex);

    std::vector<Coordinate> createHoleSection(
        const CoordinateSequence& holeCoords,
        std::size_t holeJoinIndex,
        const Coordinate& joinPt);

    static std::vector<const LinearRing*> sortHoles(
        const Polygon* poly);
 
    static std::size_t findLowestLeftVertexIndex(
        const CoordinateSequence& holeCoords);

    bool intersectsBoundary(
        const Coordinate& p0,
        const Coordinate& p1);
 
    std::unique_ptr<SegmentSetMutualIntersector> createBoundaryIntersector();
 
 
public:
 
    PolygonHoleJoiner(const Polygon* p_inputPolygon)
        : inputPolygon(p_inputPolygon)
        , boundaryIntersector(nullptr)
        {};

    static std::unique_ptr<Polygon> joinAsPolygon(
        const Polygon* p_inputPolygon);

    static std::unique_ptr<CoordinateSequence> join(
        const Polygon* p_inputPolygon);

    std::unique_ptr<CoordinateSequence> compute();
 
};
 
 
} // namespace geos.triangulate.polygon
} // namespace geos.triangulate
} // namespace geos