GEOS  3.12.0
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  std::unique_ptr<geom::Geometry> boundary;
119  const geom::GeometryFactory* factory;
120  geom::Envelope gridEnv;
122  bool done;
123  std::unique_ptr<algorithm::locate::IndexedPointInAreaLocator> ptLocator;
124  std::unique_ptr<operation::distance::IndexedFacetDistance> boundaryDistance;
125  geom::CoordinateXY centerPt;
126  geom::CoordinateXY radiusPt;
127 
138  double distanceToConstraints(const geom::Coordinate& c);
139  double distanceToConstraints(double x, double y);
140  void initBoundary();
141  void compute();
142 
143  /* private class */
144  class Cell {
145  private:
146  static constexpr double SQRT2 = 1.4142135623730951;
147  double x;
148  double y;
149  double hSize;
150  double distance;
151  double maxDist;
152 
153  public:
154  Cell(double p_x, double p_y, double p_hSize, double p_distanceToConstraints)
155  : x(p_x)
156  , y(p_y)
157  , hSize(p_hSize)
158  , distance(p_distanceToConstraints)
159  , maxDist(p_distanceToConstraints + (p_hSize*SQRT2))
160  {};
161 
162  geom::Envelope getEnvelope() const
163  {
164  geom::Envelope env(x-hSize, x+hSize, y-hSize, y+hSize);
165  return env;
166  }
167 
168  bool isFullyOutside() const
169  {
170  return maxDist < 0.0;
171  }
172  bool isOutside() const
173  {
174  return distance < 0.0;
175  }
176  double getMaxDistance() const
177  {
178  return maxDist;
179  }
180  double getDistance() const
181  {
182  return distance;
183  }
184  double getHSize() const
185  {
186  return hSize;
187  }
188  double getX() const
189  {
190  return x;
191  }
192  double getY() const
193  {
194  return y;
195  }
196  bool operator< (const Cell& rhs) const
197  {
198  return maxDist < rhs.maxDist;
199  }
200  bool operator> (const Cell& rhs) const
201  {
202  return maxDist > rhs.maxDist;
203  }
204  bool operator==(const Cell& rhs) const
205  {
206  return maxDist == rhs.maxDist;
207  }
208  };
209 
210  bool mayContainCircleCenter(const Cell& cell, const Cell& farthestCell);
211  void createInitialGrid(const geom::Envelope* env, std::priority_queue<Cell>& cellQueue);
212  Cell createCentroidCell(const geom::Geometry* geom);
213 
214 };
215 
216 
217 } // geos::algorithm::construct
218 } // geos::algorithm
219 } // geos
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:216
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:65
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25