1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
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.
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.
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.
47 //#include "decomppoly.h"
49 #define ZERO_CLOSE 0.00001f
50 #define ONE_CLOSE 0.99999f
52 #define CHECK_COLLINEARITY(vec1_x,vec1_y,vec2_x,vec2_y) \
54 if( vec1_y * vec2_y > 0 ) { \
59 if( vec1_x * vec2_x > 0 ) { \
64 // determines if edge number one lies in counterclockwise
65 // earlier than edge number two
66 inline int icvIsFirstEdgeClosier( int x0,
75 int mult, mult1, mult2;
87 mult1 = vec1_x * vec0_y - vec0_x * vec1_y;
88 mult2 = vec2_x * vec0_y - vec0_x * vec2_y;
91 CHECK_COLLINEARITY( vec0_x, vec0_y, vec1_x, vec1_y );
94 CHECK_COLLINEARITY( vec0_x, vec0_y, vec2_x, vec2_y );
96 if( mult1 > 0 && mult2 < 0 ) {
99 if( mult1 < 0 && mult2 > 0 ) {
103 mult = vec1_x * vec2_y - vec2_x * vec1_y;
105 CHECK_COLLINEARITY( vec1_x, vec1_y, vec2_x, vec2_y );
126 } // if( mult1 != 0 )
134 } // if( mult1 != 0 ) else
136 } // if( mult1 > 0 ) else
138 } // icvIsFirstEdgeClosier
140 bool icvEarCutTriangulation( CvPoint* contour,
146 int notFoundFlag = 0;
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;
164 pointExist = ( int* )malloc( num * sizeof( int ) );
166 for( i = 0; i < num; i ++ ) {
170 for( i = 0; i < num; i ++ ) {
171 outEdges[ (*numEdges) * 2 ] = i;
173 outEdges[ (*numEdges) * 2 + 1 ] = i + 1;
176 outEdges[ (*numEdges) * 2 + 1 ] = 0;
179 } // for( i = 0; i < num; i ++ )
181 // initializing data before while cycle
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;
192 while( currentNum > 3 )
198 if( dx1 * dy2 - dx2 * dy1 < 0 ) // convex condition
200 // checking for noncrossing edge
204 for( i = 0; i < num; i ++ )
207 ix2 = contour[ i + 1 ].x - contour[ i ].x;
208 iy2 = contour[ i + 1 ].y - contour[ i ].y;
211 ix2 = contour[ 0 ].x - contour[ i ].x;
212 iy2 = contour[ 0 ].y - contour[ i ].y;
214 ix0 = contour[ i ].x - x1;
215 iy0 = contour[ i ].y - y1;
217 det = ix2 * iy1 - ix1 * iy2;
218 det1 = ix2 * iy0 - ix0 * iy2;
221 t1 = ( ( float )( det1 ) ) / det;
222 if( t1 > ZERO_CLOSE && t1 < ONE_CLOSE )
224 det2 = ix1 * iy0 - ix0 * iy1;
225 t2 = ( ( float )( det2 ) ) / det;
226 if( t2 > ZERO_CLOSE && t2 < ONE_CLOSE ) {
230 } // if( t1 > ZERO_CLOSE && t1 < ONE_CLOSE )
232 } // if( det != 0.0f )
234 } // for( i = 0; i < (*numEdges); i ++ )
238 // this edge is internal
240 outEdges[ (*numEdges) * 2 ] = index1;
241 outEdges[ (*numEdges) * 2 + 1 ] = index3;
243 pointExist[ index2 ] = 0;
248 if( currentNum >= 3 ) {
251 if( index3 == num ) {
254 } while( !pointExist[ index3 ] );
255 x3 = contour[ index3 ].x;
256 y3 = contour[ index3 ].y;
257 } // if( currentNum >= 3 )
259 } // if( isInternal )
261 // this edge intersects some other initial edges
262 if( !notFoundFlag ) {
274 if( index3 == num ) {
277 if( index3 == begIndex ) {
283 } while( !pointExist[ index3 ] );
284 x3 = contour[ index3 ].x;
285 y3 = contour[ index3 ].y;
286 } // if( isInternal ) else
288 } // if( dx1 * dy2 - dx2 * dy1 < 0 )
291 if( !notFoundFlag ) {
303 if( index3 == num ) {
306 if( index3 == begIndex ) {
312 } while( !pointExist[ index3 ] );
313 x3 = contour[ index3 ].x;
314 y3 = contour[ index3 ].y;
315 } // if( dx1 * dy2 - dx2 * dy1 < 0 ) else
317 } // while( currentNum > 3 )
325 } // icvEarCutTriangulation
327 inline bool icvFindTwoNeighbourEdges( CvPoint* contour,
338 int x0, y0, x0_end, y0_end;
339 int x1_left = 0, y1_left = 0, x1_right = 0, y1_right = 0, x2, y2;
342 (*rightEdgeIdx) = -1;
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;
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;
365 for( i = 0; i < numEdges; i ++ )
367 if( ( i != mainEdgeIdx ) &&
368 ( edges[ i * 2 ] == vtxIdx || edges[ i * 2 + 1 ] == vtxIdx ) )
370 if( (*leftEdgeIdx) == -1 )
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;
378 x1_left = x1_right = contour[ edges[ i * 2 ] ].x;
379 y1_left = y1_right = contour[ edges[ i * 2 ] ].y;
382 } // if( (*leftEdgeIdx) == -1 )
385 if( edges[ i * 2 ] == vtxIdx ) {
386 x2 = contour[ edges[ i * 2 + 1 ] ].x;
387 y2 = contour[ edges[ i * 2 + 1 ] ].y;
390 x2 = contour[ edges[ i * 2 ] ].x;
391 y2 = contour[ edges[ i * 2 ] ].y;
394 compRes = icvIsFirstEdgeClosier( x0,
395 y0, x0_end, y0_end, x1_left, y1_left, x2, y2 );
399 if( compRes == -1 ) {
403 } // if( compRes == -1 )
405 compRes = icvIsFirstEdgeClosier( x0,
406 y0, x0_end, y0_end, x1_right, y1_right, x2, y2 );
416 } // if( compRes == -1 ) else
418 } // if( (*leftEdgeIdx) == -1 ) else
420 } // if( ( i != mainEdgesIdx ) && ...
422 } // for( i = 0; i < numEdges; i ++ )
426 } // icvFindTwoNeighbourEdges
428 bool icvFindReferences( CvPoint* contour,
436 int leftEdgeIdx, rightEdgeIdx;
438 if( icvEarCutTriangulation( contour, num, outEdges, numEdges ) )
440 for( i = 0; i < (*numEdges); i ++ )
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 ++ )
448 for( i = 0; i < (*numEdges); i ++ )
450 currPntIdx = outEdges[ i * 2 ];
451 if( !icvFindTwoNeighbourEdges( contour,
452 outEdges, (*numEdges), currPntIdx,
453 i, &leftEdgeIdx, &rightEdgeIdx ) )
456 } // if( !icvFindTwoNeighbourEdges( contour, ...
459 if( outEdges[ leftEdgeIdx * 2 ] == currPntIdx ) {
460 if( refer[ i * 4 ] == -1 ) {
461 refer[ i * 4 ] = ( leftEdgeIdx << 2 );
465 if( refer[ i * 4 ] == -1 ) {
466 refer[ i * 4 ] = ( leftEdgeIdx << 2 ) | 2;
469 if( outEdges[ rightEdgeIdx * 2 ] == currPntIdx ) {
470 if( refer[ i * 4 + 1 ] == -1 ) {
471 refer[ i * 4 + 1 ] = ( rightEdgeIdx << 2 ) | 3;
475 if( refer[ i * 4 + 1 ] == -1 ) {
476 refer[ i * 4 + 1 ] = ( rightEdgeIdx << 2 ) | 1;
480 } // if( !icvFindTwoNeighbourEdges( contour, ... ) else
482 currPntIdx = outEdges[ i * 2 + 1 ];
486 if( !icvFindTwoNeighbourEdges( contour,
487 outEdges, (*numEdges), currPntIdx,
488 i, &leftEdgeIdx, &rightEdgeIdx ) )
491 } // if( !icvFindTwoNeighbourEdges( contour, ...
494 if( outEdges[ leftEdgeIdx * 2 ] == currPntIdx ) {
495 if( refer[ i * 4 + 3 ] == -1 ) {
496 refer[ i * 4 + 3 ] = ( leftEdgeIdx << 2 );
500 if( refer[ i * 4 + 3 ] == -1 ) {
501 refer[ i * 4 + 3 ] = ( leftEdgeIdx << 2 ) | 2;
504 if( outEdges[ rightEdgeIdx * 2 ] == currPntIdx ) {
505 if( refer[ i * 4 + 2 ] == -1 ) {
506 refer[ i * 4 + 2 ] = ( rightEdgeIdx << 2 ) | 3;
510 if( refer[ i * 4 + 2 ] == -1 ) {
511 refer[ i * 4 + 2 ] = ( rightEdgeIdx << 2 ) | 1;
515 } // if( !icvFindTwoNeighbourEdges( contour, ... ) else
517 } // for( i = 0; i < (*numEdges); i ++ )
519 } // if( icvEarCutTriangulation( contour, num, outEdges, numEdges ) )
522 } // if( icvEarCutTriangulation( contour, num, outEdges, ... ) else
526 } // icvFindReferences
528 void cvDecompPoly( CvContour* cont,
530 CvMemStorage* storage )
536 CvSubdiv2DPoint** pntsPtrs;
537 CvQuadEdge2D** edgesPtrs;
543 CvQuadEdge2D* quadEdge;
545 numVtx = cont -> total;
550 *subdiv = ( CvSubdiv2D* )0;
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 );
562 cvStartReadSeq( ( CvSeq* )cont, &reader, 0 );
563 for( i = 0; i < numVtx; i ++ )
565 CV_READ_SEQ_ELEM( (contour[ i ]), reader );
566 } // for( i = 0; i < numVtx; i ++ )
568 if( !icvFindReferences( contour, numVtx, outEdges, refer, &numEdges ) )
572 } // if( !icvFindReferences( contour, numVtx, outEdges, refer, ...
574 *subdiv = cvCreateSubdiv2D( CV_SEQ_KIND_SUBDIV2D,
575 sizeof( CvSubdiv2D ),
576 sizeof( CvSubdiv2DPoint ),
577 sizeof( CvQuadEdge2D ),
580 for( i = 0; i < numVtx; i ++ )
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 ++ )
587 for( i = 0; i < numEdges; i ++ )
589 edgesPtrs[ i ] = ( CvQuadEdge2D* )
590 ( cvSubdiv2DMakeEdge( *subdiv ) & 0xfffffffc );
591 } // for( i = 0; i < numEdges; i ++ )
593 for( i = 0; i < numEdges; i ++ )
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 ++ )
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 );
628 // End of file decomppoly.cpp