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