00001 /********************************************************************** 00002 * 00003 * GEOS - Geometry Engine Open Source 00004 * http://geos.osgeo.org 00005 * 00006 * Copyright (C) 2011 Sandro Santilli <strk@keybit.net> 00007 * Copyright (C) 2005-2006 Refractions Research Inc. 00008 * Copyright (C) 2001-2002 Vivid Solutions Inc. 00009 * 00010 * This is free software; you can redistribute and/or modify it under 00011 * the terms of the GNU Lesser General Public Licence as published 00012 * by the Free Software Foundation. 00013 * See the COPYING file for more information. 00014 * 00015 ********************************************************************** 00016 * 00017 * Last port: algorithm/ConvexHull.java r407 (JTS-1.12+) 00018 * 00019 **********************************************************************/ 00020 00021 #ifndef GEOS_ALGORITHM_CONVEXHULL_H 00022 #define GEOS_ALGORITHM_CONVEXHULL_H 00023 00024 #include <geos/export.h> 00025 #include <vector> 00026 00027 // FIXME: avoid using Cordinate:: typedefs to avoid full include 00028 #include <geos/geom/Coordinate.h> 00029 00030 #ifdef _MSC_VER 00031 #pragma warning(push) 00032 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class 00033 #endif 00034 00035 // Forward declarations 00036 namespace geos { 00037 namespace geom { 00038 class Geometry; 00039 class GeometryFactory; 00040 class CoordinateSequence; 00041 } 00042 } 00043 00044 namespace geos { 00045 namespace algorithm { // geos::algorithm 00046 00058 class GEOS_DLL ConvexHull { 00059 private: 00060 const geom::GeometryFactory *geomFactory; 00061 geom::Coordinate::ConstVect inputPts; 00062 00063 void extractCoordinates(const geom::Geometry *geom); 00064 00069 geom::CoordinateSequence *toCoordinateSequence(geom::Coordinate::ConstVect &cv); 00070 00071 void computeOctPts(const geom::Coordinate::ConstVect &src, 00072 geom::Coordinate::ConstVect &tgt); 00073 00074 bool computeOctRing(const geom::Coordinate::ConstVect &src, 00075 geom::Coordinate::ConstVect &tgt); 00076 00101 void reduce(geom::Coordinate::ConstVect &pts); 00102 00104 void padArray3(geom::Coordinate::ConstVect &pts); 00105 00107 void preSort(geom::Coordinate::ConstVect &pts); 00108 00126 int polarCompare(const geom::Coordinate &o, 00127 const geom::Coordinate &p, const geom::Coordinate &q); 00128 00129 void grahamScan(const geom::Coordinate::ConstVect &c, 00130 geom::Coordinate::ConstVect &ps); 00131 00141 geom::Geometry* lineOrPolygon(const geom::Coordinate::ConstVect &vertices); 00142 00147 void cleanRing(const geom::Coordinate::ConstVect &input, 00148 geom::Coordinate::ConstVect &cleaned); 00149 00154 bool isBetween(const geom::Coordinate& c1, const geom::Coordinate& c2, const geom::Coordinate& c3); 00155 00156 public: 00157 00161 ConvexHull(const geom::Geometry *newGeometry); 00162 00163 00164 ~ConvexHull(); 00165 00178 geom::Geometry* getConvexHull(); 00179 }; 00180 00181 } // namespace geos::algorithm 00182 } // namespace geos 00183 00184 #ifdef _MSC_VER 00185 #pragma warning(pop) 00186 #endif 00187 00188 #ifdef GEOS_INLINE 00189 # include "geos/algorithm/ConvexHull.inl" 00190 #endif 00191 00192 #endif // GEOS_ALGORITHM_CONVEXHULL_H