PolygonEarClipper.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/index/VertexSequencePackedRtree.h>
#include <geos/triangulate/tri/TriList.h>
#include <geos/triangulate/tri/Tri.h>
#include <geos/constants.h>
#include <array>
#include <memory>
#include <limits>
// Forward declarations
namespace geos {
namespace geom {
class Coordinate;
class Polygon;
class Envelope;
}
}
namespace geos {
namespace triangulate {
namespace polygon {
class GEOS_DLL PolygonEarClipper {
using Coordinate = geos::geom::Coordinate;
using CoordinateSequence = geos::geom::CoordinateSequence;
using Polygon = geos::geom::Polygon;
using Envelope = geos::geom::Envelope;
using Tri = geos::triangulate::tri::Tri;
template<typename TriType>
using TriList = geos::triangulate::tri::TriList<TriType>;
using VertexSequencePackedRtree = geos::index::VertexSequencePackedRtree;
private:
// Members
bool isFlatCornersSkipped = false;
const CoordinateSequence& vertex;
std::vector<std::size_t> vertexNext;
std::size_t vertexSize;
// first available vertex index
std::size_t vertexFirst;
// indices for current corner
std::array<std::size_t, 3> cornerIndex;
VertexSequencePackedRtree vertexCoordIndex;
// Methods
std::vector<std::size_t> createNextLinks(std::size_t size) const;
bool isValidEar(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner);
std::size_t findIntersectingVertex(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner) const;
bool isValidEarScan(std::size_t cornerIndex, const std::array<Coordinate, 3>& corner) const;
/* private */
static Envelope envelope(const std::array<Coordinate, 3>& corner);
void removeCorner();
bool isRemoved(std::size_t vertexIndex) const;
void initCornerIndex();
void fetchCorner(std::array<Coordinate, 3>& cornerVertex) const;
void nextCorner(std::array<Coordinate, 3>& cornerVertex);
std::size_t nextIndex(std::size_t index) const;
bool isConvex(const std::array<Coordinate, 3>& pts) const;
bool isFlat(const std::array<Coordinate, 3>& pts) const;
bool isCornerInvalid(const std::array<Coordinate, 3>& pts) const;
public:
PolygonEarClipper(const geom::CoordinateSequence& polyShell);
static void triangulate(const geom::CoordinateSequence& polyShell, TriList<Tri>& triListResult);
void setSkipFlatCorners(bool p_isFlatCornersSkipped);
void compute(TriList<Tri>& triList);
std::unique_ptr<Polygon> toGeometry() const;
};
} // 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::Polygon
Represents a linear polygon, which may include holes.
Definition Polygon.h:61
geos::index::VertexSequencePackedRtree
Definition VertexSequencePackedRtree.h:49
geos::triangulate::polygon::PolygonEarClipper::triangulate
static void triangulate(const geom::CoordinateSequence &polyShell, TriList< Tri > &triListResult)
geos::triangulate::polygon::PolygonEarClipper::setSkipFlatCorners
void setSkipFlatCorners(bool p_isFlatCornersSkipped)
geos::triangulate::polygon::PolygonEarClipper::PolygonEarClipper
PolygonEarClipper(const geom::CoordinateSequence &polyShell)
geos::triangulate::tri::TriList
Definition TriList.h:50
geos::triangulate::tri::Tri
Definition Tri.h:45
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