00001 /********************************************************************** 00002 * $Id: ConvexHull.h 2556 2009-06-06 22:22:28Z strk $ 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 // Forward declarations 00027 namespace geos { 00028 namespace geom { 00029 class Geometry; 00030 class GeometryFactory; 00031 class CoordinateSequence; 00032 } 00033 } 00034 00035 namespace geos { 00036 namespace algorithm { // geos::algorithm 00037 00049 class GEOS_DLL ConvexHull { 00050 private: 00051 const geom::GeometryFactory *geomFactory; 00052 geom::Coordinate::ConstVect inputPts; 00053 00054 void extractCoordinates(const geom::Geometry *geom); 00055 00060 geom::CoordinateSequence *toCoordinateSequence(geom::Coordinate::ConstVect &cv); 00061 00062 void computeOctPts(const geom::Coordinate::ConstVect &src, 00063 geom::Coordinate::ConstVect &tgt); 00064 00065 bool computeOctRing(const geom::Coordinate::ConstVect &src, 00066 geom::Coordinate::ConstVect &tgt); 00067 00090 void reduce(geom::Coordinate::ConstVect &pts); 00091 00092 00094 void preSort(geom::Coordinate::ConstVect &pts); 00095 00113 int polarCompare(const geom::Coordinate &o, 00114 const geom::Coordinate &p, const geom::Coordinate &q); 00115 00116 void grahamScan(const geom::Coordinate::ConstVect &c, 00117 geom::Coordinate::ConstVect &ps); 00118 00128 geom::Geometry* lineOrPolygon(const geom::Coordinate::ConstVect &vertices); 00129 00134 void cleanRing(const geom::Coordinate::ConstVect &input, 00135 geom::Coordinate::ConstVect &cleaned); 00136 00141 bool isBetween(const geom::Coordinate& c1, const geom::Coordinate& c2, const geom::Coordinate& c3); 00142 00143 public: 00144 00148 ConvexHull(const geom::Geometry *newGeometry); 00149 00150 00151 ~ConvexHull(); 00152 00165 geom::Geometry* getConvexHull(); 00166 }; 00167 00168 } // namespace geos::algorithm 00169 } // namespace geos 00170 00171 #ifdef GEOS_INLINE 00172 # include "geos/algorithm/ConvexHull.inl" 00173 #endif 00174 00175 #endif // GEOS_ALGORITHM_CONVEXHULL_H 00176 00177 /********************************************************************** 00178 * $Log$ 00179 * Revision 1.2 2006/03/24 09:52:41 strk 00180 * USE_INLINE => GEOS_INLINE 00181 * 00182 * Revision 1.1 2006/03/09 16:46:48 strk 00183 * geos::geom namespace definition, first pass at headers split 00184 * 00185 **********************************************************************/ 00186