GEOS  3.10.2
LargestEmptyCircle.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/LargestEmptyCircle.java
16  * https://github.com/locationtech/jts/commit/98274a7ea9b40651e9de6323dc10fb2cac17a245
17  *
18  **********************************************************************/
19 
20 #ifndef GEOS_ALGORITHM_CONSTRUCT_LARGESTCIRCLE_H
21 #define GEOS_ALGORITHM_CONSTRUCT_LARGESTCIRCLE_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 
34 namespace geos {
35 namespace geom {
36 class Coordinate;
37 class Envelope;
38 class Geometry;
39 class GeometryFactory;
40 class LineString;
41 class Point;
42 }
43 namespace operation {
44 namespace distance {
46 }
47 }
48 }
49 
50 
51 namespace geos {
52 namespace algorithm { // geos::algorithm
53 namespace construct { // geos::algorithm::construct
54 
75 class GEOS_DLL LargestEmptyCircle {
76 
77 public:
78 
85  LargestEmptyCircle(const geom::Geometry* p_obstacles, double p_tolerance);
86  LargestEmptyCircle(const geom::Geometry* p_obstacles, const geom::Geometry* p_boundary, double p_tolerance);
87  ~LargestEmptyCircle() = default;
88 
97  static std::unique_ptr<geom::Point> getCenter(const geom::Geometry* p_obstacles, double p_tolerance);
98 
107  static std::unique_ptr<geom::LineString> getRadiusLine(const geom::Geometry* p_obstacles, double p_tolerance);
108 
109  std::unique_ptr<geom::Point> getCenter();
110  std::unique_ptr<geom::Point> getRadiusPoint();
111  std::unique_ptr<geom::LineString> getRadiusLine();
112 
113 
114 private:
115 
116  /* private members */
117  double tolerance;
118  const geom::Geometry* obstacles;
119  const geom::GeometryFactory* factory;
120  std::unique_ptr<geom::Geometry> boundary; // convexhull(obstacles)
122  bool done;
123  std::unique_ptr<algorithm::locate::IndexedPointInAreaLocator> ptLocator;
124  std::unique_ptr<operation::distance::IndexedFacetDistance> boundaryDistance;
125  geom::Coordinate centerPt;
126  geom::Coordinate radiusPt;
127 
128  /* private methods */
129  void setBoundary(const geom::Geometry* obstacles);
130 
141  double distanceToConstraints(const geom::Coordinate& c);
142  double distanceToConstraints(double x, double y);
143  void compute();
144 
145  /* private class */
146  class Cell {
147  private:
148  static constexpr double SQRT2 = 1.4142135623730951;
149  double x;
150  double y;
151  double hSize;
152  double distance;
153  double maxDist;
154 
155  public:
156  Cell(double p_x, double p_y, double p_hSize, double p_distanceToConstraints)
157  : x(p_x)
158  , y(p_y)
159  , hSize(p_hSize)
160  , distance(p_distanceToConstraints)
161  , maxDist(p_distanceToConstraints + (p_hSize*SQRT2))
162  {};
163 
164  geom::Envelope getEnvelope() const
165  {
166  geom::Envelope env(x-hSize, x+hSize, y-hSize, y+hSize);
167  return env;
168  }
169 
170  bool isFullyOutside() const
171  {
172  return maxDist < 0.0;
173  }
174  bool isOutside() const
175  {
176  return distance < 0.0;
177  }
178  double getMaxDistance() const
179  {
180  return maxDist;
181  }
182  double getDistance() const
183  {
184  return distance;
185  }
186  double getHSize() const
187  {
188  return hSize;
189  }
190  double getX() const
191  {
192  return x;
193  }
194  double getY() const
195  {
196  return y;
197  }
198  bool operator< (const Cell& rhs) const
199  {
200  return maxDist < rhs.maxDist;
201  }
202  bool operator> (const Cell& rhs) const
203  {
204  return maxDist > rhs.maxDist;
205  }
206  bool operator==(const Cell& rhs) const
207  {
208  return maxDist == rhs.maxDist;
209  }
210  };
211 
212  bool mayContainCircleCenter(const Cell& cell, const Cell& farthestCell);
213  void createInitialGrid(const geom::Envelope* env, std::priority_queue<Cell>& cellQueue);
214  Cell createCentroidCell(const geom::Geometry* geom);
215 
216 };
217 
218 
219 } // geos::algorithm::construct
220 } // geos::algorithm
221 } // geos
222 
223 #endif // GEOS_ALGORITHM_CONSTRUCT_LARGESTCIRCLE_H
Definition: LargestEmptyCircle.h:75
static std::unique_ptr< geom::Point > getCenter(const geom::Geometry *p_obstacles, double p_tolerance)
static std::unique_ptr< geom::LineString > getRadiusLine(const geom::Geometry *p_obstacles, double p_tolerance)
LargestEmptyCircle(const geom::Geometry *p_obstacles, double p_tolerance)
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: Angle.h:26