git.maemo.org Git - opencv/blob - cvaux/src/cvlcm.cpp

   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 /* Hybrid linear-contour model reconstruction */
  43 #include "_cvaux.h"
  44
  45 #define CV_IMPL CV_EXTERN_C
  46
  47 const float LCM_CONST_ZERO = 1e-6f;
  48
  49 /****************************************************************************************\
  50 *                                    Auxiliary struct definitions                                 *
  51 \****************************************************************************************/
  52 typedef struct CvLCM
  53 {
  54     CvGraph* Graph;
  55     CvVoronoiDiagram2D* VoronoiDiagram;
  56     CvMemStorage* ContourStorage;
  57     CvMemStorage* EdgeStorage;
  58     float maxWidth;
  59 } CvLCM;
  60
  61 typedef struct CvLCMComplexNodeData
  62 {
  63     CvVoronoiNode2D edge_node;
  64     CvPoint2D32f site_first_pt;
  65     CvPoint2D32f site_last_pt;
  66     CvVoronoiSite2D* site_first;
  67     CvVoronoiSite2D* site_last;
  68     CvVoronoiEdge2D* edge;
  69 } CvLCMComplexNodeData;
  70
  71 typedef struct CvLCMData
  72 {
  73     CvVoronoiNode2D* pnode;
  74     CvVoronoiSite2D* psite;
  75     CvVoronoiEdge2D* pedge;
  76 } CvLCMData;
  77
  78
  79 /****************************************************************************************\
  80 *                                    Function definitions                                *
  81 \****************************************************************************************/
  82
  83 #define _CV_READ_SEQ_ELEM( elem, reader, type )                       \
  84 {                                                              \
  85     assert( (reader).seq->elem_size == sizeof(*elem));         \
  86     elem = (type)(reader).ptr;                                 \
  87     CV_NEXT_SEQ_ELEM( sizeof(*elem), reader )                  \
  88 }
  89
  90 #define _CV_IS_SITE_REFLEX( SITE )  ((SITE) ->node[0] == (SITE) ->node[1])
  91 #define _CV_IS_EDGE_REFLEX( EDGE )  (( (EDGE)->site[0]->node[0] == (EDGE)->site[0]->node[0] ) || \
  92                                       ( (EDGE)->site[1]->node[0] == (EDGE)->site[1]->node[0] ) )
  93
  94 #define _CV_INITIALIZE_CVLCMDATA(STRUCT,SITE,EDGE,NODE)\
  95 { (STRUCT)->psite = SITE ; (STRUCT)->pedge = EDGE; (STRUCT)->pnode = NODE;}
  96 /*F///////////////////////////////////////////////////////////////////////////////////////
  97 //    Author:  Andrey Sobolev
  98 //    Name:    _cvConstructLCM
  99 //    Purpose: Function constructs hybrid model
 100 //    Context:
 101 //    Parameters:
 102 //      LCM : in&out.
 103 //    Returns: 1, if hybrid model was succesfully constructed
 104 //             0, if some error occures
 105 //F*/
 106 CV_IMPL
 107 int _cvConstructLCM(CvLCM* LCM);
 108
 109 /*F///////////////////////////////////////////////////////////////////////////////////////
 110 //    Author:  Andrey Sobolev
 111 //    Name:    _cvConstructLCMComplexNode
 112 //    Purpose: Function constructs Complex Node (node, which consists of
 113 //             two points and more) of hybrid model
 114 //    Context:
 115 //    Parameters:
 116 //      pLCM : in&out.
 117 //      pLCMEdge: in, input edge of hybrid model
 118 //      pLCMInputData: in, input parameters
 119 //    Returns: pointer to constructed node
 120 //F*/
 121 CV_IMPL
 122 CvLCMNode* _cvConstructLCMComplexNode(CvLCM* pLCM,
 123                                       CvLCMEdge* pLCMEdge,
 124                                       CvLCMData* pLCMInputData);
 125
 126 /*F///////////////////////////////////////////////////////////////////////////////////////
 127 //    Author:  Andrey Sobolev
 128 //    Name:    _cvConstructLCMSimpleNode
 129 //    Purpose: Function constructs Simple Node (node, which consists of
 130 //             one point) of hybrid model
 131 //    Context:
 132 //    Parameters:
 133 //      pLCM : in&out.
 134 //      pLCMEdge: in, input edge of hybrid model
 135 //      pLCMInputData: in, input parameters
 136 //    Returns: pointer to constructed node
 137 //F*/
 138 CV_IMPL
 139 CvLCMNode* _cvConstructLCMSimpleNode(CvLCM* pLCM,
 140                                     CvLCMEdge* pLCMEdge,
 141                                     CvLCMData* pLCMInputData);
 142
 143 /*F///////////////////////////////////////////////////////////////////////////////////////
 144 //    Author:  Andrey Sobolev
 145 //    Name:    _cvConstructLCMSimpleNode
 146 //    Purpose: Function constructs Edge of hybrid model
 147 //    Context:
 148 //    Parameters:
 149 //      pLCM : in&out.
 150 //      pLCMInputData: in, input parameters
 151 //    Returns: pointer to constructed edge
 152 //F*/
 153 CV_IMPL
 154 CvLCMEdge* _cvConstructLCMEdge(CvLCM* pLCM,
 155                                CvLCMData* pLCMInputData);
 156
 157 /*F///////////////////////////////////////////////////////////////////////////////////////
 158 //    Author:  Andrey Sobolev
 159 //    Name:    _cvTreatExeptionalCase
 160 //    Purpose: Function treats triangles and regular polygons
 161 //    Context:
 162 //    Parameters:
 163 //      pLCM : in, information about graph
 164 //      pLCMInputData: in, input parameters
 165 //    Returns: pointer to graph node
 166 //F*/
 167 CV_IMPL
 168 CvLCMNode* _cvTreatExeptionalCase(CvLCM* pLCM,
 169                                   CvLCMData* pLCMInputData);
 170
 171 /*F///////////////////////////////////////////////////////////////////////////////////////
 172 //    Author:  Andrey Sobolev
 173 //    Name:    _cvNodeMultyplicity
 174 //    Purpose: Function seeks all non-boundary edges incident to
 175 //              given node and correspondent incident sites
 176 //    Context:
 177 //    Parameters:
 178 //      pEdge : in, original edge
 179 //      pNode : in, given node
 180 //      LinkedEdges : out, matrix of incident edges
 181 //      LinkedSites : out, matrix of incident sites
 182 //      pSite: in, original site (pNode must be the begin point of pEdge
 183 //              for this pSite, this property hold out far all edges)
 184 //    Returns: number of incident edges (must be less than 10)
 185 //F*/
 186 CV_IMPL
 187 int _cvNodeMultyplicity(CvVoronoiSite2D* pSite,
 188                         CvVoronoiEdge2D* pEdge,
 189                         CvVoronoiNode2D* pNode,
 190                         CvVoronoiEdge2D** LinkedEdges,
 191                         CvVoronoiSite2D** LinkedSites);
 192
 193 /*F///////////////////////////////////////////////////////////////////////////////////////
 194 //    Author:  Andrey Sobolev
 195 //    Name:    _cvCreateLCMNode
 196 //    Purpose: Function create graph node
 197 //    Context:
 198 //    Parameters:
 199 //      pLCM : in, information about graph
 200 //    Returns: pointer to graph node
 201 //F*/
 202 CV_IMPL
 203 CvLCMNode* _cvCreateLCMNode(CvLCM* pLCM);
 204
 205 /*F///////////////////////////////////////////////////////////////////////////////////////
 206 //    Author:  Andrey Sobolev
 207 //    Name:    _cvCreateLCMEdge
 208 //    Purpose: Function create graph edge
 209 //    Context:
 210 //    Parameters:
 211 //      pLCM : in, information about graph
 212 //    Returns: pointer to graph edge
 213 //F*/
 214 CV_IMPL
 215 CvLCMEdge* _cvCreateLCMEdge(CvLCM* pLCM);
 216
 217 /*F///////////////////////////////////////////////////////////////////////////////////////
 218 //    Author:  Andrey Sobolev
 219 //    Name:    _cvCreateLCMNode
 220 //    Purpose: Function establishs the connection between node and ege
 221 //    Context:
 222 //    Parameters:
 223 //      LCMNode : in, graph node
 224 //      LCMEdge : in, graph edge
 225 //      LCMEdge_prev : in&out, previous edge, connected with given node
 226 //      index: in,
 227 //      i    : =0, if node is initial for edge
 228 //             =1, if node  is terminal for edge
 229 //    Returns:
 230 //F*/
 231 CV_IMPL
 232 void _cvAttachLCMEdgeToLCMNode(CvLCMNode* LCMNode,
 233                                CvLCMEdge* LCMEdge,
 234                                CvLCMEdge* &LCMEdge_prev,
 235                                int index,
 236                                int i);
 237 /*F///////////////////////////////////////////////////////////////////////////////////////
 238 //    Author:  Andrey Sobolev
 239 //    Name:    _cvProjectionPointToSegment
 240 //    Purpose: Function computes the ortogonal projection of PointO to
 241 //             to segment[PointA, PointB]
 242 //    Context:
 243 //    Parameters:
 244 //      PointO, PointA,PointB: in, given points
 245 //      PrPoint : out, projection
 246 //      dist : distance from PointO to PrPoint
 247 //    Returns:
 248 //F*/
 249 CV_IMPL
 250 void _cvProjectionPointToSegment(CvPoint2D32f* PointO,
 251                                  CvPoint2D32f* PointA,
 252                                  CvPoint2D32f* PointB,
 253                                  CvPoint2D32f* PrPoint,
 254                                  float* dist);
 255
 256 /*F///////////////////////////////////////////////////////////////////////////////////////
 257 //    Author:  Andrey Sobolev
 258 //    Name:    _cvPrepareData
 259 //    Purpose: Function fills up the struct CvLCMComplexNodeData
 260 //    Context:
 261 //    Parameters:
 262 //      pLCMData : in
 263 //      pLCMCCNData : out
 264 //    Returns:
 265 //F*/
 266 CV_IMPL
 267 void _cvPrepareData(CvLCMComplexNodeData* pLCMCCNData,
 268                     CvLCMData* pLCMData);
 269
 270 /****************************************************************************************\
 271 *                                    Function realization                               *
 272 \****************************************************************************************/
 273
 274 CV_IMPL CvGraph* cvLinearContorModelFromVoronoiDiagram(CvVoronoiDiagram2D* VoronoiDiagram,
 275                                                        float maxWidth)
 276 {
 277     CvMemStorage* LCMstorage;
 278     CvSet* SiteSet;
 279     CvLCM LCM = {NULL, VoronoiDiagram,NULL,NULL,maxWidth};
 280
 281     CV_FUNCNAME( "cvLinearContorModelFromVoronoiDiagram" );
 282      __BEGIN__;
 283
 284     if( !VoronoiDiagram )
 285         CV_ERROR( CV_StsBadArg,"Voronoi Diagram is not defined" );
 286     if( maxWidth < 0 )
 287         CV_ERROR( CV_StsBadArg,"Treshold parameter must be non negative" );
 288
 289     for(SiteSet = VoronoiDiagram->sites;
 290         SiteSet != NULL;
 291         SiteSet = (CvSet*)SiteSet->h_next)
 292         {
 293             if(SiteSet->v_next)
 294                 CV_ERROR( CV_StsBadArg,"Can't operate with multiconnected domains" );
 295             if(SiteSet->total > 70000)
 296                 CV_ERROR( CV_StsBadArg,"Can't operate with large domains" );
 297         }
 298
 299
 300     LCMstorage = cvCreateMemStorage(0);
 301     LCM.EdgeStorage = cvCreateChildMemStorage(LCMstorage);
 302     LCM.ContourStorage = cvCreateChildMemStorage(LCMstorage);
 303     LCM.Graph = cvCreateGraph(CV_SEQ_KIND_GRAPH|CV_GRAPH_FLAG_ORIENTED,
 304                               sizeof(CvGraph),
 305                               sizeof(CvLCMNode),
 306                               sizeof(CvLCMEdge),
 307                               LCMstorage);
 308     if(!_cvConstructLCM(&LCM))
 309         cvReleaseLinearContorModelStorage(&LCM.Graph);
 310
 311
 312     __END__;
 313     return LCM.Graph;
 314 }//end of cvLinearContorModelFromVoronoiDiagram
 315
 316 CV_IMPL int cvReleaseLinearContorModelStorage(CvGraph** Graph)
 317 {
 318     CvSeq* LCMNodeSeq, *LCMEdgeSeq;
 319     CvLCMNode* pLCMNode;
 320     CvLCMEdge* pLCMEdge;
 321
 322     /*CV_FUNCNAME( "cvReleaseLinearContorModelStorage" );*/
 323      __BEGIN__;
 324
 325     if(!Graph || !(*Graph))
 326         return 0;
 327
 328     LCMNodeSeq = (CvSeq*)(*Graph);
 329     LCMEdgeSeq = (CvSeq*)(*Graph)->edges;
 330     if(LCMNodeSeq->total > 0)
 331     {
 332         pLCMNode = (CvLCMNode*)cvGetSeqElem(LCMNodeSeq,0);
 333         if(pLCMNode->contour->storage)
 334             cvReleaseMemStorage(&pLCMNode->contour->storage);
 335     }
 336     if(LCMEdgeSeq->total > 0)
 337     {
 338         pLCMEdge = (CvLCMEdge*)cvGetSeqElem(LCMEdgeSeq,0);
 339         if(pLCMEdge->chain->storage)
 340             cvReleaseMemStorage(&pLCMEdge->chain->storage);
 341     }
 342     if((*Graph)->storage)
 343         cvReleaseMemStorage(&(*Graph)->storage);
 344     *Graph = NULL;
 345
 346
 347     __END__;
 348     return 1;
 349 }//end of cvReleaseLinearContorModelStorage
 350
 351 int _cvConstructLCM(CvLCM* LCM)
 352 {
 353     CvVoronoiSite2D* pSite = 0;
 354     CvVoronoiEdge2D* pEdge = 0, *pEdge1;
 355     CvVoronoiNode2D* pNode, *pNode1;
 356
 357     CvVoronoiEdge2D* LinkedEdges[10];
 358     CvVoronoiSite2D* LinkedSites[10];
 359
 360     CvSeqReader reader;
 361     CvLCMData LCMdata;
 362     int i;
 363
 364     for(CvSet* SiteSet = LCM->VoronoiDiagram->sites;
 365         SiteSet != NULL;
 366         SiteSet = (CvSet*)SiteSet->h_next)
 367     {
 368         cvStartReadSeq((CvSeq*)SiteSet, &reader);
 369         for(i = 0; i < SiteSet->total; i++)
 370         {
 371             _CV_READ_SEQ_ELEM(pSite,reader,CvVoronoiSite2D*);
 372             if(pSite->node[0] == pSite->node[1])
 373                 continue;
 374             pEdge = CV_LAST_VORONOIEDGE2D(pSite);
 375             pNode = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
 376             if(pNode->radius > LCM->maxWidth)
 377                 goto PREPARECOMPLEXNODE;
 378
 379             pEdge1 = CV_PREV_VORONOIEDGE2D(pEdge,pSite);
 380             pNode1 = CV_VORONOIEDGE2D_BEGINNODE(pEdge1,pSite);
 381             if(pNode1->radius > LCM->maxWidth)
 382                 goto PREPARECOMPLEXNODE;
 383             if(pNode1->radius == 0)
 384                 continue;
 385             if(_cvNodeMultyplicity(pSite, pEdge,pNode,LinkedEdges,LinkedSites) == 1)
 386                 goto PREPARESIMPLENODE;
 387         }
 388 // treate triangle or regular polygon
 389         _CV_INITIALIZE_CVLCMDATA(&LCMdata,pSite,pEdge,CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite));
 390         if(!_cvTreatExeptionalCase(LCM,&LCMdata))
 391             return 0;
 392         continue;
 393
 394 PREPARECOMPLEXNODE:
 395         _CV_INITIALIZE_CVLCMDATA(&LCMdata,pSite,pEdge,CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite));
 396         if(!_cvConstructLCMComplexNode(LCM,NULL,&LCMdata))
 397             return 0;
 398         continue;
 399
 400 PREPARESIMPLENODE:
 401         _CV_INITIALIZE_CVLCMDATA(&LCMdata,pSite,pEdge,CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite));
 402         if(!_cvConstructLCMSimpleNode(LCM,NULL,&LCMdata))
 403             return 0;
 404         continue;
 405     }
 406     return 1;
 407 }//end of _cvConstructLCM
 408
 409 CvLCMNode* _cvConstructLCMComplexNode(CvLCM* pLCM,
 410                                       CvLCMEdge* pLCMEdge,
 411                                       CvLCMData* pLCMInputData)
 412 {
 413     CvLCMNode* pLCMNode;
 414     CvLCMEdge* pLCMEdge_prev = NULL;
 415     CvSeqWriter writer;
 416     CvVoronoiSite2D* pSite, *pSite_first, *pSite_last;
 417     CvVoronoiEdge2D* pEdge, *pEdge_stop;
 418     CvVoronoiNode2D* pNode0, *pNode1;
 419     CvLCMData LCMOutputData;
 420     CvLCMComplexNodeData LCMCCNData;
 421     int index = 0;
 422
 423     _cvPrepareData(&LCMCCNData,pLCMInputData);
 424
 425     pLCMNode = _cvCreateLCMNode(pLCM);
 426     _cvAttachLCMEdgeToLCMNode(pLCMNode,pLCMEdge,pLCMEdge_prev,1,1);
 427     cvStartAppendToSeq((CvSeq*)pLCMNode->contour,&writer);
 428     CV_WRITE_SEQ_ELEM(LCMCCNData.site_last_pt, writer);
 429     index++;
 430
 431     if(pLCMEdge)
 432     {
 433         CV_WRITE_SEQ_ELEM(LCMCCNData.edge_node.pt, writer );
 434         CV_WRITE_SEQ_ELEM(LCMCCNData.site_first_pt, writer );
 435         index+=2;
 436     }
 437
 438     pSite_first = LCMCCNData.site_first;
 439     pSite_last = LCMCCNData.site_last;
 440     pEdge = LCMCCNData.edge;
 441
 442     for(pSite = pSite_first;
 443         pSite != pSite_last;
 444         pSite = CV_NEXT_VORONOISITE2D(pSite),
 445         pEdge = CV_PREV_VORONOIEDGE2D(CV_LAST_VORONOIEDGE2D(pSite),pSite))
 446     {
 447         pEdge_stop = CV_FIRST_VORONOIEDGE2D(pSite);
 448         for(;pEdge && pEdge != pEdge_stop;
 449              pEdge = CV_PREV_VORONOIEDGE2D(pEdge,pSite))
 450         {
 451             pNode0 = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
 452             pNode1 = CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite);
 453             if(pNode0->radius <= pLCM->maxWidth && pNode1->radius <= pLCM->maxWidth)
 454             {
 455                 _CV_INITIALIZE_CVLCMDATA(&LCMOutputData,pSite,pEdge,pNode1);
 456                 _cvPrepareData(&LCMCCNData,&LCMOutputData);
 457                 CV_WRITE_SEQ_ELEM(LCMCCNData.site_first_pt, writer);
 458                 CV_WRITE_SEQ_ELEM(LCMCCNData.edge_node.pt, writer );
 459                 index+=2;
 460                 pLCMEdge = _cvConstructLCMEdge(pLCM,&LCMOutputData);
 461                 _cvAttachLCMEdgeToLCMNode(pLCMNode,pLCMEdge,pLCMEdge_prev,index - 1,0);
 462                 CV_WRITE_SEQ_ELEM(LCMCCNData.site_last_pt, writer);
 463                 index++;
 464
 465                 pSite = CV_TWIN_VORONOISITE2D(pSite,pEdge);
 466                 pEdge_stop = CV_FIRST_VORONOIEDGE2D(pSite);
 467                 if(pSite == pSite_last)
 468                     break;
 469             }
 470         }
 471         if(pSite == pSite_last)
 472             break;
 473
 474         CV_WRITE_SEQ_ELEM(pSite->node[1]->pt, writer);
 475         index++;
 476     }
 477
 478     if(pLCMEdge_prev)
 479         pLCMEdge_prev->next[(pLCMEdge_prev == (CvLCMEdge*)pLCMNode->first)] = pLCMNode->first;
 480     cvEndWriteSeq(&writer);
 481     return pLCMNode;
 482 }//end of _cvConstructLCMComplexNode
 483
 484 CvLCMNode* _cvConstructLCMSimpleNode(CvLCM* pLCM,
 485                                      CvLCMEdge* pLCMEdge,
 486                                      CvLCMData* pLCMInputData)
 487 {
 488     CvVoronoiEdge2D* pEdge = pLCMInputData->pedge;
 489     CvVoronoiSite2D* pSite = pLCMInputData->psite;
 490     CvVoronoiNode2D* pNode = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
 491
 492     CvVoronoiEdge2D* LinkedEdges[10];
 493     CvVoronoiSite2D* LinkedSites[10];
 494     int multyplicity = _cvNodeMultyplicity(pSite,pEdge,pNode,LinkedEdges,LinkedSites);
 495     if(multyplicity == 2)
 496     {
 497         pLCMInputData->pedge = LinkedEdges[1];
 498         pLCMInputData->psite = CV_TWIN_VORONOISITE2D(LinkedSites[1],LinkedEdges[1]);
 499         return NULL;
 500     }
 501
 502     CvLCMEdge* pLCMEdge_prev = NULL;
 503     CvLCMNode* pLCMNode;
 504     CvLCMData LCMOutputData;
 505
 506     pLCMNode = _cvCreateLCMNode(pLCM);
 507     cvSeqPush((CvSeq*)pLCMNode->contour,&pNode->pt);
 508     _cvAttachLCMEdgeToLCMNode(pLCMNode,pLCMEdge,pLCMEdge_prev,0,1);
 509
 510     for(int i = (int)(pLCMEdge != NULL);i < multyplicity; i++)
 511     {
 512         pEdge = LinkedEdges[i];
 513         pSite = LinkedSites[i];
 514         _CV_INITIALIZE_CVLCMDATA(&LCMOutputData,CV_TWIN_VORONOISITE2D(pSite,pEdge),pEdge,pNode);
 515         pLCMEdge = _cvConstructLCMEdge(pLCM,&LCMOutputData);
 516         _cvAttachLCMEdgeToLCMNode(pLCMNode,pLCMEdge,pLCMEdge_prev,0,0);
 517     }
 518     pLCMEdge_prev->next[(pLCMEdge_prev == (CvLCMEdge*)pLCMNode->first)] = pLCMNode->first;
 519     return pLCMNode;
 520 }//end of _cvConstructLCMSimpleNode
 521
 522 CvLCMEdge* _cvConstructLCMEdge(CvLCM* pLCM,
 523                                CvLCMData* pLCMInputData)
 524 {
 525     CvVoronoiEdge2D* pEdge = pLCMInputData->pedge;
 526     CvVoronoiSite2D* pSite = pLCMInputData->psite;
 527     float width = 0;
 528
 529     CvLCMData LCMData;
 530     CvVoronoiNode2D* pNode0,*pNode1;
 531
 532     CvLCMEdge* pLCMEdge = _cvCreateLCMEdge(pLCM);
 533
 534     CvSeqWriter writer;
 535     cvStartAppendToSeq(pLCMEdge->chain,&writer );
 536
 537     pNode0 = pNode1 = pLCMInputData->pnode;
 538     CV_WRITE_SEQ_ELEM(pNode0->pt, writer);
 539     width += pNode0->radius;
 540
 541     for(int counter = 0;
 542             counter < pLCM->VoronoiDiagram->edges->total;
 543             counter++)
 544     {
 545         pNode1 = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
 546         if(pNode1->radius >= pLCM->maxWidth)
 547             goto CREATECOMPLEXNODE;
 548
 549         CV_WRITE_SEQ_ELEM(pNode1->pt,writer);
 550         width += pNode1->radius;
 551         _CV_INITIALIZE_CVLCMDATA(&LCMData,pSite,pEdge,pNode1);
 552         if(_cvConstructLCMSimpleNode(pLCM,pLCMEdge,&LCMData))
 553             goto LCMEDGEEXIT;
 554
 555         pEdge = LCMData.pedge; pSite = LCMData.psite;
 556         pNode0 = pNode1;
 557     }
 558     return NULL;
 559
 560 CREATECOMPLEXNODE:
 561     _CV_INITIALIZE_CVLCMDATA(&LCMData,pSite,pEdge,pNode0);
 562     CV_WRITE_SEQ_ELEM(LCMData.pnode->pt,writer);
 563     width += LCMData.pnode->radius;
 564     _cvConstructLCMComplexNode(pLCM,pLCMEdge,&LCMData);
 565
 566 LCMEDGEEXIT:
 567     cvEndWriteSeq(&writer);
 568     pLCMEdge->width = width/pLCMEdge->chain->total;
 569     return pLCMEdge;
 570 }//end of _cvConstructLCMEdge
 571
 572 CvLCMNode* _cvTreatExeptionalCase(CvLCM* pLCM,
 573                                   CvLCMData* pLCMInputData)
 574 {
 575     CvVoronoiEdge2D* pEdge = pLCMInputData->pedge;
 576     CvVoronoiSite2D* pSite = pLCMInputData->psite;
 577     CvVoronoiNode2D* pNode = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
 578     CvLCMNode* pLCMNode = _cvCreateLCMNode(pLCM);
 579     cvSeqPush((CvSeq*)pLCMNode->contour,&pNode->pt);
 580     return pLCMNode;
 581 }//end of _cvConstructLCMEdge
 582
 583 CV_INLINE
 584 CvLCMNode* _cvCreateLCMNode(CvLCM* pLCM)
 585 {
 586     CvLCMNode* pLCMNode;
 587     cvSetAdd((CvSet*)pLCM->Graph, NULL, (CvSetElem**)&pLCMNode );
 588     pLCMNode->contour = (CvContour*)cvCreateSeq(0, sizeof(CvContour),
 589                                                    sizeof(CvPoint2D32f),pLCM->ContourStorage);
 590     pLCMNode->first = NULL;
 591     return pLCMNode;
 592 }//end of _cvCreateLCMNode
 593
 594 CV_INLINE
 595 CvLCMEdge* _cvCreateLCMEdge(CvLCM* pLCM)
 596 {
 597     CvLCMEdge* pLCMEdge;
 598     cvSetAdd( (CvSet*)(pLCM->Graph->edges), 0, (CvSetElem**)&pLCMEdge );
 599     pLCMEdge->chain = cvCreateSeq(0, sizeof(CvSeq),sizeof(CvPoint2D32f),pLCM->EdgeStorage);
 600     pLCMEdge->next[0] = pLCMEdge->next[1] = NULL;
 601     pLCMEdge->vtx[0] =  pLCMEdge->vtx[1] = NULL;
 602     pLCMEdge->index1 =  pLCMEdge->index2 = -1;
 603     return pLCMEdge;
 604 }//end of _cvCreateLCMEdge
 605
 606 CV_INLINE
 607 void _cvAttachLCMEdgeToLCMNode(CvLCMNode* LCMNode,
 608                                CvLCMEdge* LCMEdge,
 609                                CvLCMEdge* &LCMEdge_prev,
 610                                int index,
 611                                int i)
 612 {
 613     if(!LCMEdge)
 614         return;
 615     if(i==0)
 616         LCMEdge->index1 = index;
 617     else
 618         LCMEdge->index2 = index;
 619
 620     LCMEdge->vtx[i] = (CvGraphVtx*)LCMNode;
 621     if(!LCMEdge_prev)
 622         LCMNode->first = (CvGraphEdge*)LCMEdge;
 623     else
 624 //      LCMEdge_prev->next[(LCMEdge_prev == (CvLCMEdge*)LCMNode->first)] = (CvGraphEdge*)LCMEdge;
 625         LCMEdge_prev->next[(LCMEdge_prev->vtx[0] != (CvGraphVtx*)LCMNode)] = (CvGraphEdge*)LCMEdge;
 626
 627     LCMEdge->next[i] = LCMNode->first;
 628     LCMEdge_prev = LCMEdge;
 629 }//end of _cvAttachLCMEdgeToLCMNode
 630
 631
 632 int _cvNodeMultyplicity(CvVoronoiSite2D* pSite,
 633                         CvVoronoiEdge2D* pEdge,
 634                         CvVoronoiNode2D* pNode,
 635                         CvVoronoiEdge2D** LinkedEdges,
 636                         CvVoronoiSite2D** LinkedSites)
 637 {
 638     if(!pNode->radius)
 639         return -1;
 640     assert(pNode == CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite));
 641
 642     int multyplicity = 0;
 643     CvVoronoiEdge2D* pEdge_cur = pEdge;
 644     do
 645     {
 646         if(pEdge_cur->node[0]->radius && pEdge_cur->node[1]->radius)
 647         {
 648             LinkedEdges[multyplicity] = pEdge_cur;
 649             LinkedSites[multyplicity] = pSite;
 650             multyplicity++;
 651         }
 652         pEdge_cur = CV_PREV_VORONOIEDGE2D(pEdge_cur,pSite);
 653         pSite = CV_TWIN_VORONOISITE2D(pSite,pEdge_cur);
 654     }while(pEdge_cur != pEdge);
 655     return multyplicity;
 656 }//end of _cvNodeMultyplicity
 657
 658
 659 CV_INLINE
 660 void _cvPrepareData(CvLCMComplexNodeData* pLCMCCNData,
 661                     CvLCMData* pLCMData)
 662 {
 663     pLCMCCNData->site_first = pLCMData->psite;
 664     pLCMCCNData->site_last = CV_TWIN_VORONOISITE2D(pLCMData->psite,pLCMData->pedge);
 665     if(pLCMData->pedge == CV_LAST_VORONOIEDGE2D(pLCMData->psite))
 666     {
 667         pLCMCCNData->edge = CV_PREV_VORONOIEDGE2D(pLCMData->pedge,pLCMData->psite);
 668         pLCMCCNData->edge_node = *pLCMData->pnode;
 669         pLCMCCNData->site_first_pt = pLCMData->psite->node[0]->pt;
 670         pLCMCCNData->site_last_pt = pLCMData->psite->node[0]->pt;
 671     }
 672     else
 673     {
 674         pLCMCCNData->edge = pLCMData->pedge;
 675         pLCMCCNData->edge_node = *pLCMData->pnode;
 676         _cvProjectionPointToSegment(&pLCMCCNData->edge_node.pt,
 677                                   &pLCMCCNData->site_first->node[0]->pt,
 678                                   &pLCMCCNData->site_first->node[1]->pt,
 679                                   &pLCMCCNData->site_first_pt,
 680                                   NULL);
 681         _cvProjectionPointToSegment(&pLCMCCNData->edge_node.pt,
 682                                   &pLCMCCNData->site_last->node[0]->pt,
 683                                   &pLCMCCNData->site_last->node[1]->pt,
 684                                   &pLCMCCNData->site_last_pt,
 685                                   NULL);
 686     }
 687 }//end of _cvPrepareData
 688
 689
 690 void _cvProjectionPointToSegment(CvPoint2D32f* PointO,
 691                                  CvPoint2D32f* PointA,
 692                                  CvPoint2D32f* PointB,
 693                                  CvPoint2D32f* PrPoint,
 694                                  float* dist)
 695 {
 696     float scal_AO_AB, scal_AB_AB;
 697     CvPoint2D32f VectorAB = {PointB->x - PointA->x, PointB->y - PointA->y};
 698     scal_AB_AB = VectorAB.x*VectorAB.x + VectorAB.y*VectorAB.y;
 699     if(scal_AB_AB < LCM_CONST_ZERO)
 700     {
 701         *PrPoint = *PointA;
 702         if(dist)
 703             *dist = (float)sqrt( (double)(PointO->x -PointA->x)*(PointO->x -PointA->x) + (PointO->y - PointA->y)*(PointO->y - PointA->y));
 704         return;
 705     }
 706
 707     CvPoint2D32f VectorAO = {PointO->x - PointA->x, PointO->y - PointA->y};
 708     scal_AO_AB = VectorAO.x*VectorAB.x + VectorAO.y*VectorAB.y;
 709
 710     if(dist)
 711     {
 712         float vector_AO_AB = (float)fabs(VectorAO.x*VectorAB.y - VectorAO.y*VectorAB.x);
 713         *dist = (float)(vector_AO_AB/sqrt((double)scal_AB_AB));
 714     }
 715
 716     float alfa = scal_AO_AB/scal_AB_AB;
 717     PrPoint->x = PointO->x - VectorAO.x + alfa*VectorAB.x;
 718     PrPoint->y = PointO->y - VectorAO.y + alfa*VectorAB.y;
 719     return;
 720 }//end of _cvProjectionPointToSegment
 721
 722
 723
 724