GEOS  3.11.1
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 #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 namespace operation {
43 namespace distance {
45 }
46 }
47 }
48 
49 
50 namespace geos {
51 namespace algorithm { // geos::algorithm
52 namespace construct { // geos::algorithm::construct
53 
74 class GEOS_DLL LargestEmptyCircle {
75 
76 public:
77 
84  LargestEmptyCircle(const geom::Geometry* p_obstacles, double p_tolerance);
85  LargestEmptyCircle(const geom::Geometry* p_obstacles, const geom::Geometry* p_boundary, double p_tolerance);
86  ~LargestEmptyCircle() = default;
87 
96  static std::unique_ptr<geom::Point> getCenter(const geom::Geometry* p_obstacles, double p_tolerance);
97 
106  static std::unique_ptr<geom::LineString> getRadiusLine(const geom::Geometry* p_obstacles, double p_tolerance);
107 
108  std::unique_ptr<geom::Point> getCenter();
109  std::unique_ptr<geom::Point> getRadiusPoint();
110  std::unique_ptr<geom::LineString> getRadiusLine();
111 
112 
113 private:
114 
115  /* private members */
116  double tolerance;
117  const geom::Geometry* obstacles;
118  const geom::GeometryFactory* factory;
119  std::unique_ptr<geom::Geometry> boundary; // convexhull(obstacles)
121  bool done;
122  std::unique_ptr<algorithm::locate::IndexedPointInAreaLocator> ptLocator;
123  std::unique_ptr<operation::distance::IndexedFacetDistance> boundaryDistance;
124  geom::Coordinate centerPt;
125  geom::Coordinate radiusPt;
126 
127  /* private methods */
128  void setBoundary(const geom::Geometry* obstacles);
129 
140  double distanceToConstraints(const geom::Coordinate& c);
141  double distanceToConstraints(double x, double y);
142  void compute();
143 
144  /* private class */
145  class Cell {
146  private:
147  static constexpr double SQRT2 = 1.4142135623730951;
148  double x;
149  double y;
150  double hSize;
151  double distance;
152  double maxDist;
153 
154  public:
155  Cell(double p_x, double p_y, double p_hSize, double p_distanceToConstraints)
156  : x(p_x)
157  , y(p_y)
158  , hSize(p_hSize)
159  , distance(p_distanceToConstraints)
160  , maxDist(p_distanceToConstraints + (p_hSize*SQRT2))
161  {};
162 
163  geom::Envelope getEnvelope() const
164  {
165  geom::Envelope env(x-hSize, x+hSize, y-hSize, y+hSize);
166  return env;
167  }
168 
169  bool isFullyOutside() const
170  {
171  return maxDist < 0.0;
172  }
173  bool isOutside() const
174  {
175  return distance < 0.0;
176  }
177  double getMaxDistance() const
178  {
179  return maxDist;
180  }
181  double getDistance() const
182  {
183  return distance;
184  }
185  double getHSize() const
186  {
187  return hSize;
188  }
189  double getX() const
190  {
191  return x;
192  }
193  double getY() const
194  {
195  return y;
196  }
197  bool operator< (const Cell& rhs) const
198  {
199  return maxDist < rhs.maxDist;
200  }
201  bool operator> (const Cell& rhs) const
202  {
203  return maxDist > rhs.maxDist;
204  }
205  bool operator==(const Cell& rhs) const
206  {
207  return maxDist == rhs.maxDist;
208  }
209  };
210 
211  bool mayContainCircleCenter(const Cell& cell, const Cell& farthestCell);
212  void createInitialGrid(const geom::Envelope* env, std::priority_queue<Cell>& cellQueue);
213  Cell createCentroidCell(const geom::Geometry* geom);
214 
215 };
216 
217 
218 } // geos::algorithm::construct
219 } // geos::algorithm
220 } // geos
221 
An Envelope defines a rectangulare region of the 2D coordinate plane.
Definition: Envelope.h:58
Coordinate is the lightweight class used to store coordinates.
Definition: Coordinate.h:58
Computes the distance between the facets (segments and vertices) of two Geometrys using a Branch-and-...
Definition: IndexedFacetDistance.h:46
Basic implementation of Geometry, constructed and destructed by GeometryFactory.
Definition: Geometry.h:186
Definition: LargestEmptyCircle.h:74
Supplies a set of utility methods for building Geometry objects from CoordinateSequence or other Geom...
Definition: GeometryFactory.h:66
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25