GEOS
3.3.9
|
00001 /********************************************************************** 00002 * $Id: ConvexHull.h 3255 2011-03-01 17:56:10Z mloskot $ 00003 * 00004 * GEOS - Geometry Engine Open Source 00005 * http://geos.refractions.net 00006 * 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 #ifndef GEOS_ALGORITHM_CONVEXHULL_H 00018 #define GEOS_ALGORITHM_CONVEXHULL_H 00019 00020 #include <geos/export.h> 00021 #include <vector> 00022 00023 // FIXME: avoid using Cordinate:: typedefs to avoid full include 00024 #include <geos/geom/Coordinate.h> 00025 00026 #ifdef _MSC_VER 00027 #pragma warning(push) 00028 #pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class 00029 #endif 00030 00031 // Forward declarations 00032 namespace geos { 00033 namespace geom { 00034 class Geometry; 00035 class GeometryFactory; 00036 class CoordinateSequence; 00037 } 00038 } 00039 00040 namespace geos { 00041 namespace algorithm { // geos::algorithm 00042 00054 class GEOS_DLL ConvexHull { 00055 private: 00056 const geom::GeometryFactory *geomFactory; 00057 geom::Coordinate::ConstVect inputPts; 00058 00059 void extractCoordinates(const geom::Geometry *geom); 00060 00065 geom::CoordinateSequence *toCoordinateSequence(geom::Coordinate::ConstVect &cv); 00066 00067 void computeOctPts(const geom::Coordinate::ConstVect &src, 00068 geom::Coordinate::ConstVect &tgt); 00069 00070 bool computeOctRing(const geom::Coordinate::ConstVect &src, 00071 geom::Coordinate::ConstVect &tgt); 00072 00095 void reduce(geom::Coordinate::ConstVect &pts); 00096 00097 00099 void preSort(geom::Coordinate::ConstVect &pts); 00100 00118 int polarCompare(const geom::Coordinate &o, 00119 const geom::Coordinate &p, const geom::Coordinate &q); 00120 00121 void grahamScan(const geom::Coordinate::ConstVect &c, 00122 geom::Coordinate::ConstVect &ps); 00123 00133 geom::Geometry* lineOrPolygon(const geom::Coordinate::ConstVect &vertices); 00134 00139 void cleanRing(const geom::Coordinate::ConstVect &input, 00140 geom::Coordinate::ConstVect &cleaned); 00141 00146 bool isBetween(const geom::Coordinate& c1, const geom::Coordinate& c2, const geom::Coordinate& c3); 00147 00148 public: 00149 00153 ConvexHull(const geom::Geometry *newGeometry); 00154 00155 00156 ~ConvexHull(); 00157 00170 geom::Geometry* getConvexHull(); 00171 }; 00172 00173 } // namespace geos::algorithm 00174 } // namespace geos 00175 00176 #ifdef _MSC_VER 00177 #pragma warning(pop) 00178 #endif 00179 00180 #ifdef GEOS_INLINE 00181 # include "geos/algorithm/ConvexHull.inl" 00182 #endif 00183 00184 #endif // GEOS_ALGORITHM_CONVEXHULL_H 00185 00186 /********************************************************************** 00187 * $Log$ 00188 * Revision 1.2 2006/03/24 09:52:41 strk 00189 * USE_INLINE => GEOS_INLINE 00190 * 00191 * Revision 1.1 2006/03/09 16:46:48 strk 00192 * geos::geom namespace definition, first pass at headers split 00193 * 00194 **********************************************************************/ 00195