RingHull.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (C) 2021 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/simplify/LinkedRing.h>
#include <geos/index/VertexSequencePackedRtree.h>
#include <queue>
namespace geos {
namespace geom {
class Envelope;
class LinearRing;
class LineString;
class Polygon;
}
namespace simplify {
class RingHullIndex;
}
}
namespace geos {
namespace simplify { // geos::simplify
class RingHull
{
using Coordinate = geos::geom::Coordinate;
using CoordinateSequence = geos::geom::CoordinateSequence;
using Envelope = geos::geom::Envelope;
using LinearRing = geos::geom::LinearRing;
using LineString = geos::geom::LineString;
using Polygon = geos::geom::Polygon;
using VertexSequencePackedRtree = geos::index::VertexSequencePackedRtree;
public:
/*
* Creates a new instance.
*
* @param p_ring the ring vertices to process
* @param p_isOuter whether the hull is outer or inner
*/
RingHull(const LinearRing* p_ring, bool p_isOuter);
void setMinVertexNum(std::size_t minVertexNum);
void setMaxAreaDelta(double maxAreaDelta);
const Envelope* getEnvelope() const;
std::unique_ptr<LinearRing> getHull(RingHullIndex& hullIndex);
static bool isConvex(const LinkedRing& vertexRing, std::size_t index);
static double area(const LinkedRing& vertexRing, std::size_t index);
void compute(RingHullIndex& hullIndex);
std::unique_ptr<Polygon> toGeometry() const;
private:
class Corner
{
private:
std::size_t index;
std::size_t prev;
std::size_t next;
double area;
public:
Corner(std::size_t p_idx, std::size_t p_prev, std::size_t p_next, double p_area)
: index(p_idx)
, prev(p_prev)
, next(p_next)
, area(p_area)
{};
inline int compareTo(const Corner& rhs) const {
if (area == rhs.getArea()) {
if (index == rhs.getIndex())
return 0;
else return index < rhs.getIndex() ? -1 : 1;
}
else return area < rhs.getArea() ? -1 : 1;
}
inline bool operator< (const Corner& rhs) const {
return compareTo(rhs) < 0;
};
inline bool operator> (const Corner& rhs) const {
return compareTo(rhs) > 0;
};
inline bool operator==(const Corner& rhs) const {
return compareTo(rhs) == 0;
};
bool isVertex(std::size_t p_index) const;
std::size_t getIndex() const;
double getArea() const;
void envelope(const LinkedRing& ring, Envelope& env) const;
bool intersects(const Coordinate& v, const LinkedRing& ring) const;
bool isRemoved(const LinkedRing& ring) const;
std::unique_ptr<LineString> toLineString(const LinkedRing& ring);
struct Greater {
inline bool operator()(const Corner & a, const Corner & b) const {
return a > b;
}
};
using PriorityQueue = std::priority_queue<Corner, std::vector<Corner>, Corner::Greater>;
}; // class Corner
const LinearRing* inputRing;
double targetVertexNum = -1.0;
double targetAreaDelta = -1.0;
std::unique_ptr<CoordinateSequence> vertex;
std::unique_ptr<LinkedRing> vertexRing;
double areaDelta = 0;
std::unique_ptr<VertexSequencePackedRtree> vertexIndex;
Corner::PriorityQueue cornerQueue;
void init(CoordinateSequence& ring, bool isOuter);
void addCorner(std::size_t i, Corner::PriorityQueue& cornerQueue);
bool isAtTarget(const Corner& corner);
void removeCorner(const Corner& corner, Corner::PriorityQueue& cornerQueue);
bool isRemovable(const Corner& corner, const RingHullIndex& hullIndex) const;
bool hasIntersectingVertex(
const Corner& corner,
const Envelope& cornerEnv,
const RingHull* hull) const;
const Coordinate& getCoordinate(std::size_t index) const;
void query(
const Envelope& cornerEnv,
std::vector<std::size_t>& result) const;
void queryHull(const Envelope& queryEnv, std::vector<Coordinate>& pts);
}; // RingHull
} // geos::simplify
} // geos
geos::geom::Envelope
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition Envelope.h:59
geos::geom::LineString
Definition LineString.h:66
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::geom
Definition Angle.h:26
geos::simplify
Classes which implement algorithms for simplifying or generalizing geometries.
Definition Corner.h:26
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38