+++ /dev/null
-/*M///////////////////////////////////////////////////////////////////////////////////////
-//
-// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
-//
-// By downloading, copying, installing or using the software you agree to this license.
-// If you do not agree to this license, do not download, install,
-// copy or use the software.
-//
-//
-// Intel License Agreement
-// For Open Source Computer Vision Library
-//
-// Copyright (C) 2000, Intel Corporation, all rights reserved.
-// Third party copyrights are property of their respective owners.
-//
-// Redistribution and use in source and binary forms, with or without modification,
-// are permitted provided that the following conditions are met:
-//
-// * Redistribution's of source code must retain the above copyright notice,
-// this list of conditions and the following disclaimer.
-//
-// * Redistribution's in binary form must reproduce the above copyright notice,
-// this list of conditions and the following disclaimer in the documentation
-// and/or other materials provided with the distribution.
-//
-// * The name of Intel Corporation may not be used to endorse or promote products
-// derived from this software without specific prior written permission.
-//
-// This software is provided by the copyright holders and contributors "as is" and
-// any express or implied warranties, including, but not limited to, the implied
-// warranties of merchantability and fitness for a particular purpose are disclaimed.
-// In no event shall the Intel Corporation or contributors be liable for any direct,
-// indirect, incidental, special, exemplary, or consequential damages
-// (including, but not limited to, procurement of substitute goods or services;
-// loss of use, data, or profits; or business interruption) however caused
-// and on any theory of liability, whether in contract, strict liability,
-// or tort (including negligence or otherwise) arising in any way out of
-// the use of this software, even if advised of the possibility of such damage.
-//
-//M*/
-
-#include "_cvaux.h"
-
-#if 0
-
-#include <malloc.h>
-//#include "decomppoly.h"
-
-#define ZERO_CLOSE 0.00001f
-#define ONE_CLOSE 0.99999f
-
-#define CHECK_COLLINEARITY(vec1_x,vec1_y,vec2_x,vec2_y) \
- if( vec1_x == 0 ) { \
- if( vec1_y * vec2_y > 0 ) { \
- return 0; \
- } \
- } \
- else { \
- if( vec1_x * vec2_x > 0 ) { \
- return 0; \
- } \
- }
-
-// determines if edge number one lies in counterclockwise
-// earlier than edge number two
-inline int icvIsFirstEdgeClosier( int x0,
- int y0,
- int x0_end,
- int y0_end,
- int x1_end,
- int y1_end,
- int x2_end,
- int y2_end )
-{
- int mult, mult1, mult2;
- int vec0_x, vec0_y;
- int vec1_x, vec1_y;
- int vec2_x, vec2_y;
-
- vec0_x = x0_end - x0;
- vec0_y = y0_end - y0;
- vec1_x = x1_end - x0;
- vec1_y = y1_end - y0;
- vec2_x = x2_end - x0;
- vec2_y = y2_end - y0;
-
- mult1 = vec1_x * vec0_y - vec0_x * vec1_y;
- mult2 = vec2_x * vec0_y - vec0_x * vec2_y;
-
- if( mult1 == 0 ) {
- CHECK_COLLINEARITY( vec0_x, vec0_y, vec1_x, vec1_y );
- }
- if( mult2 == 0 ) {
- CHECK_COLLINEARITY( vec0_x, vec0_y, vec2_x, vec2_y );
- }
- if( mult1 > 0 && mult2 < 0 ) {
- return 1;
- }
- if( mult1 < 0 && mult2 > 0 ) {
- return -1;
- }
-
- mult = vec1_x * vec2_y - vec2_x * vec1_y;
- if( mult == 0 ) {
- CHECK_COLLINEARITY( vec1_x, vec1_y, vec2_x, vec2_y );
- }
-
- if( mult1 > 0 )
- {
- if( mult > 0 ) {
- return -1;
- }
- else {
- return 1;
- }
- } // if( mult1 > 0 )
- else
- {
- if( mult1 != 0 ) {
- if( mult > 0 ) {
- return 1;
- }
- else {
- return -1;
- }
- } // if( mult1 != 0 )
- else {
- if( mult2 > 0 ) {
- return -1;
- }
- else {
- return 1;
- }
- } // if( mult1 != 0 ) else
-
- } // if( mult1 > 0 ) else
-
-} // icvIsFirstEdgeClosier
-
-bool icvEarCutTriangulation( CvPoint* contour,
- int num,
- int* outEdges,
- int* numEdges )
-{
- int i;
- int notFoundFlag = 0;
- int begIndex = -1;
- int isInternal;
- int currentNum = num;
- int index1, index2, index3;
- int ix0, iy0, ix1, iy1, ix2, iy2;
- int x1, y1, x2, y2, x3, y3;
- int dx1, dy1, dx2, dy2;
- int* pointExist = ( int* )0;
- int det, det1, det2;
- float t1, t2;
-
- (*numEdges) = 0;
-
- if( num <= 2 ) {
- return false;
- }
-
- pointExist = ( int* )malloc( num * sizeof( int ) );
-
- for( i = 0; i < num; i ++ ) {
- pointExist[i] = 1;
- }
-
- for( i = 0; i < num; i ++ ) {
- outEdges[ (*numEdges) * 2 ] = i;
- if( i != num - 1 ) {
- outEdges[ (*numEdges) * 2 + 1 ] = i + 1;
- }
- else {
- outEdges[ (*numEdges) * 2 + 1 ] = 0;
- }
- (*numEdges) ++;
- } // for( i = 0; i < num; i ++ )
-
- // initializing data before while cycle
- index1 = 0;
- index2 = 1;
- index3 = 2;
- x1 = contour[ index1 ].x;
- y1 = contour[ index1 ].y;
- x2 = contour[ index2 ].x;
- y2 = contour[ index2 ].y;
- x3 = contour[ index3 ].x;
- y3 = contour[ index3 ].y;
-
- while( currentNum > 3 )
- {
- dx1 = x2 - x1;
- dy1 = y2 - y1;
- dx2 = x3 - x2;
- dy2 = y3 - y2;
- if( dx1 * dy2 - dx2 * dy1 < 0 ) // convex condition
- {
- // checking for noncrossing edge
- ix1 = x3 - x1;
- iy1 = y3 - y1;
- isInternal = 1;
- for( i = 0; i < num; i ++ )
- {
- if( i != num - 1 ) {
- ix2 = contour[ i + 1 ].x - contour[ i ].x;
- iy2 = contour[ i + 1 ].y - contour[ i ].y;
- }
- else {
- ix2 = contour[ 0 ].x - contour[ i ].x;
- iy2 = contour[ 0 ].y - contour[ i ].y;
- }
- ix0 = contour[ i ].x - x1;
- iy0 = contour[ i ].y - y1;
-
- det = ix2 * iy1 - ix1 * iy2;
- det1 = ix2 * iy0 - ix0 * iy2;
- if( det != 0.0f )
- {
- t1 = ( ( float )( det1 ) ) / det;
- if( t1 > ZERO_CLOSE && t1 < ONE_CLOSE )
- {
- det2 = ix1 * iy0 - ix0 * iy1;
- t2 = ( ( float )( det2 ) ) / det;
- if( t2 > ZERO_CLOSE && t2 < ONE_CLOSE ) {
- isInternal = 0;
- }
-
- } // if( t1 > ZERO_CLOSE && t1 < ONE_CLOSE )
-
- } // if( det != 0.0f )
-
- } // for( i = 0; i < (*numEdges); i ++ )
-
- if( isInternal )
- {
- // this edge is internal
- notFoundFlag = 0;
- outEdges[ (*numEdges) * 2 ] = index1;
- outEdges[ (*numEdges) * 2 + 1 ] = index3;
- (*numEdges) ++;
- pointExist[ index2 ] = 0;
- index2 = index3;
- x2 = x3;
- y2 = y3;
- currentNum --;
- if( currentNum >= 3 ) {
- do {
- index3 ++;
- if( index3 == num ) {
- index3 = 0;
- }
- } while( !pointExist[ index3 ] );
- x3 = contour[ index3 ].x;
- y3 = contour[ index3 ].y;
- } // if( currentNum >= 3 )
-
- } // if( isInternal )
- else {
- // this edge intersects some other initial edges
- if( !notFoundFlag ) {
- notFoundFlag = 1;
- begIndex = index1;
- }
- index1 = index2;
- x1 = x2;
- y1 = y2;
- index2 = index3;
- x2 = x3;
- y2 = y3;
- do {
- index3 ++;
- if( index3 == num ) {
- index3 = 0;
- }
- if( index3 == begIndex ) {
- if( pointExist ) {
- free( pointExist );
- }
- return false;
- }
- } while( !pointExist[ index3 ] );
- x3 = contour[ index3 ].x;
- y3 = contour[ index3 ].y;
- } // if( isInternal ) else
-
- } // if( dx1 * dy2 - dx2 * dy1 < 0 )
- else
- {
- if( !notFoundFlag ) {
- notFoundFlag = 1;
- begIndex = index1;
- }
- index1 = index2;
- x1 = x2;
- y1 = y2;
- index2 = index3;
- x2 = x3;
- y2 = y3;
- do {
- index3 ++;
- if( index3 == num ) {
- index3 = 0;
- }
- if( index3 == begIndex ) {
- if( pointExist ) {
- free( pointExist );
- }
- return false;
- }
- } while( !pointExist[ index3 ] );
- x3 = contour[ index3 ].x;
- y3 = contour[ index3 ].y;
- } // if( dx1 * dy2 - dx2 * dy1 < 0 ) else
-
- } // while( currentNum > 3 )
-
- if( pointExist ) {
- free( pointExist );
- }
-
- return true;
-
-} // icvEarCutTriangulation
-
-inline bool icvFindTwoNeighbourEdges( CvPoint* contour,
- int* edges,
- int numEdges,
- int vtxIdx,
- int mainEdgeIdx,
- int* leftEdgeIdx,
- int* rightEdgeIdx )
-{
- int i;
- int compRes;
- int vec0_x, vec0_y;
- int x0, y0, x0_end, y0_end;
- int x1_left = 0, y1_left = 0, x1_right = 0, y1_right = 0, x2, y2;
-
- (*leftEdgeIdx) = -1;
- (*rightEdgeIdx) = -1;
-
- if( edges[ mainEdgeIdx * 2 ] == vtxIdx ) {
- x0 = contour[ vtxIdx ].x;
- y0 = contour[ vtxIdx ].y;
- x0_end = contour[ edges[ mainEdgeIdx * 2 + 1 ] ].x;
- y0_end = contour[ edges[ mainEdgeIdx * 2 + 1 ] ].y;
- vec0_x = x0_end - x0;
- vec0_y = y0_end - y0;
- }
- else {
- //x0 = contour[ edges[ mainEdgeIdx * 2 ] ].x;
- //y0 = contour[ edges[ mainEdgeIdx * 2 ] ].y;
- //x0_end = contour[ vtxIdx ].x;
- //y0_end = contour[ vtxIdx ].y;
- x0 = contour[ vtxIdx ].x;
- y0 = contour[ vtxIdx ].y;
- x0_end = contour[ edges[ mainEdgeIdx * 2 ] ].x;
- y0_end = contour[ edges[ mainEdgeIdx * 2 ] ].y;
- vec0_x = x0_end - x0;
- vec0_y = y0_end - y0;
- }
-
- for( i = 0; i < numEdges; i ++ )
- {
- if( ( i != mainEdgeIdx ) &&
- ( edges[ i * 2 ] == vtxIdx || edges[ i * 2 + 1 ] == vtxIdx ) )
- {
- if( (*leftEdgeIdx) == -1 )
- {
- (*leftEdgeIdx) = (*rightEdgeIdx) = i;
- if( edges[ i * 2 ] == vtxIdx ) {
- x1_left = x1_right = contour[ edges[ i * 2 + 1 ] ].x;
- y1_left = y1_right = contour[ edges[ i * 2 + 1 ] ].y;
- }
- else {
- x1_left = x1_right = contour[ edges[ i * 2 ] ].x;
- y1_left = y1_right = contour[ edges[ i * 2 ] ].y;
- }
-
- } // if( (*leftEdgeIdx) == -1 )
- else
- {
- if( edges[ i * 2 ] == vtxIdx ) {
- x2 = contour[ edges[ i * 2 + 1 ] ].x;
- y2 = contour[ edges[ i * 2 + 1 ] ].y;
- }
- else {
- x2 = contour[ edges[ i * 2 ] ].x;
- y2 = contour[ edges[ i * 2 ] ].y;
- }
-
- compRes = icvIsFirstEdgeClosier( x0,
- y0, x0_end, y0_end, x1_left, y1_left, x2, y2 );
- if( compRes == 0 ) {
- return false;
- }
- if( compRes == -1 ) {
- (*leftEdgeIdx) = i;
- x1_left = x2;
- y1_left = y2;
- } // if( compRes == -1 )
- else {
- compRes = icvIsFirstEdgeClosier( x0,
- y0, x0_end, y0_end, x1_right, y1_right, x2, y2 );
- if( compRes == 0 ) {
- return false;
- }
- if( compRes == 1 ) {
- (*rightEdgeIdx) = i;
- x1_right = x2;
- y1_right = y2;
- }
-
- } // if( compRes == -1 ) else
-
- } // if( (*leftEdgeIdx) == -1 ) else
-
- } // if( ( i != mainEdgesIdx ) && ...
-
- } // for( i = 0; i < numEdges; i ++ )
-
- return true;
-
-} // icvFindTwoNeighbourEdges
-
-bool icvFindReferences( CvPoint* contour,
- int num,
- int* outEdges,
- int* refer,
- int* numEdges )
-{
- int i;
- int currPntIdx;
- int leftEdgeIdx, rightEdgeIdx;
-
- if( icvEarCutTriangulation( contour, num, outEdges, numEdges ) )
- {
- for( i = 0; i < (*numEdges); i ++ )
- {
- refer[ i * 4 ] = -1;
- refer[ i * 4 + 1 ] = -1;
- refer[ i * 4 + 2 ] = -1;
- refer[ i * 4 + 3 ] = -1;
- } // for( i = 0; i < (*numEdges); i ++ )
-
- for( i = 0; i < (*numEdges); i ++ )
- {
- currPntIdx = outEdges[ i * 2 ];
- if( !icvFindTwoNeighbourEdges( contour,
- outEdges, (*numEdges), currPntIdx,
- i, &leftEdgeIdx, &rightEdgeIdx ) )
- {
- return false;
- } // if( !icvFindTwoNeighbourEdges( contour, ...
- else
- {
- if( outEdges[ leftEdgeIdx * 2 ] == currPntIdx ) {
- if( refer[ i * 4 ] == -1 ) {
- refer[ i * 4 ] = ( leftEdgeIdx << 2 );
- }
- }
- else {
- if( refer[ i * 4 ] == -1 ) {
- refer[ i * 4 ] = ( leftEdgeIdx << 2 ) | 2;
- }
- }
- if( outEdges[ rightEdgeIdx * 2 ] == currPntIdx ) {
- if( refer[ i * 4 + 1 ] == -1 ) {
- refer[ i * 4 + 1 ] = ( rightEdgeIdx << 2 ) | 3;
- }
- }
- else {
- if( refer[ i * 4 + 1 ] == -1 ) {
- refer[ i * 4 + 1 ] = ( rightEdgeIdx << 2 ) | 1;
- }
- }
-
- } // if( !icvFindTwoNeighbourEdges( contour, ... ) else
-
- currPntIdx = outEdges[ i * 2 + 1 ];
- if( i == 18 ) {
- i = i;
- }
- if( !icvFindTwoNeighbourEdges( contour,
- outEdges, (*numEdges), currPntIdx,
- i, &leftEdgeIdx, &rightEdgeIdx ) )
- {
- return false;
- } // if( !icvFindTwoNeighbourEdges( contour, ...
- else
- {
- if( outEdges[ leftEdgeIdx * 2 ] == currPntIdx ) {
- if( refer[ i * 4 + 3 ] == -1 ) {
- refer[ i * 4 + 3 ] = ( leftEdgeIdx << 2 );
- }
- }
- else {
- if( refer[ i * 4 + 3 ] == -1 ) {
- refer[ i * 4 + 3 ] = ( leftEdgeIdx << 2 ) | 2;
- }
- }
- if( outEdges[ rightEdgeIdx * 2 ] == currPntIdx ) {
- if( refer[ i * 4 + 2 ] == -1 ) {
- refer[ i * 4 + 2 ] = ( rightEdgeIdx << 2 ) | 3;
- }
- }
- else {
- if( refer[ i * 4 + 2 ] == -1 ) {
- refer[ i * 4 + 2 ] = ( rightEdgeIdx << 2 ) | 1;
- }
- }
-
- } // if( !icvFindTwoNeighbourEdges( contour, ... ) else
-
- } // for( i = 0; i < (*numEdges); i ++ )
-
- } // if( icvEarCutTriangulation( contour, num, outEdges, numEdges ) )
- else {
- return false;
- } // if( icvEarCutTriangulation( contour, num, outEdges, ... ) else
-
- return true;
-
-} // icvFindReferences
-
-void cvDecompPoly( CvContour* cont,
- CvSubdiv2D** subdiv,
- CvMemStorage* storage )
-{
- int* memory;
- CvPoint* contour;
- int* outEdges;
- int* refer;
- CvSubdiv2DPoint** pntsPtrs;
- CvQuadEdge2D** edgesPtrs;
- int numVtx;
- int numEdges;
- int i;
- CvSeqReader reader;
- CvPoint2D32f pnt;
- CvQuadEdge2D* quadEdge;
-
- numVtx = cont -> total;
- if( numVtx < 3 ) {
- return;
- }
-
- *subdiv = ( CvSubdiv2D* )0;
-
- memory = ( int* )malloc( sizeof( int ) * ( numVtx * 2
- + numVtx * numVtx * 2 * 5 )
- + sizeof( CvQuadEdge2D* ) * ( numVtx * numVtx )
- + sizeof( CvSubdiv2DPoint* ) * ( numVtx * 2 ) );
- contour = ( CvPoint* )memory;
- outEdges = ( int* )( contour + numVtx );
- refer = outEdges + numVtx * numVtx * 2;
- edgesPtrs = ( CvQuadEdge2D** )( refer + numVtx * numVtx * 4 );
- pntsPtrs = ( CvSubdiv2DPoint** )( edgesPtrs + numVtx * numVtx );
-
- cvStartReadSeq( ( CvSeq* )cont, &reader, 0 );
- for( i = 0; i < numVtx; i ++ )
- {
- CV_READ_SEQ_ELEM( (contour[ i ]), reader );
- } // for( i = 0; i < numVtx; i ++ )
-
- if( !icvFindReferences( contour, numVtx, outEdges, refer, &numEdges ) )
- {
- free( memory );
- return;
- } // if( !icvFindReferences( contour, numVtx, outEdges, refer, ...
-
- *subdiv = cvCreateSubdiv2D( CV_SEQ_KIND_SUBDIV2D,
- sizeof( CvSubdiv2D ),
- sizeof( CvSubdiv2DPoint ),
- sizeof( CvQuadEdge2D ),
- storage );
-
- for( i = 0; i < numVtx; i ++ )
- {
- pnt.x = ( float )contour[ i ].x;
- pnt.y = ( float )contour[ i ].y;
- pntsPtrs[ i ] = cvSubdiv2DAddPoint( *subdiv, pnt, 0 );
- } // for( i = 0; i < numVtx; i ++ )
-
- for( i = 0; i < numEdges; i ++ )
- {
- edgesPtrs[ i ] = ( CvQuadEdge2D* )
- ( cvSubdiv2DMakeEdge( *subdiv ) & 0xfffffffc );
- } // for( i = 0; i < numEdges; i ++ )
-
- for( i = 0; i < numEdges; i ++ )
- {
- quadEdge = edgesPtrs[ i ];
- quadEdge -> next[ 0 ] =
- ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 ] >> 2 ] )
- | ( refer[ i * 4 ] & 3 );
- quadEdge -> next[ 1 ] =
- ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 + 1 ] >> 2 ] )
- | ( refer[ i * 4 + 1 ] & 3 );
- quadEdge -> next[ 2 ] =
- ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 + 2 ] >> 2 ] )
- | ( refer[ i * 4 + 2 ] & 3 );
- quadEdge -> next[ 3 ] =
- ( ( CvSubdiv2DEdge )edgesPtrs[ refer[ i * 4 + 3 ] >> 2 ] )
- | ( refer[ i * 4 + 3 ] & 3 );
- quadEdge -> pt[ 0 ] = pntsPtrs[ outEdges[ i * 2 ] ];
- quadEdge -> pt[ 1 ] = ( CvSubdiv2DPoint* )0;
- quadEdge -> pt[ 2 ] = pntsPtrs[ outEdges[ i * 2 + 1 ] ];
- quadEdge -> pt[ 3 ] = ( CvSubdiv2DPoint* )0;
- } // for( i = 0; i < numEdges; i ++ )
-
- (*subdiv) -> topleft.x = ( float )cont -> rect.x;
- (*subdiv) -> topleft.y = ( float )cont -> rect.y;
- (*subdiv) -> bottomright.x =
- ( float )( cont -> rect.x + cont -> rect.width );
- (*subdiv) -> bottomright.y =
- ( float )( cont -> rect.y + cont -> rect.height );
-
- free( memory );
- return;
-
-} // cvDecompPoly
-
-#endif
-
-// End of file decomppoly.cpp
-
projects / opencv / blobdiff