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
cvLinearContorModelFromVoronoiDiagram(CvVoronoiDiagram2D * VoronoiDiagram,float maxWidth)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
cvReleaseLinearContorModelStorage(CvGraph ** Graph)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
_cvConstructLCM(CvLCM * LCM)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
_cvConstructLCMComplexNode(CvLCM * pLCM,CvLCMEdge * pLCMEdge,CvLCMData * pLCMInputData)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
_cvConstructLCMSimpleNode(CvLCM * pLCM,CvLCMEdge * pLCMEdge,CvLCMData * pLCMInputData)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
_cvConstructLCMEdge(CvLCM * pLCM,CvLCMData * pLCMInputData)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
_cvTreatExeptionalCase(CvLCM * pLCM,CvLCMData * pLCMInputData)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
_cvCreateLCMNode(CvLCM * pLCM)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
_cvCreateLCMEdge(CvLCM * pLCM)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
_cvAttachLCMEdgeToLCMNode(CvLCMNode * LCMNode,CvLCMEdge * LCMEdge,CvLCMEdge * & LCMEdge_prev,int index,int i)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
_cvNodeMultyplicity(CvVoronoiSite2D * pSite,CvVoronoiEdge2D * pEdge,CvVoronoiNode2D * pNode,CvVoronoiEdge2D ** LinkedEdges,CvVoronoiSite2D ** LinkedSites)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
_cvPrepareData(CvLCMComplexNodeData * pLCMCCNData,CvLCMData * pLCMData)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
_cvProjectionPointToSegment(CvPoint2D32f * PointO,CvPoint2D32f * PointA,CvPoint2D32f * PointB,CvPoint2D32f * PrPoint,float * dist)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