1 /**********************************************************************
2  *
3  * GEOS - Geometry Engine Open Source
4  * http://geos.osgeo.org
5  *
6  * Copyright (C) 2019 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/MinimumBoundingCircle.java 2019-01-23
16  *
17  **********************************************************************/
18 
19 #ifndef GEOS_ALGORITHM_MINIMUMBOUNDINGCIRCLE_H
20 #define GEOS_ALGORITHM_MINIMUMBOUNDINGCIRCLE_H
21 
22 #include <geos/export.h>
23 #include <geos/geom/Coordinate.h>
24 #include <geos/geom/CoordinateSequence.h>
25 #include <geos/geom/Geometry.h>
26 #include <geos/geom/Point.h>
27 #include <geos/geom/Triangle.h>
28 
29 #include <vector>
30 
31 // Forward declarations
32 // namespace geos {
33 // 	namespace geom {
34 // 		class GeometryCollection;
35 // 	}
36 // }
37 
38 
39 namespace geos {
40 namespace algorithm { // geos::algorithm
41 
42 class GEOS_DLL MinimumBoundingCircle {
43 
44 private:
45 
46     // member variables
47     const geom::Geometry* input;
48     std::vector<geom::Coordinate> extremalPts;
49     geom::Coordinate centre;
50     double radius;
51 
52     void computeCentre();
53     void compute();
54     void computeCirclePoints();
55     geom::Coordinate lowestPoint(std::vector<geom::Coordinate>& pts);
56     geom::Coordinate pointWitMinAngleWithX(std::vector<geom::Coordinate>& pts, geom::Coordinate& P);
57     geom::Coordinate pointWithMinAngleWithSegment(std::vector<geom::Coordinate>& pts,
58             geom::Coordinate& P, geom::Coordinate& Q);
59     std::vector<geom::Coordinate> farthestPoints(std::vector<geom::Coordinate>& pts);
60 
61 
62 public:
63 
MinimumBoundingCircle(const geom::Geometry * geom)64     MinimumBoundingCircle(const geom::Geometry* geom):
65         input(nullptr),
66         radius(0.0)
67     {
68         input = geom;
69         centre.setNull();
70     }
71 
~MinimumBoundingCircle()72     ~MinimumBoundingCircle() {};
73 
74     /**
75     * Gets a geometry which represents the Minimum Bounding Circle.
76     * If the input is degenerate (empty or a single unique point),
77     * this method will return an empty geometry or a single Point geometry.
78     * Otherwise, a Polygon will be returned which approximates the
79     * Minimum Bounding Circle.
80     * (Note that because the computed polygon is only an approximation,
81     * it may not precisely contain all the input points.)
82     *
83     * @return a Geometry representing the Minimum Bounding Circle.
84     */
85     std::unique_ptr<geom::Geometry> getCircle();
86 
87     /**
88     * Gets a geometry representing a line between the two farthest points
89     * in the input.
90     * These points will be two of the extremal points of the Minimum Bounding Circle.
91     * They also lie on the convex hull of the input.
92     *
93     * @return a LineString between the two farthest points of the input
94     * @return a empty LineString if the input is empty
95     * @return a Point if the input is a point
96     */
97     std::unique_ptr<geom::Geometry> getMaximumDiameter();
98 
99     /**
100     * Gets a geometry representing the diameter of the computed Minimum Bounding
101     * Circle.
102     *
103     * @return the diameter LineString of the Minimum Bounding Circle
104     * @return a empty LineString if the input is empty
105     * @return a Point if the input is a point
106     */
107     std::unique_ptr<geom::Geometry> getDiameter();
108 
109     /**
110     * Gets the extremal points which define the computed Minimum Bounding Circle.
111     * There may be zero, one, two or three of these points,
112     * depending on the number of points in the input
113     * and the geometry of those points.
114     *
115     * @return the points defining the Minimum Bounding Circle
116     */
117     std::vector<geom::Coordinate> getExtremalPoints();
118 
119     /**
120     * Gets the centre point of the computed Minimum Bounding Circle.
121     *
122     * @return the centre point of the Minimum Bounding Circle
123     * @return null if the input is empty
124     */
125     geom::Coordinate getCentre();
126 
127     /**
128     * Gets the radius of the computed Minimum Bounding Circle.
129     *
130     * @return the radius of the Minimum Bounding Circle
131     */
132     double getRadius();
133 
134 };
135 
136 } // namespace geos::algorithm
137 } // namespace geos
138 
139 #endif // GEOS_ALGORITHM_MINIMUMBOUNDINGCIRCLE_H
140 
141