/*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