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