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 725
