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
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::Geometry
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition Geometry.h:196
geos::geom::LinearRing
Models an OGC SFS LinearRing. A LinearRing is a LineString which is both closed and simple.
Definition LinearRing.h:54
geos::geom::Polygon
Represents a linear polygon, which may include holes.
Definition Polygon.h:61
geos::noding::BasicSegmentString
Represents a list of contiguous line segments, and supports noding the segments.
Definition BasicSegmentString.h:44
geos::noding::SegmentSetMutualIntersector
An intersector for the red-blue intersection problem.
Definition SegmentSetMutualIntersector.h:36
geos::triangulate::polygon::PolygonHoleJoiner::join
static std::unique_ptr< CoordinateSequence > join(const Polygon *p_inputPolygon)
geos::triangulate::polygon::PolygonHoleJoiner::joinAsPolygon
static std::unique_ptr< Polygon > joinAsPolygon(const Polygon *p_inputPolygon)
geos::triangulate::polygon::PolygonHoleJoiner::compute
std::unique_ptr< CoordinateSequence > compute()
geos::geom
Definition Angle.h:26
geos::index
Provides classes for various kinds of spatial indexes.
Definition CleanCoverage.h:39
geos::noding
Classes to compute nodings for arrangements of line segments and line segment sequences.
Definition CoverageCleaner.h:42
geos::triangulate
Classes to compute Delaunay triangulations.
Definition ConcaveHull.h:32
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38