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
33namespace geos {
34namespace geom {
35class Coordinate;
36class Envelope;
37class Geometry;
38class GeometryFactory;
39class LineString;
40class Point;
41}
42namespace operation {
43namespace distance {
45}
46}
47}
48
49
50namespace geos {
51namespace algorithm { // geos::algorithm
52namespace construct { // geos::algorithm::construct
53
74class GEOS_DLL LargestEmptyCircle {
75
76public:
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
113private:
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
Definition LargestEmptyCircle.h:74
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:216
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:65
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 geos.h:39