MaximumInscribedCircle.h
/**********************************************************************
*
* GEOS - Geometry Engine Open Source
* http://geos.osgeo.org
*
* Copyright (c) 2020 Martin Davis
* 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.
*
**********************************************************************
*
* Last port: algorithm/construct/MaximumInscribedCircle.java
* https://github.com/locationtech/jts/commit/f0b9a808bdf8a973de435f737e37b7a221e231cb
*
**********************************************************************/
#pragma once
#include <geos/geom/Coordinate.h>
#include <geos/geom/Point.h>
#include <geos/geom/Envelope.h>
#include <geos/algorithm/locate/IndexedPointInAreaLocator.h>
#include <geos/operation/distance/IndexedFacetDistance.h>
#include <memory>
#include <queue>
namespace geos {
namespace geom {
class Coordinate;
class Envelope;
class Geometry;
class GeometryFactory;
class LineString;
class Point;
}
}
namespace geos {
namespace algorithm { // geos::algorithm
namespace construct { // geos::algorithm::construct
class GEOS_DLL MaximumInscribedCircle {
using IndexedPointInAreaLocator = geos::algorithm::locate::IndexedPointInAreaLocator;
using IndexedFacetDistance = geos::operation::distance::IndexedFacetDistance;
public:
MaximumInscribedCircle(const geom::Geometry* polygonal, double tolerance);
~MaximumInscribedCircle() = default;
std::unique_ptr<geom::Point> getCenter();
std::unique_ptr<geom::Point> getRadiusPoint();
std::unique_ptr<geom::LineString> getRadiusLine();
bool isRadiusWithin(double maxRadius);
static std::unique_ptr<geom::Point> getCenter(const geom::Geometry* polygonal, double tolerance);
static std::unique_ptr<geom::LineString> getRadiusLine(const geom::Geometry* polygonal, double tolerance);
static bool isRadiusWithin(const geom::Geometry* polygonal, double maxRadius);
static std::size_t computeMaximumIterations(const geom::Geometry* geom, double toleranceDist);
private:
/* private members */
const geom::Geometry* inputGeom;
std::unique_ptr<geom::Geometry> inputGeomBoundary;
double tolerance;
IndexedFacetDistance indexedDistance;
IndexedPointInAreaLocator ptLocator;
const geom::GeometryFactory* factory;
bool done;
geom::CoordinateXY centerPt;
geom::CoordinateXY radiusPt;
double maximumRadius = -1;
/* private constant */
static constexpr double MAX_RADIUS_FRACTION = 0.0001;
/* private methods */
double distanceToBoundary(const geom::Point& pt);
double distanceToBoundary(double x, double y);
void compute();
void computeApproximation();
void createResult(const geom::CoordinateXY& c, const geom::CoordinateXY& r);
/* private class */
class Cell {
private:
static constexpr double SQRT2 = 1.4142135623730951;
double x;
double y;
double hSize;
double distance;
double maxDist;
public:
Cell(double p_x, double p_y, double p_hSize, double p_distanceToBoundary)
: x(p_x)
, y(p_y)
, hSize(p_hSize)
, distance(p_distanceToBoundary)
, maxDist(p_distanceToBoundary+(p_hSize*SQRT2))
{};
geom::Envelope getEnvelope() const
{
geom::Envelope env(x-hSize, x+hSize, y-hSize, y+hSize);
return env;
}
double getMaxDistance() const
{
return maxDist;
}
double getDistance() const
{
return distance;
}
double getHSize() const
{
return hSize;
}
double getX() const
{
return x;
}
double getY() const
{
return y;
}
bool operator< (const Cell& rhs) const
{
return maxDist < rhs.maxDist;
}
bool operator> (const Cell& rhs) const
{
return maxDist > rhs.maxDist;
}
bool operator==(const Cell& rhs) const
{
return maxDist == rhs.maxDist;
}
using CellQueue = std::priority_queue<Cell>;
};
void createInitialGrid(const geom::Envelope* env, Cell::CellQueue& cellQueue);
Cell createInteriorPointCell(const geom::Geometry* geom);
};
} // geos::algorithm::construct
} // geos::algorithm
} // geos
geos::algorithm::construct::MaximumInscribedCircle::getCenter
std::unique_ptr< geom::Point > getCenter()
geos::algorithm::construct::MaximumInscribedCircle::getCenter
static std::unique_ptr< geom::Point > getCenter(const geom::Geometry *polygonal, double tolerance)
geos::algorithm::construct::MaximumInscribedCircle::getRadiusLine
std::unique_ptr< geom::LineString > getRadiusLine()
geos::algorithm::construct::MaximumInscribedCircle::isRadiusWithin
static bool isRadiusWithin(const geom::Geometry *polygonal, double maxRadius)
geos::algorithm::construct::MaximumInscribedCircle::computeMaximumIterations
static std::size_t computeMaximumIterations(const geom::Geometry *geom, double toleranceDist)
geos::algorithm::construct::MaximumInscribedCircle::getRadiusPoint
std::unique_ptr< geom::Point > getRadiusPoint()
geos::algorithm::construct::MaximumInscribedCircle::isRadiusWithin
bool isRadiusWithin(double maxRadius)
geos::algorithm::construct::MaximumInscribedCircle::getRadiusLine
static std::unique_ptr< geom::LineString > getRadiusLine(const geom::Geometry *polygonal, double tolerance)
geos::algorithm::locate::IndexedPointInAreaLocator
Determines the location of Coordinates relative to an areal geometry, using indexing for efficiency.
Definition IndexedPointInAreaLocator.h:54
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::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::LineString
Definition LineString.h:66
geos::geom::Point
Definition Point.h:61
geos::operation::distance::IndexedFacetDistance
Computes the distance between the facets (segments and vertices) of two Geometrys using a Branch-and-...
Definition IndexedFacetDistance.h:46
geos::algorithm::distance
Classes to compute distance metrics between geometries.
Definition DiscreteFrechetDistance.h:40
geos::algorithm
Contains classes and interfaces implementing fundamental computational geometry algorithms.
Definition Angle.h:32
geos::geom
Definition Angle.h:26
geos
Basic namespace for all GEOS functionalities.
Definition geos.h:38