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 47const float LCM_CONST_ZERO = 1e-6f; 48 49/****************************************************************************************\ 50* Auxiliary struct definitions * 51\****************************************************************************************/ 52typedef struct CvLCM 53{ 54 CvGraph* Graph; 55 CvVoronoiDiagram2D* VoronoiDiagram; 56 CvMemStorage* ContourStorage; 57 CvMemStorage* EdgeStorage; 58 float maxWidth; 59} CvLCM; 60 61typedef 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 71typedef 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*/ 106CV_IMPL 107int _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*/ 121CV_IMPL 122CvLCMNode* _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*/ 138CV_IMPL 139CvLCMNode* _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*/ 153CV_IMPL 154CvLCMEdge* _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*/ 167CV_IMPL 168CvLCMNode* _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*/ 186CV_IMPL 187int _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*/ 202CV_IMPL 203CvLCMNode* _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*/ 214CV_IMPL 215CvLCMEdge* _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*/ 231CV_IMPL 232void _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*/ 249CV_IMPL 250void _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*/ 266CV_IMPL 267void _cvPrepareData(CvLCMComplexNodeData* pLCMCCNData, 268 CvLCMData* pLCMData); 269 270/****************************************************************************************\ 271* Function realization * 272\****************************************************************************************/ 273 274CV_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 316CV_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 351int _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 394PREPARECOMPLEXNODE: 395 _CV_INITIALIZE_CVLCMDATA(&LCMdata,pSite,pEdge,CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite)); 396 if(!_cvConstructLCMComplexNode(LCM,NULL,&LCMdata)) 397 return 0; 398 continue; 399 400PREPARESIMPLENODE: 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 409CvLCMNode* _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 484CvLCMNode* _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 522CvLCMEdge* _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 560CREATECOMPLEXNODE: 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 566LCMEDGEEXIT: 567 cvEndWriteSeq(&writer); 568 pLCMEdge->width = width/pLCMEdge->chain->total; 569 return pLCMEdge; 570}//end of _cvConstructLCMEdge 571 572CvLCMNode* _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 583CV_INLINE 584CvLCMNode* _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 594CV_INLINE 595CvLCMEdge* _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 606CV_INLINE 607void _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 632int _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 659CV_INLINE 660void _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 690void _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