GEOS 3.9.1
MaximumInscribedCircle.h
1/**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
7 *
8 * This is free software; you can redistribute and/or modify it under
9 * the terms of the GNU Lesser General Public Licence as published
10 * by the Free Software Foundation.
11 * See the COPYING file for more information.
12 *
13 **********************************************************************
14 *
15 * Last port: algorithm/construct/MaximumInscribedCircle.java
16 * https://github.com/locationtech/jts/commit/98274a7ea9b40651e9de6323dc10fb2cac17a245
17 *
18 **********************************************************************/
19
20#ifndef GEOS_ALGORITHM_CONSTRUCT_MAXIMUMCIRCLE_H
21#define GEOS_ALGORITHM_CONSTRUCT_MAXIMUMCIRCLE_H
22
23#include <geos/geom/Coordinate.h>
24#include <geos/geom/Point.h>
25#include <geos/geom/Envelope.h>
26#include <geos/algorithm/locate/IndexedPointInAreaLocator.h>
27#include <geos/operation/distance/IndexedFacetDistance.h>
28
29#include <memory>
30#include <queue>
31
32
33
34namespace geos {
35namespace geom {
36class Coordinate;
37class Envelope;
38class Geometry;
39class GeometryFactory;
40class LineString;
41class Point;
42}
43}
44
47
48namespace geos {
49namespace algorithm { // geos::algorithm
50namespace construct { // geos::algorithm::construct
51
57class GEOS_DLL MaximumInscribedCircle {
58
59public:
60
61 MaximumInscribedCircle(const geom::Geometry* polygonal, double tolerance);
62 ~MaximumInscribedCircle() = default;
63
70 std::unique_ptr<geom::Point> getCenter();
71
82 std::unique_ptr<geom::Point> getRadiusPoint();
83
89 std::unique_ptr<geom::LineString> getRadiusLine();
90
99 static std::unique_ptr<geom::Point> getCenter(const geom::Geometry* polygonal, double tolerance);
100
109 static std::unique_ptr<geom::LineString> getRadiusLine(const geom::Geometry* polygonal, double tolerance);
110
111private:
112
113 /* private members */
114 const geom::Geometry* inputGeom;
115 std::unique_ptr<geom::Geometry> inputGeomBoundary;
116 double tolerance;
117 IndexedFacetDistance indexedDistance;
119 const geom::GeometryFactory* factory;
120 bool done;
121 geom::Coordinate centerPt;
122 geom::Coordinate radiusPt;
123
124 /* private methods */
125 double distanceToBoundary(const geom::Coordinate& c);
126 double distanceToBoundary(double x, double y);
127 void compute();
128
129 /* private class */
130 class Cell {
131 private:
132 static constexpr double SQRT2 = 1.4142135623730951;
133 double x;
134 double y;
135 double hSize;
136 double distance;
137 double maxDist;
138
139 public:
140 Cell(double p_x, double p_y, double p_hSize, double p_distanceToBoundary)
141 : x(p_x)
142 , y(p_y)
143 , hSize(p_hSize)
144 , distance(p_distanceToBoundary)
145 , maxDist(p_distanceToBoundary+(p_hSize*SQRT2))
146 {};
147
148 geom::Envelope getEnvelope() const
149 {
150 geom::Envelope env(x-hSize, x+hSize, y-hSize, y+hSize);
151 return env;
152 }
153
154 double getMaxDistance() const
155 {
156 return maxDist;
157 }
158 double getDistance() const
159 {
160 return distance;
161 }
162 double getHSize() const
163 {
164 return hSize;
165 }
166 double getX() const
167 {
168 return x;
169 }
170 double getY() const
171 {
172 return y;
173 }
174 bool operator< (const Cell& rhs) const
175 {
176 return maxDist < rhs.maxDist;
177 }
178 bool operator> (const Cell& rhs) const
179 {
180 return maxDist > rhs.maxDist;
181 }
182 bool operator==(const Cell& rhs) const
183 {
184 return maxDist == rhs.maxDist;
185 }
186 };
187
188 void createInitialGrid(const geom::Envelope* env, std::priority_queue<Cell>& cellQueue);
189 Cell createCentroidCell(const geom::Geometry* geom);
190
191};
192
193
194} // geos::algorithm::construct
195} // geos::algorithm
196} // geos
197
198#endif // GEOS_ALGORITHM_CONSTRUCT_MAXIMUMCIRCLE_H
Definition: MaximumInscribedCircle.h:57
std::unique_ptr< geom::Point > getCenter()
static std::unique_ptr< geom::Point > getCenter(const geom::Geometry *polygonal, double tolerance)
std::unique_ptr< geom::LineString > getRadiusLine()
std::unique_ptr< geom::Point > getRadiusPoint()
static std::unique_ptr< geom::LineString > getRadiusLine(const geom::Geometry *polygonal, double tolerance)
Determines the location of Coordinates relative to an areal geometry, using indexing for efficiency.
Definition: IndexedPointInAreaLocator.h:55
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:60
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:68
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition: Geometry.h:188
Computes the distance between the facets (segments and vertices) of two Geometrys using a Branch-and-...
Definition: IndexedFacetDistance.h:47
bool operator==(const Coordinate &a, const Coordinate &b)
Equality operator for Coordinate. 2D only.
Basic namespace for all GEOS functionalities.
Definition: IndexedNestedRingTester.h:26