|
|
last update 20 Sep 2009 |
|
00001 /* 00002 * Copyright (C) 1998 00003 * Lehrstuhl fuer Technische Informatik, RWTH-Aachen, Germany 00004 * 00005 * 00006 * This file is part of the Computer Vision and Robotics Library (CVR-Lib) 00007 * 00008 * The CVR-Lib is free software; you can redistribute it and/or 00009 * modify it under the terms of the BSD License. 00010 * 00011 * All rights reserved. 00012 * 00013 * Redistribution and use in source and binary forms, with or without 00014 * modification, are permitted provided that the following conditions are met: 00015 * 00016 * 1. Redistributions of source code must retain the above copyright notice, 00017 * this list of conditions and the following disclaimer. 00018 * 00019 * 2. Redistributions in binary form must reproduce the above copyright notice, 00020 * this list of conditions and the following disclaimer in the documentation 00021 * and/or other materials provided with the distribution. 00022 * 00023 * 3. Neither the name of the authors nor the names of its contributors may be 00024 * used to endorse or promote products derived from this software without 00025 * specific prior written permission. 00026 * 00027 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 00028 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00029 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00030 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 00031 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 00032 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 00033 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 00034 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 00035 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 00036 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 00037 * POSSIBILITY OF SUCH DAMAGE. 00038 */ 00039 00040 00041 00042 /** 00043 * \file cvrPolygonPoints.h 00044 * \author Ruediger Weiler 00045 * \date 06.12.2000 00046 * 00047 * $Id: cvrPolygonPoints.h,v 1.4 2007/09/15 03:36:57 alvarado Exp $ 00048 */ 00049 00050 #ifndef _CVR_POLYGON_POINTS_H 00051 #define _CVR_POLYGON_POINTS_H 00052 00053 #include <list> 00054 #include "cvrMath.h" 00055 #include "cvrTypes.h" 00056 #include "cvrPointList.h" 00057 00058 namespace cvr { 00059 00060 //declared in cvrContour.h 00061 class borderPoints; 00062 class ioPoints; 00063 00064 /** 00065 * Contour classes: polygonPoints. 00066 * 00067 * For the explanation of the contour description in this class, see 00068 * following image: 00069 * 00070 * \code 00071 * -- 00000000001111111111222222222233 00072 * -- 01234567890123456789012345678901 00073 * 00 -------------------------------- 00074 * 01 -------------------------------- 00075 * 02 -------------------------------- 00076 * 03 --------Xooo-------Soo---------- 00077 * 04 -------o++++Xoo----E++o--------- 00078 * 05 -------o+++++++X---o+++X-------- 00079 * 06 ------X+++++++o-----o+o--------- 00080 * 07 -------o+++++++XoooX++o--------- 00081 * 08 ---------X++++++++++++X--------- 00082 * 09 --------o+++++++++++++++o------- 00083 * 10 --------o+++++++++++++++o------- 00084 * 11 -------X++++++++++++++Xo-------- 00085 * 12 ------o++++++++++++++o---------- 00086 * 13 ------o++++++++++++++oX--------- 00087 * 14 -----X++++++++++++++++++o------- 00088 * 15 -----o+++++++++++++++++++o------ 00089 * 16 ----o+++++++++++++++++++Xo------ 00090 * 17 ---X++++++++++++++++++oo-------- 00091 * 18 ----ooooooooX++++++++X---------- 00092 * 19 -------------oooooXoo----------- 00093 * 20 -------------------------------- 00094 * 21 -------------------------------- 00095 * 22 -------------------------------- 00096 * 23 -------------------------------- 00097 * \endcode 00098 * 00099 * "-" means the background, "+" represents the inner part of the object, 00100 * "o" indicates a borderPoint, "X" is a polygonPoint, the 00101 * borderPoint "S" is start point of the polygonPointList and "E" the end 00102 * point of the list. 00103 * 00104 * This class cast given borderPoints into a polygon. The polygon 00105 * has usually less points than the borderPoints, and thus it saves 00106 * memory. The disadvantage is that you loose details of the 00107 * object when you do the cast. Two parameters minLength and 00108 * maxDistance control the number of points of the resulting 00109 * polygon. 00110 * 00111 * Between two points in the polygon there must be more than 00112 * minLength points of the borderPoints, and the polygon must be 00113 * closer to the borderPoints as maxDistance. 00114 * 00115 * It is also possible to get the convex hull of a set of points 00116 * (given in a pointList or in an ioPoints list) calling the respective 00117 * castFrom() methods. 00118 * 00119 * @see cvr::borderPoints, cvr::ioPoints, cvr::pointList 00120 * 00121 * @ingroup gAggregate 00122 * @ingroup gShape 00123 */ 00124 template<class T> 00125 class polygonPoints : public pointList<T> { 00126 00127 public: 00128 /** 00129 * default constructor creates an empty border-point-list 00130 */ 00131 polygonPoints(); 00132 00133 /** 00134 * create this pointList as a copy of another pointList 00135 * @param other the pointList to be copied. 00136 */ 00137 polygonPoints(const polygonPoints<T>& other); 00138 00139 /** 00140 * destructor 00141 */ 00142 virtual ~polygonPoints(); 00143 00144 /** 00145 * returns the name of this class 00146 */ 00147 const std::string& name() const; 00148 00149 /** 00150 * alias for approximate() 00151 */ 00152 polygonPoints<T>& castFrom(const borderPoints& theBorderPoints, 00153 const int minLength=-1, 00154 const double maxDistance=1.0, 00155 const bool closed=true, 00156 const bool searchMaxDist=false); 00157 00158 /** 00159 * creates the smallest convex polygon that contains all points in 00160 * the given io-points list. (see computeConvexHull()). 00161 * 00162 * This method eliminates the points present twice in the list before 00163 * computing the convex hull. 00164 */ 00165 polygonPoints<T>& castFrom(const ioPoints& thePointList); 00166 00167 /** 00168 * This is an alias for computeConvexHull() 00169 */ 00170 polygonPoints<T>& castFrom(const pointList<T>& thePointList); 00171 00172 /** 00173 * assigment operator (alias for copy(other)). 00174 * @param other the pointList to be copied 00175 * @return a reference to the actual pointList 00176 */ 00177 inline polygonPoints<T>& operator=(const polygonPoints<T>& other); 00178 00179 /** 00180 * Compute the 2 x area of this polygon. 00181 * 00182 * The reason to return twice the area and not the area itself is very 00183 * simple: For integer point types, twice the area is always an integer 00184 * value, but the area itself is not. 00185 * 00186 * If the area is positive, the polygon has a clockwise direction. 00187 * Otherwise it will be negative. 00188 */ 00189 T areaX2() const; 00190 00191 /** 00192 * Compute if this polygon has a clockwise direction or not. 00193 */ 00194 bool clockwise() const; 00195 00196 /** 00197 * Approximate the given border points as a polygon. 00198 * 00199 * At the end of the approximation process this polygon-points-list 00200 * contains the coordinates of the vertices. 00201 * 00202 * @param theBorderPoints list with the border points to be approximated 00203 * with a polygon. The elements of this list must 00204 * be adjacent. 00205 * @param minStep minimal "distance" between vertices of the polygon. 00206 * (if 0 or negative, only the maxDistance parameter 00207 * will be considered). 00208 * The "distance" used here is \b NOT the 00209 * euclidean distance between the vertices but 00210 * the number of elements between both vertices 00211 * in the border list. These is usually 00212 * therefore a city-block distance or a 00213 * 8-neighborhood distance depending on the 00214 * border points description used. 00215 * @param maxDistance specify the maximal allowed \b euclidean distance 00216 * between the border points and the approximated polygon. 00217 * (if negative, each "minLength" pixel of the 00218 * border points will be taken). 00219 * @param closed if true (default), only the found vertices will be 00220 * in the list. If false, the last point of the list 00221 * will be adjacent to the first point in the list. 00222 * @param searchMaxDist if true, the first two vertices will be computed 00223 * as the two points in the border with the maximal 00224 * distance. If false, the first point in the 00225 * list will be a vertex and the border point with 00226 * the maximal distance to it too. This faster 00227 * method is the default. It provides usually 00228 * good results. 00229 * 00230 * @return a reference to this polygon-points instance. 00231 */ 00232 polygonPoints<T>& approximate(const borderPoints& theBorderPoints, 00233 const int minStep=-1, 00234 const double maxDistance=1, 00235 const bool closed=false, 00236 const bool searchMaxDist=false); 00237 00238 /** 00239 * Approximate the given border points as a polygon, but ensure 00240 * that the given points are vertices. The given list of points 00241 * \b must fulfill following two conditions: 00242 * -# It must have the same sequence than theBorderPoints. 00243 * -# The points must be contained by the theBorderPoints 00244 * 00245 * If one of these condition is not met, the algorithm will take too much 00246 * time trying to figure out what happend and to recover. 00247 * 00248 * The first condition ensures an efficient search for the 00249 * vertices in the border points list. 00250 * 00251 * At the end of the approximation process this polygon-points-list 00252 * contains the coordinates of the vertices. 00253 * 00254 * @param theBorderPoints list with the border points to be approximated 00255 * with a polygon. The elements of this list must 00256 * be adjacent. 00257 * @param forcedVertices list of vertices that must be included in 00258 * the polygon representation. This list must be a 00259 * subset and respect the same ordering as in 00260 * theBorderPoints 00261 * @param minStep minimal "distance" between vertices of the polygon. 00262 * (if 0 or negative, only the maxDistance parameter 00263 * will be considered). 00264 * The "distance" used here is \b NOT the 00265 * euclidean distance between the vertices but 00266 * the number of elements between both vertices 00267 * in the border list. These is usually 00268 * therefore a city-block distance or a 00269 * 8-neighborhood distance depending on the 00270 * border points description used. 00271 * @param maxDistance specify the maximal allowed \b euclidean distance 00272 * between the border points and the approximated polygon. 00273 * (if negative, each "minLength" pixel of the 00274 * border points will be taken). 00275 * @param closed if true (default), only the found vertices will be 00276 * in the list. If false, the last point of the list 00277 * will be adjacent to the first point in the list. 00278 * @param searchMaxDist if true, the first two vertices will be computed 00279 * as the two points in the border with the maximal 00280 * distance. If false, the first point in the 00281 * list will be a vertex and the border point with 00282 * the maximal distance to it too. This faster 00283 * method is the default. It provides usually 00284 * good results. 00285 * @return a reference to this polygon-points instance. 00286 */ 00287 polygonPoints<T>& approximate(const borderPoints& theBorderPoints, 00288 const ipointList& forcedVertices, 00289 const int minStep=-1, 00290 const double maxDistance=1, 00291 const bool closed=false, 00292 const bool searchMaxDist=false); 00293 00294 /** 00295 * invert the direction of the polygon points 00296 */ 00297 void invert(); 00298 00299 /* 00300 * Combine two polygons. The result is the union of the points of 00301 * both polygons. If both given polygons do not overlap, the result 00302 * will be the first polygon. 00303 * 00304 * @param polygon1 first polygon 00305 * @param polygon2 second polygon 00306 * @param minLength minimal distance between vertices of the polygon. 00307 * @param maxDistance specify the maximal allowed distance between the 00308 * border points and the approximated polygon. 00309 * If set to 0, every minLength points will be 00310 * taken as vertice of the polygon. 00311 * @return a reference to this object 00312 * 00313 */ 00314 /* TODO 00315 polygonPoints<T>& clipPoly(const polygonPoints<T>& polygon1, 00316 const polygonPoints<T>& polygon2, 00317 const int minLength = 4, 00318 const double& maxDistance = 0.8); 00319 */ 00320 00321 protected: 00322 /** 00323 * Used in the approximation of a border points with a polygon. 00324 * 00325 * Implements the Ramer (or Duda Hart) method. See also 00326 * Haralick and Shapiro. Computer and Robot Vision vol. 1 Addison Wesley, 00327 * 1992. pp. 563ff 00328 * 00329 * @param vct set of vertices of the polygon 00330 * @param idx1 initial index 00331 * @param idx2 final index 00332 * @param maxDistance maximum allowed distance 00333 * @param flags flags for the points. 00334 */ 00335 void fitAndSplit(const vector< ipoint >& vct, 00336 const int idx1, 00337 const int idx2, 00338 const double maxDistance, 00339 vector<ubyte>& flags); 00340 }; 00341 00342 /** 00343 * Polygon Points of Integer Points 00344 */ 00345 typedef polygonPoints<int> ipolygonPoints; 00346 00347 } 00348 00349 #include "cvrPolygonPoints_inline.h" 00350 00351 #endif 00352