GEOS  3.11.0rc0
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 #pragma once
21 
22 #include <geos/geom/Coordinate.h>
23 #include <geos/geom/Point.h>
24 #include <geos/geom/Envelope.h>
25 #include <geos/algorithm/locate/IndexedPointInAreaLocator.h>
26 #include <geos/operation/distance/IndexedFacetDistance.h>
27 
28 #include <memory>
29 #include <queue>
30 
31 
32 
33 namespace geos {
34 namespace geom {
35 class Coordinate;
36 class Envelope;
37 class Geometry;
38 class GeometryFactory;
39 class LineString;
40 class Point;
41 }
42 }
43 
46 
47 namespace geos {
48 namespace algorithm { // geos::algorithm
49 namespace construct { // geos::algorithm::construct
50 
56 class GEOS_DLL MaximumInscribedCircle {
57 
58 public:
59 
60  MaximumInscribedCircle(const geom::Geometry* polygonal, double tolerance);
61  ~MaximumInscribedCircle() = default;
62 
69  std::unique_ptr<geom::Point> getCenter();
70 
81  std::unique_ptr<geom::Point> getRadiusPoint();
82 
88  std::unique_ptr<geom::LineString> getRadiusLine();
89 
98  static std::unique_ptr<geom::Point> getCenter(const geom::Geometry* polygonal, double tolerance);
99 
108  static std::unique_ptr<geom::LineString> getRadiusLine(const geom::Geometry* polygonal, double tolerance);
109 
110 private:
111 
112  /* private members */
113  const geom::Geometry* inputGeom;
114  std::unique_ptr<geom::Geometry> inputGeomBoundary;
115  double tolerance;
116  IndexedFacetDistance indexedDistance;
117  IndexedPointInAreaLocator ptLocator;
118  const geom::GeometryFactory* factory;
119  bool done;
120  geom::Coordinate centerPt;
121  geom::Coordinate radiusPt;
122 
123  /* private methods */
124  double distanceToBoundary(const geom::Coordinate& c);
125  double distanceToBoundary(double x, double y);
126  void compute();
127 
128  /* private class */
129  class Cell {
130  private:
131  static constexpr double SQRT2 = 1.4142135623730951;
132  double x;
133  double y;
134  double hSize;
135  double distance;
136  double maxDist;
137 
138  public:
139  Cell(double p_x, double p_y, double p_hSize, double p_distanceToBoundary)
140  : x(p_x)
141  , y(p_y)
142  , hSize(p_hSize)
143  , distance(p_distanceToBoundary)
144  , maxDist(p_distanceToBoundary+(p_hSize*SQRT2))
145  {};
146 
147  geom::Envelope getEnvelope() const
148  {
149  geom::Envelope env(x-hSize, x+hSize, y-hSize, y+hSize);
150  return env;
151  }
152 
153  double getMaxDistance() const
154  {
155  return maxDist;
156  }
157  double getDistance() const
158  {
159  return distance;
160  }
161  double getHSize() const
162  {
163  return hSize;
164  }
165  double getX() const
166  {
167  return x;
168  }
169  double getY() const
170  {
171  return y;
172  }
173  bool operator< (const Cell& rhs) const
174  {
175  return maxDist < rhs.maxDist;
176  }
177  bool operator> (const Cell& rhs) const
178  {
179  return maxDist > rhs.maxDist;
180  }
181  bool operator==(const Cell& rhs) const
182  {
183  return maxDist == rhs.maxDist;
184  }
185  };
186 
187  void createInitialGrid(const geom::Envelope* env, std::priority_queue<Cell>& cellQueue);
188  Cell createCentroidCell(const geom::Geometry* geom);
189 
190 };
191 
192 
193 } // geos::algorithm::construct
194 } // geos::algorithm
195 } // geos
196 
Definition: MaximumInscribedCircle.h:56
std::unique_ptr< geom::LineString > getRadiusLine()
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)
std::unique_ptr< geom::Point > getCenter()
std::unique_ptr< geom::Point > getRadiusPoint()
Determines the location of Coordinates relative to an areal geometry, using indexing for efficiency.
Definition: IndexedPointInAreaLocator.h:54
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:58
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:66
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition: Geometry.h:186
Computes the distance between the facets (segments and vertices) of two Geometrys using a Branch-and-...
Definition: IndexedFacetDistance.h:46
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25