xref: /external/opencv/cvaux/src/decomppoly.cpp

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