GEOS 3.9.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#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
34namespace geos {
35namespace geom {
36class Coordinate;
37class Envelope;
38class Geometry;
39class GeometryFactory;
40class LineString;
41class Point;
42}
43namespace operation {
44namespace distance {
46}
47}
48}
49
50
51namespace geos {
52namespace algorithm { // geos::algorithm
53namespace construct { // geos::algorithm::construct
54
60class GEOS_DLL LargestEmptyCircle {
61
62public:
63
70 LargestEmptyCircle(const geom::Geometry* p_obstacles, double p_tolerance);
71 LargestEmptyCircle(const geom::Geometry* p_obstacles, const geom::Geometry* p_boundary, double p_tolerance);
72 ~LargestEmptyCircle() = default;
73
82 static std::unique_ptr<geom::Point> getCenter(const geom::Geometry* p_obstacles, double p_tolerance);
83
92 static std::unique_ptr<geom::LineString> getRadiusLine(const geom::Geometry* p_obstacles, double p_tolerance);
93
94 std::unique_ptr<geom::Point> getCenter();
95 std::unique_ptr<geom::Point> getRadiusPoint();
96 std::unique_ptr<geom::LineString> getRadiusLine();
97
98
99private:
100
101 /* private members */
102 double tolerance;
103 const geom::Geometry* obstacles;
104 const geom::GeometryFactory* factory;
105 std::unique_ptr<geom::Geometry> boundary; // convexhull(obstacles)
107 bool done;
108 std::unique_ptr<algorithm::locate::IndexedPointInAreaLocator> ptLocator;
109 std::unique_ptr<operation::distance::IndexedFacetDistance> boundaryDistance;
110 geom::Coordinate centerPt;
111 geom::Coordinate radiusPt;
112
113 /* private methods */
114 void setBoundary(const geom::Geometry* obstacles);
115
126 double distanceToConstraints(const geom::Coordinate& c);
127 double distanceToConstraints(double x, double y);
128 void compute();
129
130 /* private class */
131 class Cell {
132 private:
133 static constexpr double SQRT2 = 1.4142135623730951;
134 double x;
135 double y;
136 double hSize;
137 double distance;
138 double maxDist;
139
140 public:
141 Cell(double p_x, double p_y, double p_hSize, double p_distanceToConstraints)
142 : x(p_x)
143 , y(p_y)
144 , hSize(p_hSize)
145 , distance(p_distanceToConstraints)
146 , maxDist(p_distanceToConstraints + (p_hSize*SQRT2))
147 {};
148
149 geom::Envelope getEnvelope() const
150 {
151 geom::Envelope env(x-hSize, x+hSize, y-hSize, y+hSize);
152 return env;
153 }
154
155 bool isFullyOutside() const
156 {
157 return maxDist < 0.0;
158 }
159 bool isOutside() const
160 {
161 return distance < 0.0;
162 }
163 double getMaxDistance() const
164 {
165 return maxDist;
166 }
167 double getDistance() const
168 {
169 return distance;
170 }
171 double getHSize() const
172 {
173 return hSize;
174 }
175 double getX() const
176 {
177 return x;
178 }
179 double getY() const
180 {
181 return y;
182 }
183 bool operator< (const Cell& rhs) const
184 {
185 return maxDist < rhs.maxDist;
186 }
187 bool operator> (const Cell& rhs) const
188 {
189 return maxDist > rhs.maxDist;
190 }
191 bool operator==(const Cell& rhs) const
192 {
193 return maxDist == rhs.maxDist;
194 }
195 };
196
197 bool mayContainCircleCenter(const Cell& cell, const Cell& farthestCell);
198 void createInitialGrid(const geom::Envelope* env, std::priority_queue<Cell>& cellQueue);
199 Cell createCentroidCell(const geom::Geometry* geom);
200
201};
202
203
204} // geos::algorithm::construct
205} // geos::algorithm
206} // geos
207
208#endif // GEOS_ALGORITHM_CONSTRUCT_LARGESTCIRCLE_H
Definition LargestEmptyCircle.h:60
static std::unique_ptr< geom::LineString > getRadiusLine(const geom::Geometry *p_obstacles, double p_tolerance)
static std::unique_ptr< geom::Point > getCenter(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 IndexedNestedRingTester.h:26