1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
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.
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.
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.
42 /* Hybrid linear-contour model reconstruction */
45 #define CV_IMPL CV_EXTERN_C
47 const float LCM_CONST_ZERO = 1e-6f;
49 /****************************************************************************************\
50 * Auxiliary struct definitions *
51 \****************************************************************************************/
55 CvVoronoiDiagram2D* VoronoiDiagram;
56 CvMemStorage* ContourStorage;
57 CvMemStorage* EdgeStorage;
61 typedef struct CvLCMComplexNodeData
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;
71 typedef struct CvLCMData
73 CvVoronoiNode2D* pnode;
74 CvVoronoiSite2D* psite;
75 CvVoronoiEdge2D* pedge;
79 /****************************************************************************************\
80 * Function definitions *
81 \****************************************************************************************/
83 #define _CV_READ_SEQ_ELEM( elem, reader, type ) \
85 assert( (reader).seq->elem_size == sizeof(*elem)); \
86 elem = (type)(reader).ptr; \
87 CV_NEXT_SEQ_ELEM( sizeof(*elem), reader ) \
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] ) )
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
103 // Returns: 1, if hybrid model was succesfully constructed
104 // 0, if some error occures
107 int _cvConstructLCM(CvLCM* LCM);
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
117 // pLCMEdge: in, input edge of hybrid model
118 // pLCMInputData: in, input parameters
119 // Returns: pointer to constructed node
122 CvLCMNode* _cvConstructLCMComplexNode(CvLCM* pLCM,
124 CvLCMData* pLCMInputData);
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
134 // pLCMEdge: in, input edge of hybrid model
135 // pLCMInputData: in, input parameters
136 // Returns: pointer to constructed node
139 CvLCMNode* _cvConstructLCMSimpleNode(CvLCM* pLCM,
141 CvLCMData* pLCMInputData);
143 /*F///////////////////////////////////////////////////////////////////////////////////////
144 // Author: Andrey Sobolev
145 // Name: _cvConstructLCMSimpleNode
146 // Purpose: Function constructs Edge of hybrid model
150 // pLCMInputData: in, input parameters
151 // Returns: pointer to constructed edge
154 CvLCMEdge* _cvConstructLCMEdge(CvLCM* pLCM,
155 CvLCMData* pLCMInputData);
157 /*F///////////////////////////////////////////////////////////////////////////////////////
158 // Author: Andrey Sobolev
159 // Name: _cvTreatExeptionalCase
160 // Purpose: Function treats triangles and regular polygons
163 // pLCM : in, information about graph
164 // pLCMInputData: in, input parameters
165 // Returns: pointer to graph node
168 CvLCMNode* _cvTreatExeptionalCase(CvLCM* pLCM,
169 CvLCMData* pLCMInputData);
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
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)
187 int _cvNodeMultyplicity(CvVoronoiSite2D* pSite,
188 CvVoronoiEdge2D* pEdge,
189 CvVoronoiNode2D* pNode,
190 CvVoronoiEdge2D** LinkedEdges,
191 CvVoronoiSite2D** LinkedSites);
193 /*F///////////////////////////////////////////////////////////////////////////////////////
194 // Author: Andrey Sobolev
195 // Name: _cvCreateLCMNode
196 // Purpose: Function create graph node
199 // pLCM : in, information about graph
200 // Returns: pointer to graph node
203 CvLCMNode* _cvCreateLCMNode(CvLCM* pLCM);
205 /*F///////////////////////////////////////////////////////////////////////////////////////
206 // Author: Andrey Sobolev
207 // Name: _cvCreateLCMEdge
208 // Purpose: Function create graph edge
211 // pLCM : in, information about graph
212 // Returns: pointer to graph edge
215 CvLCMEdge* _cvCreateLCMEdge(CvLCM* pLCM);
217 /*F///////////////////////////////////////////////////////////////////////////////////////
218 // Author: Andrey Sobolev
219 // Name: _cvCreateLCMNode
220 // Purpose: Function establishs the connection between node and ege
223 // LCMNode : in, graph node
224 // LCMEdge : in, graph edge
225 // LCMEdge_prev : in&out, previous edge, connected with given node
227 // i : =0, if node is initial for edge
228 // =1, if node is terminal for edge
232 void _cvAttachLCMEdgeToLCMNode(CvLCMNode* LCMNode,
234 CvLCMEdge* &LCMEdge_prev,
237 /*F///////////////////////////////////////////////////////////////////////////////////////
238 // Author: Andrey Sobolev
239 // Name: _cvProjectionPointToSegment
240 // Purpose: Function computes the ortogonal projection of PointO to
241 // to segment[PointA, PointB]
244 // PointO, PointA,PointB: in, given points
245 // PrPoint : out, projection
246 // dist : distance from PointO to PrPoint
250 void _cvProjectionPointToSegment(CvPoint2D32f* PointO,
251 CvPoint2D32f* PointA,
252 CvPoint2D32f* PointB,
253 CvPoint2D32f* PrPoint,
256 /*F///////////////////////////////////////////////////////////////////////////////////////
257 // Author: Andrey Sobolev
258 // Name: _cvPrepareData
259 // Purpose: Function fills up the struct CvLCMComplexNodeData
267 void _cvPrepareData(CvLCMComplexNodeData* pLCMCCNData,
268 CvLCMData* pLCMData);
270 /****************************************************************************************\
271 * Function realization *
272 \****************************************************************************************/
274 CV_IMPL CvGraph* cvLinearContorModelFromVoronoiDiagram(CvVoronoiDiagram2D* VoronoiDiagram,
277 CvMemStorage* LCMstorage;
279 CvLCM LCM = {NULL, VoronoiDiagram,NULL,NULL,maxWidth};
281 CV_FUNCNAME( "cvLinearContorModelFromVoronoiDiagram" );
284 if( !VoronoiDiagram )
285 CV_ERROR( CV_StsBadArg,"Voronoi Diagram is not defined" );
287 CV_ERROR( CV_StsBadArg,"Treshold parameter must be non negative" );
289 for(SiteSet = VoronoiDiagram->sites;
291 SiteSet = (CvSet*)SiteSet->h_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" );
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,
308 if(!_cvConstructLCM(&LCM))
309 cvReleaseLinearContorModelStorage(&LCM.Graph);
314 }//end of cvLinearContorModelFromVoronoiDiagram
316 CV_IMPL int cvReleaseLinearContorModelStorage(CvGraph** Graph)
318 CvSeq* LCMNodeSeq, *LCMEdgeSeq;
322 /*CV_FUNCNAME( "cvReleaseLinearContorModelStorage" );*/
325 if(!Graph || !(*Graph))
328 LCMNodeSeq = (CvSeq*)(*Graph);
329 LCMEdgeSeq = (CvSeq*)(*Graph)->edges;
330 if(LCMNodeSeq->total > 0)
332 pLCMNode = (CvLCMNode*)cvGetSeqElem(LCMNodeSeq,0);
333 if(pLCMNode->contour->storage)
334 cvReleaseMemStorage(&pLCMNode->contour->storage);
336 if(LCMEdgeSeq->total > 0)
338 pLCMEdge = (CvLCMEdge*)cvGetSeqElem(LCMEdgeSeq,0);
339 if(pLCMEdge->chain->storage)
340 cvReleaseMemStorage(&pLCMEdge->chain->storage);
342 if((*Graph)->storage)
343 cvReleaseMemStorage(&(*Graph)->storage);
349 }//end of cvReleaseLinearContorModelStorage
351 int _cvConstructLCM(CvLCM* LCM)
353 CvVoronoiSite2D* pSite = 0;
354 CvVoronoiEdge2D* pEdge = 0, *pEdge1;
355 CvVoronoiNode2D* pNode, *pNode1;
357 CvVoronoiEdge2D* LinkedEdges[10];
358 CvVoronoiSite2D* LinkedSites[10];
364 for(CvSet* SiteSet = LCM->VoronoiDiagram->sites;
366 SiteSet = (CvSet*)SiteSet->h_next)
368 cvStartReadSeq((CvSeq*)SiteSet, &reader);
369 for(i = 0; i < SiteSet->total; i++)
371 _CV_READ_SEQ_ELEM(pSite,reader,CvVoronoiSite2D*);
372 if(pSite->node[0] == pSite->node[1])
374 pEdge = CV_LAST_VORONOIEDGE2D(pSite);
375 pNode = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
376 if(pNode->radius > LCM->maxWidth)
377 goto PREPARECOMPLEXNODE;
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)
385 if(_cvNodeMultyplicity(pSite, pEdge,pNode,LinkedEdges,LinkedSites) == 1)
386 goto PREPARESIMPLENODE;
388 // treate triangle or regular polygon
389 _CV_INITIALIZE_CVLCMDATA(&LCMdata,pSite,pEdge,CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite));
390 if(!_cvTreatExeptionalCase(LCM,&LCMdata))
395 _CV_INITIALIZE_CVLCMDATA(&LCMdata,pSite,pEdge,CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite));
396 if(!_cvConstructLCMComplexNode(LCM,NULL,&LCMdata))
401 _CV_INITIALIZE_CVLCMDATA(&LCMdata,pSite,pEdge,CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite));
402 if(!_cvConstructLCMSimpleNode(LCM,NULL,&LCMdata))
407 }//end of _cvConstructLCM
409 CvLCMNode* _cvConstructLCMComplexNode(CvLCM* pLCM,
411 CvLCMData* pLCMInputData)
414 CvLCMEdge* pLCMEdge_prev = NULL;
416 CvVoronoiSite2D* pSite, *pSite_first, *pSite_last;
417 CvVoronoiEdge2D* pEdge, *pEdge_stop;
418 CvVoronoiNode2D* pNode0, *pNode1;
419 CvLCMData LCMOutputData;
420 CvLCMComplexNodeData LCMCCNData;
423 _cvPrepareData(&LCMCCNData,pLCMInputData);
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);
433 CV_WRITE_SEQ_ELEM(LCMCCNData.edge_node.pt, writer );
434 CV_WRITE_SEQ_ELEM(LCMCCNData.site_first_pt, writer );
438 pSite_first = LCMCCNData.site_first;
439 pSite_last = LCMCCNData.site_last;
440 pEdge = LCMCCNData.edge;
442 for(pSite = pSite_first;
444 pSite = CV_NEXT_VORONOISITE2D(pSite),
445 pEdge = CV_PREV_VORONOIEDGE2D(CV_LAST_VORONOIEDGE2D(pSite),pSite))
447 pEdge_stop = CV_FIRST_VORONOIEDGE2D(pSite);
448 for(;pEdge && pEdge != pEdge_stop;
449 pEdge = CV_PREV_VORONOIEDGE2D(pEdge,pSite))
451 pNode0 = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
452 pNode1 = CV_VORONOIEDGE2D_ENDNODE(pEdge,pSite);
453 if(pNode0->radius <= pLCM->maxWidth && pNode1->radius <= pLCM->maxWidth)
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 );
460 pLCMEdge = _cvConstructLCMEdge(pLCM,&LCMOutputData);
461 _cvAttachLCMEdgeToLCMNode(pLCMNode,pLCMEdge,pLCMEdge_prev,index - 1,0);
462 CV_WRITE_SEQ_ELEM(LCMCCNData.site_last_pt, writer);
465 pSite = CV_TWIN_VORONOISITE2D(pSite,pEdge);
466 pEdge_stop = CV_FIRST_VORONOIEDGE2D(pSite);
467 if(pSite == pSite_last)
471 if(pSite == pSite_last)
474 CV_WRITE_SEQ_ELEM(pSite->node[1]->pt, writer);
479 pLCMEdge_prev->next[(pLCMEdge_prev == (CvLCMEdge*)pLCMNode->first)] = pLCMNode->first;
480 cvEndWriteSeq(&writer);
482 }//end of _cvConstructLCMComplexNode
484 CvLCMNode* _cvConstructLCMSimpleNode(CvLCM* pLCM,
486 CvLCMData* pLCMInputData)
488 CvVoronoiEdge2D* pEdge = pLCMInputData->pedge;
489 CvVoronoiSite2D* pSite = pLCMInputData->psite;
490 CvVoronoiNode2D* pNode = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
492 CvVoronoiEdge2D* LinkedEdges[10];
493 CvVoronoiSite2D* LinkedSites[10];
494 int multyplicity = _cvNodeMultyplicity(pSite,pEdge,pNode,LinkedEdges,LinkedSites);
495 if(multyplicity == 2)
497 pLCMInputData->pedge = LinkedEdges[1];
498 pLCMInputData->psite = CV_TWIN_VORONOISITE2D(LinkedSites[1],LinkedEdges[1]);
502 CvLCMEdge* pLCMEdge_prev = NULL;
504 CvLCMData LCMOutputData;
506 pLCMNode = _cvCreateLCMNode(pLCM);
507 cvSeqPush((CvSeq*)pLCMNode->contour,&pNode->pt);
508 _cvAttachLCMEdgeToLCMNode(pLCMNode,pLCMEdge,pLCMEdge_prev,0,1);
510 for(int i = (int)(pLCMEdge != NULL);i < multyplicity; i++)
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);
518 pLCMEdge_prev->next[(pLCMEdge_prev == (CvLCMEdge*)pLCMNode->first)] = pLCMNode->first;
520 }//end of _cvConstructLCMSimpleNode
522 CvLCMEdge* _cvConstructLCMEdge(CvLCM* pLCM,
523 CvLCMData* pLCMInputData)
525 CvVoronoiEdge2D* pEdge = pLCMInputData->pedge;
526 CvVoronoiSite2D* pSite = pLCMInputData->psite;
530 CvVoronoiNode2D* pNode0,*pNode1;
532 CvLCMEdge* pLCMEdge = _cvCreateLCMEdge(pLCM);
535 cvStartAppendToSeq(pLCMEdge->chain,&writer );
537 pNode0 = pNode1 = pLCMInputData->pnode;
538 CV_WRITE_SEQ_ELEM(pNode0->pt, writer);
539 width += pNode0->radius;
542 counter < pLCM->VoronoiDiagram->edges->total;
545 pNode1 = CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite);
546 if(pNode1->radius >= pLCM->maxWidth)
547 goto CREATECOMPLEXNODE;
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))
555 pEdge = LCMData.pedge; pSite = LCMData.psite;
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);
567 cvEndWriteSeq(&writer);
568 pLCMEdge->width = width/pLCMEdge->chain->total;
570 }//end of _cvConstructLCMEdge
572 CvLCMNode* _cvTreatExeptionalCase(CvLCM* pLCM,
573 CvLCMData* pLCMInputData)
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);
581 }//end of _cvConstructLCMEdge
584 CvLCMNode* _cvCreateLCMNode(CvLCM* pLCM)
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;
592 }//end of _cvCreateLCMNode
595 CvLCMEdge* _cvCreateLCMEdge(CvLCM* pLCM)
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;
604 }//end of _cvCreateLCMEdge
607 void _cvAttachLCMEdgeToLCMNode(CvLCMNode* LCMNode,
609 CvLCMEdge* &LCMEdge_prev,
616 LCMEdge->index1 = index;
618 LCMEdge->index2 = index;
620 LCMEdge->vtx[i] = (CvGraphVtx*)LCMNode;
622 LCMNode->first = (CvGraphEdge*)LCMEdge;
624 // LCMEdge_prev->next[(LCMEdge_prev == (CvLCMEdge*)LCMNode->first)] = (CvGraphEdge*)LCMEdge;
625 LCMEdge_prev->next[(LCMEdge_prev->vtx[0] != (CvGraphVtx*)LCMNode)] = (CvGraphEdge*)LCMEdge;
627 LCMEdge->next[i] = LCMNode->first;
628 LCMEdge_prev = LCMEdge;
629 }//end of _cvAttachLCMEdgeToLCMNode
632 int _cvNodeMultyplicity(CvVoronoiSite2D* pSite,
633 CvVoronoiEdge2D* pEdge,
634 CvVoronoiNode2D* pNode,
635 CvVoronoiEdge2D** LinkedEdges,
636 CvVoronoiSite2D** LinkedSites)
640 assert(pNode == CV_VORONOIEDGE2D_BEGINNODE(pEdge,pSite));
642 int multyplicity = 0;
643 CvVoronoiEdge2D* pEdge_cur = pEdge;
646 if(pEdge_cur->node[0]->radius && pEdge_cur->node[1]->radius)
648 LinkedEdges[multyplicity] = pEdge_cur;
649 LinkedSites[multyplicity] = pSite;
652 pEdge_cur = CV_PREV_VORONOIEDGE2D(pEdge_cur,pSite);
653 pSite = CV_TWIN_VORONOISITE2D(pSite,pEdge_cur);
654 }while(pEdge_cur != pEdge);
656 }//end of _cvNodeMultyplicity
660 void _cvPrepareData(CvLCMComplexNodeData* pLCMCCNData,
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))
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;
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,
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,
687 }//end of _cvPrepareData
690 void _cvProjectionPointToSegment(CvPoint2D32f* PointO,
691 CvPoint2D32f* PointA,
692 CvPoint2D32f* PointB,
693 CvPoint2D32f* PrPoint,
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)
703 *dist = (float)sqrt( (double)(PointO->x -PointA->x)*(PointO->x -PointA->x) + (PointO->y - PointA->y)*(PointO->y - PointA->y));
707 CvPoint2D32f VectorAO = {PointO->x - PointA->x, PointO->y - PointA->y};
708 scal_AO_AB = VectorAO.x*VectorAB.x + VectorAO.y*VectorAB.y;
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));
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;
720 }//end of _cvProjectionPointToSegment