1 /*M/////////////////////////////////////////////////////////////////////////////////////// 2 // 3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4 // 5 // By downloading, copying, installing or using the software you agree to this license. 6 // If you do not agree to this license, do not download, install, 7 // copy or use the software. 8 // 9 // 10 // Intel License Agreement 11 // For Open Source Computer Vision Library 12 // 13 // Copyright (C) 2000, Intel Corporation, all rights reserved. 14 // Third party copyrights are property of their respective owners. 15 // 16 // Redistribution and use in source and binary forms, with or without modification, 17 // are permitted provided that the following conditions are met: 18 // 19 // * Redistribution's of source code must retain the above copyright notice, 20 // this list of conditions and the following disclaimer. 21 // 22 // * Redistribution's in binary form must reproduce the above copyright notice, 23 // this list of conditions and the following disclaimer in the documentation 24 // and/or other materials provided with the distribution. 25 // 26 // * The name of Intel Corporation may not be used to endorse or promote products 27 // derived from this software without specific prior written permission. 28 // 29 // This software is provided by the copyright holders and contributors "as is" and 30 // any express or implied warranties, including, but not limited to, the implied 31 // warranties of merchantability and fitness for a particular purpose are disclaimed. 32 // In no event shall the Intel Corporation or contributors be liable for any direct, 33 // indirect, incidental, special, exemplary, or consequential damages 34 // (including, but not limited to, procurement of substitute goods or services; 35 // loss of use, data, or profits; or business interruption) however caused 36 // and on any theory of liability, whether in contract, strict liability, 37 // or tort (including negligence or otherwise) arising in any way out of 38 // the use of this software, even if advised of the possibility of such damage. 39 // 40 //M*/ 41 42 #include "_cvaux.h" 43 44 #if 0 45 46 #include <malloc.h> 47 //#include "decomppoly.h" 48 49 #define ZERO_CLOSE 0.00001f 50 #define ONE_CLOSE 0.99999f 51 52 #define CHECK_COLLINEARITY(vec1_x,vec1_y,vec2_x,vec2_y) \ 53 if( vec1_x == 0 ) { \ 54 if( vec1_y * vec2_y > 0 ) { \ 55 return 0; \ 56 } \ 57 } \ 58 else { \ 59 if( vec1_x * vec2_x > 0 ) { \ 60 return 0; \ 61 } \ 62 } 63 64 // determines if edge number one lies in counterclockwise 65 // earlier than edge number two 66 inline int icvIsFirstEdgeClosier( int x0, 67 int y0, 68 int x0_end, 69 int y0_end, 70 int x1_end, 71 int y1_end, 72 int x2_end, 73 int y2_end ) 74 { 75 int mult, mult1, mult2; 76 int vec0_x, vec0_y; 77 int vec1_x, vec1_y; 78 int vec2_x, vec2_y; 79 80 vec0_x = x0_end - x0; 81 vec0_y = y0_end - y0; 82 vec1_x = x1_end - x0; 83 vec1_y = y1_end - y0; 84 vec2_x = x2_end - x0; 85 vec2_y = y2_end - y0; 86 87 mult1 = vec1_x * vec0_y - vec0_x * vec1_y; 88 mult2 = vec2_x * vec0_y - vec0_x * vec2_y; 89 90 if( mult1 == 0 ) { 91 CHECK_COLLINEARITY( vec0_x, vec0_y, vec1_x, vec1_y ); 92 } 93 if( mult2 == 0 ) { 94 CHECK_COLLINEARITY( vec0_x, vec0_y, vec2_x, vec2_y ); 95 } 96 if( mult1 > 0 && mult2 < 0 ) { 97 return 1; 98 } 99 if( mult1 < 0 && mult2 > 0 ) { 100 return -1; 101 } 102 103 mult = vec1_x * vec2_y - vec2_x * vec1_y; 104 if( mult == 0 ) { 105 CHECK_COLLINEARITY( vec1_x, vec1_y, vec2_x, vec2_y ); 106 } 107 108 if( mult1 > 0 ) 109 { 110 if( mult > 0 ) { 111 return -1; 112 } 113 else { 114 return 1; 115 } 116 } // if( mult1 > 0 ) 117 else 118 { 119 if( mult1 != 0 ) { 120 if( mult > 0 ) { 121 return 1; 122 } 123 else { 124 return -1; 125 } 126 } // if( mult1 != 0 ) 127 else { 128 if( mult2 > 0 ) { 129 return -1; 130 } 131 else { 132 return 1; 133 } 134 } // if( mult1 != 0 ) else 135 136 } // if( mult1 > 0 ) else 137 138 } // icvIsFirstEdgeClosier 139 140 bool icvEarCutTriangulation( CvPoint* contour, 141 int num, 142 int* outEdges, 143 int* numEdges ) 144 { 145 int i; 146 int notFoundFlag = 0; 147 int begIndex = -1; 148 int isInternal; 149 int currentNum = num; 150 int index1, index2, index3; 151 int ix0, iy0, ix1, iy1, ix2, iy2; 152 int x1, y1, x2, y2, x3, y3; 153 int dx1, dy1, dx2, dy2; 154 int* pointExist = ( int* )0; 155 int det, det1, det2; 156 float t1, t2; 157 158 (*numEdges) = 0; 159 160 if( num <= 2 ) { 161 return false; 162 } 163 164 pointExist = ( int* )malloc( num * sizeof( int ) ); 165 166 for( i = 0; i < num; i ++ ) { 167 pointExist[i] = 1; 168 } 169 170 for( i = 0; i < num; i ++ ) { 171 outEdges[ (*numEdges) * 2 ] = i; 172 if( i != num - 1 ) { 173 outEdges[ (*numEdges) * 2 + 1 ] = i + 1; 174 } 175 else { 176 outEdges[ (*numEdges) * 2 + 1 ] = 0; 177 } 178 (*numEdges) ++; 179 } // for( i = 0; i < num; i ++ ) 180 181 // initializing data before while cycle 182 index1 = 0; 183 index2 = 1; 184 index3 = 2; 185 x1 = contour[ index1 ].x; 186 y1 = contour[ index1 ].y; 187 x2 = contour[ index2 ].x; 188 y2 = contour[ index2 ].y; 189 x3 = contour[ index3 ].x; 190 y3 = contour[ index3 ].y; 191 192 while( currentNum > 3 ) 193 { 194 dx1 = x2 - x1; 195 dy1 = y2 - y1; 196 dx2 = x3 - x2; 197 dy2 = y3 - y2; 198 if( dx1 * dy2 - dx2 * dy1 < 0 ) // convex condition 199 { 200 // checking for noncrossing edge 201 ix1 = x3 - x1; 202 iy1 = y3 - y1; 203 isInternal = 1; 204 for( i = 0; i < num; i ++ ) 205 { 206 if( i != num - 1 ) { 207 ix2 = contour[ i + 1 ].x - contour[ i ].x; 208 iy2 = contour[ i + 1 ].y - contour[ i ].y; 209 } 210 else { 211 ix2 = contour[ 0 ].x - contour[ i ].x; 212 iy2 = contour[ 0 ].y - contour[ i ].y; 213 } 214 ix0 = contour[ i ].x - x1; 215 iy0 = contour[ i ].y - y1; 216 217 det = ix2 * iy1 - ix1 * iy2; 218 det1 = ix2 * iy0 - ix0 * iy2; 219 if( det != 0.0f ) 220 { 221 t1 = ( ( float )( det1 ) ) / det; 222 if( t1 > ZERO_CLOSE && t1 < ONE_CLOSE ) 223 { 224 det2 = ix1 * iy0 - ix0 * iy1; 225 t2 = ( ( float )( det2 ) ) / det; 226 if( t2 > ZERO_CLOSE && t2 < ONE_CLOSE ) { 227 isInternal = 0; 228 } 229 230 } // if( t1 > ZERO_CLOSE && t1 < ONE_CLOSE ) 231 232 } // if( det != 0.0f ) 233 234 } // for( i = 0; i < (*numEdges); i ++ ) 235 236 if( isInternal ) 237 { 238 // this edge is internal 239 notFoundFlag = 0; 240 outEdges[ (*numEdges) * 2 ] = index1; 241 outEdges[ (*numEdges) * 2 + 1 ] = index3; 242 (*numEdges) ++; 243 pointExist[ index2 ] = 0; 244 index2 = index3; 245 x2 = x3; 246 y2 = y3; 247 currentNum --; 248 if( currentNum >= 3 ) { 249 do { 250 index3 ++; 251 if( index3 == num ) { 252 index3 = 0; 253 } 254 } while( !pointExist[ index3 ] ); 255 x3 = contour[ index3 ].x; 256 y3 = contour[ index3 ].y; 257 } // if( currentNum >= 3 ) 258 259 } // if( isInternal ) 260 else { 261 // this edge intersects some other initial edges 262 if( !notFoundFlag ) { 263 notFoundFlag = 1; 264 begIndex = index1; 265 } 266 index1 = index2; 267 x1 = x2; 268 y1 = y2; 269 index2 = index3; 270 x2 = x3; 271 y2 = y3; 272 do { 273 index3 ++; 274 if( index3 == num ) { 275 index3 = 0; 276 } 277 if( index3 == begIndex ) { 278 if( pointExist ) { 279 free( pointExist ); 280 } 281 return false; 282 } 283 } while( !pointExist[ index3 ] ); 284 x3 = contour[ index3 ].x; 285 y3 = contour[ index3 ].y; 286 } // if( isInternal ) else 287 288 } // if( dx1 * dy2 - dx2 * dy1 < 0 ) 289 else 290 { 291 if( !notFoundFlag ) { 292 notFoundFlag = 1; 293 begIndex = index1; 294 } 295 index1 = index2; 296 x1 = x2; 297 y1 = y2; 298 index2 = index3; 299 x2 = x3; 300 y2 = y3; 301 do { 302 index3 ++; 303 if( index3 == num ) { 304 index3 = 0; 305 } 306 if( index3 == begIndex ) { 307 if( pointExist ) { 308 free( pointExist ); 309 } 310 return false; 311 } 312 } while( !pointExist[ index3 ] ); 313 x3 = contour[ index3 ].x; 314 y3 = contour[ index3 ].y; 315 } // if( dx1 * dy2 - dx2 * dy1 < 0 ) else 316 317 } // while( currentNum > 3 ) 318 319 if( pointExist ) { 320 free( pointExist ); 321 } 322 323 return true; 324 325 } // icvEarCutTriangulation 326 327 inline bool icvFindTwoNeighbourEdges( CvPoint* contour, 328 int* edges, 329 int numEdges, 330 int vtxIdx, 331 int mainEdgeIdx, 332 int* leftEdgeIdx, 333 int* rightEdgeIdx ) 334 { 335 int i; 336 int compRes; 337 int vec0_x, vec0_y; 338 int x0, y0, x0_end, y0_end; 339 int x1_left = 0, y1_left = 0, x1_right = 0, y1_right = 0, x2, y2; 340 341 (*leftEdgeIdx) = -1; 342 (*rightEdgeIdx) = -1; 343 344 if( edges[ mainEdgeIdx * 2 ] == vtxIdx ) { 345 x0 = contour[ vtxIdx ].x; 346 y0 = contour[ vtxIdx ].y; 347 x0_end = contour[ edges[ mainEdgeIdx * 2 + 1 ] ].x; 348 y0_end = contour[ edges[ mainEdgeIdx * 2 + 1 ] ].y; 349 vec0_x = x0_end - x0; 350 vec0_y = y0_end - y0; 351 } 352 else { 353 //x0 = contour[ edges[ mainEdgeIdx * 2 ] ].x; 354 //y0 = contour[ edges[ mainEdgeIdx * 2 ] ].y; 355 //x0_end = contour[ vtxIdx ].x; 356 //y0_end = contour[ vtxIdx ].y; 357 x0 = contour[ vtxIdx ].x; 358 y0 = contour[ vtxIdx ].y; 359 x0_end = contour[ edges[ mainEdgeIdx * 2 ] ].x; 360 y0_end = contour[ edges[ mainEdgeIdx * 2 ] ].y; 361 vec0_x = x0_end - x0; 362 vec0_y = y0_end - y0; 363 } 364 365 for( i = 0; i < numEdges; i ++ ) 366 { 367 if( ( i != mainEdgeIdx ) && 368 ( edges[ i * 2 ] == vtxIdx || edges[ i * 2 + 1 ] == vtxIdx ) ) 369 { 370 if( (*leftEdgeIdx) == -1 ) 371 { 372 (*leftEdgeIdx) = (*rightEdgeIdx) = i; 373 if( edges[ i * 2 ] == vtxIdx ) { 374 x1_left = x1_right = contour[ edges[ i * 2 + 1 ] ].x; 375 y1_left = y1_right = contour[ edges[ i * 2 + 1 ] ].y; 376 } 377 else { 378 x1_left = x1_right = contour[ edges[ i * 2 ] ].x; 379 y1_left = y1_right = contour[ edges[ i * 2 ] ].y; 380 } 381 382 } // if( (*leftEdgeIdx) == -1 ) 383 else 384 { 385 if( edges[ i * 2 ] == vtxIdx ) { 386 x2 = contour[ edges[ i * 2 + 1 ] ].x; 387 y2 = contour[ edges[ i * 2 + 1 ] ].y; 388 } 389 else { 390 x2 = contour[ edges[ i * 2 ] ].x; 391 y2 = contour[ edges[ i * 2 ] ].y; 392 } 393 394 compRes = icvIsFirstEdgeClosier( x0, 395 y0, x0_end, y0_end, x1_left, y1_left, x2, y2 ); 396 if( compRes == 0 ) { 397 return false; 398 } 399 if( compRes == -1 ) { 400 (*leftEdgeIdx) = i; 401 x1_left = x2; 402 y1_left = y2; 403 } // if( compRes == -1 ) 404 else { 405 compRes = icvIsFirstEdgeClosier( x0, 406 y0, x0_end, y0_end, x1_right, y1_right, x2, y2 ); 407 if( compRes == 0 ) { 408 return false; 409 } 410 if( compRes == 1 ) { 411 (*rightEdgeIdx) = i; 412 x1_right = x2; 413 y1_right = y2; 414 } 415 416 } // if( compRes == -1 ) else 417 418 } // if( (*leftEdgeIdx) == -1 ) else 419 420 } // if( ( i != mainEdgesIdx ) && ... 421 422 } // for( i = 0; i < numEdges; i ++ ) 423 424 return true; 425 426 } // icvFindTwoNeighbourEdges 427 428 bool icvFindReferences( CvPoint* contour, 429 int num, 430 int* outEdges, 431 int* refer, 432 int* numEdges ) 433 { 434 int i; 435 int currPntIdx; 436 int leftEdgeIdx, rightEdgeIdx; 437 438 if( icvEarCutTriangulation( contour, num, outEdges, numEdges ) ) 439 { 440 for( i = 0; i < (*numEdges); i ++ ) 441 { 442 refer[ i * 4 ] = -1; 443 refer[ i * 4 + 1 ] = -1; 444 refer[ i * 4 + 2 ] = -1; 445 refer[ i * 4 + 3 ] = -1; 446 } // for( i = 0; i < (*numEdges); i ++ ) 447 448 for( i = 0; i < (*numEdges); i ++ ) 449 { 450 currPntIdx = outEdges[ i * 2 ]; 451 if( !icvFindTwoNeighbourEdges( contour, 452 outEdges, (*numEdges), currPntIdx, 453 i, &leftEdgeIdx, &rightEdgeIdx ) ) 454 { 455 return false; 456 } // if( !icvFindTwoNeighbourEdges( contour, ... 457 else 458 { 459 if( outEdges[ leftEdgeIdx * 2 ] == currPntIdx ) { 460 if( refer[ i * 4 ] == -1 ) { 461 refer[ i * 4 ] = ( leftEdgeIdx << 2 ); 462 } 463 } 464 else { 465 if( refer[ i * 4 ] == -1 ) { 466 refer[ i * 4 ] = ( leftEdgeIdx << 2 ) | 2; 467 } 468 } 469 if( outEdges[ rightEdgeIdx * 2 ] == currPntIdx ) { 470 if( refer[ i * 4 + 1 ] == -1 ) { 471 refer[ i * 4 + 1 ] = ( rightEdgeIdx << 2 ) | 3; 472 } 473 } 474 else { 475 if( refer[ i * 4 + 1 ] == -1 ) { 476 refer[ i * 4 + 1 ] = ( rightEdgeIdx << 2 ) | 1; 477 } 478 } 479 480 } // if( !icvFindTwoNeighbourEdges( contour, ... ) else 481 482 currPntIdx = outEdges[ i * 2 + 1 ]; 483 if( i == 18 ) { 484 i = i; 485 } 486 if( !icvFindTwoNeighbourEdges( contour, 487 outEdges, (*numEdges), currPntIdx, 488 i, &leftEdgeIdx, &rightEdgeIdx ) ) 489 { 490 return false; 491 } // if( !icvFindTwoNeighbourEdges( contour, ... 492 else 493 { 494 if( outEdges[ leftEdgeIdx * 2 ] == currPntIdx ) { 495 if( refer[ i * 4 + 3 ] == -1 ) { 496 refer[ i * 4 + 3 ] = ( leftEdgeIdx << 2 ); 497 } 498 } 499 else { 500 if( refer[ i * 4 + 3 ] == -1 ) { 501 refer[ i * 4 + 3 ] = ( leftEdgeIdx << 2 ) | 2; 502 } 503 } 504 if( outEdges[ rightEdgeIdx * 2 ] == currPntIdx ) { 505 if( refer[ i * 4 + 2 ] == -1 ) { 506 refer[ i * 4 + 2 ] = ( rightEdgeIdx << 2 ) | 3; 507 } 508 } 509 else { 510 if( refer[ i * 4 + 2 ] == -1 ) { 511 refer[ i * 4 + 2 ] = ( rightEdgeIdx << 2 ) | 1; 512 } 513 } 514 515 } // if( !icvFindTwoNeighbourEdges( contour, ... ) else 516 517 } // for( i = 0; i < (*numEdges); i ++ ) 518 519 } // if( icvEarCutTriangulation( contour, num, outEdges, numEdges ) ) 520 else { 521 return false; 522 } // if( icvEarCutTriangulation( contour, num, outEdges, ... ) else 523 524 return true; 525 526 } // icvFindReferences 527 528 void cvDecompPoly( CvContour* cont, 529 CvSubdiv2D** subdiv, 530 CvMemStorage* storage ) 531 { 532 int* memory; 533 CvPoint* contour; 534 int* outEdges; 535 int* refer; 536 CvSubdiv2DPoint** pntsPtrs; 537 CvQuadEdge2D** edgesPtrs; 538 int numVtx; 539 int numEdges; 540 int i; 541 CvSeqReader reader; 542 CvPoint2D32f pnt; 543 CvQuadEdge2D* quadEdge; 544 545 numVtx = cont -> total; 546 if( numVtx < 3 ) { 547 return; 548 } 549 550 *subdiv = ( CvSubdiv2D* )0; 551 552 memory = ( int* )malloc( sizeof( int ) * ( numVtx * 2 553 + numVtx * numVtx * 2 * 5 ) 554 + sizeof( CvQuadEdge2D* ) * ( numVtx * numVtx ) 555 + sizeof( CvSubdiv2DPoint* ) * ( numVtx * 2 ) ); 556 contour = ( CvPoint* )memory; 557 outEdges = ( int* )( contour + numVtx ); 558 refer = outEdges + numVtx * numVtx * 2; 559 edgesPtrs = ( CvQuadEdge2D** )( refer + numVtx * numVtx * 4 ); 560 pntsPtrs = ( CvSubdiv2DPoint** )( edgesPtrs + numVtx * numVtx ); 561 562 cvStartReadSeq( ( CvSeq* )cont, &reader, 0 ); 563 for( i = 0; i < numVtx; i ++ ) 564 { 565 CV_READ_SEQ_ELEM( (contour[ i ]), reader ); 566 } // for( i = 0; i < numVtx; i ++ ) 567 568 if( !icvFindReferences( contour, numVtx, outEdges, refer, &numEdges ) ) 569 { 570 free( memory ); 571 return; 572 } // if( !icvFindReferences( contour, numVtx, outEdges, refer, ... 573 574 *subdiv = cvCreateSubdiv2D( CV_SEQ_KIND_SUBDIV2D, 575 sizeof( CvSubdiv2D ), 576 sizeof( CvSubdiv2DPoint ), 577 sizeof( CvQuadEdge2D ), 578 storage ); 579 580 for( i = 0; i < numVtx; i ++ ) 581 { 582 pnt.x = ( float )contour[ i ].x; 583 pnt.y = ( float )contour[ i ].y; 584 pntsPtrs[ i ] = cvSubdiv2DAddPoint( *subdiv, pnt, 0 ); 585 } // for( i = 0; i < numVtx; i ++ ) 586 587 for( i = 0; i < numEdges; i ++ ) 588 { 589 edgesPtrs[ i ] = ( CvQuadEdge2D* ) 590 ( cvSubdiv2DMakeEdge( *subdiv ) & 0xfffffffc ); 591 } // for( i = 0; i < numEdges; i ++ ) 592 593 for( i = 0; i < numEdges; i ++ ) 594 { 595 quadEdge = edgesPtrs[ i ]; 596 quadEdge -> next[ 0 ] = 597 ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 ] >> 2 ] ) 598 | ( refer[ i * 4 ] & 3 ); 599 quadEdge -> next[ 1 ] = 600 ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 + 1 ] >> 2 ] ) 601 | ( refer[ i * 4 + 1 ] & 3 ); 602 quadEdge -> next[ 2 ] = 603 ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 + 2 ] >> 2 ] ) 604 | ( refer[ i * 4 + 2 ] & 3 ); 605 quadEdge -> next[ 3 ] = 606 ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 + 3 ] >> 2 ] ) 607 | ( refer[ i * 4 + 3 ] & 3 ); 608 quadEdge -> pt[ 0 ] = pntsPtrs[ outEdges[ i * 2 ] ]; 609 quadEdge -> pt[ 1 ] = ( CvSubdiv2DPoint* )0; 610 quadEdge -> pt[ 2 ] = pntsPtrs[ outEdges[ i * 2 + 1 ] ]; 611 quadEdge -> pt[ 3 ] = ( CvSubdiv2DPoint* )0; 612 } // for( i = 0; i < numEdges; i ++ ) 613 614 (*subdiv) -> topleft.x = ( float )cont -> rect.x; 615 (*subdiv) -> topleft.y = ( float )cont -> rect.y; 616 (*subdiv) -> bottomright.x = 617 ( float )( cont -> rect.x + cont -> rect.width ); 618 (*subdiv) -> bottomright.y = 619 ( float )( cont -> rect.y + cont -> rect.height ); 620 621 free( memory ); 622 return; 623 624 } // cvDecompPoly 625 626 #endif 627 628 // End of file decomppoly.cpp 629 630