ConcaveHullOfPolygons.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2022 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/triangulate/tri/TriList.h>
#include <geos/triangulate/tri/Tri.h>
#include <set>
#include <deque>
#include <map>
namespace geos {
namespace geom {
class Coordinate;
class CoordinateSequence;
class Envelope;
class Geometry;
class GeometryCollection;
class GeometryFactory;
class LinearRing;
class Polygon;
}
namespace triangulate {
namespace tri {
class Tri;
}
}
}
namespace geos {
namespace algorithm { // geos::algorithm
namespace hull { // geos::algorithm::hull
class GEOS_DLL ConcaveHullOfPolygons {
using Coordinate = geos::geom::Coordinate;
using CoordinateSequence = geos::geom::CoordinateSequence;
using Envelope = geos::geom::Envelope;
using Geometry = geos::geom::Geometry;
using GeometryCollection = geos::geom::GeometryCollection;
using GeometryFactory = geos::geom::GeometryFactory;
using LinearRing = geos::geom::LinearRing;
using Polygon = geos::geom::Polygon;
using Tri = geos::triangulate::tri::Tri;
template<typename TriType>
using TriList = geos::triangulate::tri::TriList<TriType>;
private:
/* Members */
static constexpr int FRAME_EXPAND_FACTOR = 4;
const Geometry* inputPolygons;
const GeometryFactory* geomFactory;
double maxEdgeLength;
double maxEdgeLengthRatio;
bool isHolesAllowed;
bool isTight;
std::set<Tri*> hullTris;
std::deque<Tri*> borderTriQue;
std::vector<const LinearRing*> polygonRings;
TriList<Tri> triList;
std::map<Tri*, TriIndex> borderEdgeMap;
/* Methods */
std::unique_ptr<Geometry> createEmptyHull();
void buildHullTris();
std::unique_ptr<Polygon> createFrame(
const Envelope* polygonsEnv);
double computeTargetEdgeLength(
TriList<Tri>& triList,
const CoordinateSequence* frameCorners,
double edgeLengthRatio) const;
bool isFrameTri(
const Tri* tri,
const CoordinateSequence* frameCorners) const;
void removeFrameCornerTris(
TriList<Tri>& tris,
const CoordinateSequence* frameCorners);
TriIndex vertexIndex(
const Tri* tri,
const CoordinateSequence* pts) const;
void removeBorderTris();
void removeHoleTris();
Tri* findHoleSeedTri() const;
bool isHoleSeedTri(const Tri* tri) const;
bool isBorderTri(const Tri* tri) const;
bool isRemovable(const Tri* tri) const;
bool isTouchingSinglePolygon(const Tri* tri) const;
void addBorderTris(Tri* tri);
void addBorderTri(Tri* tri, TriIndex index);
void removeBorderTri(Tri* tri);
bool hasAllVertices(const LinearRing* ring, const Tri* tri) const;
bool hasVertex(const LinearRing* ring, const Coordinate& v) const;
void envelope(const Tri* tri, Envelope& env) const;
std::unique_ptr<Geometry> createHullGeometry(bool isIncludeInput);
public:
static std::unique_ptr<Geometry>
concaveHullByLength(const Geometry* polygons, double maxLength);
static std::unique_ptr<Geometry>
concaveHullByLength(
const Geometry* polygons, double maxLength,
bool isTight, bool isHolesAllowed);
static std::unique_ptr<Geometry>
concaveHullByLengthRatio(const Geometry* polygons, double lengthRatio);
static std::unique_ptr<Geometry>
concaveHullByLengthRatio(
const Geometry* polygons, double lengthRatio,
bool isTight, bool isHolesAllowed);
static std::unique_ptr<Geometry>
concaveFillByLength(const Geometry* polygons, double maxLength);
static std::unique_ptr<Geometry>
concaveFillByLengthRatio(const Geometry* polygons, double lengthRatio);
ConcaveHullOfPolygons(const Geometry* geom);
void setMaximumEdgeLength(double edgeLength);
void setMaximumEdgeLengthRatio(double edgeLengthRatio);
void setHolesAllowed(bool p_isHolesAllowed);
void setTight(bool p_isTight);
std::unique_ptr<Geometry> getHull();
std::unique_ptr<Geometry> getFill();
};
} // geos::algorithm::hull
} // geos::algorithm
} // geos
geos::algorithm::hull::ConcaveHullOfPolygons::setTight
void setTight(bool p_isTight)
geos::algorithm::hull::ConcaveHullOfPolygons::getFill
std::unique_ptr< Geometry > getFill()
geos::algorithm::hull::ConcaveHullOfPolygons::concaveHullByLengthRatio
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *polygons, double lengthRatio, bool isTight, bool isHolesAllowed)
geos::algorithm::hull::ConcaveHullOfPolygons::concaveHullByLength
static std::unique_ptr< Geometry > concaveHullByLength(const Geometry *polygons, double maxLength, bool isTight, bool isHolesAllowed)
geos::algorithm::hull::ConcaveHullOfPolygons::concaveHullByLength
static std::unique_ptr< Geometry > concaveHullByLength(const Geometry *polygons, double maxLength)
geos::algorithm::hull::ConcaveHullOfPolygons::concaveHullByLengthRatio
static std::unique_ptr< Geometry > concaveHullByLengthRatio(const Geometry *polygons, double lengthRatio)
geos::algorithm::hull::ConcaveHullOfPolygons::setMaximumEdgeLength
void setMaximumEdgeLength(double edgeLength)
geos::algorithm::hull::ConcaveHullOfPolygons::concaveFillByLengthRatio
static std::unique_ptr< Geometry > concaveFillByLengthRatio(const Geometry *polygons, double lengthRatio)
geos::algorithm::hull::ConcaveHullOfPolygons::getHull
std::unique_ptr< Geometry > getHull()
geos::algorithm::hull::ConcaveHullOfPolygons::ConcaveHullOfPolygons
ConcaveHullOfPolygons(const Geometry *geom)
geos::algorithm::hull::ConcaveHullOfPolygons::setHolesAllowed
void setHolesAllowed(bool p_isHolesAllowed)
geos::algorithm::hull::ConcaveHullOfPolygons::setMaximumEdgeLengthRatio
void setMaximumEdgeLengthRatio(double edgeLengthRatio)
geos::algorithm::hull::ConcaveHullOfPolygons::concaveFillByLength
static std::unique_ptr< Geometry > concaveFillByLength(const Geometry *polygons, double maxLength)
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::GeometryCollection
Represents a collection of heterogeneous Geometry objects.
Definition GeometryCollection.h:51
geos::geom::GeometryFactory
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition GeometryFactory.h:70
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::triangulate::tri::TriList
Definition TriList.h:50
geos::triangulate::tri::Tri
Definition Tri.h:45
geos::algorithm
Contains classes and interfaces implementing fundamental computational geometry algorithms.
Definition Angle.h:32
geos::geom
Definition Angle.h:26
geos::index
Provides classes for various kinds of spatial indexes.
Definition CleanCoverage.h:39
geos::triangulate
Classes to compute Delaunay triangulations.
Definition ConcaveHull.h:32
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38