310 lines
9.9 KiB
C
310 lines
9.9 KiB
C
|
/**********************************************************************
|
||
|
|
*
|
||
|
|
* 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/Triangle.h>
|
||
|
|
#include <geos/triangulate/tri/Tri.h>
|
||
|
|
#include <geos/triangulate/tri/TriList.h>
|
||
|
|
#include <geos/triangulate/quadedge/TriangleVisitor.h>
|
||
|
|
#include <geos/algorithm/hull/HullTri.h>
|
||
|
|
|
||
|
|
#include <queue>
|
||
|
|
#include <deque>
|
||
|
|
|
||
|
|
namespace geos {
|
||
|
|
namespace geom {
|
||
|
|
class Coordinate;
|
||
|
|
class Geometry;
|
||
|
|
class GeometryFactory;
|
||
|
|
}
|
||
|
|
namespace triangulate {
|
||
|
|
namespace quadedge {
|
||
|
|
class Quadedge;
|
||
|
|
class QuadEdgeSubdivision;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
using geos::geom::Coordinate;
|
||
|
|
using geos::geom::Geometry;
|
||
|
|
using geos::geom::GeometryFactory;
|
||
|
|
using geos::geom::Triangle;
|
||
|
|
using geos::triangulate::quadedge::QuadEdge;
|
||
|
|
using geos::triangulate::quadedge::QuadEdgeSubdivision;
|
||
|
|
using geos::triangulate::quadedge::TriangleVisitor;
|
||
|
|
using geos::triangulate::tri::Tri;
|
||
|
|
using geos::triangulate::tri::TriList;
|
||
|
|
|
||
|
|
namespace geos {
|
||
|
|
namespace algorithm { // geos::algorithm
|
||
|
|
namespace hull { // geos::algorithm::hull
|
||
|
|
|
||
|
|
|
||
|
|
typedef std::priority_queue<HullTri*, std::vector<HullTri*>, HullTri::HullTriCompare> HullTriQueue;
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Constructs a concave hull of a set of points.
|
||
|
|
* The hull is constructed by removing border triangles
|
||
|
|
* of the Delaunay Triangulation of the points
|
||
|
|
* as long as their "size" is larger than the target criterion.
|
||
|
|
* The target criteria are:
|
||
|
|
*
|
||
|
|
* * Maximum Edge Length Ratio - determines the Maximum Edge Length
|
||
|
|
* by a fraction of the difference between
|
||
|
|
* the longest and shortest edge lengths
|
||
|
|
* in the Delaunay Triangulation. This normalizes the
|
||
|
|
* Maximum Edge Length to be scale-independent.
|
||
|
|
* * Maximum Area Ratio - the ratio of the concave hull area to the convex
|
||
|
|
* hull area will be no larger than this value
|
||
|
|
* * Alpha - produces Alpha-shapes, by removing border triangles
|
||
|
|
* with a circumradius greater than alpha.
|
||
|
|
* Large values produce the convex hull; a value of 0
|
||
|
|
* produces maximum concaveness.
|
||
|
|
*
|
||
|
|
* The preferred criterium is the Maximum Edge Length Ratio, since it is
|
||
|
|
* scale-free and local (so that no assumption needs to be made about the
|
||
|
|
* total amount of concavity present.
|
||
|
|
*
|
||
|
|
* Other length criteria can be used by setting the Maximum Edge Length.
|
||
|
|
* For example, use a length relative to the longest edge length
|
||
|
|
* in the Minimum Spanning Tree of the point set.
|
||
|
|
* Or, use a length derived from the uniformGridEdgeLength() value.
|
||
|
|
*
|
||
|
|
* The computed hull is always a single connected geom::Polygon
|
||
|
|
* (unless it is degenerate, in which case it will be a geom::Point or a geom::LineString).
|
||
|
|
* This constraint may cause the concave hull to fail to meet the target criteria.
|
||
|
|
*
|
||
|
|
* Optionally the concave hull can be allowed
|
||
|
|
* to contain holes by calling setHolesAllowed(boolean).
|
||
|
|
*
|
||
|
|
* @author mdavis
|
||
|
|
*/
|
||
|
|
class GEOS_DLL ConcaveHull {
|
||
|
|
|
||
|
|
public:
|
||
|
|
|
||
|
|
ConcaveHull(const Geometry* geom);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Computes the approximate edge length of
|
||
|
|
* a uniform square grid having the same number of
|
||
|
|
* points as a geometry and the same area as its convex hull.
|
||
|
|
* This value can be used to determine a suitable length threshold value
|
||
|
|
* for computing a concave hull.
|
||
|
|
* A value from 2 to 4 times the uniform grid length
|
||
|
|
* seems to produce reasonable results.
|
||
|
|
*
|
||
|
|
* @param geom a geometry
|
||
|
|
* @return the approximate uniform grid length
|
||
|
|
*/
|
||
|
|
static double uniformEdgeLength(const Geometry* geom);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Computes the concave hull of the vertices in a geometry
|
||
|
|
* using the target criteria of maximum edge length.
|
||
|
|
*
|
||
|
|
* @param geom the input geometry
|
||
|
|
* @param maxLength the target maximum edge length
|
||
|
|
* @return the concave hull
|
||
|
|
*/
|
||
|
|
static std::unique_ptr<Geometry> concaveHullByLength(
|
||
|
|
const Geometry* geom, double maxLength);
|
||
|
|
|
||
|
|
static std::unique_ptr<Geometry> concaveHullByLength(
|
||
|
|
const Geometry* geom, double maxLength, bool isHolesAllowed);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Computes the concave hull of the vertices in a geometry
|
||
|
|
* using the target criteria of maximum edge length ratio.
|
||
|
|
* The edge length ratio is a fraction of the length difference
|
||
|
|
* between the longest and shortest edges
|
||
|
|
* in the Delaunay Triangulation of the input points.
|
||
|
|
*
|
||
|
|
* @param geom the input geometry
|
||
|
|
* @param lengthRatio the target edge length factor
|
||
|
|
* @return the concave hull
|
||
|
|
*/
|
||
|
|
static std::unique_ptr<Geometry> concaveHullByLengthRatio(
|
||
|
|
const Geometry* geom, double lengthRatio);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Computes the concave hull of the vertices in a geometry
|
||
|
|
* using the target criterion of maximum edge length factor,
|
||
|
|
* and optionally allowing holes.
|
||
|
|
* The edge length factor is a fraction of the length difference
|
||
|
|
* between the longest and shortest edges
|
||
|
|
* in the Delaunay Triangulation of the input points.
|
||
|
|
*
|
||
|
|
* @param geom the input geometry
|
||
|
|
* @param lengthRatio the target maximum edge length
|
||
|
|
* @param isHolesAllowed whether holes are allowed in the result
|
||
|
|
* @return the concave hull
|
||
|
|
*/
|
||
|
|
static std::unique_ptr<Geometry> concaveHullByLengthRatio(
|
||
|
|
const Geometry* geom,
|
||
|
|
double lengthRatio,
|
||
|
|
bool isHolesAllowed);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Computes the alpha shape of a geometry as a polygon.
|
||
|
|
* The alpha parameter is the radius of the eroding disc.
|
||
|
|
*
|
||
|
|
* @param geom the input geometry
|
||
|
|
* @param alpha the radius of the eroding disc
|
||
|
|
* @param isHolesAllowed whether holes are allowed in the result
|
||
|
|
* @return the alpha shape polygon
|
||
|
|
*/
|
||
|
|
static std::unique_ptr<Geometry> alphaShape(
|
||
|
|
const Geometry* geom,
|
||
|
|
double alpha,
|
||
|
|
bool isHolesAllowed);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Sets the target maximum edge length for the concave hull.
|
||
|
|
* The length value must be zero or greater.
|
||
|
|
*
|
||
|
|
* * The value 0.0 produces the concave hull of smallest area
|
||
|
|
* that is still connected.
|
||
|
|
* * Larger values produce less concave results.
|
||
|
|
* A value equal or greater than the longest Delaunay Triangulation edge length
|
||
|
|
* produces the convex hull.
|
||
|
|
*
|
||
|
|
* The uniformGridEdgeLength value may be used as
|
||
|
|
* the basis for estimating an appropriate target maximum edge length.
|
||
|
|
*
|
||
|
|
* @param edgeLength a non-negative length
|
||
|
|
*/
|
||
|
|
void setMaximumEdgeLength(double edgeLength);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Sets the target maximum edge length ratio for the concave hull.
|
||
|
|
* The edge length ratio is a fraction of the length delta
|
||
|
|
* between the longest and shortest edges
|
||
|
|
* in the Delaunay Triangulation of the input points.
|
||
|
|
* A value of 1.0 produces the convex hull.
|
||
|
|
* A value of 0.0 produces a concave hull of minimum area
|
||
|
|
* that is still connected.
|
||
|
|
*
|
||
|
|
* @param edgeLengthRatio a length ratio value between 0 and 1
|
||
|
|
*/
|
||
|
|
void setMaximumEdgeLengthRatio(double edgeLengthRatio);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Sets whether holes are allowed in the concave hull polygon.
|
||
|
|
*
|
||
|
|
* @param holesAllowed true if holes are allowed in the result
|
||
|
|
*/
|
||
|
|
void setHolesAllowed(bool holesAllowed);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Sets the alpha parameter to compute an alpha shape of the input.
|
||
|
|
* Alpha is the radius of the eroding disc.
|
||
|
|
* Border triangles with circumradius greater than alpha are removed.
|
||
|
|
*
|
||
|
|
* @param newAlpha the alpha radius
|
||
|
|
*/
|
||
|
|
void setAlpha(double newAlpha);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Gets the computed concave hull.
|
||
|
|
*
|
||
|
|
* @return the concave hull
|
||
|
|
*/
|
||
|
|
std::unique_ptr<Geometry> getHull();
|
||
|
|
|
||
|
|
|
||
|
|
private:
|
||
|
|
|
||
|
|
// Constants
|
||
|
|
static constexpr int PARAM_EDGE_LENGTH = 1;
|
||
|
|
static constexpr int PARAM_ALPHA = 2;
|
||
|
|
|
||
|
|
// Members
|
||
|
|
const Geometry* inputGeometry;
|
||
|
|
double maxEdgeLengthRatio;
|
||
|
|
double alpha;
|
||
|
|
bool isHolesAllowed;
|
||
|
|
int criteriaType;
|
||
|
|
double maxSizeInHull;
|
||
|
|
const GeometryFactory* geomFactory;
|
||
|
|
|
||
|
|
// Methods
|
||
|
|
static double computeTargetEdgeLength(
|
||
|
|
TriList<HullTri>& triList,
|
||
|
|
double edgeLengthFactor);
|
||
|
|
|
||
|
|
void computeHull(TriList<HullTri>& triList);
|
||
|
|
void computeHullBorder(TriList<HullTri>& triList);
|
||
|
|
void createBorderQueue(HullTriQueue& queue, TriList<HullTri>& triList);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Adds a Tri to the queue.
|
||
|
|
* Only add tris with a single border edge.
|
||
|
|
* since otherwise that would risk isolating a vertex if
|
||
|
|
* the tri ends up being eroded from the hull.
|
||
|
|
* Sets the tri size according to the threshold parameter being used.
|
||
|
|
*
|
||
|
|
* @param tri the Tri to add
|
||
|
|
* @param queue the priority queue
|
||
|
|
*/
|
||
|
|
void addBorderTri(HullTri* tri, HullTriQueue& queue);
|
||
|
|
void computeHullHoles(TriList<HullTri>& triList);
|
||
|
|
void setSize(HullTri* tri);
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Finds tris which may be the start of holes.
|
||
|
|
* Only tris which have a long enough edge and which do not touch the current hull
|
||
|
|
* boundary are included.
|
||
|
|
* This avoids the risk of disconnecting the result polygon.
|
||
|
|
* The list is sorted in decreasing order of edge length.
|
||
|
|
* The list is sorted in decreasing order of size.
|
||
|
|
*
|
||
|
|
* @param triList
|
||
|
|
* @param maxSizeInHull maximum tri size which is not in a hole
|
||
|
|
* @return
|
||
|
|
*/
|
||
|
|
static std::vector<HullTri*> findCandidateHoles(
|
||
|
|
TriList<HullTri>& triList, double maxSizeInHull);
|
||
|
|
|
||
|
|
void removeHole(TriList<HullTri>& triList, HullTri* triHole);
|
||
|
|
void setSize(TriList<HullTri>& triList);
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Tests if a tri is included in the hull.
|
||
|
|
* Tris with size less than the maximum are included in the hull.
|
||
|
|
*
|
||
|
|
* @param tri the tri to test
|
||
|
|
* @return true if the tri is included in the hull
|
||
|
|
*/
|
||
|
|
bool isInHull(const HullTri* tri) const;
|
||
|
|
|
||
|
|
bool isRemovableBorder(const HullTri* tri) const;
|
||
|
|
bool isRemovableHole(const HullTri* tri) const;
|
||
|
|
|
||
|
|
std::unique_ptr<Geometry> toGeometry(
|
||
|
|
TriList<HullTri>& triList,
|
||
|
|
const GeometryFactory* factory);
|
||
|
|
|
||
|
|
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
} // geos::algorithm::hull
|
||
|
|
} // geos::algorithm
|
||
|
|
} // geos
|
||
|
|
|