Renesas GR-PEACH OpenCV Development
/
gr-peach-opencv-project-sd-card_update
Important changes to repositories hosted on mbed.com
Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.
To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.
It is also possible to export all your personal repositories from the account settings page.
Fork of
gr-peach-opencv-project-sd-card
by 
the do
Embed:
(wiki syntax)
Show/hide line numbers
min_enclosing_triangle.cpp
00001 /*M/////////////////////////////////////////////////////////////////////////////////////// 00002 // 00003 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 00004 // 00005 // By downloading, copying, installing or using the software you agree to this license. 00006 // If you do not agree to this license, do not download, install, 00007 // copy or use the software. 00008 // 00009 // INFORMATION REGARDING THE CONTRIBUTION: 00010 // 00011 // Author: Ovidiu Parvu 00012 // Affiliation: Brunel University 00013 // Created: 11.09.2013 00014 // E-mail: <ovidiu.parvu[AT]gmail.com> 00015 // Web: http://people.brunel.ac.uk/~cspgoop 00016 // 00017 // These functions were implemented during Ovidiu Parvu's first year as a PhD student at 00018 // Brunel University, London, UK. The PhD project is supervised by prof. David Gilbert (principal) 00019 // and prof. Nigel Saunders (second). 00020 // 00021 // THE IMPLEMENTATION OF THE MODULES IS BASED ON THE FOLLOWING PAPERS: 00022 // 00023 // [1] V. Klee and M. C. Laskowski, "Finding the smallest triangles containing a given convex 00024 // polygon", Journal of Algorithms, vol. 6, no. 3, pp. 359-375, Sep. 1985. 00025 // [2] J. O'Rourke, A. Aggarwal, S. Maddila, and M. Baldwin, "An optimal algorithm for finding 00026 // minimal enclosing triangles", Journal of Algorithms, vol. 7, no. 2, pp. 258-269, Jun. 1986. 00027 // 00028 // The overall complexity of the algorithm is theta(n) where "n" represents the number 00029 // of vertices in the convex polygon. 00030 // 00031 // 00032 // 00033 // License Agreement 00034 // For Open Source Computer Vision Library 00035 // 00036 // Copyright (C) 2000, Intel Corporation, all rights reserved. 00037 // Copyright (C) 2013, OpenCV Foundation, all rights reserved. 00038 // Copyright (C) 2013, Ovidiu Parvu, all rights reserved. 00039 // Third party copyrights are property of their respective owners. 00040 // 00041 // Redistribution and use in source and binary forms, with or without modification, 00042 // are permitted provided that the following conditions are met: 00043 // 00044 // * Redistribution's of source code must retain the above copyright notice, 00045 // this list of conditions and the following disclaimer. 00046 // 00047 // * Redistribution's in binary form must reproduce the above copyright notice, 00048 // this list of conditions and the following disclaimer in the documentation 00049 // and/or other materials provided with the distribution. 00050 // 00051 // * The name of the copyright holders may not be used to endorse or promote products 00052 // derived from this software without specific prior written permission. 00053 // 00054 // This software is provided by the copyright holders and contributors "as is" and 00055 // any express or implied warranties, including, but not limited to, the implied 00056 // warranties of merchantability and fitness for a particular purpose are disclaimed. 00057 // In no event shall the Intel Corporation or contributors be liable for any direct, 00058 // indirect, incidental, special, exemplary, or consequential damages 00059 // (including, but not limited to, procurement of substitute goods or services; 00060 // loss of use, data, or profits; or business interruption) however caused 00061 // and on any theory of liability, whether in contract, strict liability, 00062 // or tort (including negligence or otherwise) arising in any way out of 00063 // the use of this software, even if advised of the possibility of such damage. 00064 // 00065 //M*/ 00066 00067 #include "precomp.hpp" 00068 00069 #include <algorithm> 00070 #include <cmath> 00071 #include <limits> 00072 #include <vector> 00073 00074 00075 ///////////////////////////////// Constants definitions ////////////////////////////////// 00076 00077 00078 // Intersection of line and polygon 00079 00080 #define INTERSECTS_BELOW 1 00081 #define INTERSECTS_ABOVE 2 00082 #define INTERSECTS_CRITICAL 3 00083 00084 // Error messages 00085 00086 #define ERR_SIDE_B_GAMMA "The position of side B could not be determined, because gamma(b) could not be computed." 00087 #define ERR_VERTEX_C_ON_SIDE_B "The position of the vertex C on side B could not be determined, because the considered lines do not intersect." 00088 00089 // Possible values for validation flag 00090 00091 #define VALIDATION_SIDE_A_TANGENT 0 00092 #define VALIDATION_SIDE_B_TANGENT 1 00093 #define VALIDATION_SIDES_FLUSH 2 00094 00095 // Threshold value for comparisons 00096 00097 #define EPSILON 1E-5 00098 00099 00100 ////////////////////////////// Helper functions declarations ///////////////////////////// 00101 00102 00103 namespace minEnclosingTriangle { 00104 00105 static void advance(unsigned int &index, unsigned int nrOfPoints); 00106 00107 static void advanceBToRightChain(const std::vector<cv::Point2f> &polygon, 00108 unsigned int nrOfPoints, unsigned int &b, 00109 unsigned int c); 00110 00111 static bool almostEqual(double number1, double number2); 00112 00113 static double angleOfLineWrtOxAxis(const cv::Point2f &a, const cv::Point2f &b); 00114 00115 static bool areEqualPoints(const cv::Point2f &point1, const cv::Point2f &point2); 00116 00117 static bool areIdenticalLines(const std::vector<double> &side1Params, 00118 const std::vector<double> &side2Params, double sideCExtraParam); 00119 00120 static bool areIdenticalLines(double a1, double b1, double c1, double a2, double b2, double c2); 00121 00122 static bool areIntersectingLines(const std::vector<double> &side1Params, 00123 const std::vector<double> &side2Params, 00124 double sideCExtraParam, cv::Point2f &intersectionPoint1, 00125 cv::Point2f &intersectionPoint2); 00126 00127 static bool areOnTheSameSideOfLine(const cv::Point2f &p1, const cv::Point2f &p2, 00128 const cv::Point2f &a, const cv::Point2f &b); 00129 00130 static double areaOfTriangle(const cv::Point2f &a, const cv::Point2f &b, const cv::Point2f &c); 00131 00132 static void copyResultingTriangle(const std::vector<cv::Point2f> &resultingTriangle, cv::OutputArray triangle); 00133 00134 static void createConvexHull(cv::InputArray points, std::vector<cv::Point2f> &polygon); 00135 00136 static double distanceBtwPoints(const cv::Point2f &a, const cv::Point2f &b); 00137 00138 static double distanceFromPointToLine(const cv::Point2f &a, const cv::Point2f &linePointB, 00139 const cv::Point2f &linePointC); 00140 00141 static bool findGammaIntersectionPoints(const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00142 unsigned int c, unsigned int polygonPointIndex, 00143 const cv::Point2f &side1StartVertex, const cv::Point2f &side1EndVertex, 00144 const cv::Point2f &side2StartVertex, const cv::Point2f &side2EndVertex, 00145 cv::Point2f &intersectionPoint1, cv::Point2f &intersectionPoint2); 00146 00147 static void findMinEnclosingTriangle(cv::InputArray points, 00148 CV_OUT cv::OutputArray triangle, CV_OUT double &area); 00149 00150 static void findMinEnclosingTriangle(const std::vector<cv::Point2f> &polygon, 00151 std::vector<cv::Point2f> &triangle, double &area); 00152 00153 static void findMinimumAreaEnclosingTriangle(const std::vector<cv::Point2f> &polygon, 00154 std::vector<cv::Point2f> &triangle, double &area); 00155 00156 static cv::Point2f findVertexCOnSideB(const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00157 unsigned int a, unsigned int c, 00158 const cv::Point2f &sideBStartVertex, 00159 const cv::Point2f &sideBEndVertex, 00160 const cv::Point2f &sideCStartVertex, 00161 const cv::Point2f &sideCEndVertex); 00162 00163 static bool gamma(unsigned int polygonPointIndex, cv::Point2f &gammaPoint, 00164 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00165 unsigned int a, unsigned int c); 00166 00167 static bool greaterOrEqual(double number1, double number2); 00168 00169 static double height(const cv::Point2f &polygonPoint, const std::vector<cv::Point2f> &polygon, 00170 unsigned int nrOfPoints, unsigned int c); 00171 00172 static double height(unsigned int polygonPointIndex, const std::vector<cv::Point2f> &polygon, 00173 unsigned int nrOfPoints, unsigned int c); 00174 00175 static void initialise(std::vector<cv::Point2f> &triangle, double &area); 00176 00177 static unsigned int intersects(double angleGammaAndPoint, unsigned int polygonPointIndex, 00178 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00179 unsigned int c); 00180 00181 static bool intersectsAbove(const cv::Point2f &gammaPoint, unsigned int polygonPointIndex, 00182 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00183 unsigned int c); 00184 00185 static unsigned int intersectsAboveOrBelow(unsigned int succPredIndex, unsigned int pointIndex, 00186 const std::vector<cv::Point2f> &polygon, 00187 unsigned int nrOfPoints, unsigned int c); 00188 00189 static bool intersectsBelow(const cv::Point2f &gammaPoint, unsigned int polygonPointIndex, 00190 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00191 unsigned int c); 00192 00193 static bool isAngleBetween(double angle1, double angle2, double angle3); 00194 00195 static bool isAngleBetweenNonReflex(double angle1, double angle2, double angle3); 00196 00197 static bool isFlushAngleBtwPredAndSucc(double &angleFlushEdge, double anglePred, double angleSucc); 00198 00199 static bool isGammaAngleBtw(double &gammaAngle, double angle1, double angle2); 00200 00201 static bool isGammaAngleEqualTo(double &gammaAngle, double angle); 00202 00203 static bool isLocalMinimalTriangle(cv::Point2f &vertexA, cv::Point2f &vertexB, 00204 cv::Point2f &vertexC, const std::vector<cv::Point2f> &polygon, 00205 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00206 unsigned int validationFlag, const cv::Point2f &sideAStartVertex, 00207 const cv::Point2f &sideAEndVertex, const cv::Point2f &sideBStartVertex, 00208 const cv::Point2f &sideBEndVertex, const cv::Point2f &sideCStartVertex, 00209 const cv::Point2f &sideCEndVertex); 00210 00211 static bool isNotBTangency(const std::vector<cv::Point2f> &polygon, 00212 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00213 unsigned int c); 00214 00215 static bool isOppositeAngleBetweenNonReflex(double angle1, double angle2, double angle3); 00216 00217 static bool isPointOnLineSegment(const cv::Point2f &point, const cv::Point2f &lineSegmentStart, 00218 const cv::Point2f &lineSegmentEnd); 00219 00220 static bool isValidMinimalTriangle(const cv::Point2f &vertexA, const cv::Point2f &vertexB, 00221 const cv::Point2f &vertexC, const std::vector<cv::Point2f> &polygon, 00222 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00223 unsigned int validationFlag, const cv::Point2f &sideAStartVertex, 00224 const cv::Point2f &sideAEndVertex, const cv::Point2f &sideBStartVertex, 00225 const cv::Point2f &sideBEndVertex, const cv::Point2f &sideCStartVertex, 00226 const cv::Point2f &sideCEndVertex); 00227 00228 static bool lessOrEqual(double number1, double number2); 00229 00230 static void lineEquationDeterminedByPoints(const cv::Point2f &p, const cv::Point2f &q, 00231 double &a, double &b, double &c); 00232 00233 static std::vector<double> lineEquationParameters(const cv::Point2f & p, const cv::Point2f &q); 00234 00235 static bool lineIntersection(const cv::Point2f &a1, const cv::Point2f &b1, const cv::Point2f &a2, 00236 const cv::Point2f &b2, cv::Point2f &intersection); 00237 00238 static bool lineIntersection(double a1, double b1, double c1, double a2, double b2, double c2, 00239 cv::Point2f &intersection); 00240 00241 static double maximum(double number1, double number2, double number3); 00242 00243 static cv::Point2f middlePoint(const cv::Point2f &a, const cv::Point2f &b); 00244 00245 static bool middlePointOfSideB(cv::Point2f &middlePointOfSideB, const cv::Point2f &sideAStartVertex, 00246 const cv::Point2f &sideAEndVertex, const cv::Point2f &sideBStartVertex, 00247 const cv::Point2f &sideBEndVertex, const cv::Point2f &sideCStartVertex, 00248 const cv::Point2f &sideCEndVertex); 00249 00250 static void moveAIfLowAndBIfHigh(const std::vector<cv::Point2f> &polygon, 00251 unsigned int nrOfPoints, unsigned int &a, unsigned int &b, 00252 unsigned int c); 00253 00254 static double oppositeAngle(double angle); 00255 00256 static unsigned int predecessor(unsigned int index, unsigned int nrOfPoints); 00257 00258 static void returnMinimumAreaEnclosingTriangle(const std::vector<cv::Point2f> &polygon, 00259 std::vector<cv::Point2f> &triangle, double &area); 00260 00261 static void searchForBTangency(const std::vector<cv::Point2f> &polygon, 00262 unsigned int nrOfPoints, unsigned int a, unsigned int &b, 00263 unsigned int c); 00264 00265 static int sign(double number); 00266 00267 static unsigned int successor(unsigned int index, unsigned int nrOfPoints); 00268 00269 static void updateMinimumAreaEnclosingTriangle(std::vector<cv::Point2f> &triangle, double &area, 00270 const cv::Point2f &vertexA, const cv::Point2f &vertexB, 00271 const cv::Point2f &vertexC); 00272 00273 static void updateSideB(const std::vector<cv::Point2f> &polygon, 00274 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00275 unsigned int c, unsigned int &validationFlag, 00276 cv::Point2f &sideBStartVertex, cv::Point2f &sideBEndVertex); 00277 00278 static void updateSidesBA(const std::vector<cv::Point2f> &polygon, 00279 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00280 unsigned int c, unsigned int &validationFlag, 00281 cv::Point2f &sideAStartVertex, cv::Point2f &sideAEndVertex, 00282 cv::Point2f &sideBStartVertex, cv::Point2f &sideBEndVertex, 00283 const cv::Point2f &sideCStartVertex, const cv::Point2f &sideCEndVertex); 00284 00285 static void updateSidesCA(const std::vector<cv::Point2f> &polygon, 00286 unsigned int nrOfPoints, unsigned int a, unsigned int c, 00287 cv::Point2f &sideAStartVertex, cv::Point2f &sideAEndVertex, 00288 cv::Point2f &sideCStartVertex, cv::Point2f &sideCEndVertex); 00289 00290 } 00291 00292 00293 ///////////////////////////////////// Main functions ///////////////////////////////////// 00294 00295 00296 //! Find the minimum enclosing triangle for the given set of points and return its area 00297 /*! 00298 * @param points Set of points 00299 * @param triangle Minimum area triangle enclosing the given set of points 00300 */ 00301 double cv::minEnclosingTriangle(cv::InputArray points, CV_OUT cv::OutputArray triangle) { 00302 double area; 00303 00304 minEnclosingTriangle::findMinEnclosingTriangle(points, triangle, area); 00305 00306 return area; 00307 } 00308 00309 00310 /////////////////////////////// Helper functions definition ////////////////////////////// 00311 00312 00313 namespace minEnclosingTriangle { 00314 00315 //! Find the minimum enclosing triangle and its area 00316 /*! 00317 * @param points Set of points 00318 * @param triangle Minimum area triangle enclosing the given set of points 00319 * @param area Area of the minimum area enclosing triangle 00320 */ 00321 static void findMinEnclosingTriangle(cv::InputArray points, 00322 CV_OUT cv::OutputArray triangle, CV_OUT double &area) { 00323 std::vector<cv::Point2f> resultingTriangle, polygon; 00324 00325 createConvexHull(points, polygon); 00326 findMinEnclosingTriangle(polygon, resultingTriangle, area); 00327 copyResultingTriangle(resultingTriangle, triangle); 00328 } 00329 00330 //! Create the convex hull of the given set of points 00331 /*! 00332 * @param points The provided set of points 00333 * @param polygon The polygon representing the convex hull of the points 00334 */ 00335 static void createConvexHull(cv::InputArray points, std::vector<cv::Point2f> &polygon) { 00336 cv::Mat pointsMat = points.getMat(); 00337 std::vector<cv::Point2f> pointsVector; 00338 00339 CV_Assert((pointsMat.checkVector(2) > 0) && 00340 ((pointsMat.depth() == CV_32F) || (pointsMat.depth() == CV_32S))); 00341 00342 pointsMat.convertTo(pointsVector, CV_32F); 00343 00344 convexHull(pointsVector, polygon, true, true); 00345 } 00346 00347 //! Find the minimum enclosing triangle and its area 00348 /*! 00349 * The overall complexity of the algorithm is theta(n) where "n" represents the number 00350 * of vertices in the convex polygon 00351 * 00352 * @param polygon The polygon representing the convex hull of the points 00353 * @param triangle Minimum area triangle enclosing the given polygon 00354 * @param area Area of the minimum area enclosing triangle 00355 */ 00356 static void findMinEnclosingTriangle(const std::vector<cv::Point2f> &polygon, 00357 std::vector<cv::Point2f> &triangle, double &area) { 00358 initialise(triangle, area); 00359 00360 if (polygon.size() > 3) { 00361 findMinimumAreaEnclosingTriangle(polygon, triangle, area); 00362 } else { 00363 returnMinimumAreaEnclosingTriangle(polygon, triangle, area); 00364 } 00365 } 00366 00367 //! Copy resultingTriangle to the OutputArray triangle 00368 /*! 00369 * @param resultingTriangle Minimum area triangle enclosing the given polygon found by the algorithm 00370 * @param triangle Minimum area triangle enclosing the given polygon returned to the user 00371 */ 00372 static void copyResultingTriangle(const std::vector<cv::Point2f> &resultingTriangle, 00373 cv::OutputArray triangle) { 00374 cv::Mat(resultingTriangle).copyTo(triangle); 00375 } 00376 00377 //! Initialisation function 00378 /*! 00379 * @param triangle Minimum area triangle enclosing the given polygon 00380 * @param area Area of the minimum area enclosing triangle 00381 */ 00382 static void initialise(std::vector<cv::Point2f> &triangle, double &area) { 00383 area = std::numeric_limits<double>::max(); 00384 00385 // Clear all points previously stored in the vector 00386 triangle.clear(); 00387 } 00388 00389 //! Find the minimum area enclosing triangle for the given polygon 00390 /*! 00391 * @param polygon The polygon representing the convex hull of the points 00392 * @param triangle Minimum area triangle enclosing the given polygon 00393 * @param area Area of the minimum area enclosing triangle 00394 */ 00395 static void findMinimumAreaEnclosingTriangle(const std::vector<cv::Point2f> &polygon, 00396 std::vector<cv::Point2f> &triangle, double &area) { 00397 // Algorithm specific variables 00398 00399 unsigned int validationFlag; 00400 00401 cv::Point2f vertexA, vertexB, vertexC; 00402 00403 cv::Point2f sideAStartVertex, sideAEndVertex; 00404 cv::Point2f sideBStartVertex, sideBEndVertex; 00405 cv::Point2f sideCStartVertex, sideCEndVertex; 00406 00407 unsigned int a, b, c; 00408 unsigned int nrOfPoints; 00409 00410 // Variables initialisation 00411 00412 nrOfPoints = static_cast<unsigned int>(polygon.size()); 00413 00414 a = 1; 00415 b = 2; 00416 c = 0; 00417 00418 // Main algorithm steps 00419 00420 for (c = 0; c < nrOfPoints; c++) { 00421 advanceBToRightChain(polygon, nrOfPoints, b, c); 00422 moveAIfLowAndBIfHigh(polygon, nrOfPoints, a, b, c); 00423 searchForBTangency(polygon, nrOfPoints, a ,b, c); 00424 00425 updateSidesCA(polygon, nrOfPoints, a, c, sideAStartVertex, sideAEndVertex, 00426 sideCStartVertex, sideCEndVertex); 00427 00428 if (isNotBTangency(polygon, nrOfPoints, a, b, c)) { 00429 updateSidesBA(polygon, nrOfPoints, a, b, c, validationFlag, sideAStartVertex, 00430 sideAEndVertex, sideBStartVertex, sideBEndVertex, 00431 sideCStartVertex, sideCEndVertex); 00432 } else { 00433 updateSideB(polygon, nrOfPoints, a, b, c, validationFlag, 00434 sideBStartVertex, sideBEndVertex); 00435 } 00436 00437 if (isLocalMinimalTriangle(vertexA, vertexB, vertexC, polygon, nrOfPoints, a, b, 00438 validationFlag, sideAStartVertex, sideAEndVertex, 00439 sideBStartVertex, sideBEndVertex, sideCStartVertex, 00440 sideCEndVertex)) { 00441 updateMinimumAreaEnclosingTriangle(triangle, area, vertexA, vertexB, vertexC); 00442 } 00443 } 00444 } 00445 00446 //! Return the minimum area enclosing (pseudo-)triangle in case the convex polygon has at most three points 00447 /*! 00448 * @param polygon The polygon representing the convex hull of the points 00449 * @param triangle Minimum area triangle enclosing the given polygon 00450 * @param area Area of the minimum area enclosing triangle 00451 */ 00452 static void returnMinimumAreaEnclosingTriangle(const std::vector<cv::Point2f> &polygon, 00453 std::vector<cv::Point2f> &triangle, double &area) { 00454 unsigned int nrOfPoints = static_cast<unsigned int>(polygon.size()); 00455 00456 for (int i = 0; i < 3; i++) { 00457 triangle.push_back(polygon[i % nrOfPoints]); 00458 } 00459 00460 area = areaOfTriangle(triangle[0], triangle[1], triangle[2]); 00461 } 00462 00463 //! Advance b to the right chain 00464 /*! 00465 * See paper [2] for more details 00466 * 00467 * @param polygon The polygon representing the convex hull of the points 00468 * @param nrOfPoints Number of points defining the convex polygon 00469 * @param b Index b 00470 * @param c Index c 00471 */ 00472 static void advanceBToRightChain(const std::vector<cv::Point2f> &polygon, 00473 unsigned int nrOfPoints, unsigned int &b, 00474 unsigned int c) { 00475 while (greaterOrEqual(height(successor(b, nrOfPoints), polygon, nrOfPoints, c), 00476 height(b, polygon, nrOfPoints, c))) { 00477 advance(b, nrOfPoints); 00478 } 00479 } 00480 00481 //! Move "a" if it is low and "b" if it is high 00482 /*! 00483 * See paper [2] for more details 00484 * 00485 * @param polygon The polygon representing the convex hull of the points 00486 * @param nrOfPoints Number of points defining the convex polygon 00487 * @param a Index a 00488 * @param b Index b 00489 * @param c Index c 00490 */ 00491 static void moveAIfLowAndBIfHigh(const std::vector<cv::Point2f> &polygon, 00492 unsigned int nrOfPoints, unsigned int &a, unsigned int &b, 00493 unsigned int c) { 00494 cv::Point2f gammaOfA; 00495 00496 while(height(b, polygon, nrOfPoints, c) > height(a, polygon, nrOfPoints, c)) { 00497 if ((gamma(a, gammaOfA, polygon, nrOfPoints, a, c)) && (intersectsBelow(gammaOfA, b, polygon, nrOfPoints, c))) { 00498 advance(b, nrOfPoints); 00499 } else { 00500 advance(a, nrOfPoints); 00501 } 00502 } 00503 } 00504 00505 //! Search for the tangency of side B 00506 /*! 00507 * See paper [2] for more details 00508 * 00509 * @param polygon The polygon representing the convex hull of the points 00510 * @param nrOfPoints Number of points defining the convex polygon 00511 * @param a Index a 00512 * @param b Index b 00513 * @param c Index c 00514 */ 00515 static void searchForBTangency(const std::vector<cv::Point2f> &polygon, 00516 unsigned int nrOfPoints, unsigned int a, unsigned int &b, 00517 unsigned int c) { 00518 cv::Point2f gammaOfB; 00519 00520 while (((gamma(b, gammaOfB, polygon, nrOfPoints, a, c)) && 00521 (intersectsBelow(gammaOfB, b, polygon, nrOfPoints, c))) && 00522 (greaterOrEqual(height(b, polygon, nrOfPoints, c), 00523 height(predecessor(a, nrOfPoints), polygon, nrOfPoints, c))) 00524 ) { 00525 advance(b, nrOfPoints); 00526 } 00527 } 00528 00529 //! Check if tangency for side B was not obtained 00530 /*! 00531 * See paper [2] for more details 00532 * 00533 * @param polygon The polygon representing the convex hull of the points 00534 * @param nrOfPoints Number of points defining the convex polygon 00535 * @param a Index a 00536 * @param b Index b 00537 * @param c Index c 00538 */ 00539 static bool isNotBTangency(const std::vector<cv::Point2f> &polygon, 00540 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00541 unsigned int c) { 00542 cv::Point2f gammaOfB; 00543 00544 if (((gamma(b, gammaOfB, polygon, nrOfPoints, a, c)) && 00545 (intersectsAbove(gammaOfB, b, polygon, nrOfPoints, c))) || 00546 (height(b, polygon, nrOfPoints, c) < height(predecessor(a, nrOfPoints), polygon, nrOfPoints, c))) { 00547 return true; 00548 } 00549 00550 return false; 00551 } 00552 00553 //! Update sides A and C 00554 /*! 00555 * Side C will have as start and end vertices the polygon points "c" and "c-1" 00556 * Side A will have as start and end vertices the polygon points "a" and "a-1" 00557 * 00558 * @param polygon The polygon representing the convex hull of the points 00559 * @param nrOfPoints Number of points defining the convex polygon 00560 * @param a Index a 00561 * @param c Index c 00562 * @param sideAStartVertex Start vertex for defining side A 00563 * @param sideAEndVertex End vertex for defining side A 00564 * @param sideCStartVertex Start vertex for defining side C 00565 * @param sideCEndVertex End vertex for defining side C 00566 */ 00567 static void updateSidesCA(const std::vector<cv::Point2f> &polygon, 00568 unsigned int nrOfPoints, unsigned int a, unsigned int c, 00569 cv::Point2f &sideAStartVertex, cv::Point2f &sideAEndVertex, 00570 cv::Point2f &sideCStartVertex, cv::Point2f &sideCEndVertex) { 00571 sideCStartVertex = polygon[predecessor(c, nrOfPoints)]; 00572 sideCEndVertex = polygon[c]; 00573 00574 sideAStartVertex = polygon[predecessor(a, nrOfPoints)]; 00575 sideAEndVertex = polygon[a]; 00576 } 00577 00578 //! Update sides B and possibly A if tangency for side B was not obtained 00579 /*! 00580 * See paper [2] for more details 00581 * 00582 * @param polygon The polygon representing the convex hull of the points 00583 * @param nrOfPoints Number of points defining the convex polygon 00584 * @param a Index a 00585 * @param b Index b 00586 * @param c Index c 00587 * @param validationFlag Flag used for validation 00588 * @param sideAStartVertex Start vertex for defining side A 00589 * @param sideAEndVertex End vertex for defining side A 00590 * @param sideBStartVertex Start vertex for defining side B 00591 * @param sideBEndVertex End vertex for defining side B 00592 * @param sideCStartVertex Start vertex for defining side C 00593 * @param sideCEndVertex End vertex for defining side C 00594 */ 00595 static void updateSidesBA(const std::vector<cv::Point2f> &polygon, 00596 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00597 unsigned int c, unsigned int &validationFlag, 00598 cv::Point2f &sideAStartVertex, cv::Point2f &sideAEndVertex, 00599 cv::Point2f &sideBStartVertex, cv::Point2f &sideBEndVertex, 00600 const cv::Point2f &sideCStartVertex, const cv::Point2f &sideCEndVertex) { 00601 // Side B is flush with edge [b, b-1] 00602 sideBStartVertex = polygon[predecessor(b, nrOfPoints)]; 00603 sideBEndVertex = polygon[b]; 00604 00605 // Find middle point of side B 00606 cv::Point2f sideBMiddlePoint; 00607 00608 if ((middlePointOfSideB(sideBMiddlePoint, sideAStartVertex, sideAEndVertex, sideBStartVertex, 00609 sideBEndVertex, sideCStartVertex, sideCEndVertex)) && 00610 (height(sideBMiddlePoint, polygon, nrOfPoints, c) < 00611 height(predecessor(a, nrOfPoints), polygon, nrOfPoints, c))) { 00612 sideAStartVertex = polygon[predecessor(a, nrOfPoints)]; 00613 sideAEndVertex = findVertexCOnSideB(polygon, nrOfPoints, a, c, 00614 sideBStartVertex, sideBEndVertex, 00615 sideCStartVertex, sideCEndVertex); 00616 00617 validationFlag = VALIDATION_SIDE_A_TANGENT; 00618 } else { 00619 validationFlag = VALIDATION_SIDES_FLUSH; 00620 } 00621 } 00622 00623 //! Set side B if tangency for side B was obtained 00624 /*! 00625 * See paper [2] for more details 00626 * 00627 * @param polygon The polygon representing the convex hull of the points 00628 * @param nrOfPoints Number of points defining the convex polygon 00629 * @param a Index a 00630 * @param b Index b 00631 * @param c Index c 00632 * @param validationFlag Flag used for validation 00633 * @param sideBStartVertex Start vertex for defining side B 00634 * @param sideBEndVertex End vertex for defining side B 00635 */ 00636 static void updateSideB(const std::vector<cv::Point2f> &polygon, 00637 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00638 unsigned int c, unsigned int &validationFlag, 00639 cv::Point2f &sideBStartVertex, cv::Point2f &sideBEndVertex) { 00640 if (!gamma(b, sideBStartVertex, polygon, nrOfPoints, a, c)) { 00641 CV_Error(cv::Error::StsInternal, ERR_SIDE_B_GAMMA); 00642 } 00643 00644 sideBEndVertex = polygon[b]; 00645 00646 validationFlag = VALIDATION_SIDE_B_TANGENT; 00647 } 00648 00649 //! Update the triangle vertices after all sides were set and check if a local minimal triangle was found or not 00650 /*! 00651 * See paper [2] for more details 00652 * 00653 * @param vertexA Vertex A of the enclosing triangle 00654 * @param vertexB Vertex B of the enclosing triangle 00655 * @param vertexC Vertex C of the enclosing triangle 00656 * @param polygon The polygon representing the convex hull of the points 00657 * @param nrOfPoints Number of points defining the convex polygon 00658 * @param a Index a 00659 * @param b Index b 00660 * @param validationFlag Flag used for validation 00661 * @param sideAStartVertex Start vertex for defining side A 00662 * @param sideAEndVertex End vertex for defining side A 00663 * @param sideBStartVertex Start vertex for defining side B 00664 * @param sideBEndVertex End vertex for defining side B 00665 * @param sideCStartVertex Start vertex for defining side C 00666 * @param sideCEndVertex End vertex for defining side C 00667 */ 00668 static bool isLocalMinimalTriangle(cv::Point2f &vertexA, cv::Point2f &vertexB, 00669 cv::Point2f &vertexC, const std::vector<cv::Point2f> &polygon, 00670 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00671 unsigned int validationFlag, const cv::Point2f &sideAStartVertex, 00672 const cv::Point2f &sideAEndVertex, const cv::Point2f &sideBStartVertex, 00673 const cv::Point2f &sideBEndVertex, const cv::Point2f &sideCStartVertex, 00674 const cv::Point2f &sideCEndVertex) { 00675 if ((!lineIntersection(sideAStartVertex, sideAEndVertex, 00676 sideBStartVertex, sideBEndVertex, vertexC)) || 00677 (!lineIntersection(sideAStartVertex, sideAEndVertex, 00678 sideCStartVertex, sideCEndVertex, vertexB)) || 00679 (!lineIntersection(sideBStartVertex, sideBEndVertex, 00680 sideCStartVertex, sideCEndVertex, vertexA))) { 00681 return false; 00682 } 00683 00684 return isValidMinimalTriangle(vertexA, vertexB, vertexC, polygon, nrOfPoints, a, b, 00685 validationFlag, sideAStartVertex, sideAEndVertex, 00686 sideBStartVertex, sideBEndVertex, sideCStartVertex, 00687 sideCEndVertex); 00688 } 00689 00690 //! Check if the found minimal triangle is valid 00691 /*! 00692 * This means that all midpoints of the triangle should touch the polygon 00693 * 00694 * See paper [2] for more details 00695 * 00696 * @param vertexA Vertex A of the enclosing triangle 00697 * @param vertexB Vertex B of the enclosing triangle 00698 * @param vertexC Vertex C of the enclosing triangle 00699 * @param polygon The polygon representing the convex hull of the points 00700 * @param nrOfPoints Number of points defining the convex polygon 00701 * @param a Index a 00702 * @param b Index b 00703 * @param validationFlag Flag used for validation 00704 * @param sideAStartVertex Start vertex for defining side A 00705 * @param sideAEndVertex End vertex for defining side A 00706 * @param sideBStartVertex Start vertex for defining side B 00707 * @param sideBEndVertex End vertex for defining side B 00708 * @param sideCStartVertex Start vertex for defining side C 00709 * @param sideCEndVertex End vertex for defining side C 00710 */ 00711 static bool isValidMinimalTriangle(const cv::Point2f &vertexA, const cv::Point2f &vertexB, 00712 const cv::Point2f &vertexC, const std::vector<cv::Point2f> &polygon, 00713 unsigned int nrOfPoints, unsigned int a, unsigned int b, 00714 unsigned int validationFlag, const cv::Point2f &sideAStartVertex, 00715 const cv::Point2f &sideAEndVertex, const cv::Point2f &sideBStartVertex, 00716 const cv::Point2f &sideBEndVertex, const cv::Point2f &sideCStartVertex, 00717 const cv::Point2f &sideCEndVertex) { 00718 cv::Point2f midpointSideA = middlePoint(vertexB, vertexC); 00719 cv::Point2f midpointSideB = middlePoint(vertexA, vertexC); 00720 cv::Point2f midpointSideC = middlePoint(vertexA, vertexB); 00721 00722 bool sideAValid = (validationFlag == VALIDATION_SIDE_A_TANGENT) 00723 ? (areEqualPoints(midpointSideA, polygon[predecessor(a, nrOfPoints)])) 00724 : (isPointOnLineSegment(midpointSideA, sideAStartVertex, sideAEndVertex)); 00725 00726 bool sideBValid = (validationFlag == VALIDATION_SIDE_B_TANGENT) 00727 ? (areEqualPoints(midpointSideB, polygon[b])) 00728 : (isPointOnLineSegment(midpointSideB, sideBStartVertex, sideBEndVertex)); 00729 00730 bool sideCValid = isPointOnLineSegment(midpointSideC, sideCStartVertex, sideCEndVertex); 00731 00732 return (sideAValid && sideBValid && sideCValid); 00733 } 00734 00735 //! Update the current minimum area enclosing triangle if the newly obtained one has a smaller area 00736 /*! 00737 * @param triangle Minimum area triangle enclosing the given polygon 00738 * @param area Area of the minimum area triangle enclosing the given polygon 00739 * @param vertexA Vertex A of the enclosing triangle 00740 * @param vertexB Vertex B of the enclosing triangle 00741 * @param vertexC Vertex C of the enclosing triangle 00742 */ 00743 static void updateMinimumAreaEnclosingTriangle(std::vector<cv::Point2f> &triangle, double &area, 00744 const cv::Point2f &vertexA, const cv::Point2f &vertexB, 00745 const cv::Point2f &vertexC) { 00746 double triangleArea = areaOfTriangle(vertexA, vertexB, vertexC); 00747 00748 if (triangleArea < area) { 00749 triangle.clear(); 00750 00751 triangle.push_back(vertexA); 00752 triangle.push_back(vertexB); 00753 triangle.push_back(vertexC); 00754 00755 area = triangleArea; 00756 } 00757 } 00758 00759 //! Return the middle point of side B 00760 /*! 00761 * @param middlePointOfSideB Middle point of side B 00762 * @param sideAStartVertex Start vertex for defining side A 00763 * @param sideAEndVertex End vertex for defining side A 00764 * @param sideBStartVertex Start vertex for defining side B 00765 * @param sideBEndVertex End vertex for defining side B 00766 * @param sideCStartVertex Start vertex for defining side C 00767 * @param sideCEndVertex End vertex for defining side C 00768 */ 00769 static bool middlePointOfSideB(cv::Point2f &middlePointOfSideB, const cv::Point2f &sideAStartVertex, 00770 const cv::Point2f &sideAEndVertex, const cv::Point2f &sideBStartVertex, 00771 const cv::Point2f &sideBEndVertex, const cv::Point2f &sideCStartVertex, 00772 const cv::Point2f &sideCEndVertex) { 00773 cv::Point2f vertexA, vertexC; 00774 00775 if ((!lineIntersection(sideBStartVertex, sideBEndVertex, sideCStartVertex, sideCEndVertex, vertexA)) || 00776 (!lineIntersection(sideBStartVertex, sideBEndVertex, sideAStartVertex, sideAEndVertex, vertexC))) { 00777 return false; 00778 } 00779 00780 middlePointOfSideB = middlePoint(vertexA, vertexC); 00781 00782 return true; 00783 } 00784 00785 //! Check if the line intersects below 00786 /*! 00787 * Check if the line determined by gammaPoint and polygon[polygonPointIndex] intersects 00788 * the polygon below the point polygon[polygonPointIndex] 00789 * 00790 * @param gammaPoint Gamma(p) 00791 * @param polygonPointIndex Index of the polygon point which is considered when determining the line 00792 * @param polygon The polygon representing the convex hull of the points 00793 * @param nrOfPoints Number of points defining the convex polygon 00794 * @param c Index c 00795 */ 00796 static bool intersectsBelow(const cv::Point2f &gammaPoint, unsigned int polygonPointIndex, 00797 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00798 unsigned int c) { 00799 double angleOfGammaAndPoint = angleOfLineWrtOxAxis(polygon[polygonPointIndex], gammaPoint); 00800 00801 return (intersects(angleOfGammaAndPoint, polygonPointIndex, polygon, nrOfPoints, c) == INTERSECTS_BELOW); 00802 } 00803 00804 //! Check if the line intersects above 00805 /*! 00806 * Check if the line determined by gammaPoint and polygon[polygonPointIndex] intersects 00807 * the polygon above the point polygon[polygonPointIndex] 00808 * 00809 * @param gammaPoint Gamma(p) 00810 * @param polygonPointIndex Index of the polygon point which is considered when determining the line 00811 * @param polygon The polygon representing the convex hull of the points 00812 * @param nrOfPoints Number of points defining the convex polygon 00813 * @param c Index c 00814 */ 00815 static bool intersectsAbove(const cv::Point2f &gammaPoint, unsigned int polygonPointIndex, 00816 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00817 unsigned int c) { 00818 double angleOfGammaAndPoint = angleOfLineWrtOxAxis(gammaPoint, polygon[polygonPointIndex]); 00819 00820 return (intersects(angleOfGammaAndPoint, polygonPointIndex, polygon, nrOfPoints, c) == INTERSECTS_ABOVE); 00821 } 00822 00823 //! Check if/where the line determined by gammaPoint and polygon[polygonPointIndex] intersects the polygon 00824 /*! 00825 * @param angleGammaAndPoint Angle determined by gammaPoint and polygon[polygonPointIndex] wrt Ox axis 00826 * @param polygonPointIndex Index of the polygon point which is considered when determining the line 00827 * @param polygon The polygon representing the convex hull of the points 00828 * @param nrOfPoints Number of points defining the convex polygon 00829 * @param c Index c 00830 */ 00831 static unsigned int intersects(double angleGammaAndPoint, unsigned int polygonPointIndex, 00832 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00833 unsigned int c) { 00834 double anglePointPredecessor = angleOfLineWrtOxAxis(polygon[predecessor(polygonPointIndex, nrOfPoints)], 00835 polygon[polygonPointIndex]); 00836 double anglePointSuccessor = angleOfLineWrtOxAxis(polygon[successor(polygonPointIndex, nrOfPoints)], 00837 polygon[polygonPointIndex]); 00838 double angleFlushEdge = angleOfLineWrtOxAxis(polygon[predecessor(c, nrOfPoints)], 00839 polygon[c]); 00840 00841 if (isFlushAngleBtwPredAndSucc(angleFlushEdge, anglePointPredecessor, anglePointSuccessor)) { 00842 if ((isGammaAngleBtw(angleGammaAndPoint, anglePointPredecessor, angleFlushEdge)) || 00843 (almostEqual(angleGammaAndPoint, anglePointPredecessor))) { 00844 return intersectsAboveOrBelow(predecessor(polygonPointIndex, nrOfPoints), 00845 polygonPointIndex, polygon, nrOfPoints, c); 00846 } else if ((isGammaAngleBtw(angleGammaAndPoint, anglePointSuccessor, angleFlushEdge)) || 00847 (almostEqual(angleGammaAndPoint, anglePointSuccessor))) { 00848 return intersectsAboveOrBelow(successor(polygonPointIndex, nrOfPoints), 00849 polygonPointIndex, polygon, nrOfPoints, c); 00850 } 00851 } else { 00852 if ( 00853 (isGammaAngleBtw(angleGammaAndPoint, anglePointPredecessor, anglePointSuccessor)) || 00854 ( 00855 (isGammaAngleEqualTo(angleGammaAndPoint, anglePointPredecessor)) && 00856 (!isGammaAngleEqualTo(angleGammaAndPoint, angleFlushEdge)) 00857 ) || 00858 ( 00859 (isGammaAngleEqualTo(angleGammaAndPoint, anglePointSuccessor)) && 00860 (!isGammaAngleEqualTo(angleGammaAndPoint, angleFlushEdge)) 00861 ) 00862 ) { 00863 return INTERSECTS_BELOW; 00864 } 00865 } 00866 00867 return INTERSECTS_CRITICAL; 00868 } 00869 00870 //! If (gamma(x) x) intersects P between successorOrPredecessorIndex and pointIntex is it above/below? 00871 /*! 00872 * @param succPredIndex Index of the successor or predecessor 00873 * @param pointIndex Index of the point x in the polygon 00874 * @param polygon The polygon representing the convex hull of the points 00875 * @param nrOfPoints Number of points defining the convex polygon 00876 * @param c Index c 00877 */ 00878 static unsigned int intersectsAboveOrBelow(unsigned int succPredIndex, unsigned int pointIndex, 00879 const std::vector<cv::Point2f> &polygon, 00880 unsigned int nrOfPoints, unsigned int c) { 00881 if (height(succPredIndex, polygon, nrOfPoints, c) > height(pointIndex, polygon, nrOfPoints, c)) { 00882 return INTERSECTS_ABOVE; 00883 } else { 00884 return INTERSECTS_BELOW; 00885 } 00886 } 00887 00888 //! Find gamma for a given point "p" specified by its index 00889 /*! 00890 * The function returns true if gamma exists i.e. if lines (a a-1) and (x y) intersect 00891 * and false otherwise. In case the two lines intersect in point intersectionPoint, gamma is computed. 00892 * 00893 * Considering that line (x y) is a line parallel to (c c-1) and that the distance between the lines is equal 00894 * to 2 * height(p), we can have two possible (x y) lines. 00895 * 00896 * Therefore, we will compute two intersection points between the lines (x y) and (a a-1) and take the 00897 * point which is on the same side of line (c c-1) as the polygon. 00898 * 00899 * See paper [2] and formula for distance from point to a line for more details 00900 * 00901 * @param polygonPointIndex Index of the polygon point 00902 * @param gammaPoint Point gamma(polygon[polygonPointIndex]) 00903 * @param polygon The polygon representing the convex hull of the points 00904 * @param nrOfPoints Number of points defining the convex polygon 00905 * @param a Index a 00906 * @param c Index c 00907 */ 00908 static bool gamma(unsigned int polygonPointIndex, cv::Point2f &gammaPoint, 00909 const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00910 unsigned int a, unsigned int c) { 00911 cv::Point2f intersectionPoint1, intersectionPoint2; 00912 00913 // Get intersection points if they exist 00914 if (!findGammaIntersectionPoints(polygon, nrOfPoints, c, polygonPointIndex, 00915 polygon[a], polygon[predecessor(a, nrOfPoints)], 00916 polygon[c], polygon[predecessor(c, nrOfPoints)], 00917 intersectionPoint1, intersectionPoint2)) { 00918 return false; 00919 } 00920 00921 // Select the point which is on the same side of line C as the polygon 00922 if (areOnTheSameSideOfLine(intersectionPoint1, polygon[successor(c, nrOfPoints)], 00923 polygon[c], polygon[predecessor(c, nrOfPoints)])) { 00924 gammaPoint = intersectionPoint1; 00925 } else { 00926 gammaPoint = intersectionPoint2; 00927 } 00928 00929 return true; 00930 } 00931 00932 //! Find vertex C which lies on side B at a distance = 2 * height(a-1) from side C 00933 /*! 00934 * Considering that line (x y) is a line parallel to (c c-1) and that the distance between the lines is equal 00935 * to 2 * height(a-1), we can have two possible (x y) lines. 00936 * 00937 * Therefore, we will compute two intersection points between the lines (x y) and (b b-1) and take the 00938 * point which is on the same side of line (c c-1) as the polygon. 00939 * 00940 * See paper [2] and formula for distance from point to a line for more details 00941 * 00942 * @param polygon The polygon representing the convex hull of the points 00943 * @param nrOfPoints Number of points defining the convex polygon 00944 * @param a Index a 00945 * @param c Index c 00946 * @param sideBStartVertex Start vertex for defining side B 00947 * @param sideBEndVertex End vertex for defining side B 00948 * @param sideCStartVertex Start vertex for defining side C 00949 * @param sideCEndVertex End vertex for defining side C 00950 */ 00951 static cv::Point2f findVertexCOnSideB(const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00952 unsigned int a, unsigned int c, 00953 const cv::Point2f &sideBStartVertex, 00954 const cv::Point2f &sideBEndVertex, 00955 const cv::Point2f &sideCStartVertex, 00956 const cv::Point2f &sideCEndVertex) { 00957 cv::Point2f intersectionPoint1, intersectionPoint2; 00958 00959 // Get intersection points if they exist 00960 if (!findGammaIntersectionPoints(polygon, nrOfPoints, c, predecessor(a, nrOfPoints), 00961 sideBStartVertex, sideBEndVertex, 00962 sideCStartVertex, sideCEndVertex, 00963 intersectionPoint1, intersectionPoint2)) { 00964 CV_Error(cv::Error::StsInternal, ERR_VERTEX_C_ON_SIDE_B); 00965 } 00966 00967 // Select the point which is on the same side of line C as the polygon 00968 if (areOnTheSameSideOfLine(intersectionPoint1, polygon[successor(c, nrOfPoints)], 00969 polygon[c], polygon[predecessor(c, nrOfPoints)])) { 00970 return intersectionPoint1; 00971 } else { 00972 return intersectionPoint2; 00973 } 00974 } 00975 00976 //! Find the intersection points to compute gamma(point) 00977 /*! 00978 * @param polygon The polygon representing the convex hull of the points 00979 * @param nrOfPoints Number of points defining the convex polygon 00980 * @param c Index c 00981 * @param polygonPointIndex Index of the polygon point for which the distance is known 00982 * @param side1StartVertex Start vertex for side 1 00983 * @param side1EndVertex End vertex for side 1 00984 * @param side2StartVertex Start vertex for side 2 00985 * @param side2EndVertex End vertex for side 2 00986 * @param intersectionPoint1 First intersection point between one pair of lines 00987 * @param intersectionPoint2 Second intersection point between other pair of lines 00988 */ 00989 static bool findGammaIntersectionPoints(const std::vector<cv::Point2f> &polygon, unsigned int nrOfPoints, 00990 unsigned int c, unsigned int polygonPointIndex, 00991 const cv::Point2f &side1StartVertex, const cv::Point2f &side1EndVertex, 00992 const cv::Point2f &side2StartVertex, const cv::Point2f &side2EndVertex, 00993 cv::Point2f &intersectionPoint1, cv::Point2f &intersectionPoint2) { 00994 std::vector<double> side1Params = lineEquationParameters(side1StartVertex, side1EndVertex); 00995 std::vector<double> side2Params = lineEquationParameters(side2StartVertex, side2EndVertex); 00996 00997 // Compute side C extra parameter using the formula for distance from a point to a line 00998 double polygonPointHeight = height(polygonPointIndex, polygon, nrOfPoints, c); 00999 double distFormulaDenom = sqrt((side2Params[0] * side2Params[0]) + (side2Params[1] * side2Params[1])); 01000 double sideCExtraParam = 2 * polygonPointHeight * distFormulaDenom; 01001 01002 // Get intersection points if they exist or if lines are identical 01003 if (!areIntersectingLines(side1Params, side2Params, sideCExtraParam, intersectionPoint1, intersectionPoint2)) { 01004 return false; 01005 } else if (areIdenticalLines(side1Params, side2Params, sideCExtraParam)) { 01006 intersectionPoint1 = side1StartVertex; 01007 intersectionPoint2 = side1EndVertex; 01008 } 01009 01010 return true; 01011 } 01012 01013 //! Check if the given lines are identical or not 01014 /*! 01015 * The lines are specified as: 01016 * ax + by + c = 0 01017 * OR 01018 * ax + by + c (+/-) sideCExtraParam = 0 01019 * 01020 * @param side1Params Vector containing the values of a, b and c for side 1 01021 * @param side2Params Vector containing the values of a, b and c for side 2 01022 * @param sideCExtraParam Extra parameter for the flush edge C 01023 */ 01024 static bool areIdenticalLines(const std::vector<double> &side1Params, 01025 const std::vector<double> &side2Params, double sideCExtraParam) { 01026 return ( 01027 (areIdenticalLines(side1Params[0], side1Params[1], -(side1Params[2]), 01028 side2Params[0], side2Params[1], -(side2Params[2]) - sideCExtraParam)) || 01029 (areIdenticalLines(side1Params[0], side1Params[1], -(side1Params[2]), 01030 side2Params[0], side2Params[1], -(side2Params[2]) + sideCExtraParam)) 01031 ); 01032 } 01033 01034 //! Check if the given lines intersect or not. If the lines intersect find their intersection points. 01035 /*! 01036 * The lines are specified as: 01037 * ax + by + c = 0 01038 * OR 01039 * ax + by + c (+/-) sideCExtraParam = 0 01040 * 01041 * @param side1Params Vector containing the values of a, b and c for side 1 01042 * @param side2Params Vector containing the values of a, b and c for side 2 01043 * @param sideCExtraParam Extra parameter for the flush edge C 01044 * @param intersectionPoint1 The first intersection point, if it exists 01045 * @param intersectionPoint2 The second intersection point, if it exists 01046 */ 01047 static bool areIntersectingLines(const std::vector<double> &side1Params, 01048 const std::vector<double> &side2Params, 01049 double sideCExtraParam, cv::Point2f &intersectionPoint1, 01050 cv::Point2f &intersectionPoint2) { 01051 return ( 01052 (lineIntersection(side1Params[0], side1Params[1], -(side1Params[2]), 01053 side2Params[0], side2Params[1], -(side2Params[2]) - sideCExtraParam, 01054 intersectionPoint1)) && 01055 (lineIntersection(side1Params[0], side1Params[1], -(side1Params[2]), 01056 side2Params[0], side2Params[1], -(side2Params[2]) + sideCExtraParam, 01057 intersectionPoint2)) 01058 ); 01059 } 01060 01061 //! Get the line equation parameters "a", "b" and "c" for the line determined by points "p" and "q" 01062 /*! 01063 * The equation of the line is considered in the general form: 01064 * ax + by + c = 0 01065 * 01066 * @param p One point for defining the equation of the line 01067 * @param q Second point for defining the equation of the line 01068 */ 01069 static std::vector<double> lineEquationParameters(const cv::Point2f & p, const cv::Point2f &q) { 01070 std::vector<double> lineEquationParameters; 01071 double a, b, c; 01072 01073 lineEquationDeterminedByPoints(p, q, a, b, c); 01074 01075 lineEquationParameters.push_back(a); 01076 lineEquationParameters.push_back(b); 01077 lineEquationParameters.push_back(c); 01078 01079 return lineEquationParameters; 01080 } 01081 01082 //! Compute the height of the point 01083 /*! 01084 * See paper [2] for more details 01085 * 01086 * @param polygonPoint Polygon point 01087 * @param polygon The polygon representing the convex hull of the points 01088 * @param nrOfPoints Number of points defining the convex polygon 01089 * @param c Index c 01090 */ 01091 static double height(const cv::Point2f &polygonPoint, const std::vector<cv::Point2f> &polygon, 01092 unsigned int nrOfPoints, unsigned int c) { 01093 cv::Point2f pointC = polygon[c]; 01094 cv::Point2f pointCPredecessor = polygon[predecessor(c, nrOfPoints)]; 01095 01096 return distanceFromPointToLine(polygonPoint, pointC, pointCPredecessor); 01097 } 01098 01099 //! Compute the height of the point specified by the given index 01100 /*! 01101 * See paper [2] for more details 01102 * 01103 * @param polygonPointIndex Index of the polygon point 01104 * @param polygon The polygon representing the convex hull of the points 01105 * @param nrOfPoints Number of points defining the convex polygon 01106 * @param c Index c 01107 */ 01108 static double height(unsigned int polygonPointIndex, const std::vector<cv::Point2f> &polygon, 01109 unsigned int nrOfPoints, unsigned int c) { 01110 cv::Point2f pointC = polygon[c]; 01111 cv::Point2f pointCPredecessor = polygon[predecessor(c, nrOfPoints)]; 01112 01113 cv::Point2f polygonPoint = polygon[polygonPointIndex]; 01114 01115 return distanceFromPointToLine(polygonPoint, pointC, pointCPredecessor); 01116 } 01117 01118 //! Advance the given index with one position 01119 /*! 01120 * @param index Index of the point 01121 * @param nrOfPoints Number of points defining the convex polygon 01122 */ 01123 static void advance(unsigned int &index, unsigned int nrOfPoints) { 01124 index = successor(index, nrOfPoints); 01125 } 01126 01127 //! Return the succesor of the provided point index 01128 /*! 01129 * The succesor of the last polygon point is the first polygon point 01130 * (circular referencing) 01131 * 01132 * @param index Index of the point 01133 * @param nrOfPoints Number of points defining the convex polygon 01134 */ 01135 static unsigned int successor(unsigned int index, unsigned int nrOfPoints) { 01136 return ((index + 1) % nrOfPoints); 01137 } 01138 01139 //! Return the predecessor of the provided point index 01140 /*! 01141 * The predecessor of the first polygon point is the last polygon point 01142 * (circular referencing) 01143 * 01144 * @param index Index of the point 01145 * @param nrOfPoints Number of points defining the convex polygon 01146 */ 01147 static unsigned int predecessor(unsigned int index, unsigned int nrOfPoints) { 01148 return (index == 0) ? (nrOfPoints - 1) 01149 : (index - 1); 01150 } 01151 01152 //! Check if the flush edge angle/opposite angle lie between the predecessor and successor angle 01153 /*! 01154 * Check if the angle of the flush edge or its opposite angle lie between the angle of 01155 * the predecessor and successor 01156 * 01157 * @param angleFlushEdge Angle of the flush edge 01158 * @param anglePred Angle of the predecessor 01159 * @param angleSucc Angle of the successor 01160 */ 01161 static bool isFlushAngleBtwPredAndSucc(double &angleFlushEdge, double anglePred, double angleSucc) { 01162 if (isAngleBetweenNonReflex(angleFlushEdge, anglePred, angleSucc)) { 01163 return true; 01164 } else if (isOppositeAngleBetweenNonReflex(angleFlushEdge, anglePred, angleSucc)) { 01165 angleFlushEdge = oppositeAngle(angleFlushEdge); 01166 01167 return true; 01168 } 01169 01170 return false; 01171 } 01172 01173 //! Check if the angle of the line (gamma(p) p) or its opposite angle is equal to the given angle 01174 /*! 01175 * @param gammaAngle Angle of the line (gamma(p) p) 01176 * @param angle Angle to compare against 01177 */ 01178 static bool isGammaAngleEqualTo(double &gammaAngle, double angle) { 01179 return (almostEqual(gammaAngle, angle)); 01180 } 01181 01182 //! Check if the angle of the line (gamma(p) p) or its opposite angle lie between angle1 and angle2 01183 /*! 01184 * @param gammaAngle Angle of the line (gamma(p) p) 01185 * @param angle1 One of the boundary angles 01186 * @param angle2 Another boundary angle 01187 */ 01188 static bool isGammaAngleBtw(double &gammaAngle, double angle1, double angle2) { 01189 return (isAngleBetweenNonReflex(gammaAngle, angle1, angle2)); 01190 } 01191 01192 //! Get the angle of the line measured from the Ox axis in counterclockwise direction 01193 /*! 01194 * The line is specified by points "a" and "b". The value of the angle is expressed in degrees. 01195 * 01196 * @param a Point a 01197 * @param b Point b 01198 */ 01199 static double angleOfLineWrtOxAxis(const cv::Point2f &a, const cv::Point2f &b) { 01200 double y = b.y - a.y; 01201 double x = b.x - a.x; 01202 01203 double angle = (std::atan2(y, x) * 180 / CV_PI); 01204 01205 return (angle < 0) ? (angle + 360) 01206 : angle; 01207 } 01208 01209 //! Check if angle1 lies between non reflex angle determined by angles 2 and 3 01210 /*! 01211 * @param angle1 The angle which lies between angle2 and angle3 or not 01212 * @param angle2 One of the boundary angles 01213 * @param angle3 The other boundary angle 01214 */ 01215 static bool isAngleBetweenNonReflex(double angle1, double angle2, double angle3) { 01216 if (std::abs(angle2 - angle3) > 180) { 01217 if (angle2 > angle3) { 01218 return (((angle2 < angle1) && (lessOrEqual(angle1, 360))) || 01219 ((lessOrEqual(0, angle1)) && (angle1 < angle3))); 01220 } else { 01221 return (((angle3 < angle1) && (lessOrEqual(angle1, 360))) || 01222 ((lessOrEqual(0, angle1)) && (angle1 < angle2))); 01223 } 01224 } else { 01225 return isAngleBetween(angle1, angle2, angle3); 01226 } 01227 } 01228 01229 //! Check if the opposite of angle1, ((angle1 + 180) % 360), lies between non reflex angle determined by angles 2 and 3 01230 /*! 01231 * @param angle1 The angle which lies between angle2 and angle3 or not 01232 * @param angle2 One of the boundary angles 01233 * @param angle3 The other boundary angle 01234 */ 01235 static bool isOppositeAngleBetweenNonReflex(double angle1, double angle2, double angle3) { 01236 double angle1Opposite = oppositeAngle(angle1); 01237 01238 return (isAngleBetweenNonReflex(angle1Opposite, angle2, angle3)); 01239 } 01240 01241 //! Check if angle1 lies between angles 2 and 3 01242 /*! 01243 * @param angle1 The angle which lies between angle2 and angle3 or not 01244 * @param angle2 One of the boundary angles 01245 * @param angle3 The other boundary angle 01246 */ 01247 static bool isAngleBetween(double angle1, double angle2, double angle3) { 01248 if ((((int)(angle2 - angle3)) % 180) > 0) { 01249 return ((angle3 < angle1) && (angle1 < angle2)); 01250 } else { 01251 return ((angle2 < angle1) && (angle1 < angle3)); 01252 } 01253 } 01254 01255 //! Return the angle opposite to the given angle 01256 /*! 01257 * if (angle < 180) then 01258 * return (angle + 180); 01259 * else 01260 * return (angle - 180); 01261 * endif 01262 * 01263 * @param angle Angle 01264 */ 01265 static double oppositeAngle(double angle) { 01266 return (angle > 180) ? (angle - 180) 01267 : (angle + 180); 01268 } 01269 01270 //! Compute the distance from a point "a" to a line specified by two points "B" and "C" 01271 /*! 01272 * Formula used: 01273 * 01274 * |(x_c - x_b) * (y_b - y_a) - (x_b - x_a) * (y_c - y_b)| 01275 * d = ------------------------------------------------------- 01276 * sqrt(((x_c - x_b)^2) + ((y_c - y_b)^2)) 01277 * 01278 * Reference: http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html 01279 * (Last access: 15.09.2013) 01280 * 01281 * @param a Point from which the distance is measures 01282 * @param linePointB One of the points determining the line 01283 * @param linePointC One of the points determining the line 01284 */ 01285 static double distanceFromPointToLine(const cv::Point2f &a, const cv::Point2f &linePointB, 01286 const cv::Point2f &linePointC) { 01287 double term1 = linePointC.x - linePointB.x; 01288 double term2 = linePointB.y - a.y; 01289 double term3 = linePointB.x - a.x; 01290 double term4 = linePointC.y - linePointB.y; 01291 01292 double nominator = std::abs((term1 * term2) - (term3 * term4)); 01293 double denominator = std::sqrt((term1 * term1) + (term4 * term4)); 01294 01295 return (denominator != 0) ? (nominator / denominator) 01296 : 0; 01297 } 01298 01299 //! Compute the distance between two points 01300 /*! Compute the Euclidean distance between two points 01301 * 01302 * @param a Point a 01303 * @param b Point b 01304 */ 01305 static double distanceBtwPoints(const cv::Point2f &a, const cv::Point2f &b) { 01306 double xDiff = a.x - b.x; 01307 double yDiff = a.y - b.y; 01308 01309 return std::sqrt((xDiff * xDiff) + (yDiff * yDiff)); 01310 } 01311 01312 //! Compute the area of a triangle defined by three points 01313 /*! 01314 * The area is computed using the determinant method. 01315 * An example is depicted at http://demonstrations.wolfram.com/TheAreaOfATriangleUsingADeterminant/ 01316 * (Last access: 15.09.2013) 01317 * 01318 * @param a Point a 01319 * @param b Point b 01320 * @param c Point c 01321 */ 01322 static double areaOfTriangle(const cv::Point2f &a, const cv::Point2f &b, const cv::Point2f &c) { 01323 double posTerm = (a.x * b.y) + (a.y * c.x) + (b.x * c.y); 01324 double negTerm = (b.y * c.x) + (a.x * c.y) + (a.y * b.x); 01325 01326 double determinant = posTerm - negTerm; 01327 01328 return std::abs(determinant) / 2; 01329 } 01330 01331 //! Get the point in the middle of the segment determined by points "a" and "b" 01332 /*! 01333 * @param a Point a 01334 * @param b Point b 01335 */ 01336 static cv::Point2f middlePoint(const cv::Point2f &a, const cv::Point2f &b) { 01337 double middleX = static_cast<double>((a.x + b.x) / 2); 01338 double middleY = static_cast<double>((a.y + b.y) / 2); 01339 01340 return cv::Point2f (static_cast<float>(middleX), static_cast<float>(middleY)); 01341 } 01342 01343 //! Determine the intersection point of two lines, if this point exists 01344 /*! Two lines intersect if they are not parallel (Parallel lines intersect at 01345 * +/- infinity, but we do not consider this case here). 01346 * 01347 * The lines are specified in the following form: 01348 * A1x + B1x = C1 01349 * A2x + B2x = C2 01350 * 01351 * If det (= A1*B2 - A2*B1) == 0, then lines are parallel 01352 * else they intersect 01353 * 01354 * If they intersect, then let us denote the intersection point with P(x, y) where: 01355 * x = (C1*B2 - C2*B1) / (det) 01356 * y = (C2*A1 - C1*A2) / (det) 01357 * 01358 * @param a1 A1 01359 * @param b1 B1 01360 * @param c1 C1 01361 * @param a2 A2 01362 * @param b2 B2 01363 * @param c2 C2 01364 * @param intersection The intersection point, if this point exists 01365 */ 01366 static bool lineIntersection(double a1, double b1, double c1, double a2, double b2, double c2, 01367 cv::Point2f &intersection) { 01368 double det = (a1 * b2) - (a2 * b1); 01369 01370 if (!(almostEqual(det, 0))) { 01371 intersection.x = static_cast<float>(((c1 * b2) - (c2 * b1)) / (det)); 01372 intersection.y = static_cast<float>(((c2 * a1) - (c1 * a2)) / (det)); 01373 01374 return true; 01375 } 01376 01377 return false; 01378 } 01379 01380 //! Determine the intersection point of two lines, if this point exists 01381 /*! Two lines intersect if they are not parallel (Parallel lines intersect at 01382 * +/- infinity, but we do not consider this case here). 01383 * 01384 * The lines are specified by a pair of points each. If they intersect, then 01385 * the function returns true, else it returns false. 01386 * 01387 * Lines can be specified in the following form: 01388 * A1x + B1x = C1 01389 * A2x + B2x = C2 01390 * 01391 * If det (= A1*B2 - A2*B1) == 0, then lines are parallel 01392 * else they intersect 01393 * 01394 * If they intersect, then let us denote the intersection point with P(x, y) where: 01395 * x = (C1*B2 - C2*B1) / (det) 01396 * y = (C2*A1 - C1*A2) / (det) 01397 * 01398 * @param a1 First point for determining the first line 01399 * @param b1 Second point for determining the first line 01400 * @param a2 First point for determining the second line 01401 * @param b2 Second point for determining the second line 01402 * @param intersection The intersection point, if this point exists 01403 */ 01404 static bool lineIntersection(const cv::Point2f &a1, const cv::Point2f &b1, const cv::Point2f &a2, 01405 const cv::Point2f &b2, cv::Point2f &intersection) { 01406 double A1 = b1.y - a1.y; 01407 double B1 = a1.x - b1.x; 01408 double C1 = (a1.x * A1) + (a1.y * B1); 01409 01410 double A2 = b2.y - a2.y; 01411 double B2 = a2.x - b2.x; 01412 double C2 = (a2.x * A2) + (a2.y * B2); 01413 01414 double det = (A1 * B2) - (A2 * B1); 01415 01416 if (!almostEqual(det, 0)) { 01417 intersection.x = static_cast<float>(((C1 * B2) - (C2 * B1)) / (det)); 01418 intersection.y = static_cast<float>(((C2 * A1) - (C1 * A2)) / (det)); 01419 01420 return true; 01421 } 01422 01423 return false; 01424 } 01425 01426 //! Get the values of "a", "b" and "c" of the line equation ax + by + c = 0 knowing that point "p" and "q" are on the line 01427 /*! 01428 * a = q.y - p.y 01429 * b = p.x - q.x 01430 * c = - (p.x * a) - (p.y * b) 01431 * 01432 * @param p Point p 01433 * @param q Point q 01434 * @param a Parameter "a" from the line equation 01435 * @param b Parameter "b" from the line equation 01436 * @param c Parameter "c" from the line equation 01437 */ 01438 static void lineEquationDeterminedByPoints(const cv::Point2f &p, const cv::Point2f &q, 01439 double &a, double &b, double &c) { 01440 CV_Assert(areEqualPoints(p, q) == false); 01441 01442 a = q.y - p.y; 01443 b = p.x - q.x; 01444 c = ((-p.y) * b) - (p.x * a); 01445 } 01446 01447 //! Check if p1 and p2 are on the same side of the line determined by points a and b 01448 /*! 01449 * @param p1 Point p1 01450 * @param p2 Point p2 01451 * @param a First point for determining line 01452 * @param b Second point for determining line 01453 */ 01454 static bool areOnTheSameSideOfLine(const cv::Point2f &p1, const cv::Point2f &p2, 01455 const cv::Point2f &a, const cv::Point2f &b) { 01456 double a1, b1, c1; 01457 01458 lineEquationDeterminedByPoints(a, b, a1, b1, c1); 01459 01460 double p1OnLine = (a1 * p1.x) + (b1 * p1.y) + c1; 01461 double p2OnLine = (a1 * p2.x) + (b1 * p2.y) + c1; 01462 01463 return (sign(p1OnLine) == sign(p2OnLine)); 01464 } 01465 01466 //! Check if one point lies between two other points 01467 /*! 01468 * @param point Point lying possibly outside the line segment 01469 * @param lineSegmentStart First point determining the line segment 01470 * @param lineSegmentEnd Second point determining the line segment 01471 */ 01472 static bool isPointOnLineSegment(const cv::Point2f &point, const cv::Point2f &lineSegmentStart, 01473 const cv::Point2f &lineSegmentEnd) { 01474 double d1 = distanceBtwPoints(point, lineSegmentStart); 01475 double d2 = distanceBtwPoints(point, lineSegmentEnd); 01476 double lineSegmentLength = distanceBtwPoints(lineSegmentStart, lineSegmentEnd); 01477 01478 return (almostEqual(d1 + d2, lineSegmentLength)); 01479 } 01480 01481 //! Check if two lines are identical 01482 /*! 01483 * Lines are be specified in the following form: 01484 * A1x + B1x = C1 01485 * A2x + B2x = C2 01486 * 01487 * If (A1/A2) == (B1/B2) == (C1/C2), then the lines are identical 01488 * else they are not 01489 * 01490 * @param a1 A1 01491 * @param b1 B1 01492 * @param c1 C1 01493 * @param a2 A2 01494 * @param b2 B2 01495 * @param c2 C2 01496 */ 01497 static bool areIdenticalLines(double a1, double b1, double c1, double a2, double b2, double c2) { 01498 double a1B2 = a1 * b2; 01499 double a2B1 = a2 * b1; 01500 double a1C2 = a1 * c2; 01501 double a2C1 = a2 * c1; 01502 double b1C2 = b1 * c2; 01503 double b2C1 = b2 * c1; 01504 01505 return ((almostEqual(a1B2, a2B1)) && (almostEqual(b1C2, b2C1)) && (almostEqual(a1C2, a2C1))); 01506 } 01507 01508 //! Check if points point1 and point2 are equal or not 01509 /*! 01510 * @param point1 One point 01511 * @param point2 The other point 01512 */ 01513 static bool areEqualPoints(const cv::Point2f &point1, const cv::Point2f &point2) { 01514 return (almostEqual(point1.x, point2.x) && almostEqual(point1.y, point2.y)); 01515 } 01516 01517 //! Return the sign of the number 01518 /*! 01519 * The sign function returns: 01520 * -1, if number < 0 01521 * +1, if number > 0 01522 * 0, otherwise 01523 */ 01524 static int sign(double number) { 01525 return (number > 0) ? 1 : ((number < 0) ? -1 : 0); 01526 } 01527 01528 //! Return the maximum of the provided numbers 01529 static double maximum(double number1, double number2, double number3) { 01530 return std::max(std::max(number1, number2), number3); 01531 } 01532 01533 //! Check if the two numbers are equal (almost) 01534 /*! 01535 * The expression for determining if two real numbers are equal is: 01536 * if (Abs(x - y) <= EPSILON * Max(1.0f, Abs(x), Abs(y))). 01537 * 01538 * @param number1 First number 01539 * @param number2 Second number 01540 */ 01541 static bool almostEqual(double number1, double number2) { 01542 return (std::abs(number1 - number2) <= (EPSILON * maximum(1.0, std::abs(number1), std::abs(number2)))); 01543 } 01544 01545 //! Check if the first number is greater than or equal to the second number 01546 /*! 01547 * @param number1 First number 01548 * @param number2 Second number 01549 */ 01550 static bool greaterOrEqual(double number1, double number2) { 01551 return ((number1 > number2) || (almostEqual(number1, number2))); 01552 } 01553 01554 //! Check if the first number is less than or equal to the second number 01555 /*! 01556 * @param number1 First number 01557 * @param number2 Second number 01558 */ 01559 static bool lessOrEqual(double number1, double number2) { 01560 return ((number1 < number2) || (almostEqual(number1, number2))); 01561 } 01562 01563 } 01564
Generated on Tue Jul 12 2022 14:47:27 by
1.7.2