/*M/////////////////////////////////////////////////////////////////////////////////////// // // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. // // By downloading, copying, installing or using the software you agree to this license. // If you do not agree to this license, do not download, install, // copy or use the software. // // // Intel License Agreement // For Open Source Computer Vision Library // // Copyright (C) 2000, Intel Corporation, all rights reserved. // Third party copyrights are property of their respective owners. // // Redistribution and use in source and binary forms, with or without modification, // are permitted provided that the following conditions are met: // // * Redistribution's of source code must retain the above copyright notice, // this list of conditions and the following disclaimer. // // * Redistribution's in binary form must reproduce the above copyright notice, // this list of conditions and the following disclaimer in the documentation // and/or other materials provided with the distribution. // // * The name of Intel Corporation may not be used to endorse or promote products // derived from this software without specific prior written permission. // // This software is provided by the copyright holders and contributors "as is" and // any express or implied warranties, including, but not limited to, the implied // warranties of merchantability and fitness for a particular purpose are disclaimed. // In no event shall the Intel Corporation or contributors be liable for any direct, // indirect, incidental, special, exemplary, or consequential damages // (including, but not limited to, procurement of substitute goods or services; // loss of use, data, or profits; or business interruption) however caused // and on any theory of liability, whether in contract, strict liability, // or tort (including negligence or otherwise) arising in any way out of // the use of this software, even if advised of the possibility of such damage. // //M*/ /* Reconstruction of contour skeleton */ #include "_cvaux.h" #include #define NEXT_SEQ(seq,seq_first) ((seq) == (seq_first) ? seq->v_next : seq->h_next) #define SIGN(x) ( x<0 ? -1:( x>0 ? 1:0 ) ) const float LEE_CONST_ZERO = 1e-6f; const float LEE_CONST_DIFF_POINTS = 1e-2f; const float LEE_CONST_ACCEPTABLE_ERROR = 1e-4f; /****************************************************************************************\ * Auxiliary struct definitions * \****************************************************************************************/ template struct CvLeePoint { T x,y; }; typedef CvLeePoint CvPointFloat; typedef CvLeePoint CvDirection; struct CvVoronoiSiteInt; struct CvVoronoiEdgeInt; struct CvVoronoiNodeInt; struct CvVoronoiParabolaInt; struct CvVoronoiChainInt; struct CvVoronoiHoleInt; struct CvVoronoiDiagramInt { CvSeq* SiteSeq; CvSeq* EdgeSeq; CvSeq* NodeSeq; CvSeq* ChainSeq; CvSeq* ParabolaSeq; CvSeq* DirectionSeq; CvSeq* HoleSeq; CvVoronoiSiteInt* reflex_site; CvVoronoiHoleInt* top_hole; }; struct CvVoronoiStorageInt { CvMemStorage* SiteStorage; CvMemStorage* EdgeStorage; CvMemStorage* NodeStorage; CvMemStorage* ChainStorage; CvMemStorage* ParabolaStorage; CvMemStorage* DirectionStorage; CvMemStorage* HoleStorage; }; struct CvVoronoiNodeInt { CvPointFloat node; float radius; }; struct CvVoronoiSiteInt { CvVoronoiNodeInt* node1; CvVoronoiNodeInt* node2; CvVoronoiEdgeInt* edge1; CvVoronoiEdgeInt* edge2; CvVoronoiSiteInt* next_site; CvVoronoiSiteInt* prev_site; CvDirection* direction; }; struct CvVoronoiEdgeInt { CvVoronoiNodeInt* node1; CvVoronoiNodeInt* node2; CvVoronoiSiteInt* site; CvVoronoiEdgeInt* next_edge; CvVoronoiEdgeInt* prev_edge; CvVoronoiEdgeInt* twin_edge; CvVoronoiParabolaInt* parabola; CvDirection* direction; }; struct CvVoronoiParabolaInt { float map[6]; float a; CvVoronoiNodeInt* focus; CvVoronoiSiteInt* directrice; }; struct CvVoronoiChainInt { CvVoronoiSiteInt * first_site; CvVoronoiSiteInt * last_site; CvVoronoiChainInt* next_chain; }; struct CvVoronoiHoleInt { CvSeq* SiteSeq; CvSeq* ChainSeq; CvVoronoiSiteInt* site_top; CvVoronoiSiteInt* site_nearest; CvVoronoiSiteInt* site_opposite; CvVoronoiNodeInt* node; CvVoronoiHoleInt* next_hole; bool error; float x_coord; }; typedef CvVoronoiSiteInt* pCvVoronoiSite; typedef CvVoronoiEdgeInt* pCvVoronoiEdge; typedef CvVoronoiNodeInt* pCvVoronoiNode; typedef CvVoronoiParabolaInt* pCvVoronoiParabola; typedef CvVoronoiChainInt* pCvVoronoiChain; typedef CvVoronoiHoleInt* pCvVoronoiHole; typedef CvPointFloat* pCvPointFloat; typedef CvDirection* pCvDirection; /****************************************************************************************\ * Function definitions * \****************************************************************************************/ /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvLee // Purpose: Compute Voronoi Diagram for one given polygon with holes // Context: // Parameters: // ContourSeq : in, vertices of polygon. // VoronoiDiagramInt : in&out, pointer to struct, which contains the // description of Voronoi Diagram. // VoronoiStorage: in, storage for Voronoi Diagram. // contour_type: in, type of vertices. // The possible values are CV_LEE_INT,CV_LEE_FLOAT,CV_LEE_DOUBLE. // contour_orientation: in, orientation of polygons. // = 1, if contour is left - oriented in left coordinat system // =-1, if contour is left - oriented in right coordinat system // attempt_number: in, number of unsuccessful attemts made by program to compute // the Voronoi Diagram befor return the error // // Returns: 1, if Voronoi Diagram was succesfully computed // 0, if some error occures //F*/ static int _cvLee(CvSeq* ContourSeq, CvVoronoiDiagramInt* pVoronoiDiagramInt, CvMemStorage* VoronoiStorage, CvLeeParameters contour_type, int contour_orientation, int attempt_number); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvConstuctSites // Purpose : Compute sites for given polygon with holes // (site is an edge of polygon or a reflex vertex). // Context: // Parameters: // ContourSeq : in, vertices of polygon // pVoronoiDiagram : in, pointer to struct, which contains the // description of Voronoi Diagram // contour_type: in, type of vertices. The possible values are // CV_LEE_INT,CV_LEE_FLOAT,CV_LEE_DOUBLE. // contour_orientation: in, orientation of polygons. // = 1, if contour is left - oriented in left coordinat system // =-1, if contour is left - oriented in right coordinat system // Return: 1, if sites were succesfully constructed // 0, if some error occures //F*/ static int _cvConstuctSites(CvSeq* ContourSeq, CvVoronoiDiagramInt* pVoronoiDiagram, CvLeeParameters contour_type, int contour_orientation); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvConstructChains // Purpose : Compute chains for given polygon with holes. // Context: // Parameters: // pVoronoiDiagram : in, pointer to struct, which contains the // description of Voronoi Diagram // Return: 1, if chains were succesfully constructed // 0, if some error occures //F*/ static int _cvConstructChains(CvVoronoiDiagramInt* pVoronoiDiagram); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvConstructSkeleton // Purpose: Compute skeleton for given collection of sites, using Lee algorithm // Context: // Parameters: // VoronoiDiagram : in, pointer to struct, which contains the // description of Voronoi Diagram. // Returns: 1, if skeleton was succesfully computed // 0, if some error occures //F*/ static int _cvConstructSkeleton(CvVoronoiDiagramInt* pVoronoiDiagram); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvConstructSiteTree // Purpose: Construct tree of sites (by analogy with contour tree). // Context: // Parameters: // VoronoiDiagram : in, pointer to struct, which contains the // description of Voronoi Diagram. // Returns: //F*/ static void _cvConstructSiteTree(CvVoronoiDiagramInt* pVoronoiDiagram); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvReleaseVoronoiStorage // Purpose : Function realease storages. // The storages are divided into two groups: // SiteStorage, EdgeStorage, NodeStorage form the first group; // ChainStorage,ParabolaStorage,DirectionStorage,HoleStorage form the second group. // Context: // Parameters: // pVoronoiStorage: in, // group1,group2: in, if group1<>0 then storages from first group released // if group2<>0 then storages from second group released // Return : //F*/ static void _cvReleaseVoronoiStorage(CvVoronoiStorageInt* pVoronoiStorage, int group1, int group2); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvConvert // Purpose : Function convert internal representation of VD (via // structs CvVoronoiSiteInt, CvVoronoiEdgeInt,CvVoronoiNodeInt) into // external representation of VD (via structs CvVoronoiSite2D, CvVoronoiEdge2D, // CvVoronoiNode2D) // Context: // Parameters: // VoronoiDiagram: in // VoronoiStorage: in // change_orientation: in, if = -1 then the convertion is accompanied with change // of orientation // // Return: 1, if convertion was succesfully completed // 0, if some error occures //F*/ /* static int _cvConvert(CvVoronoiDiagram2D* VoronoiDiagram, CvMemStorage* VoronoiStorage, int change_orientation); */ static int _cvConvert(CvVoronoiDiagram2D* VoronoiDiagram, CvVoronoiDiagramInt VoronoiDiagramInt, CvSet* &NewSiteSeqPrev, CvSeqWriter &NodeWriter, CvSeqWriter &EdgeWriter, CvMemStorage* VoronoiStorage, int change_orientation); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvConvertSameOrientation // Purpose : Function convert internal representation of VD (via // structs CvVoronoiSiteInt, CvVoronoiEdgeInt,CvVoronoiNodeInt) into // external representation of VD (via structs CvVoronoiSite2D, CvVoronoiEdge2D, // CvVoronoiNode2D) without change of orientation // Context: // Parameters: // VoronoiDiagram: in // VoronoiStorage: in / // Return: 1, if convertion was succesfully completed // 0, if some error occures //F*/ /* static int _cvConvertSameOrientation(CvVoronoiDiagram2D* VoronoiDiagram, CvMemStorage* VoronoiStorage); */ static int _cvConvertSameOrientation(CvVoronoiDiagram2D* VoronoiDiagram, CvVoronoiDiagramInt VoronoiDiagramInt, CvSet* &NewSiteSeqPrev, CvSeqWriter &NodeWriter, CvSeqWriter &EdgeWriter, CvMemStorage* VoronoiStorage); /*F/////////////////////////////////////////////////////////////////////////////////////// // Author: Andrey Sobolev // Name: _cvConvertChangeOrientation // Purpose : Function convert internal representation of VD (via // structs CvVoronoiSiteInt, CvVoronoiEdgeInt,CvVoronoiNodeInt) into // external representation of VD (via structs CvVoronoiSite2D, CvVoronoiEdge2D, // CvVoronoiNode2D) with change of orientation // Context: // Parameters: // VoronoiDiagram: in // VoronoiStorage: in / // Return: 1, if convertion was succesfully completed // 0, if some error occures //F*/ /* static int _cvConvertChangeOrientation(CvVoronoiDiagram2D* VoronoiDiagram, CvMemStorage* VoronoiStorage); */ static int _cvConvertChangeOrientation(CvVoronoiDiagram2D* VoronoiDiagram, CvVoronoiDiagramInt VoronoiDiagramInt, CvSet* &NewSiteSeqPrev, CvSeqWriter &NodeWriter, CvSeqWriter &EdgeWriter, CvMemStorage* VoronoiStorage); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute sites for external polygon. Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram ContourSeq : in, vertices of polygon pReflexSite: out, pointer to reflex site,if any exist,else NULL orientation: in, orientation of contour ( = 1 or = -1) type: in, type of vertices. The possible values are (int)1, (float)1,(double)1. Return: 1, if sites were succesfully constructed 0, if some error occures : --------------------------------------------------------------------------*/ template int _cvConstructExtSites(CvVoronoiDiagramInt* pVoronoiDiagram, CvSeq* ContourSeq, int orientation, T /*type*/); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute sites for internal polygon (for hole). Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram CurrSiteSeq: in, the sequence for sites to be constructed CurrContourSeq : in, vertices of polygon pTopSite: out, pointer to the most left site of polygon (it is the most left vertex of polygon) orientation: in, orientation of contour ( = 1 or = -1) type: in, type of vertices. The possible values are (int)1, (float)1,(double)1. Return: 1, if sites were succesfully constructed 0, if some error occures : --------------------------------------------------------------------------*/ template int _cvConstructIntSites(CvVoronoiDiagramInt* pVoronoiDiagram, CvSeq* CurrSiteSeq, CvSeq* CurrContourSeq, pCvVoronoiSite &pTopSite, int orientation, T /*type*/); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the simple chains of sites for external polygon. Arguments pVoronoiDiagram : in&out, pointer to struct, which contains the description of Voronoi Diagram Return: 1, if chains were succesfully constructed 0, if some error occures --------------------------------------------------------------------------*/ static int _cvConstructExtChains(CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the simple chains of sites for internal polygon (= hole) Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram CurrSiteSeq : in, the sequence of sites CurrChainSeq : in,the sequence for chains to be constructed pTopSite : in, the most left site of hole Return : --------------------------------------------------------------------------*/ static void _cvConstructIntChains(CvVoronoiDiagramInt* pVoronoiDiagram, CvSeq* CurrChainSeq, CvSeq* CurrSiteSeq, pCvVoronoiSite pTopSite); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the initial Voronoi Diagram for single site Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pSite: in, pointer to site Return : --------------------------------------------------------------------------*/ static void _cvConstructEdges(pCvVoronoiSite pSite,CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function moves each node on small random value. The nodes are taken from pVoronoiDiagram->NodeSeq. Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram begin,end: in, the first and the last nodes in pVoronoiDiagram->NodeSeq, which moves shift: in, the value of maximal shift. Return : --------------------------------------------------------------------------*/ static void _cvRandomModification(CvVoronoiDiagramInt* pVoronoiDiagram, int begin, int end, float shift); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the internal Voronoi Diagram for external polygon. Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram Return : 1, if VD was constructed succesfully 0, if some error occure --------------------------------------------------------------------------*/ static int _cvConstructExtVD(CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the external Voronoi Diagram for each internal polygon (hole). Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram Return : --------------------------------------------------------------------------*/ static void _cvConstructIntVD(CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function joins the Voronoi Diagrams of different chains into one Voronoi Diagram Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pChain1,pChain1: in, given chains Return : 1, if joining was succesful 0, if some error occure --------------------------------------------------------------------------*/ static int _cvJoinChains(pCvVoronoiChain pChain1, pCvVoronoiChain pChain2, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function finds the nearest site for top vertex (= the most left vertex) of each hole Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram Return : --------------------------------------------------------------------------*/ static void _cvFindNearestSite(CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function seeks for site, which has common bisector in final VD with top vertex of given hole. It stores in pHole->opposite_site. The search begins from Hole->nearest_site and realizes in clockwise direction around the top vertex of given hole. Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pHole : in, given hole Return : 1, if the search was succesful 0, if some error occure --------------------------------------------------------------------------*/ static int _cvFindOppositSiteCW(pCvVoronoiHole pHole, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function seeks for site, which has common bisector in final VD with top vertex of given hole. It stores in pHole->opposite_site. The search begins from Hole->nearest_site and realizes in counterclockwise direction around the top vertex of given hole. Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pHole : in, given hole Return : 1, if the search was succesful 0, if some error occure --------------------------------------------------------------------------*/ static int _cvFindOppositSiteCCW(pCvVoronoiHole pHole,CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function merges external VD of hole and internal VD, which was constructed ealier. Arguments pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pHole : in, given hole Return : 1, if merging was succesful 0, if some error occure --------------------------------------------------------------------------*/ static int _cvMergeVD(pCvVoronoiHole pHole,CvVoronoiDiagramInt* pVoronoiDiagram); /* /////////////////////////////////////////////////////////////////////////////////////// // Computation of bisectors // /////////////////////////////////////////////////////////////////////////////////////// */ /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the bisector of two sites Arguments pSite_left,pSite_right: in, given sites pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pEdge : out, bisector Return : --------------------------------------------------------------------------*/ void _cvCalcEdge(pCvVoronoiSite pSite_left, pCvVoronoiSite pSite_right, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the bisector of point and site Arguments pSite : in, site pNode : in, point pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pEdge : out, bisector Return : --------------------------------------------------------------------------*/ void _cvCalcEdge(pCvVoronoiSite pSite, pCvVoronoiNode pNode, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the bisector of point and site Arguments pSite : in, site pNode : in, point pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pEdge : out, bisector Return : --------------------------------------------------------------------------*/ void _cvCalcEdge(pCvVoronoiNode pNode, pCvVoronoiSite pSite, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the direction of bisector of two segments Arguments pDirection1: in, direction of first segment pDirection2: in, direction of second segment pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pEdge : out, bisector Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvCalcEdgeLL(pCvDirection pDirection1, pCvDirection pDirection2, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the bisector of two points Arguments pPoint1, pPoint2: in, given points pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pEdge : out, bisector Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvCalcEdgePP(pCvPointFloat pPoint1, pCvPointFloat pPoint2, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the bisector of segment and point. Since it is parabola, it is defined by its focus (site - point) and directrice(site-segment) Arguments pFocus : in, point, which defines the focus of parabola pDirectrice: in, site - segment, which defines the directrice of parabola pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pEdge : out, bisector Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvCalcEdgePL(pCvVoronoiNode pFocus, pCvVoronoiSite pDirectrice, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Compute the bisector of segment and point. Since it is parabola, it is defined by its focus (site - point) and directrice(site-segment) Arguments pFocus : in, point, which defines the focus of parabola pDirectrice: in, site - segment, which defines the directrice of parabola pVoronoiDiagram : in, pointer to struct, which contains the description of Voronoi Diagram pEdge : out, bisector Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvCalcEdgeLP(pCvVoronoiSite pDirectrice, pCvVoronoiNode pFocus, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram); /* /////////////////////////////////////////////////////////////////////////////////////// // Computation of intersections of bisectors // /////////////////////////////////////////////////////////////////////////////////////// */ /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1,pEdge2: in, two edges pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvCalcEdgeIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, CvPointFloat* pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, straight ray pEdge2: in, straight ray or segment pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvLine_LineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, straight ray pEdge2: in, parabolic ray or segment pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvLine_ParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, straight ray pEdge2: in, parabolic segment pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvLine_CloseParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, straight ray pEdge2: in, parabolic ray pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvLine_OpenParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, parabolic ray pEdge2: in, straight ray or segment pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvPar_LineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, parabolic ray pEdge2: in, straight ray pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvPar_OpenLineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, parabolic ray pEdge2: in, straight segment pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvPar_CloseLineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, parabolic ray pEdge2: in, parabolic ray or segment pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvPar_ParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, parabolic ray pEdge2: in, parabolic ray pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvPar_OpenParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes intersection of two edges. Intersection must be the nearest to the marked point on pEdge1 (this marked point is pEdge1->node1->node). Arguments pEdge1 : in, parabolic ray pEdge2: in, parabolic segment pPoint: out, intersection of pEdge1 and pEdge2 Radius: out, distance between pPoint and sites, assosiated with pEdge1 and pEdge2 (pPoint is situated on the equal distance from site, assosiated with pEdge1 and from site,assosiated with pEdge2) Return : distance between pPoint and marked point on pEdge1 or : -1, if edges have no intersections --------------------------------------------------------------------------*/ static float _cvPar_CloseParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius); /* /////////////////////////////////////////////////////////////////////////////////////// // Subsidiary functions // /////////////////////////////////////////////////////////////////////////////////////// */ /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Arguments pEdge1 : in pEdge2 : out Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvMakeTwinEdge(pCvVoronoiEdge pEdge2, pCvVoronoiEdge pEdge1); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Arguments pEdge : in&out pEdge_left_prev : in&out pSite_left : in&out Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvStickEdgeLeftBegin(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_left_prev, pCvVoronoiSite pSite_left); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Arguments pEdge : in&out pEdge_right_next : in&out pSite_right : in&out Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvStickEdgeRightBegin(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_right_next, pCvVoronoiSite pSite_right); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Arguments pEdge : in&out pEdge_left_next : in&out pSite_left : in&out Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvStickEdgeLeftEnd(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_left_next, pCvVoronoiSite pSite_left); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Arguments pEdge : in&out pEdge_right_prev : in&out pSite_right : in&out Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvStickEdgeRightEnd(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_right_prev, pCvVoronoiSite pSite_right); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Arguments pEdge_left_cur : in pEdge_left : in Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvTwinNULLLeft(pCvVoronoiEdge pEdge_left_cur, pCvVoronoiEdge pEdge_left); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Arguments pEdge_right_cur : in pEdge_right : in Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvTwinNULLRight(pCvVoronoiEdge pEdge_right_cur, pCvVoronoiEdge pEdge_right); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function initializes the struct CvVoronoiNode Arguments pNode : out pPoint : in, radius : in Return : --------------------------------------------------------------------------*/ template CV_INLINE void _cvInitVoronoiNode(pCvVoronoiNode pNode, T pPoint, float radius = 0); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function initializes the struct CvVoronoiSite Arguments pSite : out pNode1,pNode2,pPrev_site : in Return : --------------------------------------------------------------------------*/ CV_INLINE void _cvInitVoronoiSite(pCvVoronoiSite pSite, pCvVoronoiNode pNode1, pCvVoronoiNode pNode2, pCvVoronoiSite pPrev_site); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function pushs the element in the end of the sequence end returns its adress Arguments Seq : in, pointer to the sequence Elem : in, element Return : pointer to the element in the sequence --------------------------------------------------------------------------*/ template CV_INLINE T _cvSeqPush(CvSeq* Seq, T pElem); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function pushs the element in the begin of the sequence end returns its adress Arguments Seq : in, pointer to the sequence Elem : in, element Return : pointer to the element in the sequence --------------------------------------------------------------------------*/ template CV_INLINE T _cvSeqPushFront(CvSeq* Seq, T pElem); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function pushs the element pHole in pHoleHierarchy->HoleSeq so as all elements in this sequence would be normalized according to field .x_coord of element. pHoleHierarchy->TopHole points to hole with smallest x_coord. Arguments pHoleHierarchy : in, pointer to the structur pHole : in, element Return : pointer to the element in the sequence --------------------------------------------------------------------------*/ CV_INLINE void _cvSeqPushInOrder(CvVoronoiDiagramInt* pVoronoiDiagram, pCvVoronoiHole pHole); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function intersects given edge pEdge (and his twin edge) by point pNode on two parts Arguments pEdge : in, given edge pNode : in, given point EdgeSeq : in Return : one of parts --------------------------------------------------------------------------*/ CV_INLINE pCvVoronoiEdge _cvDivideRightEdge(pCvVoronoiEdge pEdge, pCvVoronoiNode pNode, CvSeq* EdgeSeq); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function intersects given edge pEdge (and his twin edge) by point pNode on two parts Arguments pEdge : in, given edge pNode : in, given point EdgeSeq : in Return : one of parts --------------------------------------------------------------------------*/ CV_INLINE pCvVoronoiEdge _cvDivideLeftEdge(pCvVoronoiEdge pEdge, pCvVoronoiNode pNode, CvSeq* EdgeSeq); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : function pushs the element in the end of the sequence end returns its adress Arguments writer: in, writer associated with sequence pElem : in, element Return : pointer to the element in the sequence --------------------------------------------------------------------------*/ template CV_INLINE T _cvWriteSeqElem(T pElem, CvSeqWriter &writer); /* /////////////////////////////////////////////////////////////////////////////////////// // Mathematical functions // /////////////////////////////////////////////////////////////////////////////////////// */ /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function changes x and y Arguments x,y : in&out Return : --------------------------------------------------------------------------*/ template CV_INLINE void _cvSwap(T &x, T &y); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes the inverse map to the given ortogonal affine map Arguments A : in, given ortogonal affine map B : out, inverse map Return : 1, if inverse map exist 0, else --------------------------------------------------------------------------*/ template CV_INLINE int _cvCalcOrtogInverse(T* B, T* A); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes the composition of two affine maps Arguments A,B : in, given affine maps Result: out, composition of A and B (Result = AB) Return : --------------------------------------------------------------------------*/ template CV_INLINE void _cvCalcComposition(T* Result,T* A,T* B); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes the image of point under given affin map Arguments A : in, affine maps pPoint : in, pointer to point pImgPoint:out, pointer to image of point Return : --------------------------------------------------------------------------*/ template CV_INLINE void _cvCalcPointImage(pCvPointFloat pImgPoint,pCvPointFloat pPoint,T* A); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes the image of vector under given affin map Arguments A : in, affine maps pVector : in, pointer to vector pImgVector:out, pointer to image of vector Return : --------------------------------------------------------------------------*/ template CV_INLINE void _cvCalcVectorImage(pCvDirection pImgVector,pCvDirection pVector,T* A); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes the distance between the point and site. Internal function. Arguments pPoint : in, point pSite : in, site Return : distance --------------------------------------------------------------------------*/ CV_INLINE float _cvCalcDist(pCvPointFloat pPoint, pCvVoronoiSite pSite); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes the distance between two points Arguments pPoint1,pPoint2 : in, two points Return : distance --------------------------------------------------------------------------*/ CV_INLINE float _cvPPDist(pCvPointFloat pPoint1,pCvPointFloat pPoint2); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function computes the distance betwin point and segment. Internal function. Arguments pPoint: in, point pPoint1,pPoint2 : in, segment [pPoint1,pPoint2] Return : distance --------------------------------------------------------------------------*/ CV_INLINE float _cvPLDist(pCvPointFloat pPoint,pCvPointFloat pPoint1,pCvDirection pDirection); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function solves the squar equation with real coefficients T - float or double Arguments c2,c1,c0: in, real coefficients of polynom X: out, array of roots Return : number of roots --------------------------------------------------------------------------*/ template int _cvSolveEqu2thR(T c2, T c1, T c0, T* X); /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : Function solves the linear equation with real or complex coefficients T - float or double or complex Arguments c1,c0: in, real or complex coefficients of polynom X: out, array of roots Return : number of roots --------------------------------------------------------------------------*/ template CV_INLINE int _cvSolveEqu1th(T c1, T c0, T* X); /****************************************************************************************\ * Storage Block Increase * \****************************************************************************************/ /*-------------------------------------------------------------------------- Author : Andrey Sobolev Description : For each sequence function creates the memory block sufficient to store all elements of sequnce Arguments pVoronoiDiagramInt: in, pointer to struct, which contains the description of Voronoi Diagram. vertices_number: in, number of vertices in polygon Return : --------------------------------------------------------------------------*/ void _cvSetSeqBlockSize(CvVoronoiDiagramInt* pVoronoiDiagramInt,int vertices_number) { int N = 2*vertices_number; cvSetSeqBlockSize(pVoronoiDiagramInt->SiteSeq,N*pVoronoiDiagramInt->SiteSeq->elem_size); cvSetSeqBlockSize(pVoronoiDiagramInt->EdgeSeq,3*N*pVoronoiDiagramInt->EdgeSeq->elem_size); cvSetSeqBlockSize(pVoronoiDiagramInt->NodeSeq,5*N*pVoronoiDiagramInt->NodeSeq->elem_size); cvSetSeqBlockSize(pVoronoiDiagramInt->ParabolaSeq,N*pVoronoiDiagramInt->ParabolaSeq->elem_size); cvSetSeqBlockSize(pVoronoiDiagramInt->DirectionSeq,3*N*pVoronoiDiagramInt->DirectionSeq->elem_size); cvSetSeqBlockSize(pVoronoiDiagramInt->ChainSeq,N*pVoronoiDiagramInt->DirectionSeq->elem_size); cvSetSeqBlockSize(pVoronoiDiagramInt->HoleSeq,100*pVoronoiDiagramInt->HoleSeq->elem_size); } /****************************************************************************************\ * Function realization * \****************************************************************************************/ CV_IMPL int cvVoronoiDiagramFromContour(CvSeq* ContourSeq, CvVoronoiDiagram2D** VoronoiDiagram, CvMemStorage* VoronoiStorage, CvLeeParameters contour_type, int contour_orientation, int attempt_number) { CV_FUNCNAME( "cvVoronoiDiagramFromContour" ); __BEGIN__; CvSet* SiteSeq = NULL; CvSeq* CurContourSeq = NULL; CvVoronoiDiagramInt VoronoiDiagramInt; CvSeqWriter NodeWriter, EdgeWriter; CvMemStorage* storage; memset( &VoronoiDiagramInt, 0, sizeof(VoronoiDiagramInt) ); if( !ContourSeq ) CV_ERROR( CV_StsBadArg,"Contour sequence is empty" ); if(!VoronoiStorage) CV_ERROR( CV_StsBadArg,"Storage is not initialized" ); if( contour_type < 0 || contour_type > 2) CV_ERROR( CV_StsBadArg,"Unsupported parameter: type" ); if( contour_orientation != 1 && contour_orientation != -1) CV_ERROR( CV_StsBadArg,"Unsupported parameter: orientation" ); storage = cvCreateChildMemStorage(VoronoiStorage); (*VoronoiDiagram) = (CvVoronoiDiagram2D*)cvCreateSet(0,sizeof(CvVoronoiDiagram2D),sizeof(CvVoronoiNode2D), storage); storage = cvCreateChildMemStorage(VoronoiStorage); (*VoronoiDiagram)->edges = cvCreateSet(0,sizeof(CvSet),sizeof(CvVoronoiEdge2D), storage); cvStartAppendToSeq((CvSeq*)(*VoronoiDiagram)->edges, &EdgeWriter); cvStartAppendToSeq((CvSeq*)(*VoronoiDiagram), &NodeWriter); for(CurContourSeq = ContourSeq;\ CurContourSeq != NULL;\ CurContourSeq = CurContourSeq->h_next) { if(_cvLee(CurContourSeq, &VoronoiDiagramInt,VoronoiStorage,contour_type,contour_orientation,attempt_number)) { if(!_cvConvert(*VoronoiDiagram,VoronoiDiagramInt,SiteSeq,NodeWriter,EdgeWriter,VoronoiStorage,contour_orientation)) goto exit; } else if(CurContourSeq->total >= 3) goto exit; } cvEndWriteSeq(&EdgeWriter); cvEndWriteSeq(&NodeWriter); if(SiteSeq != NULL) return 1; __END__; return 0; }//end of cvVoronoiDiagramFromContour CV_IMPL int cvVoronoiDiagramFromImage(IplImage* pImage, CvSeq** ContourSeq, CvVoronoiDiagram2D** VoronoiDiagram, CvMemStorage* VoronoiStorage, CvLeeParameters regularization_method, float approx_precision) { CV_FUNCNAME( "cvVoronoiDiagramFromContour" ); int RESULT = 0; __BEGIN__; IplImage* pWorkImage = NULL; CvSize image_size; int i, multiplicator = 3; int approx_method; CvMemStorage* ApproxContourStorage = NULL; CvSeq* ApproxContourSeq = NULL; if( !ContourSeq ) CV_ERROR( CV_StsBadArg,"Contour sequence is not initialized" ); if( (*ContourSeq)->total != 0) CV_ERROR( CV_StsBadArg,"Contour sequence is not empty" ); if(!VoronoiStorage) CV_ERROR( CV_StsBadArg,"Storage is not initialized" ); if(!pImage) CV_ERROR( CV_StsBadArg,"Image is not initialized" ); if(pImage->nChannels != 1 || pImage->depth != 8) CV_ERROR( CV_StsBadArg,"Unsupported image format" ); if(approx_precision<0 && approx_precision != CV_LEE_AUTO) CV_ERROR( CV_StsBadArg,"Unsupported presision value" ); switch(regularization_method) { case CV_LEE_ERODE: image_size.width = pImage->width; image_size.height = pImage->height; pWorkImage = cvCreateImage(image_size,8,1); cvErode(pImage,pWorkImage,0,1); approx_method = CV_CHAIN_APPROX_TC89_L1; break; case CV_LEE_ZOOM: image_size.width = multiplicator*pImage->width; image_size.height = multiplicator*pImage->height; pWorkImage = cvCreateImage(image_size,8,1); cvResize(pImage, pWorkImage, CV_INTER_NN); approx_method = CV_CHAIN_APPROX_TC89_L1; break; case CV_LEE_NON: pWorkImage = pImage; approx_method = CV_CHAIN_APPROX_TC89_L1; break; default: CV_ERROR( CV_StsBadArg,"Unsupported regularisation method" ); break; } cvFindContours(pWorkImage, (*ContourSeq)->storage, ContourSeq, \ sizeof(CvContour), CV_RETR_CCOMP, approx_method ); if(pWorkImage && pWorkImage != pImage ) cvReleaseImage(&pWorkImage); ApproxContourStorage = cvCreateMemStorage(0); if(approx_precision > 0) { ApproxContourSeq = cvApproxPoly(*ContourSeq, sizeof(CvContour), ApproxContourStorage,\ CV_POLY_APPROX_DP,approx_precision,1); RESULT = cvVoronoiDiagramFromContour(ApproxContourSeq,VoronoiDiagram,VoronoiStorage,CV_LEE_INT,-1,10); } else if(approx_precision == CV_LEE_AUTO) { ApproxContourSeq = *ContourSeq; for(i = 1; i < 50; i++) { RESULT = cvVoronoiDiagramFromContour(ApproxContourSeq,VoronoiDiagram,VoronoiStorage,CV_LEE_INT,-1,1); if(RESULT) break; ApproxContourSeq = cvApproxPoly(ApproxContourSeq, sizeof(CvContour),ApproxContourStorage,\ CV_POLY_APPROX_DP,(float)i,1); } } else RESULT = cvVoronoiDiagramFromContour(*ContourSeq,VoronoiDiagram,VoronoiStorage,CV_LEE_INT,-1,10); /* if(ApproxContourSeq) { cvClearMemStorage( (*ContourSeq)->storage ); *ContourSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvPoint),(*ContourSeq)->storage); CvSeqReader reader; CvSeqWriter writer; CvPoint Point; cvStartAppendToSeq(*ContourSeq, &writer); cvStartReadSeq(ApproxContourSeq, &reader); for(int i = 0;i < ApproxContourSeq->total;i++) { CV_READ_SEQ_ELEM(Point,reader); Point.y = 600 - Point.y; CV_WRITE_SEQ_ELEM(Point,writer); } cvEndWriteSeq(&writer); } */ cvReleaseMemStorage(&ApproxContourStorage); __END__; return RESULT; }//end of cvVoronoiDiagramFromImage CV_IMPL void cvReleaseVoronoiStorage(CvVoronoiDiagram2D* VoronoiDiagram, CvMemStorage** pVoronoiStorage) { /*CV_FUNCNAME( "cvReleaseVoronoiStorage" );*/ __BEGIN__; CvSeq* Seq; if(VoronoiDiagram->storage) cvReleaseMemStorage(&VoronoiDiagram->storage); for(Seq = (CvSeq*)VoronoiDiagram->sites; Seq != NULL; Seq = Seq->h_next) if(Seq->storage) cvReleaseMemStorage(&Seq->storage); for(Seq = (CvSeq*)VoronoiDiagram->edges; Seq != NULL; Seq = Seq->h_next) if(Seq->storage) cvReleaseMemStorage(&Seq->storage); if(*pVoronoiStorage) cvReleaseMemStorage(pVoronoiStorage); __END__; }//end of cvReleaseVoronoiStorage static int _cvLee(CvSeq* ContourSeq, CvVoronoiDiagramInt* pVoronoiDiagramInt, CvMemStorage* VoronoiStorage, CvLeeParameters contour_type, int contour_orientation, int attempt_number) { //orientation = 1 for left coordinat system //orientation = -1 for right coordinat system if(ContourSeq->total<3) return 0; int attempt = 0; CvVoronoiStorageInt VoronoiStorageInt; srand((int)time(NULL)); NEXTATTEMPT: VoronoiStorageInt.SiteStorage = cvCreateChildMemStorage(VoronoiStorage); VoronoiStorageInt.NodeStorage = cvCreateChildMemStorage(VoronoiStorage); VoronoiStorageInt.EdgeStorage = cvCreateChildMemStorage(VoronoiStorage); VoronoiStorageInt.ParabolaStorage = cvCreateMemStorage(0); VoronoiStorageInt.ChainStorage = cvCreateMemStorage(0); VoronoiStorageInt.DirectionStorage = cvCreateMemStorage(0); VoronoiStorageInt.HoleStorage = cvCreateMemStorage(0); pVoronoiDiagramInt->SiteSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiSiteInt),VoronoiStorageInt.SiteStorage); pVoronoiDiagramInt->NodeSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiNodeInt),VoronoiStorageInt.NodeStorage); pVoronoiDiagramInt->EdgeSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiEdgeInt),VoronoiStorageInt.EdgeStorage); pVoronoiDiagramInt->ChainSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiChainInt),VoronoiStorageInt.ChainStorage); pVoronoiDiagramInt->DirectionSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvDirection),VoronoiStorageInt.DirectionStorage); pVoronoiDiagramInt->ParabolaSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiParabolaInt),VoronoiStorageInt.ParabolaStorage); pVoronoiDiagramInt->HoleSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiHoleInt),VoronoiStorageInt.HoleStorage); _cvSetSeqBlockSize(pVoronoiDiagramInt,ContourSeq->total); if(!_cvConstuctSites(ContourSeq, pVoronoiDiagramInt, contour_type,contour_orientation)) { attempt = attempt_number; goto FAULT; } _cvRandomModification(pVoronoiDiagramInt, 0,pVoronoiDiagramInt->NodeSeq->total,0.2f); if(!_cvConstructChains(pVoronoiDiagramInt)) { attempt = attempt_number; goto FAULT; } if(!_cvConstructSkeleton(pVoronoiDiagramInt)) goto FAULT; _cvConstructSiteTree(pVoronoiDiagramInt); //SUCCESS: _cvReleaseVoronoiStorage(&VoronoiStorageInt,0,1); return 1; FAULT: _cvReleaseVoronoiStorage(&VoronoiStorageInt,1,1); if(++attempt < attempt_number) goto NEXTATTEMPT; return 0; }// end of _cvLee static int _cvConstuctSites(CvSeq* ContourSeq, CvVoronoiDiagramInt* pVoronoiDiagram, CvLeeParameters contour_type, int contour_orientation) { pVoronoiDiagram->reflex_site = NULL; pVoronoiDiagram->top_hole = NULL; int result = 0; switch(contour_type) { case CV_LEE_INT : result = _cvConstructExtSites(pVoronoiDiagram,ContourSeq,contour_orientation,(int)1); break; case CV_LEE_FLOAT : result = _cvConstructExtSites(pVoronoiDiagram,ContourSeq,contour_orientation,(float)1); break; case CV_LEE_DOUBLE : result = _cvConstructExtSites(pVoronoiDiagram,ContourSeq,contour_orientation,(double)1); break; default: return 0; } if(!result) return 0; CvSeq* CurSiteSeq; CvVoronoiHoleInt Hole = {NULL,NULL,NULL,NULL,NULL,NULL,NULL,false,0}; pCvVoronoiSite pTopSite = 0; for(CvSeq* CurContourSeq = ContourSeq->v_next;\ CurContourSeq != NULL;\ CurContourSeq = CurContourSeq->h_next) { if(CurContourSeq->total == 0) continue; CurSiteSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiSiteInt),pVoronoiDiagram->SiteSeq->storage); switch(contour_type) { case CV_LEE_INT : result = _cvConstructIntSites(pVoronoiDiagram,CurSiteSeq,CurContourSeq,pTopSite,contour_orientation,(int)1); break; case CV_LEE_FLOAT : result = _cvConstructIntSites(pVoronoiDiagram,CurSiteSeq,CurContourSeq,pTopSite,contour_orientation,(float)1); break; case CV_LEE_DOUBLE :result = _cvConstructIntSites(pVoronoiDiagram,CurSiteSeq,CurContourSeq,pTopSite,contour_orientation,(double)1); break; default: result = 0; } if(!result) continue; Hole.SiteSeq = CurSiteSeq; Hole.site_top = pTopSite; Hole.x_coord = pTopSite->node1->node.x; Hole.error = false; _cvSeqPushInOrder(pVoronoiDiagram, &Hole); } return 1; }//end of _cvConstuctSites static int _cvConstructChains(CvVoronoiDiagramInt* pVoronoiDiagram) { if(!_cvConstructExtChains(pVoronoiDiagram)) return 0; CvSeq* CurrChainSeq; for(pCvVoronoiHole pHole = pVoronoiDiagram->top_hole;\ pHole != NULL; \ pHole = pHole->next_hole) { pHole->error = false; CurrChainSeq = cvCreateSeq(0,sizeof(CvSeq),sizeof(CvVoronoiChainInt),pVoronoiDiagram->ChainSeq->storage); _cvConstructIntChains(pVoronoiDiagram,CurrChainSeq,pHole->SiteSeq,pHole->site_top); pHole->ChainSeq = CurrChainSeq; } return 1; }//end of _cvConstructChains static int _cvConstructSkeleton(CvVoronoiDiagramInt* pVoronoiDiagram) { if(!_cvConstructExtVD(pVoronoiDiagram)) return 0; _cvConstructIntVD(pVoronoiDiagram); _cvFindNearestSite(pVoronoiDiagram); float dx,dy; int result; for(pCvVoronoiHole pHole = pVoronoiDiagram->top_hole;\ pHole != NULL; pHole = pHole->next_hole) { if(pHole->error) continue; dx = pHole->node->node.x - pHole->site_top->node1->node.x; dy = pHole->node->node.y - pHole->site_top->node1->node.y; if(fabs(dy) < 0.01 && dx < 0) pHole->site_opposite = pHole->site_nearest; else { if(dy > 0) result = _cvFindOppositSiteCCW(pHole,pVoronoiDiagram); else result = _cvFindOppositSiteCW(pHole,pVoronoiDiagram); if(!result) { pHole->error = true; continue; } } if(!_cvMergeVD(pHole,pVoronoiDiagram)) return 0; } return 1; }//end of _cvConstructSkeleton static void _cvConstructSiteTree(CvVoronoiDiagramInt* pVoronoiDiagram) { CvSeq* CurSeq = pVoronoiDiagram->SiteSeq; for(pCvVoronoiHole pHole = pVoronoiDiagram->top_hole;\ pHole != NULL; pHole = pHole->next_hole) { if(pHole->error) continue; if(CurSeq == pVoronoiDiagram->SiteSeq) { CurSeq->v_next = pHole->SiteSeq; pHole->SiteSeq->v_prev = CurSeq; } else { CurSeq->h_next = pHole->SiteSeq; pHole->SiteSeq->h_prev = CurSeq; pHole->SiteSeq->v_prev = pVoronoiDiagram->SiteSeq; } CurSeq = pHole->SiteSeq; } CurSeq->h_next = NULL; }//end of _cvConstructSiteTree static void _cvRandomModification(CvVoronoiDiagramInt* pVoronoiDiagram, int begin, int end, float shift) { CvSeqReader Reader; pCvVoronoiNode pNode; const float rnd_const = shift/RAND_MAX; int i; cvStartReadSeq(pVoronoiDiagram->NodeSeq, &Reader,0); for( i = begin; i < end; i++) { pNode = (pCvVoronoiNode)Reader.ptr; pNode->node.x = (float)cvFloor(pNode->node.x) + rand()*rnd_const; pNode->node.y = (float)cvFloor(pNode->node.y) + rand()*rnd_const; CV_NEXT_SEQ_ELEM( sizeof(CvVoronoiNodeInt), Reader ); } for(pCvVoronoiHole pHole = pVoronoiDiagram->top_hole;\ pHole != NULL;\ pHole = pHole->next_hole) { pHole->site_top->node1->node.x = (float)cvFloor(pHole->site_top->node1->node.x); } }//end of _cvRandomModification static void _cvReleaseVoronoiStorage(CvVoronoiStorageInt* pVoronoiStorage, int group1, int group2) { //if group1 = 1 then SiteSeq, NodeSeq, EdgeSeq released //if group2 = 1 then DirectionSeq, ParabolaSeq, ChainSeq, HoleSeq released if(group1 == 1) { if(pVoronoiStorage->SiteStorage!=NULL) cvReleaseMemStorage(&pVoronoiStorage->SiteStorage); if(pVoronoiStorage->EdgeStorage!=NULL) cvReleaseMemStorage(&pVoronoiStorage->EdgeStorage); if(pVoronoiStorage->NodeStorage!=NULL) cvReleaseMemStorage(&pVoronoiStorage->NodeStorage); } if(group2 == 1) { if(pVoronoiStorage->ParabolaStorage!=NULL) cvReleaseMemStorage(&pVoronoiStorage->ParabolaStorage); if(pVoronoiStorage->ChainStorage!=NULL) cvReleaseMemStorage(&pVoronoiStorage->ChainStorage); if(pVoronoiStorage->DirectionStorage!=NULL) cvReleaseMemStorage(&pVoronoiStorage->DirectionStorage); if(pVoronoiStorage->HoleStorage != NULL) cvReleaseMemStorage(&pVoronoiStorage->HoleStorage); } }// end of _cvReleaseVoronoiStorage static int _cvConvert(CvVoronoiDiagram2D* VoronoiDiagram, CvVoronoiDiagramInt VoronoiDiagramInt, CvSet* &SiteSeq, CvSeqWriter &NodeWriter, CvSeqWriter &EdgeWriter, CvMemStorage* VoronoiStorage, int contour_orientation) { if(contour_orientation == 1) return _cvConvertSameOrientation(VoronoiDiagram,VoronoiDiagramInt,SiteSeq,NodeWriter, EdgeWriter,VoronoiStorage); else return _cvConvertChangeOrientation(VoronoiDiagram,VoronoiDiagramInt,SiteSeq,NodeWriter, EdgeWriter,VoronoiStorage); }// end of _cvConvert static int _cvConvertSameOrientation(CvVoronoiDiagram2D* VoronoiDiagram, CvVoronoiDiagramInt VoronoiDiagramInt, CvSet* &NewSiteSeqPrev, CvSeqWriter &NodeWriter, CvSeqWriter &EdgeWriter, CvMemStorage* VoronoiStorage) { CvSeq* SiteSeq = VoronoiDiagramInt.SiteSeq; CvSeq* EdgeSeq = VoronoiDiagramInt.EdgeSeq; CvSeq* NodeSeq = VoronoiDiagramInt.NodeSeq; CvMemStorage *NewSiteStorage = cvCreateChildMemStorage(VoronoiStorage); CvSet *NewSiteSeq = NULL,*CurrNewSiteSeq = NULL, *PrevNewSiteSeq = NULL;; CvSeqWriter SiteWriter; CvVoronoiSite2D NewSite = {{0,0},{0,0},{0,0}},NewSite_prev; CvVoronoiSite2D *pNewSite, *pNewSite_prev = &NewSite_prev; pCvVoronoiSite pSite,pFirstSite; CvVoronoiEdge2D NewEdge = {{0,0},{0,0},{0,0,0,0}}; CvVoronoiEdge2D *pNewEdge1, *pNewEdge2; pCvVoronoiEdge pEdge; CvVoronoiNode2D* pNode1, *pNode2; CvVoronoiNode2D Node; Node.next_free = NULL; for(CvSeq* CurrSiteSeq = SiteSeq;\ CurrSiteSeq != NULL;\ CurrSiteSeq = NEXT_SEQ(CurrSiteSeq,SiteSeq)) { CurrNewSiteSeq = cvCreateSet(0,sizeof(CvSet),sizeof(CvVoronoiSite2D), NewSiteStorage); if(!NewSiteSeq) NewSiteSeq = PrevNewSiteSeq = CurrNewSiteSeq; else if(PrevNewSiteSeq->v_prev == NULL) { PrevNewSiteSeq->v_next = (CvSeq*)CurrNewSiteSeq; CurrNewSiteSeq->v_prev = (CvSeq*)PrevNewSiteSeq; } else { PrevNewSiteSeq->h_next = (CvSeq*)CurrNewSiteSeq; CurrNewSiteSeq->h_prev = (CvSeq*)PrevNewSiteSeq; CurrNewSiteSeq->v_prev = (CvSeq*)PrevNewSiteSeq->v_prev; } PrevNewSiteSeq = CurrNewSiteSeq; pSite = pFirstSite = (pCvVoronoiSite)cvGetSeqElem(CurrSiteSeq, 0); while(pSite->prev_site->node1 == pSite->prev_site->node2)\ pSite = pSite->next_site; pFirstSite = pSite; pNewSite_prev = &NewSite_prev; cvStartAppendToSeq((CvSeq*)CurrNewSiteSeq, &SiteWriter); do { pNewSite = _cvWriteSeqElem(&NewSite,SiteWriter); pNewSite->next[0] = pNewSite_prev; pNewSite_prev->next[1] = pNewSite; pEdge = pSite->edge1; if(!pEdge || !pEdge->node1 || !pEdge->node2) return 0; if(pEdge->site == NULL) { pNewEdge1 = (CvVoronoiEdge2D*)pEdge->twin_edge; pNewEdge1->site[1] = pNewSite; pNewSite->node[0] = pNewEdge1->node[0]; } else { pNewEdge1 = _cvWriteSeqElem(&NewEdge,EdgeWriter); pNewEdge1->site[0] = pNewSite; pNode1 = _cvWriteSeqElem(&Node,NodeWriter); pNode2 = _cvWriteSeqElem(&Node,NodeWriter); pNode1->pt.x = pEdge->node1->node.x; pNode1->pt.y = pEdge->node1->node.y; pNode1->radius = pEdge->node1->radius; pNode2->pt.x = pEdge->node2->node.x; pNode2->pt.y = pEdge->node2->node.y; pNode2->radius = pEdge->node2->radius; pNewEdge1->node[0] = pNode1; pNewEdge1->node[1] = pNode2; pNewSite->node[0] = pNewEdge1->node[1]; if(!pNewEdge1->node[0] || !pNewEdge1->node[1]) return 0; pEdge->twin_edge->site = NULL; pEdge->twin_edge->twin_edge = (pCvVoronoiEdge)pNewEdge1; } pNewSite->edge[1] = pNewEdge1; pEdge = pEdge->prev_edge; while((pEdge != NULL && CurrSiteSeq->total>1) || (pEdge != pSite->edge2 && CurrSiteSeq->total == 1)) { if(pEdge->site == NULL) { pNewEdge2 = (CvVoronoiEdge2D*)pEdge->twin_edge; pNewEdge2->site[1] = pNewSite; if(CV_VORONOIEDGE2D_BEGINNODE(pNewEdge1,pNewSite) != pNewEdge2->node[0]) { cvFlushSeqWriter(&NodeWriter); // cvSetRemove((CvSet*)VoronoiDiagram,VoronoiDiagram->total-1); pNewEdge1->node[0] = pNewEdge2->node[0]; } } else { pNewEdge2 = _cvWriteSeqElem(&NewEdge,EdgeWriter); pNewEdge2->site[0] = pNewSite; pNode1 = _cvWriteSeqElem(&Node,NodeWriter); pNode1->pt.x = pEdge->node1->node.x; pNode1->pt.y = pEdge->node1->node.y; pNode1->radius = pEdge->node1->radius; pNewEdge2->node[0] = pNode1; if(pNewEdge1->site[0] == pNewSite) pNewEdge2->node[1] = pNewEdge1->node[0]; else pNewEdge2->node[1] = pNewEdge1->node[1]; if(!pNewEdge1->node[0] || !pNewEdge1->node[1]) return 0; pEdge->twin_edge->site = NULL; pEdge->twin_edge->twin_edge = (pCvVoronoiEdge)pNewEdge2; } if(pNewEdge1->site[0] == pNewSite) pNewEdge1->next[2] = pNewEdge2; else pNewEdge1->next[3] = pNewEdge2; if(pNewEdge2->site[0] == pNewSite) pNewEdge2->next[0] = pNewEdge1; else pNewEdge2->next[1] = pNewEdge1; pEdge = pEdge->prev_edge; pNewEdge1 = pNewEdge2; } pNewSite->edge[0] = pNewEdge1; pNewSite->node[1] = pNewEdge1->node[0]; if(pSite->node1 == pSite->node2 && pSite != pSite->next_site && pNewEdge1->node[0] != pNewEdge1->node[1]) { cvFlushSeqWriter(&NodeWriter); // cvSetRemove((CvSet*)VoronoiDiagram,VoronoiDiagram->total-1); pNewSite->node[1] = pNewEdge1->node[0] = pNewSite->node[0]; } pNewSite_prev = pNewSite; pSite = pSite->next_site; }while(pSite != pFirstSite); pNewSite->node[1] = pNewEdge1->node[1]; if(pSite == pSite->next_site) { Node.pt.x = pSite->node1->node.x; Node.pt.y = pSite->node1->node.y; Node.radius = 0; pNewSite->node[0] = pNewSite->node[1] = _cvWriteSeqElem(&Node,NodeWriter); } cvEndWriteSeq(&SiteWriter); pNewSite = (CvVoronoiSite2D*)cvGetSetElem(CurrNewSiteSeq, 0); pNewSite->next[0] = pNewSite_prev; pNewSite_prev->next[1] = pNewSite; } cvReleaseMemStorage(&(SiteSeq->storage)); cvReleaseMemStorage(&(EdgeSeq->storage)); cvReleaseMemStorage(&(NodeSeq->storage)); if(NewSiteSeqPrev == NULL) VoronoiDiagram->sites = NewSiteSeq; else { NewSiteSeqPrev->h_next = (CvSeq*)NewSiteSeq; NewSiteSeq->h_prev = (CvSeq*)NewSiteSeqPrev; } NewSiteSeqPrev = NewSiteSeq; return 1; }//end of _cvConvertSameOrientation static int _cvConvertChangeOrientation(CvVoronoiDiagram2D* VoronoiDiagram, CvVoronoiDiagramInt VoronoiDiagramInt, CvSet* &NewSiteSeqPrev, CvSeqWriter &NodeWriter, CvSeqWriter &EdgeWriter, CvMemStorage* VoronoiStorage) { // pNewSite->edge[1] = pSite->edge2 // pNewSite->edge[0] = pSite->edge1 CvSeq* SiteSeq = VoronoiDiagramInt.SiteSeq; CvSeq* EdgeSeq = VoronoiDiagramInt.EdgeSeq; CvSeq* NodeSeq = VoronoiDiagramInt.NodeSeq; CvMemStorage *NewSiteStorage = cvCreateChildMemStorage(VoronoiStorage); CvSet *NewSiteSeq = NULL,*CurrNewSiteSeq = NULL, *PrevNewSiteSeq = NULL;; CvSeqWriter SiteWriter; CvVoronoiSite2D NewSite = {{0,0},{0,0},{0,0}},NewSite_prev; CvVoronoiSite2D *pNewSite, *pNewSite_prev = &NewSite_prev; pCvVoronoiSite pSite,pFirstSite; CvVoronoiEdge2D NewEdge = {{0,0},{0,0},{0,0,0,0}}; CvVoronoiEdge2D *pNewEdge1, *pNewEdge2; pCvVoronoiEdge pEdge; CvVoronoiNode2D* pNode1, *pNode2; CvVoronoiNode2D Node; Node.next_free = NULL; for(CvSeq* CurrSiteSeq = SiteSeq;\ CurrSiteSeq != NULL;\ CurrSiteSeq = NEXT_SEQ(CurrSiteSeq,SiteSeq)) { CurrNewSiteSeq = cvCreateSet(0,sizeof(CvSet),sizeof(CvVoronoiSite2D), NewSiteStorage); if(!NewSiteSeq) NewSiteSeq = PrevNewSiteSeq = CurrNewSiteSeq; else if(PrevNewSiteSeq->v_prev == NULL) { PrevNewSiteSeq->v_next = (CvSeq*)CurrNewSiteSeq; CurrNewSiteSeq->v_prev = (CvSeq*)PrevNewSiteSeq; } else { PrevNewSiteSeq->h_next = (CvSeq*)CurrNewSiteSeq; CurrNewSiteSeq->h_prev = (CvSeq*)PrevNewSiteSeq; CurrNewSiteSeq->v_prev = (CvSeq*)PrevNewSiteSeq->v_prev; } PrevNewSiteSeq = CurrNewSiteSeq; pSite = (pCvVoronoiSite)cvGetSeqElem(CurrSiteSeq, 0); while(pSite->next_site->node1 == pSite->next_site->node2)\ pSite = pSite->next_site; pFirstSite = pSite; pNewSite_prev = &NewSite_prev; cvStartAppendToSeq((CvSeq*)CurrNewSiteSeq, &SiteWriter); do { pNewSite = _cvWriteSeqElem(&NewSite,SiteWriter); pNewSite->next[0] = pNewSite_prev; pNewSite_prev->next[1] = pNewSite; pEdge = pSite->edge2; if(!pEdge || !pEdge->node1 || !pEdge->node2) return 0; if(pEdge->site == NULL) { pNewEdge1 = (CvVoronoiEdge2D*)pEdge->twin_edge; pNewEdge1->site[1] = pNewSite; pNewSite->node[0] = pNewEdge1->node[0]; } else { pNewEdge1 = _cvWriteSeqElem(&NewEdge,EdgeWriter); pNewEdge1->site[0] = pNewSite; pNode1 = _cvWriteSeqElem(&Node,NodeWriter); pNode2 = _cvWriteSeqElem(&Node,NodeWriter); pNode1->pt.x = pEdge->node1->node.x; pNode1->pt.y = pEdge->node1->node.y; pNode1->radius = pEdge->node1->radius; pNode2->pt.x = pEdge->node2->node.x; pNode2->pt.y = pEdge->node2->node.y; pNode2->radius = pEdge->node2->radius; pNewEdge1->node[0] = pNode2; pNewEdge1->node[1] = pNode1; pNewSite->node[0] = pNewEdge1->node[1]; if(!pNewEdge1->node[0] || !pNewEdge1->node[1]) return 0; pEdge->twin_edge->site = NULL; pEdge->twin_edge->twin_edge = (pCvVoronoiEdge)pNewEdge1; } pNewSite->edge[1] = pNewEdge1; pEdge = pEdge->next_edge; while((pEdge != NULL && CurrSiteSeq->total>1) || (pEdge != pSite->edge1 && CurrSiteSeq->total == 1)) { if(pEdge->site == NULL) { pNewEdge2 = (CvVoronoiEdge2D*)pEdge->twin_edge; pNewEdge2->site[1] = pNewSite; if(CV_VORONOIEDGE2D_BEGINNODE(pNewEdge1,pNewSite) != pNewEdge2->node[0]) { cvFlushSeqWriter(&NodeWriter); // cvSetRemove((CvSet*)VoronoiDiagram,VoronoiDiagram->total-1); pNewEdge1->node[0] = pNewEdge2->node[0]; } } else { pNewEdge2 = _cvWriteSeqElem(&NewEdge,EdgeWriter); pNewEdge2->site[0] = pNewSite; pNode2 = _cvWriteSeqElem(&Node,NodeWriter); pNode2->pt.x = pEdge->node2->node.x; pNode2->pt.y = pEdge->node2->node.y; pNode2->radius = pEdge->node2->radius; pNewEdge2->node[0] = pNode2; if(pNewEdge1->site[0] == pNewSite) pNewEdge2->node[1] = pNewEdge1->node[0]; else pNewEdge2->node[1] = pNewEdge1->node[1]; if(!pNewEdge1->node[0] || !pNewEdge1->node[1]) return 0; pEdge->twin_edge->site = NULL; pEdge->twin_edge->twin_edge = (pCvVoronoiEdge)pNewEdge2; } if(pNewEdge1->site[0] == pNewSite) pNewEdge1->next[2] = pNewEdge2; else pNewEdge1->next[3] = pNewEdge2; if(pNewEdge2->site[0] == pNewSite) pNewEdge2->next[0] = pNewEdge1; else pNewEdge2->next[1] = pNewEdge1; pEdge = pEdge->next_edge; pNewEdge1 = pNewEdge2; } pNewSite->edge[0] = pNewEdge1; pNewSite->node[1] = pNewEdge1->node[0]; if(pSite->node1 == pSite->node2 && pSite != pSite->next_site && pNewEdge1->node[0] != pNewEdge1->node[1]) { cvFlushSeqWriter(&NodeWriter); // cvSetRemove((CvSet*)VoronoiDiagram,VoronoiDiagram->total-1); pNewSite->node[1] = pNewEdge1->node[0] = pNewSite->node[0]; } pNewSite_prev = pNewSite; pSite = pSite->prev_site; }while(pSite != pFirstSite); pNewSite->node[1] = pNewEdge1->node[1]; if(pSite == pSite->next_site) { Node.pt.x = pSite->node1->node.x; Node.pt.y = pSite->node1->node.y; Node.radius = 0; pNewSite->node[0] = pNewSite->node[1] = _cvWriteSeqElem(&Node,NodeWriter); } cvEndWriteSeq(&SiteWriter); pNewSite = (CvVoronoiSite2D*)cvGetSetElem(CurrNewSiteSeq, 0); pNewSite->next[0] = pNewSite_prev; pNewSite_prev->next[1] = pNewSite; } cvReleaseMemStorage(&(SiteSeq->storage)); cvReleaseMemStorage(&(EdgeSeq->storage)); cvReleaseMemStorage(&(NodeSeq->storage)); if(NewSiteSeqPrev == NULL) VoronoiDiagram->sites = NewSiteSeq; else { NewSiteSeqPrev->h_next = (CvSeq*)NewSiteSeq; NewSiteSeq->h_prev = (CvSeq*)NewSiteSeqPrev; } NewSiteSeqPrev = NewSiteSeq; return 1; }//end of _cvConvert template int _cvConstructExtSites(CvVoronoiDiagramInt* pVoronoiDiagram, CvSeq* ContourSeq, int orientation, T type) { const double angl_eps = 0.03; CvSeq* SiteSeq = pVoronoiDiagram->SiteSeq; CvSeq* NodeSeq = pVoronoiDiagram->NodeSeq; //CvSeq* DirectionSeq = pVoronoiDiagram->DirectionSeq; CvPointFloat Vertex1,Vertex2,Vertex3; CvLeePoint VertexT1,VertexT2,VertexT3; CvSeqReader ContourReader; CvVoronoiSiteInt Site = {NULL,NULL,NULL,NULL,NULL,NULL,NULL}; CvVoronoiSiteInt SiteTemp = {NULL,NULL,NULL,NULL,NULL,NULL,NULL}; CvVoronoiNodeInt Node; pCvVoronoiNode pNode1,pNode2; pCvVoronoiSite pSite = &SiteTemp,pSite_prev = &SiteTemp; pCvVoronoiSite pReflexSite = NULL; int NReflexSite = 0; float delta_x_rc, delta_x_cl, delta_y_rc, delta_y_cl; float norm_cl,norm_rc, mult_cl_rc; float _sin, _cos; int i; if(orientation == 1) { cvStartReadSeq(ContourSeq, &ContourReader,0); CV_READ_SEQ_ELEM(VertexT1,ContourReader); CV_READ_SEQ_ELEM(VertexT2,ContourReader); } else { cvStartReadSeq(ContourSeq, &ContourReader,1); CV_REV_READ_SEQ_ELEM(VertexT1,ContourReader); CV_REV_READ_SEQ_ELEM(VertexT2,ContourReader); } Vertex1.x = (float)VertexT1.x; Vertex1.y = (float)VertexT1.y; Vertex2.x = (float)VertexT2.x; Vertex2.y = (float)VertexT2.y; _cvInitVoronoiNode(&Node, &Vertex2); pNode1 = _cvSeqPush(NodeSeq, &Node); delta_x_cl = Vertex2.x - Vertex1.x; delta_y_cl = Vertex2.y - Vertex1.y; norm_cl = (float)sqrt((double)delta_x_cl*delta_x_cl + delta_y_cl*delta_y_cl); for( i = 0;itotal;i++) { if(orientation == 1) { CV_READ_SEQ_ELEM(VertexT3,ContourReader); } else { CV_REV_READ_SEQ_ELEM(VertexT3,ContourReader); } Vertex3.x = (float)VertexT3.x; Vertex3.y = (float)VertexT3.y; _cvInitVoronoiNode(&Node, &Vertex3); pNode2 = _cvSeqPush(NodeSeq, &Node); delta_x_rc = Vertex3.x - Vertex2.x; delta_y_rc = Vertex3.y - Vertex2.y; norm_rc = (float)sqrt((double)delta_x_rc*delta_x_rc + delta_y_rc*delta_y_rc); if(norm_rc==0) continue; mult_cl_rc = norm_cl*norm_rc; _sin = (delta_y_rc* delta_x_cl - delta_x_rc* delta_y_cl)/mult_cl_rc; _cos = -(delta_x_cl*delta_x_rc + delta_y_cl*delta_y_rc)/mult_cl_rc; if((_sin > angl_eps) || (_sin > 0 && _cos > 0)) { pSite = _cvSeqPush(SiteSeq, &Site); _cvInitVoronoiSite(pSite,pNode1,pNode2,pSite_prev); pSite_prev->next_site = pSite; } else if((_sin < -angl_eps) || (_sin < 0 && _cos > 0)) { pSite = _cvSeqPush(SiteSeq, &Site); _cvInitVoronoiSite(pSite,pNode1,pNode1,pSite_prev); pReflexSite = pSite; NReflexSite++; pSite_prev->next_site = pSite; pSite_prev = pSite; pSite = _cvSeqPush(SiteSeq, &Site); _cvInitVoronoiSite(pSite,pNode1,pNode2,pSite_prev); pSite_prev->next_site = pSite; } else { Vertex2 = Vertex3; delta_y_rc = delta_y_cl + delta_y_rc; delta_x_rc = delta_x_cl + delta_x_rc; pSite->node2 = pNode2; norm_rc = (float)sqrt((double)delta_y_rc*delta_y_rc + delta_x_rc*delta_x_rc); } Vertex2=Vertex3; delta_y_cl= delta_y_rc; delta_x_cl= delta_x_rc; norm_cl = norm_rc; pSite_prev = pSite; pNode1 = pNode2; } if(SiteTemp.next_site==NULL) return 0; if(ContourSeq->total - NReflexSite<2) return 0; if(SiteSeq->total<3) return 0; pSite->node2 = SiteTemp.next_site->node1; pSite->next_site = SiteTemp.next_site; SiteTemp.next_site->prev_site = pSite; i = 0; if(pReflexSite!=NULL) for(i=0; itotal; i++) { if(pReflexSite->next_site->next_site->node1 != pReflexSite->next_site->next_site->node2) break; else pReflexSite = pReflexSite->next_site->next_site; } pVoronoiDiagram->reflex_site = pReflexSite; return (itotal); }//end of _cvConstructExtSites template int _cvConstructIntSites(CvVoronoiDiagramInt* pVoronoiDiagram, CvSeq* CurrSiteSeq, CvSeq* CurrContourSeq, pCvVoronoiSite &pTopSite, int orientation, T type) { const double angl_eps = 0.03; float min_x = (float)999999999; CvSeq* SiteSeq = CurrSiteSeq; CvSeq* NodeSeq = pVoronoiDiagram->NodeSeq; //CvSeq* DirectionSeq = pVoronoiDiagram->DirectionSeq; CvPointFloat Vertex1,Vertex2,Vertex3; CvLeePoint VertexT1,VertexT2,VertexT3; CvSeqReader ContourReader; CvVoronoiSiteInt Site = {NULL,NULL,NULL,NULL,NULL,NULL,NULL}; CvVoronoiSiteInt SiteTemp = {NULL,NULL,NULL,NULL,NULL,NULL,NULL}; CvVoronoiNodeInt Node; pCvVoronoiNode pNode1,pNode2; pCvVoronoiSite pSite = &SiteTemp,pSite_prev = &SiteTemp; pTopSite = NULL; int NReflexSite = 0; if(CurrContourSeq->total == 1) { cvStartReadSeq(CurrContourSeq, &ContourReader,0); CV_READ_SEQ_ELEM(VertexT1,ContourReader); Vertex1.x = (float)VertexT1.x; Vertex1.y = (float)VertexT1.y; _cvInitVoronoiNode(&Node, &Vertex1); pNode1 = _cvSeqPush(NodeSeq, &Node); pTopSite = pSite = _cvSeqPush(SiteSeq, &Site); _cvInitVoronoiSite(pSite,pNode1,pNode1,pSite); pSite->next_site = pSite; return 1; } float delta_x_rc, delta_x_cl, delta_y_rc, delta_y_cl; float norm_cl,norm_rc, mult_cl_rc; float _sin, _cos; int i; if(orientation == 1) { cvStartReadSeq(CurrContourSeq, &ContourReader,0); CV_READ_SEQ_ELEM(VertexT1,ContourReader); CV_READ_SEQ_ELEM(VertexT2,ContourReader); } else { cvStartReadSeq(CurrContourSeq, &ContourReader,1); CV_REV_READ_SEQ_ELEM(VertexT1,ContourReader); CV_REV_READ_SEQ_ELEM(VertexT2,ContourReader); } Vertex1.x = (float)VertexT1.x; Vertex1.y = (float)VertexT1.y; Vertex2.x = (float)VertexT2.x; Vertex2.y = (float)VertexT2.y; _cvInitVoronoiNode(&Node, &Vertex2); pNode1 = _cvSeqPush(NodeSeq, &Node); delta_x_cl = Vertex2.x - Vertex1.x; delta_y_cl = Vertex2.y - Vertex1.y; norm_cl = (float)sqrt((double)delta_x_cl*delta_x_cl + delta_y_cl*delta_y_cl); for( i = 0;itotal;i++) { if(orientation == 1) { CV_READ_SEQ_ELEM(VertexT3,ContourReader); } else { CV_REV_READ_SEQ_ELEM(VertexT3,ContourReader); } Vertex3.x = (float)VertexT3.x; Vertex3.y = (float)VertexT3.y; _cvInitVoronoiNode(&Node, &Vertex3); pNode2 = _cvSeqPush(NodeSeq, &Node); delta_x_rc = Vertex3.x - Vertex2.x; delta_y_rc = Vertex3.y - Vertex2.y; norm_rc = (float)sqrt((double)delta_x_rc*delta_x_rc + delta_y_rc*delta_y_rc); if(norm_rc==0) continue; mult_cl_rc = norm_cl*norm_rc; _sin = (delta_y_rc* delta_x_cl - delta_x_rc* delta_y_cl)/mult_cl_rc; _cos = -(delta_x_cl*delta_x_rc + delta_y_cl*delta_y_rc)/mult_cl_rc; if((_sin > angl_eps) || (_sin > 0 && _cos > 0)) { pSite = _cvSeqPush(SiteSeq, &Site); _cvInitVoronoiSite(pSite,pNode1,pNode2,pSite_prev); pSite_prev->next_site = pSite; } else if((_sin < -angl_eps) || (_sin < 0 && _cos > 0) || (_sin == 0 && CurrContourSeq->total == 2)) { pSite = _cvSeqPush(SiteSeq, &Site); _cvInitVoronoiSite(pSite,pNode1,pNode1,pSite_prev); if(pNode1->node.x < min_x) { min_x = pNode1->node.x; pTopSite = pSite; } NReflexSite++; pSite_prev->next_site = pSite; pSite_prev = pSite; pSite = _cvSeqPush(SiteSeq, &Site); _cvInitVoronoiSite(pSite,pNode1,pNode2,pSite_prev); pSite_prev->next_site = pSite; } else { Vertex2 = Vertex3; delta_y_rc = delta_y_cl + delta_y_rc; delta_x_rc = delta_x_cl + delta_x_rc; norm_rc = (float)sqrt((double)delta_y_rc*delta_y_rc + delta_x_rc*delta_x_rc); pSite->node2 = pNode2; } Vertex1=Vertex2; Vertex2=Vertex3; delta_y_cl= delta_y_rc; delta_x_cl= delta_x_rc; norm_cl = norm_rc; pSite_prev = pSite; pNode1 = pNode2; } if(SiteTemp.next_site==NULL) return 0; if(NReflexSite < 3 && CurrContourSeq->total > 2 || NReflexSite < 2) return 0; pSite->node2 = SiteTemp.next_site->node1; pSite->next_site = SiteTemp.next_site; SiteTemp.next_site->prev_site = pSite; return 1; }//end of _cvConstructIntSites static int _cvConstructExtChains(CvVoronoiDiagramInt* pVoronoiDiagram) { CvSeq* SiteSeq = pVoronoiDiagram->SiteSeq; CvSeq* ChainSeq = pVoronoiDiagram->ChainSeq; CvVoronoiChainInt Chain; pCvVoronoiChain pChain,pChainFirst; pCvVoronoiSite pSite, pSite_prev, pSiteFirst,pReflexSite = pVoronoiDiagram->reflex_site; if(pReflexSite==NULL) pSite = pSiteFirst = (pCvVoronoiSite)cvGetSeqElem(SiteSeq, 0); else { while(pReflexSite->next_site->next_site->node1== pReflexSite->next_site->next_site->node2) pReflexSite = pReflexSite->next_site->next_site; pSite = pSiteFirst = pReflexSite->next_site; } Chain.last_site = pSite; _cvConstructEdges(pSite,pVoronoiDiagram); pSite_prev = pSite; pSite = pSite->prev_site; do { if(pSite->node1!=pSite->node2) { Chain.first_site = pSite_prev; pChain = _cvSeqPushFront(ChainSeq,&Chain); _cvConstructEdges(pSite,pVoronoiDiagram); Chain.last_site = pSite; Chain.next_chain = pChain; } else { pSite=pSite->prev_site; _cvConstructEdges(pSite,pVoronoiDiagram); _cvConstructEdges(pSite->next_site,pVoronoiDiagram); } pSite_prev = pSite; pSite = pSite->prev_site; }while(pSite!=pSiteFirst); Chain.first_site = pSite_prev; pChain = _cvSeqPushFront(ChainSeq,&Chain); pChainFirst = (pCvVoronoiChain)cvGetSeqElem(ChainSeq,ChainSeq->total - 1); pChainFirst->next_chain = pChain; if(ChainSeq->total < 3) return 0; else return 1; }// end of _cvConstructExtChains static void _cvConstructIntChains(CvVoronoiDiagramInt* pVoronoiDiagram, CvSeq* CurrChainSeq, CvSeq* CurrSiteSeq, pCvVoronoiSite pTopSite) { CvSeq* ChainSeq = CurrChainSeq; if(CurrSiteSeq->total == 1) return; CvVoronoiChainInt Chain = {NULL,NULL,NULL}; pCvVoronoiChain pChain,pChainFirst;; pCvVoronoiSite pSite, pSite_prev, pSiteFirst; pSite = pSiteFirst = pTopSite->next_site; Chain.last_site = pSite; _cvConstructEdges(pSite,pVoronoiDiagram); pSite_prev = pSite; pSite = pSite->prev_site; do { if(pSite->node1!=pSite->node2) { Chain.first_site = pSite_prev; pChain = _cvSeqPushFront(ChainSeq,&Chain); _cvConstructEdges(pSite,pVoronoiDiagram); Chain.last_site = pSite; Chain.next_chain = pChain; } else { pSite=pSite->prev_site; if(pSite != pSiteFirst) _cvConstructEdges(pSite,pVoronoiDiagram); _cvConstructEdges(pSite->next_site,pVoronoiDiagram); } pSite_prev = pSite; pSite = pSite->prev_site; }while(pSite!=pSiteFirst && pSite!= pSiteFirst->prev_site); if(pSite == pSiteFirst->prev_site && ChainSeq->total == 0) return; Chain.first_site = pSite_prev; if(pSite == pSiteFirst->prev_site) { pChainFirst = (pCvVoronoiChain)cvGetSeqElem(ChainSeq,ChainSeq->total - 1); pChainFirst->last_site = Chain.last_site; pChainFirst->next_chain = Chain.next_chain; return; } else { pChain = _cvSeqPushFront(ChainSeq,&Chain); pChainFirst = (pCvVoronoiChain)cvGetSeqElem(ChainSeq,ChainSeq->total - 1); pChainFirst->next_chain = pChain; return; } }// end of _cvConstructIntChains CV_INLINE void _cvConstructEdges(pCvVoronoiSite pSite,CvVoronoiDiagramInt* pVoronoiDiagram) { CvSeq* EdgeSeq = pVoronoiDiagram->EdgeSeq; CvSeq* DirectionSeq = pVoronoiDiagram->DirectionSeq; CvVoronoiEdgeInt Edge = {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL}; pCvVoronoiEdge pEdge1,pEdge2; CvDirection EdgeDirection,SiteDirection; float site_lengh; Edge.site = pSite; if(pSite->node1!=pSite->node2) { SiteDirection.x = pSite->node2->node.x - pSite->node1->node.x; SiteDirection.y = pSite->node2->node.y - pSite->node1->node.y; site_lengh = (float)sqrt((double)SiteDirection.x*SiteDirection.x + SiteDirection.y * SiteDirection.y); SiteDirection.x /= site_lengh; SiteDirection.y /= site_lengh; EdgeDirection.x = -SiteDirection.y; EdgeDirection.y = SiteDirection.x; Edge.direction = _cvSeqPush(DirectionSeq,&EdgeDirection); pSite->direction = _cvSeqPush(DirectionSeq,&SiteDirection); pEdge1 = _cvSeqPush(EdgeSeq,&Edge); pEdge2 = _cvSeqPush(EdgeSeq,&Edge); } else { pCvVoronoiSite pSite_prev = pSite->prev_site; pCvVoronoiSite pSite_next = pSite->next_site; pEdge1 = _cvSeqPush(EdgeSeq,&Edge); pEdge2 = _cvSeqPush(EdgeSeq,&Edge); pEdge2->direction = pSite_next->edge1->direction; pEdge2->twin_edge = pSite_next->edge1; pSite_next->edge1->twin_edge = pEdge2; pEdge1->direction = pSite_prev->edge2->direction; pEdge1->twin_edge = pSite_prev->edge2; pSite_prev->edge2->twin_edge = pEdge1; } pEdge2->node1 = pSite->node2; pEdge1->node2 = pSite->node1; pSite->edge1 = pEdge1; pSite->edge2 = pEdge2; pEdge2->next_edge = pEdge1; pEdge1->prev_edge = pEdge2; }// end of _cvConstructEdges static int _cvConstructExtVD(CvVoronoiDiagramInt* pVoronoiDiagram) { pCvVoronoiSite pSite_right = 0,pSite_left = 0; pCvVoronoiEdge pEdge_left,pEdge_right; pCvVoronoiChain pChain1, pChain2; pChain1 = (pCvVoronoiChain)cvGetSeqElem(pVoronoiDiagram->ChainSeq,0); do { pChain2 = pChain1->next_chain; if(pChain2->next_chain==pChain1) { pSite_right = pChain1->first_site; pSite_left = pChain2->last_site; pEdge_left = pSite_left->edge2->next_edge; pEdge_right = pSite_right->edge1->prev_edge; pEdge_left->prev_edge = NULL; pEdge_right->next_edge = NULL; pSite_right->edge1 = NULL; pSite_left->edge2 = NULL; } if(!_cvJoinChains(pChain1,pChain2,pVoronoiDiagram)) return 0; pChain1->last_site = pChain2->last_site; pChain1->next_chain = pChain2->next_chain; pChain1 = pChain1->next_chain; }while(pChain1->next_chain != pChain1); pCvVoronoiNode pEndNode = pSite_left->node2; if(pSite_right->edge1==NULL) return 0; else pSite_right->edge1->node2 = pEndNode; if(pSite_left->edge2==NULL) return 0; else pSite_left->edge2->node1 = pEndNode; return 1; }//end of _cvConstructExtVD static int _cvJoinChains(pCvVoronoiChain pChain1, pCvVoronoiChain pChain2, CvVoronoiDiagramInt* pVoronoiDiagram) { const double dist_eps = 0.05; if(pChain1->first_site == NULL || pChain1->last_site == NULL || pChain2->first_site == NULL || pChain2->last_site == NULL) return 0; CvVoronoiEdgeInt EdgeNULL = {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL}; CvSeq* NodeSeq = pVoronoiDiagram->NodeSeq; CvSeq* EdgeSeq = pVoronoiDiagram->EdgeSeq; pCvVoronoiSite pSite_left = pChain1->last_site; pCvVoronoiSite pSite_right = pChain2->first_site; pCvVoronoiEdge pEdge_left = pSite_left->edge2->next_edge; pCvVoronoiEdge pEdge_right = pSite_right->edge1->prev_edge; pCvVoronoiEdge pEdge_left_cur = pEdge_left; pCvVoronoiEdge pEdge_right_cur = pEdge_right; pCvVoronoiEdge pEdge_left_prev = NULL; pCvVoronoiEdge pEdge_right_next = NULL; pCvVoronoiNode pNode_siteleft = pChain1->first_site->node1; pCvVoronoiNode pNode_siteright = pChain2->last_site->node2; /*CvVoronoiSiteInt Site_left_chain = {pNode_siteleft,pNode_siteleft,NULL,NULL,NULL,NULL}; CvVoronoiSiteInt Site_right_chain = {pNode_siteright,pNode_siteright,NULL,NULL,NULL,NULL};*/ pCvVoronoiEdge pEdge1,pEdge2; CvPointFloat Point1 = {0,0}, Point2 = {0,0}; float radius1,radius2,dist1,dist2; bool left = true,right = true; CvVoronoiNodeInt Node; pCvVoronoiNode pNode_begin = pSite_left->node2; pEdge1 = pSite_left->edge2; pEdge1->node2 = NULL; pEdge2 = pSite_right->edge1; pEdge2->node1 = NULL; for(;;) { if(left) pEdge1->node1 = pNode_begin; if(right) pEdge2->node2 = pNode_begin; pEdge_left = pEdge_left_cur; pEdge_right = pEdge_right_cur; if(left&&right) { _cvCalcEdge(pSite_left,pSite_right,pEdge1,pVoronoiDiagram); _cvMakeTwinEdge(pEdge2,pEdge1); _cvStickEdgeLeftBegin(pEdge1,pEdge_left_prev,pSite_left); _cvStickEdgeRightBegin(pEdge2,pEdge_right_next,pSite_right); } else if(!left) { _cvCalcEdge(pNode_siteleft,pSite_right,pEdge2,pVoronoiDiagram); _cvStickEdgeRightBegin(pEdge2,pEdge_right_next,pSite_right); } else if(!right) { _cvCalcEdge(pSite_left,pNode_siteright,pEdge1,pVoronoiDiagram); _cvStickEdgeLeftBegin(pEdge1,pEdge_left_prev,pSite_left); } dist1=dist2=-1; radius1 = -1; radius2 = -2; while(pEdge_left!=NULL) { if(pEdge_left->node2 == NULL) { pEdge_left_cur = pEdge_left = pEdge_left->next_edge; if(pEdge_left == NULL) break; } if(left) dist1 = _cvCalcEdgeIntersection(pEdge1, pEdge_left, &Point1,radius1); else dist1 = _cvCalcEdgeIntersection(pEdge2, pEdge_left, &Point1,radius1); if(dist1>=0) break; pEdge_left = pEdge_left->next_edge; } while(pEdge_right!=NULL) { if(pEdge_right->node1 == NULL) { pEdge_right_cur = pEdge_right = pEdge_right->prev_edge; if(pEdge_right == NULL) break; } if(left) dist2 = _cvCalcEdgeIntersection(pEdge1, pEdge_right, &Point2, radius2); else dist2 = _cvCalcEdgeIntersection(pEdge2, pEdge_right, &Point2, radius2); if(dist2>=0) break; pEdge_right = pEdge_right->prev_edge; } if(dist1<0&&dist2<0) { if(left) { pEdge_left = pSite_left->edge1; if(pEdge_left==NULL) _cvStickEdgeLeftEnd(pEdge1,NULL,pSite_left); else { while(pEdge_left->node1!=NULL &&pEdge_left->node1==pEdge_left->prev_edge->node2) { pEdge_left = pEdge_left->prev_edge; if(pEdge_left==NULL || pEdge_left->prev_edge == NULL) return 0; } _cvStickEdgeLeftEnd(pEdge1,pEdge_left,pSite_left); } } if(right) { pEdge_right = pSite_right->edge2; if(pEdge_right==NULL) _cvStickEdgeRightEnd(pEdge2,NULL,pSite_right); else { while(pEdge_right->node2!=NULL && pEdge_right->node2==pEdge_right->next_edge->node1) { pEdge_right = pEdge_right->next_edge; if(pEdge_right==NULL || pEdge_right->next_edge == NULL ) return 0; } _cvStickEdgeRightEnd(pEdge2,pEdge_right,pSite_right); } } return 1; } if(fabs(dist1 - dist2)node2 = pNode_begin; pEdge2->node1 = pNode_begin; _cvStickEdgeLeftEnd(pEdge1,pEdge_left,pSite_left); _cvTwinNULLLeft(pEdge_left_cur,pEdge_left); _cvStickEdgeRightEnd(pEdge2,pEdge_right,pSite_right); _cvTwinNULLRight(pEdge_right_cur,pEdge_right); if(pEdge_left->twin_edge!=NULL&&pEdge_right->twin_edge!=NULL) { pEdge_left_prev = pEdge_left->twin_edge; if(!pEdge_left_prev) return 0; pEdge_left_cur = pEdge_left_prev->next_edge; pEdge_right_next = pEdge_right->twin_edge; if(!pEdge_right_next) return 0; pEdge_right_cur = pEdge_right_next->prev_edge; pSite_right = pEdge_right_next->site; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); pSite_left = pEdge_left_prev->site; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } if(pEdge_left->twin_edge==NULL&&pEdge_right->twin_edge!=NULL) { pEdge_right_next = pEdge_right->twin_edge; if(!pEdge_right_next) return 0; pEdge_right_cur = pEdge_right_next->prev_edge; pSite_right = pEdge_right_next->site; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); pEdge_left_cur = NULL; left = false; continue; } if(pEdge_left->twin_edge!=NULL&&pEdge_right->twin_edge==NULL) { pEdge_left_prev = pEdge_left->twin_edge; if(!pEdge_left_prev) return 0; pEdge_left_cur = pEdge_left_prev->next_edge; pSite_left = pEdge_left_prev->site; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); pEdge_right_cur = NULL; right = false; continue; } if(pEdge_left->twin_edge==NULL&&pEdge_right->twin_edge==NULL) return 1; } if((dist1=0)||(dist1>=0&&dist2<0)) { pNode_begin = _cvSeqPush(NodeSeq,&Node); _cvInitVoronoiNode(pNode_begin, &Point1,radius1); pEdge1->node2 = pNode_begin; _cvTwinNULLLeft(pEdge_left_cur,pEdge_left); _cvStickEdgeLeftEnd(pEdge1,pEdge_left,pSite_left); if(right) { pEdge2->node1 = pNode_begin; pEdge_right_next = pEdge2; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); if(pEdge_left->twin_edge!=NULL) { pEdge_left_prev = pEdge_left->twin_edge; if(!pEdge_left_prev) return 0; pEdge_left_cur = pEdge_left_prev->next_edge; pSite_left = pEdge_left_prev->site; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } else { pEdge_left_cur = NULL; left = false; continue; } } else { if(pEdge_left->twin_edge!=NULL) { pEdge_left_prev = pEdge_left->twin_edge; if(!pEdge_left_prev) return 0; pEdge_left_cur = pEdge_left_prev->next_edge; pSite_left = pEdge_left_prev->site; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } else return 1; } } if((dist1>dist2&&dist2>=0)||(dist1<0&&dist2>=0)) { pNode_begin = _cvSeqPush(NodeSeq,&Node); _cvInitVoronoiNode(pNode_begin, &Point2,radius2); pEdge2->node1 = pNode_begin; _cvTwinNULLRight(pEdge_right_cur,pEdge_right); _cvStickEdgeRightEnd(pEdge2,pEdge_right,pSite_right); if(left) { pEdge1->node2 = pNode_begin; pEdge_left_prev = pEdge1; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); if(pEdge_right->twin_edge!=NULL) { pEdge_right_next = pEdge_right->twin_edge; if(!pEdge_right_next) return 0; pEdge_right_cur = pEdge_right_next->prev_edge; pSite_right = pEdge_right_next->site; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } else { pEdge_right_cur = NULL; right = false; continue; } } else { if(pEdge_right->twin_edge!=NULL) { pEdge_right_next = pEdge_right->twin_edge; if(!pEdge_right_next) return 0; pEdge_right_cur = pEdge_right_next->prev_edge; pSite_right = pEdge_right_next->site; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } else return 1; } } } }// end of _cvJoinChains static void _cvFindNearestSite(CvVoronoiDiagramInt* pVoronoiDiagram) { pCvVoronoiHole pCurrHole, pHole = pVoronoiDiagram->top_hole; pCvPointFloat pTopPoint,pPoint1,pPoint2; CvPointFloat Direction; pCvVoronoiSite pSite; CvVoronoiNodeInt Node; CvSeq* CurrSeq; float min_distance,distance; int i; for(;pHole != NULL; pHole = pHole->next_hole) { if(pHole->error) continue; pTopPoint = &pHole->site_top->node1->node; pCurrHole = NULL; CurrSeq = pVoronoiDiagram->SiteSeq; min_distance = (float)3e+34; while(pCurrHole != pHole) { if(pCurrHole && pCurrHole->error) continue; pSite = (pCvVoronoiSite)cvGetSeqElem(CurrSeq,0); if(CurrSeq->total == 1) { distance = _cvCalcDist(pTopPoint, pSite); if(distance < min_distance) { min_distance = distance; pHole->site_nearest = pSite; } } else { for(i = 0; i < CurrSeq->total;i++, pSite = pSite->next_site) { if(pSite->node1 != pSite->node2) { pPoint1 = &pSite->node1->node; pPoint2 = &pSite->node2->node; Direction.x = -pSite->direction->y; Direction.y = pSite->direction->x; if( (pTopPoint->x - pPoint2->x)*Direction.y - (pTopPoint->y - pPoint2->y)*Direction.x > 0 || (pTopPoint->x - pPoint1->x)*Direction.y - (pTopPoint->y - pPoint1->y)*Direction.x < 0 || (pTopPoint->x - pPoint1->x)*pSite->direction->y - (pTopPoint->y - pPoint1->y)*pSite->direction->x > 0 ) continue; distance = _cvCalcDist(pTopPoint, pSite); } else { pPoint1 = &pSite->node1->node; if( (pTopPoint->x - pPoint1->x)*pSite->edge2->direction->y - (pTopPoint->y - pPoint1->y)*pSite->edge2->direction->x > 0 || (pTopPoint->x - pPoint1->x)*pSite->edge1->direction->y - (pTopPoint->y - pPoint1->y)*pSite->edge1->direction->x < 0 ) continue; distance = _cvCalcDist(pTopPoint, pSite); } if(distance < min_distance) { min_distance = distance; pHole->site_nearest = pSite; } } } if(pCurrHole == NULL) pCurrHole = pVoronoiDiagram->top_hole; else pCurrHole = pCurrHole->next_hole; CurrSeq = pCurrHole->SiteSeq; } pHole->x_coord = min_distance; if(pHole->site_nearest->node1 == pHole->site_nearest->node2) { Direction.x = (pHole->site_nearest->node1->node.x - pHole->site_top->node1->node.x)/2; Direction.y = (pHole->site_nearest->node1->node.y - pHole->site_top->node1->node.y)/2; } else { Direction.x = pHole->site_nearest->direction->y * min_distance / 2; Direction.y = - pHole->site_nearest->direction->x * min_distance / 2; } Node.node.x = pHole->site_top->node1->node.x + Direction.x; Node.node.y = pHole->site_top->node1->node.y + Direction.y; pHole->node = _cvSeqPush(pVoronoiDiagram->NodeSeq, &Node); } }//end of _cvFindNearestSite static void _cvConstructIntVD(CvVoronoiDiagramInt* pVoronoiDiagram) { pCvVoronoiChain pChain1, pChain2; pCvVoronoiHole pHole; int i; pHole = pVoronoiDiagram->top_hole; for(;pHole != NULL; pHole = pHole->next_hole) { if(pHole->ChainSeq->total == 0) continue; pChain1 = (pCvVoronoiChain)cvGetSeqElem(pHole->ChainSeq,0); for(i = pHole->ChainSeq->total; i > 0;i--) { pChain2 = pChain1->next_chain; if(!_cvJoinChains(pChain1,pChain2,pVoronoiDiagram)) { pHole->error = true; break; } pChain1->last_site = pChain2->last_site; pChain1->next_chain = pChain2->next_chain; pChain1 = pChain1->next_chain; } } }// end of _cvConstructIntVD static int _cvFindOppositSiteCW(pCvVoronoiHole pHole, CvVoronoiDiagramInt* pVoronoiDiagram) { pCvVoronoiSite pSite_left = pHole->site_nearest; pCvVoronoiSite pSite_right = pHole->site_top; pCvVoronoiNode pNode = pHole->node; CvDirection Direction = {-1,0}; CvVoronoiEdgeInt Edge_right = {NULL,pSite_right->node1,pSite_right,NULL,NULL,NULL,NULL,&Direction}; pCvVoronoiEdge pEdge_left = pSite_left->edge2->next_edge; pCvVoronoiEdge pEdge_right = &Edge_right; CvVoronoiEdgeInt Edge = {NULL,pNode,pSite_right,NULL,NULL,NULL,NULL,NULL}; CvVoronoiEdgeInt Edge_cur = {NULL,NULL,NULL,NULL,NULL,NULL,NULL}; pCvVoronoiEdge pEdge = &Edge; float radius1, radius2,dist1, dist2; CvPointFloat Point1 = {0,0}, Point2 = {0,0}; for(;;) { pEdge->direction = NULL; pEdge->parabola = NULL; _cvCalcEdge(pSite_left,pSite_right,pEdge,pVoronoiDiagram); dist1=dist2=-1; radius1 = -1; radius2 = -2; while(pEdge_left!=NULL) { dist1 = _cvCalcEdgeIntersection(pEdge, pEdge_left, &Point1,radius1); if(dist1>=0) break; pEdge_left = pEdge_left->next_edge; } dist2 = _cvCalcEdgeIntersection(pEdge, pEdge_right, &Point2, radius2); if(dist2>=0 && dist1 >= dist2) { pHole->site_opposite = pSite_left; pNode->node = Point2; return 1; } if(dist1<0) return 0; Edge_cur = *pEdge_left->twin_edge; Edge_cur.node1 = pNode; pEdge_left = &Edge_cur; pSite_left = pEdge_left->site; pNode->node = Point1; } }//end of _cvFindOppositSiteCW static int _cvFindOppositSiteCCW(pCvVoronoiHole pHole,CvVoronoiDiagramInt* pVoronoiDiagram) { pCvVoronoiSite pSite_right = pHole->site_nearest; pCvVoronoiSite pSite_left = pHole->site_top; pCvVoronoiNode pNode = pHole->node; CvDirection Direction = {-1,0}; CvVoronoiEdgeInt Edge_left = {pSite_left->node1,NULL,pSite_left,NULL,NULL,NULL, NULL, &Direction}; pCvVoronoiEdge pEdge_left = &Edge_left; pCvVoronoiEdge pEdge_right = pSite_right->edge1->prev_edge; CvVoronoiEdgeInt Edge = {NULL,pNode,pSite_left,NULL,NULL,NULL,NULL}; CvVoronoiEdgeInt Edge_cur = {NULL,NULL,NULL,NULL,NULL,NULL,NULL}; pCvVoronoiEdge pEdge = &Edge; double dist1, dist2; float radius1, radius2; CvPointFloat Point1 = {0,0}, Point2 = {0,0}; for(;;) { pEdge->direction = NULL; pEdge->parabola = NULL; _cvCalcEdge(pSite_left,pSite_right,pEdge,pVoronoiDiagram); dist1=dist2=-1; radius1 = -1; radius2 = -2; while(pEdge_right!=NULL) { dist1 = _cvCalcEdgeIntersection(pEdge, pEdge_right, &Point1,radius2); if(dist1>=0) break; pEdge_right = pEdge_right->prev_edge; } dist2 = _cvCalcEdgeIntersection(pEdge, pEdge_left, &Point2, radius1); if(dist2>=0 && dist1 > dist2) { pHole->site_opposite = pSite_right; pNode->node = Point2; return 1; } if(dist1<0) return 0; Edge_cur = *pEdge_right->twin_edge; Edge_cur.node2 = pNode; pEdge_right = &Edge_cur; pSite_right = pEdge_right->site; pNode->node = Point1; } }//end of _cvFindOppositSiteCCW static int _cvMergeVD(pCvVoronoiHole pHole,CvVoronoiDiagramInt* pVoronoiDiagram) { pCvVoronoiSite pSite_left_first = pHole->site_top; pCvVoronoiSite pSite_right_first = pHole->site_opposite; pCvVoronoiNode pNode_begin = pHole->node; if(pSite_left_first == NULL || pSite_right_first == NULL || pNode_begin == NULL) return 0; pCvVoronoiSite pSite_left = pSite_left_first; pCvVoronoiSite pSite_right = pSite_right_first; const double dist_eps = 0.05; CvVoronoiEdgeInt EdgeNULL = {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL}; CvSeq* NodeSeq = pVoronoiDiagram->NodeSeq; CvSeq* EdgeSeq = pVoronoiDiagram->EdgeSeq; pCvVoronoiEdge pEdge_left = NULL; if(pSite_left->edge2 != NULL) pEdge_left = pSite_left->edge2->next_edge; pCvVoronoiEdge pEdge_right = pSite_right->edge1; pCvVoronoiEdge pEdge_left_cur = pEdge_left; pCvVoronoiEdge pEdge_right_cur = pEdge_right; pCvVoronoiEdge pEdge_left_prev = NULL; pCvVoronoiEdge pEdge_right_next = NULL; pCvVoronoiEdge pEdge1,pEdge2,pEdge1_first, pEdge2_first; CvPointFloat Point1 = {0,0}, Point2 = {0,0}; float radius1,radius2,dist1,dist2; CvVoronoiNodeInt Node; pEdge1_first = pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL);; pEdge2_first = pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL);; pEdge1->site = pSite_left_first; pEdge2->site = pSite_right_first; do { pEdge1->node1 = pEdge2->node2 = pNode_begin; pEdge_left = pEdge_left_cur; pEdge_right = pEdge_right_cur->prev_edge; _cvCalcEdge(pSite_left,pSite_right,pEdge1,pVoronoiDiagram); _cvMakeTwinEdge(pEdge2,pEdge1); if(pEdge_left_prev != NULL) _cvStickEdgeLeftBegin(pEdge1,pEdge_left_prev,pSite_left); if(pEdge_right_next != NULL) _cvStickEdgeRightBegin(pEdge2,pEdge_right_next,pSite_right); dist1=dist2=-1; radius1 = -1; radius2 = -2; //LEFT: while(pEdge_left!=NULL) { if(pEdge_left->node2 == NULL) pEdge_left_cur = pEdge_left = pEdge_left->next_edge; dist1 = _cvCalcEdgeIntersection(pEdge1, pEdge_left, &Point1,radius1); if(dist1>=0) goto RIGHT; pEdge_left = pEdge_left->next_edge; } RIGHT: while(pEdge_right!=NULL) { dist2 = _cvCalcEdgeIntersection(pEdge1, pEdge_right, &Point2,radius2); if(dist2>=0) goto RESULTHANDLING; pEdge_right = pEdge_right->prev_edge; } pEdge_right = pEdge_right_cur; dist2 = _cvCalcEdgeIntersection(pEdge1, pEdge_right, &Point2, radius2); RESULTHANDLING: if(dist1<0&&dist2<0) return 0; if(fabs(dist1 - dist2)node2 = pNode_begin; pEdge2->node1 = pNode_begin; pEdge_right_cur = _cvDivideRightEdge(pEdge_right,pNode_begin,EdgeSeq); _cvStickEdgeLeftEnd(pEdge1,pEdge_left,pSite_left); _cvStickEdgeRightEnd(pEdge2,pEdge_right,pSite_right); pEdge_left_prev = pEdge_left->twin_edge; if(!pEdge_left_prev) return 0; pEdge_left_cur = pEdge_left_prev->next_edge; pSite_left = pEdge_left_prev->site; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); pEdge_right_next = pEdge_right->twin_edge; if(!pEdge_right_next) return 0; pSite_right = pEdge_right_next->site; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } if((dist1=0)||(dist1>=0&&dist2<0)) { pNode_begin = _cvSeqPush(NodeSeq,&Node); _cvInitVoronoiNode(pNode_begin, &Point1,radius1); pEdge1->node2 = pNode_begin; _cvStickEdgeLeftEnd(pEdge1,pEdge_left,pSite_left); pEdge2->node1 = pNode_begin; pEdge_right_next = pEdge2; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); pEdge_left_prev = pEdge_left->twin_edge; if(!pEdge_left_prev) return 0; pEdge_left_cur = pEdge_left_prev->next_edge; pSite_left = pEdge_left_prev->site; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } if((dist1>dist2&&dist2>=0)||(dist1<0&&dist2>=0)) { pNode_begin = _cvSeqPush(NodeSeq,&Node); _cvInitVoronoiNode(pNode_begin, &Point2,radius2); pEdge_right_cur = _cvDivideRightEdge(pEdge_right,pNode_begin,EdgeSeq); pEdge2->node1 = pNode_begin; _cvStickEdgeRightEnd(pEdge2,pEdge_right,pSite_right); pEdge1->node2 = pNode_begin; pEdge_left_prev = pEdge1; pEdge1 = _cvSeqPush(EdgeSeq, &EdgeNULL); pEdge_right_next = pEdge_right->twin_edge; if(!pEdge_right_next) return 0; pSite_right = pEdge_right_next->site; pEdge2 = _cvSeqPush(EdgeSeq, &EdgeNULL); continue; } }while(!(pSite_left == pSite_left_first && pSite_right == pSite_right_first)); pEdge1_first->node1 = pNode_begin; pEdge2_first->node2 = pNode_begin; _cvStickEdgeLeftBegin(pEdge1_first,pEdge_left_prev,pSite_left_first); _cvStickEdgeRightBegin(pEdge2_first,pEdge_right_next,pSite_right_first); if(pSite_left_first->edge2 == NULL) pSite_left_first->edge2 = pSite_left_first->edge1 = pEdge1_first; return 1; }// end of _cvMergeVD /* /////////////////////////////////////////////////////////////////////////////////////// // Computation of bisectors // /////////////////////////////////////////////////////////////////////////////////////// */ void _cvCalcEdge(pCvVoronoiSite pSite_left, pCvVoronoiSite pSite_right, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram) { if((pSite_left->node1!=pSite_left->node2)&& (pSite_right->node1!=pSite_right->node2)) _cvCalcEdgeLL(pSite_left->direction, pSite_right->direction, pEdge,pVoronoiDiagram); else if((pSite_left->node1!=pSite_left->node2)&& (pSite_right->node1 == pSite_right->node2)) _cvCalcEdgeLP(pSite_left,pSite_right->node1,pEdge,pVoronoiDiagram); else if((pSite_left->node1==pSite_left->node2)&& (pSite_right->node1!=pSite_right->node2)) _cvCalcEdgePL(pSite_left->node1,pSite_right,pEdge,pVoronoiDiagram); else _cvCalcEdgePP(&(pSite_left->node1->node), &(pSite_right->node1->node), pEdge,pVoronoiDiagram); }//end of _cvCalcEdge void _cvCalcEdge(pCvVoronoiSite pSite, pCvVoronoiNode pNode, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram) { if(pSite->node1!=pSite->node2) _cvCalcEdgeLP(pSite, pNode, pEdge,pVoronoiDiagram); else _cvCalcEdgePP(&(pSite->node1->node), &pNode->node, pEdge,pVoronoiDiagram); }//end of _cvCalcEdge void _cvCalcEdge(pCvVoronoiNode pNode, pCvVoronoiSite pSite, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram) { if(pSite->node1!=pSite->node2) _cvCalcEdgePL(pNode,pSite,pEdge,pVoronoiDiagram); else _cvCalcEdgePP(&pNode->node,&pSite->node1->node,pEdge,pVoronoiDiagram); }//end of _cvCalcEdge CV_INLINE void _cvCalcEdgeLL(pCvDirection pDirection1, pCvDirection pDirection2, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram) { CvDirection Direction = {pDirection2->x - pDirection1->x, pDirection2->y - pDirection1->y}; if((fabs(Direction.x)direction = _cvSeqPush(pVoronoiDiagram->DirectionSeq,&Direction);; }//end of _cvCalcEdgeLL CV_INLINE void _cvCalcEdgePP(pCvPointFloat pPoint1, pCvPointFloat pPoint2, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram) { CvDirection Direction = {pPoint1->y - pPoint2->y,pPoint2->x - pPoint1->x}; pEdge->direction = _cvSeqPush(pVoronoiDiagram->DirectionSeq,&Direction); }//end of _cvCalcEdgePP CV_INLINE void _cvCalcEdgePL(pCvVoronoiNode pFocus, pCvVoronoiSite pDirectrice, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram) { pCvPointFloat pPoint0 = &pFocus->node; pCvPointFloat pPoint1 = &pDirectrice->node1->node; CvDirection Vector01 = {pPoint0->x - pPoint1->x,pPoint0->y - pPoint1->y}; float half_h = (Vector01.y*pDirectrice->direction->x - Vector01.x*pDirectrice->direction->y)/2; CvDirection Normal = {-pDirectrice->direction->y,pDirectrice->direction->x}; if(half_h < LEE_CONST_ZERO) { pEdge->direction = _cvSeqPush(pVoronoiDiagram->DirectionSeq,&Normal); return; } CvVoronoiParabolaInt Parabola; pCvVoronoiParabola pParabola = _cvSeqPush(pVoronoiDiagram->ParabolaSeq,&Parabola); float* map = pParabola->map; map[1] = Normal.x; map[4] = Normal.y; map[0] = Normal.y; map[3] = -Normal.x; map[2] = pPoint0->x - Normal.x*half_h; map[5] = pPoint0->y - Normal.y*half_h; pParabola->a = 1/(4*half_h); pParabola->focus = pFocus; pParabola->directrice = pDirectrice; pEdge->parabola = pParabola; }//end of _cvCalcEdgePL CV_INLINE void _cvCalcEdgeLP(pCvVoronoiSite pDirectrice, pCvVoronoiNode pFocus, pCvVoronoiEdge pEdge, CvVoronoiDiagramInt* pVoronoiDiagram) { pCvPointFloat pPoint0 = &pFocus->node; pCvPointFloat pPoint1 = &pDirectrice->node1->node; CvDirection Vector01 = {pPoint0->x - pPoint1->x,pPoint0->y - pPoint1->y}; float half_h = (Vector01.y*pDirectrice->direction->x - Vector01.x*pDirectrice->direction->y)/2; CvDirection Normal = {-pDirectrice->direction->y,pDirectrice->direction->x}; if(half_h < LEE_CONST_ZERO) { pEdge->direction = _cvSeqPush(pVoronoiDiagram->DirectionSeq,&Normal); return; } CvVoronoiParabolaInt Parabola; pCvVoronoiParabola pParabola = _cvSeqPush(pVoronoiDiagram->ParabolaSeq,&Parabola); float* map = pParabola->map; map[1] = Normal.x; map[4] = Normal.y; map[0] = -Normal.y; map[3] = Normal.x; map[2] = pPoint0->x - Normal.x*half_h; map[5] = pPoint0->y - Normal.y*half_h; pParabola->a = 1/(4*half_h); pParabola->focus = pFocus; pParabola->directrice = pDirectrice; pEdge->parabola = pParabola; }//end of _cvCalcEdgeLP /* /////////////////////////////////////////////////////////////////////////////////////// // Computation of intersections of bisectors // /////////////////////////////////////////////////////////////////////////////////////// */ static float _cvCalcEdgeIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, CvPointFloat* pPoint, float &Radius) { if((pEdge1->parabola==NULL)&&(pEdge2->parabola==NULL)) return _cvLine_LineIntersection(pEdge1,pEdge2,pPoint,Radius); if((pEdge1->parabola==NULL)&&(pEdge2->parabola!=NULL)) return _cvLine_ParIntersection(pEdge1,pEdge2,pPoint,Radius); if((pEdge1->parabola!=NULL)&&(pEdge2->parabola==NULL)) return _cvPar_LineIntersection(pEdge1,pEdge2,pPoint,Radius); if((pEdge1->parabola!=NULL)&&(pEdge2->parabola!=NULL)) return _cvPar_ParIntersection(pEdge1,pEdge2,pPoint,Radius); return -1; }//end of _cvCalcEdgeIntersection static float _cvLine_LineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { if(((pEdge1->node1 == pEdge2->node1 || pEdge1->node1 == pEdge2->node2) && pEdge1->node1 != NULL)|| ((pEdge1->node2 == pEdge2->node1 || pEdge1->node2 == pEdge2->node2) && pEdge1->node2 != NULL)) return -1; CvPointFloat Point1,Point3; float det; float k,m; float x21,x43,y43,y21,x31,y31; if(pEdge1->node1!=NULL) { Point1.x = pEdge1->node1->node.x; Point1.y = pEdge1->node1->node.y; } else { Point1.x = pEdge1->node2->node.x; Point1.y = pEdge1->node2->node.y; } x21 = pEdge1->direction->x; y21 = pEdge1->direction->y; if(pEdge2->node2==NULL) { Point3.x = pEdge2->node1->node.x; Point3.y = pEdge2->node1->node.y; x43 = pEdge2->direction->x; y43 = pEdge2->direction->y; } else if(pEdge2->node1==NULL) { Point3.x = pEdge2->node2->node.x; Point3.y = pEdge2->node2->node.y; x43 = pEdge2->direction->x; y43 = pEdge2->direction->y; } else { Point3.x = pEdge2->node1->node.x; Point3.y = pEdge2->node1->node.y; x43 = pEdge2->node2->node.x - Point3.x; y43 = pEdge2->node2->node.y - Point3.y; } x31 = Point3.x - Point1.x; y31 = Point3.y - Point1.y; det = y21*x43 - x21*y43; if(fabs(det) < LEE_CONST_ZERO) return -1; k = (x43*y31 - y43*x31)/det; m = (x21*y31 - y21*x31)/det; if(k<-LEE_CONST_ACCEPTABLE_ERROR||m<-LEE_CONST_ACCEPTABLE_ERROR) return -1; if(((pEdge1->node2!=NULL)&&(pEdge1->node1!=NULL))&&(k>1.f+LEE_CONST_ACCEPTABLE_ERROR)) return -1; if(((pEdge2->node2!=NULL)&&(pEdge2->node1!=NULL))&&(m>1.f+LEE_CONST_ACCEPTABLE_ERROR)) return -1; pPoint->x = (float)(k*x21) + Point1.x; pPoint->y = (float)(k*y21) + Point1.y; Radius = _cvCalcDist(pPoint,pEdge1->site); return _cvPPDist(pPoint,&Point1);; }//end of _cvLine_LineIntersection static float _cvLine_ParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { if(pEdge2->node1==NULL||pEdge2->node2==NULL) return _cvLine_OpenParIntersection(pEdge1,pEdge2,pPoint,Radius); else return _cvLine_CloseParIntersection(pEdge1,pEdge2,pPoint,Radius); }//end of _cvLine_ParIntersection static float _cvLine_OpenParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { int IntersectionNumber = 1; if(((pEdge1->node1 == pEdge2->node1 || pEdge1->node1 == pEdge2->node2) && pEdge1->node1 != NULL)|| ((pEdge1->node2 == pEdge2->node1 || pEdge1->node2 == pEdge2->node2) && pEdge1->node2 != NULL)) IntersectionNumber = 2; pCvPointFloat pRayPoint1; if(pEdge1->node1!=NULL) pRayPoint1 = &(pEdge1->node1->node); else pRayPoint1 = &(pEdge1->node2->node); pCvDirection pDirection = pEdge1->direction; float* Parabola = pEdge2->parabola->map; pCvPointFloat pParPoint1; if(pEdge2->node1==NULL) pParPoint1 = &(pEdge2->node2->node); else pParPoint1 = &(pEdge2->node1->node); float InversParabola[6]; _cvCalcOrtogInverse(InversParabola, Parabola); CvPointFloat Point,ParPoint1_img,RayPoint1_img; CvDirection Direction_img; _cvCalcPointImage(&RayPoint1_img, pRayPoint1, InversParabola); _cvCalcVectorImage(&Direction_img,pDirection, InversParabola); float c2 = pEdge2->parabola->a*Direction_img.x; float c1 = -Direction_img.y; float c0 = Direction_img.y* RayPoint1_img.x - Direction_img.x*RayPoint1_img.y; float X[2]; int N = _cvSolveEqu2thR(c2,c1,c0,X); if(N==0) return -1; _cvCalcPointImage(&ParPoint1_img, pParPoint1, InversParabola); int sign_x = SIGN(Direction_img.x); int sign_y = SIGN(Direction_img.y); if(N==1) { if(X[0]parabola->a*X[0]*X[0]-RayPoint1_img.y)*sign_y; if(pr0 <= -LEE_CONST_ACCEPTABLE_ERROR) return -1; } else { if(X[1]parabola->a*X[0]*X[0]-RayPoint1_img.y)*sign_y; float pr1 = (X[1]-RayPoint1_img.x)*sign_x + \ (pEdge2->parabola->a*X[1]*X[1]-RayPoint1_img.y)*sign_y; if(pr0 <= -LEE_CONST_ACCEPTABLE_ERROR &&pr1 <= -LEE_CONST_ACCEPTABLE_ERROR) return -1; if(pr0 >- LEE_CONST_ACCEPTABLE_ERROR && pr1 >- LEE_CONST_ACCEPTABLE_ERROR) { if(X[0] >= ParPoint1_img.x - LEE_CONST_ACCEPTABLE_ERROR) { if(pr0>pr1) _cvSwap(X[0],X[1]); } else { N=1; X[0] = X[1]; } } else if(pr0 >- LEE_CONST_ACCEPTABLE_ERROR) { N = 1; if(X[0] < ParPoint1_img.x - LEE_CONST_ACCEPTABLE_ERROR) return -1; } else if(pr1 >- LEE_CONST_ACCEPTABLE_ERROR) { N=1; X[0] = X[1]; } else return -1; } Point.x = X[(N-1)*(IntersectionNumber - 1)]; Point.y = pEdge2->parabola->a*Point.x*Point.x; Radius = Point.y + 1.f/(4*pEdge2->parabola->a); _cvCalcPointImage(pPoint,&Point,Parabola); float dist = _cvPPDist(pPoint, pRayPoint1); if(IntersectionNumber == 2 && dist < LEE_CONST_DIFF_POINTS) return -1; else return dist; }// end of _cvLine_OpenParIntersection static float _cvLine_CloseParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { int IntersectionNumber = 1; if(((pEdge1->node1 == pEdge2->node1 || pEdge1->node1 == pEdge2->node2) && pEdge1->node1 != NULL)|| ((pEdge1->node2 == pEdge2->node1 || pEdge1->node2 == pEdge2->node2) && pEdge1->node2 != NULL)) IntersectionNumber = 2; pCvPointFloat pRayPoint1; if(pEdge1->node1!=NULL) pRayPoint1 = &(pEdge1->node1->node); else pRayPoint1 = &(pEdge1->node2->node); pCvDirection pDirection = pEdge1->direction; float* Parabola = pEdge2->parabola->map; pCvPointFloat pParPoint1,pParPoint2; pParPoint2 = &(pEdge2->node1->node); pParPoint1 = &(pEdge2->node2->node); float InversParabola[6]; _cvCalcOrtogInverse(InversParabola, Parabola); CvPointFloat Point,ParPoint1_img,ParPoint2_img,RayPoint1_img; CvDirection Direction_img; _cvCalcPointImage(&RayPoint1_img, pRayPoint1, InversParabola); _cvCalcVectorImage(&Direction_img,pDirection, InversParabola); float c2 = pEdge2->parabola->a*Direction_img.x; float c1 = -Direction_img.y; float c0 = Direction_img.y* RayPoint1_img.x - Direction_img.x*RayPoint1_img.y; float X[2]; int N = _cvSolveEqu2thR(c2,c1,c0,X); if(N==0) return -1; _cvCalcPointImage(&ParPoint1_img, pParPoint1, InversParabola); _cvCalcPointImage(&ParPoint2_img, pParPoint2, InversParabola); if(ParPoint1_img.x>ParPoint2_img.x) _cvSwap(ParPoint1_img,ParPoint2_img); int sign_x = SIGN(Direction_img.x); int sign_y = SIGN(Direction_img.y); if(N==1) { if((X[0]ParPoint2_img.x + LEE_CONST_ACCEPTABLE_ERROR)) return -1; float pr0 = (X[0]-RayPoint1_img.x)*sign_x + \ (pEdge2->parabola->a*X[0]*X[0]-RayPoint1_img.y)*sign_y; if(pr0 <= -LEE_CONST_ACCEPTABLE_ERROR) return -1; } else { if((X[1]ParPoint2_img.x + LEE_CONST_ACCEPTABLE_ERROR)) return -1; if((X[0]ParPoint2_img.x + LEE_CONST_ACCEPTABLE_ERROR)) return -1; float pr0 = (X[0]-RayPoint1_img.x)*sign_x + \ (pEdge2->parabola->a*X[0]*X[0]-RayPoint1_img.y)*sign_y; float pr1 = (X[1]-RayPoint1_img.x)*sign_x + \ (pEdge2->parabola->a*X[1]*X[1]-RayPoint1_img.y)*sign_y; if(pr0 <= -LEE_CONST_ACCEPTABLE_ERROR && pr1 <= -LEE_CONST_ACCEPTABLE_ERROR) return -1; if(pr0 > -LEE_CONST_ACCEPTABLE_ERROR && pr1 > -LEE_CONST_ACCEPTABLE_ERROR) { if(X[0] >= ParPoint1_img.x - LEE_CONST_ACCEPTABLE_ERROR) { if(X[1] <= ParPoint2_img.x + LEE_CONST_ACCEPTABLE_ERROR) { if(pr0>pr1) _cvSwap(X[0], X[1]); } else N=1; } else { N=1; X[0] = X[1]; } } else if(pr0 > -LEE_CONST_ACCEPTABLE_ERROR) { if(X[0] >= ParPoint1_img.x - LEE_CONST_ACCEPTABLE_ERROR) N=1; else return -1; } else if(pr1 > -LEE_CONST_ACCEPTABLE_ERROR) { if(X[1] <= ParPoint2_img.x + LEE_CONST_ACCEPTABLE_ERROR) { N=1; X[0] = X[1]; } else return -1; } else return -1; } Point.x = X[(N-1)*(IntersectionNumber - 1)]; Point.y = pEdge2->parabola->a*Point.x*Point.x; Radius = Point.y + 1.f/(4*pEdge2->parabola->a); _cvCalcPointImage(pPoint,&Point,Parabola); float dist = _cvPPDist(pPoint, pRayPoint1); if(IntersectionNumber == 2 && dist < LEE_CONST_DIFF_POINTS) return -1; else return dist; }// end of _cvLine_CloseParIntersection static float _cvPar_LineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { if(pEdge2->node1==NULL||pEdge2->node2==NULL) return _cvPar_OpenLineIntersection(pEdge1,pEdge2,pPoint,Radius); else return _cvPar_CloseLineIntersection(pEdge1,pEdge2,pPoint,Radius); }//end _cvPar_LineIntersection static float _cvPar_OpenLineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { int i, IntersectionNumber = 1; if(((pEdge1->node1 == pEdge2->node1 || pEdge1->node1 == pEdge2->node2) && pEdge1->node1 != NULL)|| ((pEdge1->node2 == pEdge2->node1 || pEdge1->node2 == pEdge2->node2) && pEdge1->node2 != NULL)) IntersectionNumber = 2; float* Parabola = pEdge1->parabola->map; pCvPointFloat pParPoint1; if(pEdge1->node1!=NULL) pParPoint1 = &(pEdge1->node1->node); else pParPoint1 = &(pEdge1->node2->node); pCvPointFloat pRayPoint1; if(pEdge2->node1==NULL) pRayPoint1 = &(pEdge2->node2->node); else pRayPoint1 = &(pEdge2->node1->node); pCvDirection pDirection = pEdge2->direction; float InversParabola[6]; _cvCalcOrtogInverse(InversParabola, Parabola); CvPointFloat Point = {0,0},ParPoint1_img,RayPoint1_img; CvDirection Direction_img; _cvCalcVectorImage(&Direction_img,pDirection, InversParabola); _cvCalcPointImage(&RayPoint1_img, pRayPoint1, InversParabola); float q = RayPoint1_img.y - pEdge1->parabola->a*RayPoint1_img.x*RayPoint1_img.x; if(pEdge2->site->node1 == pEdge2->site->node2 && q < 0 || pEdge2->site->node1 != pEdge2->site->node2 && q > 0) return -1; float c2 = pEdge1->parabola->a*Direction_img.x; float c1 = -Direction_img.y; float c0 = Direction_img.y* RayPoint1_img.x - Direction_img.x*RayPoint1_img.y; float X[2]; int N = _cvSolveEqu2thR(c2,c1,c0,X); if(N==0) return -1; _cvCalcPointImage(&ParPoint1_img, pParPoint1, InversParabola); int sign_x = SIGN(Direction_img.x); int sign_y = SIGN(Direction_img.y); float pr; if(N==2 && IntersectionNumber == 2) _cvSwap(X[0], X[1]); for( i=0;iparabola->a*X[i]*X[i]-RayPoint1_img.y)*sign_y; if(pr <= -LEE_CONST_ACCEPTABLE_ERROR) continue; else { Point.x = X[i]; break; } } if(i==N) return -1; Point.y = pEdge1->parabola->a*Point.x*Point.x; Radius = Point.y + 1.f/(4*pEdge1->parabola->a); _cvCalcPointImage(pPoint,&Point,Parabola); float dist = Point.x - ParPoint1_img.x; if(IntersectionNumber == 2 && dist < LEE_CONST_DIFF_POINTS) return -1; else return dist; }// end of _cvPar_OpenLineIntersection static float _cvPar_CloseLineIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { int i, IntersectionNumber = 1; if(((pEdge1->node1 == pEdge2->node1 || pEdge1->node1 == pEdge2->node2) && pEdge1->node1 != NULL)|| ((pEdge1->node2 == pEdge2->node1 || pEdge1->node2 == pEdge2->node2) && pEdge1->node2 != NULL)) IntersectionNumber = 2; float* Parabola = pEdge1->parabola->map; pCvPointFloat pParPoint1; if(pEdge1->node1!=NULL) pParPoint1 = &(pEdge1->node1->node); else pParPoint1 = &(pEdge1->node2->node); pCvPointFloat pRayPoint1,pRayPoint2; pRayPoint2 = &(pEdge2->node1->node); pRayPoint1 = &(pEdge2->node2->node); pCvDirection pDirection = pEdge2->direction; float InversParabola[6]; _cvCalcOrtogInverse(InversParabola, Parabola); CvPointFloat Point={0,0},ParPoint1_img,RayPoint1_img,RayPoint2_img; CvDirection Direction_img; _cvCalcPointImage(&RayPoint1_img, pRayPoint1, InversParabola); _cvCalcPointImage(&RayPoint2_img, pRayPoint2, InversParabola); float q; if(Radius == -1) { q = RayPoint1_img.y - pEdge1->parabola->a*RayPoint1_img.x*RayPoint1_img.x; if(pEdge2->site->node1 == pEdge2->site->node2 && q < 0 || pEdge2->site->node1 != pEdge2->site->node2 && q > 0) return -1; } if(Radius == -2) { q = RayPoint2_img.y - pEdge1->parabola->a*RayPoint2_img.x*RayPoint2_img.x; if(pEdge2->site->node1 == pEdge2->site->node2 && q < 0 || pEdge2->site->node1 != pEdge2->site->node2 && q > 0) return -1; } _cvCalcPointImage(&ParPoint1_img, pParPoint1, InversParabola); _cvCalcVectorImage(&Direction_img,pDirection, InversParabola); float c2 = pEdge1->parabola->a*Direction_img.x; float c1 = -Direction_img.y; float c0 = Direction_img.y* RayPoint1_img.x - Direction_img.x*RayPoint1_img.y; float X[2]; int N = _cvSolveEqu2thR(c2,c1,c0,X); if(N==0) return -1; int sign_x = SIGN(RayPoint2_img.x - RayPoint1_img.x); int sign_y = SIGN(RayPoint2_img.y - RayPoint1_img.y); float pr_dir = (RayPoint2_img.x - RayPoint1_img.x)*sign_x + (RayPoint2_img.y - RayPoint1_img.y)*sign_y; float pr; if(N==2 && IntersectionNumber == 2) _cvSwap(X[0], X[1]); for( i =0;iparabola->a*X[i]*X[i]-RayPoint1_img.y)*sign_y; if(pr <= -LEE_CONST_ACCEPTABLE_ERROR || pr>=pr_dir + LEE_CONST_ACCEPTABLE_ERROR) continue; else { Point.x = X[i]; break; } } if(i==N) return -1; Point.y = pEdge1->parabola->a*Point.x*Point.x; Radius = Point.y + 1.f/(4*pEdge1->parabola->a); _cvCalcPointImage(pPoint,&Point,Parabola); float dist = Point.x - ParPoint1_img.x; if(IntersectionNumber == 2 && dist < LEE_CONST_DIFF_POINTS) return -1; else return dist; }// end of _cvPar_CloseLineIntersection static float _cvPar_ParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { if(pEdge2->node1==NULL||pEdge2->node2==NULL) return _cvPar_OpenParIntersection(pEdge1,pEdge2,pPoint,Radius); else return _cvPar_CloseParIntersection(pEdge1,pEdge2,pPoint,Radius); }// end of _cvPar_ParIntersection static float _cvPar_OpenParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { int i, IntersectionNumber = 1; if(((pEdge1->node1 == pEdge2->node1 || pEdge1->node1 == pEdge2->node2) && pEdge1->node1 != NULL)|| ((pEdge1->node2 == pEdge2->node1 || pEdge1->node2 == pEdge2->node2) && pEdge1->node2 != NULL)) IntersectionNumber = 2; float* Parabola1 = pEdge1->parabola->map; pCvPointFloat pPar1Point1; if(pEdge1->node1!=NULL) pPar1Point1 = &(pEdge1->node1->node); else pPar1Point1 = &(pEdge1->node2->node); float* Parabola2 = pEdge2->parabola->map; pCvPointFloat pPar2Point1; if(pEdge2->node1!=NULL) pPar2Point1 = &(pEdge2->node1->node); else pPar2Point1 = &(pEdge2->node2->node); CvPointFloat Point; CvDirection Direction; if(pEdge1->parabola->directrice==pEdge2->parabola->directrice) //common site is segment -> different focuses { pCvPointFloat pFocus1 = &(pEdge1->parabola->focus->node); pCvPointFloat pFocus2 = &(pEdge2->parabola->focus->node); Point.x = (pFocus1->x + pFocus2->x)/2; Point.y = (pFocus1->y + pFocus2->y)/2; Direction.x = pFocus1->y - pFocus2->y; Direction.y = pFocus2->x - pFocus1->x; } else//common site is focus -> different directrices { pCvVoronoiSite pDirectrice1 = pEdge1->parabola->directrice; pCvPointFloat pPoint1 = &(pDirectrice1->node1->node); pCvDirection pVector21 = pDirectrice1->direction; pCvVoronoiSite pDirectrice2 = pEdge2->parabola->directrice; pCvPointFloat pPoint3 = &(pDirectrice2->node1->node); pCvDirection pVector43 = pDirectrice2->direction; Direction.x = pVector43->x - pVector21->x; Direction.y = pVector43->y - pVector21->y; if((fabs(Direction.x) < LEE_CONST_ZERO) && (fabs(Direction.y) < LEE_CONST_ZERO)) Direction = *pVector43; float det = pVector21->y * pVector43->x - pVector21->x * pVector43->y; if(fabs(det) < LEE_CONST_ZERO) { Point.x = (pPoint1->x + pPoint3->x)/2; Point.y = (pPoint1->y + pPoint3->y)/2; } else { float d1 = pVector21->y*pPoint1->x - pVector21->x*pPoint1->y; float d2 = pVector43->y*pPoint3->x - pVector43->x*pPoint3->y; Point.x = (float)((pVector43->x*d1 - pVector21->x*d2)/det); Point.y = (float)((pVector43->y*d1 - pVector21->y*d2)/det); } } float InversParabola2[6]; _cvCalcOrtogInverse(InversParabola2, Parabola2); CvPointFloat Par2Point1_img,Point_img; CvDirection Direction_img; _cvCalcVectorImage(&Direction_img,&Direction, InversParabola2); _cvCalcPointImage(&Point_img, &Point, InversParabola2); float a1 = pEdge1->parabola->a; float a2 = pEdge2->parabola->a; float c2 = a2*Direction_img.x; float c1 = -Direction_img.y; float c0 = Direction_img.y* Point_img.x - Direction_img.x*Point_img.y; float X[2]; int N = _cvSolveEqu2thR(c2,c1,c0,X); if(N==0) return -1; _cvCalcPointImage(&Par2Point1_img, pPar2Point1, InversParabola2); if(X[N-1]X[1] && IntersectionNumber == 1)|| (X[0]parabola->a); _cvCalcPointImage(pPoint,&Point,Parabola1); float dist = Point.x - Par1Point1_img.x; if(IntersectionNumber == 2 && dist < LEE_CONST_DIFF_POINTS) return -1; else return dist; }// end of _cvPar_OpenParIntersection static float _cvPar_CloseParIntersection(pCvVoronoiEdge pEdge1, pCvVoronoiEdge pEdge2, pCvPointFloat pPoint, float &Radius) { int i, IntersectionNumber = 1; if(((pEdge1->node1 == pEdge2->node1 || pEdge1->node1 == pEdge2->node2) && pEdge1->node1 != NULL)|| ((pEdge1->node2 == pEdge2->node1 || pEdge1->node2 == pEdge2->node2) && pEdge1->node2 != NULL)) IntersectionNumber = 2; float* Parabola1 = pEdge1->parabola->map; float* Parabola2 = pEdge2->parabola->map; pCvPointFloat pPar1Point1; if(pEdge1->node1!=NULL) pPar1Point1 = &(pEdge1->node1->node); else pPar1Point1 = &(pEdge1->node2->node); pCvPointFloat pPar2Point1 = &(pEdge2->node1->node); pCvPointFloat pPar2Point2 = &(pEdge2->node2->node); CvPointFloat Point; CvDirection Direction; if(pEdge1->parabola->directrice==pEdge2->parabola->directrice) //common site is segment -> different focuses { pCvPointFloat pFocus1 = &(pEdge1->parabola->focus->node); pCvPointFloat pFocus2 = &(pEdge2->parabola->focus->node); Point.x = (pFocus1->x + pFocus2->x)/2; Point.y = (pFocus1->y + pFocus2->y)/2; Direction.x = pFocus1->y - pFocus2->y; Direction.y = pFocus2->x - pFocus1->x; } else//common site is focus -> different directrices { pCvVoronoiSite pDirectrice1 = pEdge1->parabola->directrice; pCvPointFloat pPoint1 = &(pDirectrice1->node1->node); pCvDirection pVector21 = pDirectrice1->direction; pCvVoronoiSite pDirectrice2 = pEdge2->parabola->directrice; pCvPointFloat pPoint3 = &(pDirectrice2->node1->node); pCvDirection pVector43 = pDirectrice2->direction; Direction.x = pVector43->x - pVector21->x; Direction.y = pVector43->y - pVector21->y; if((fabs(Direction.x) < LEE_CONST_ZERO) && (fabs(Direction.y) < LEE_CONST_ZERO)) Direction = *pVector43; float det = pVector21->y * pVector43->x - pVector21->x * pVector43->y; if(fabs(det) < LEE_CONST_ZERO) { Point.x = (pPoint1->x + pPoint3->x)/2; Point.y = (pPoint1->y + pPoint3->y)/2; } else { float d1 = pVector21->y*pPoint1->x - pVector21->x*pPoint1->y; float d2 = pVector43->y*pPoint3->x - pVector43->x*pPoint3->y; Point.x = (float)((pVector43->x*d1 - pVector21->x*d2)/det); Point.y = (float)((pVector43->y*d1 - pVector21->y*d2)/det); } } float InversParabola2[6]; _cvCalcOrtogInverse(InversParabola2, Parabola2); CvPointFloat Par2Point1_img,Par2Point2_img,Point_img; CvDirection Direction_img; _cvCalcVectorImage(&Direction_img,&Direction, InversParabola2); _cvCalcPointImage(&Point_img, &Point, InversParabola2); float a1 = pEdge1->parabola->a; float a2 = pEdge2->parabola->a; float c2 = a2*Direction_img.x; float c1 = -Direction_img.y; float c0 = Direction_img.y* Point_img.x - Direction_img.x*Point_img.y; float X[2]; int N = _cvSolveEqu2thR(c2,c1,c0,X); if(N==0) return -1; _cvCalcPointImage(&Par2Point1_img, pPar2Point1, InversParabola2); _cvCalcPointImage(&Par2Point2_img, pPar2Point2, InversParabola2); if(Par2Point1_img.x>Par2Point2_img.x) _cvSwap(Par2Point1_img,Par2Point2_img); if(X[0]>Par2Point2_img.x||X[N-1]Par2Point2_img.x) N=1; float InversParabola1[6]; CvPointFloat Par1Point1_img; _cvCalcOrtogInverse(InversParabola1, Parabola1); _cvCalcPointImage(&Par1Point1_img, pPar1Point1, InversParabola1); float InvPar1_Par2[6]; _cvCalcComposition(InvPar1_Par2,InversParabola1,Parabola2); for(i=0;iX[1] && IntersectionNumber == 1)|| (X[0]direction = pEdge1->direction; pEdge2->parabola = pEdge1->parabola; pEdge2->node1 = pEdge1->node2; pEdge2->twin_edge = pEdge1; pEdge1->twin_edge = pEdge2; }//end of _cvMakeTwinEdge CV_INLINE void _cvStickEdgeLeftBegin(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_left_prev, pCvVoronoiSite pSite_left) { pEdge->prev_edge = pEdge_left_prev; pEdge->site = pSite_left; if(pEdge_left_prev == NULL) pSite_left->edge2 = pEdge; else { pEdge_left_prev->node2 = pEdge->node1; pEdge_left_prev->next_edge = pEdge; } }//end of _cvStickEdgeLeftBegin CV_INLINE void _cvStickEdgeRightBegin(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_right_next, pCvVoronoiSite pSite_right) { pEdge->next_edge = pEdge_right_next; pEdge->site = pSite_right; if(pEdge_right_next == NULL) pSite_right->edge1 = pEdge; else { pEdge_right_next->node1 = pEdge->node2; pEdge_right_next->prev_edge = pEdge; } }// end of _cvStickEdgeRightBegin CV_INLINE void _cvStickEdgeLeftEnd(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_left_next, pCvVoronoiSite pSite_left) { pEdge->next_edge = pEdge_left_next; if(pEdge_left_next == NULL) pSite_left->edge1 = pEdge; else { pEdge_left_next->node1 = pEdge->node2; pEdge_left_next->prev_edge = pEdge; } }//end of _cvStickEdgeLeftEnd CV_INLINE void _cvStickEdgeRightEnd(pCvVoronoiEdge pEdge, pCvVoronoiEdge pEdge_right_prev, pCvVoronoiSite pSite_right) { pEdge->prev_edge = pEdge_right_prev; if(pEdge_right_prev == NULL) pSite_right->edge2 = pEdge; else { pEdge_right_prev->node2 = pEdge->node1; pEdge_right_prev->next_edge = pEdge; } }//end of _cvStickEdgeRightEnd template CV_INLINE void _cvInitVoronoiNode(pCvVoronoiNode pNode, T pPoint, float radius) { pNode->node.x = (float)pPoint->x; pNode->node.y = (float)pPoint->y; pNode->radius = radius; }//end of _cvInitVoronoiNode CV_INLINE void _cvInitVoronoiSite(pCvVoronoiSite pSite, pCvVoronoiNode pNode1, pCvVoronoiNode pNode2, pCvVoronoiSite pPrev_site) { pSite->node1 = pNode1; pSite->node2 = pNode2; pSite->prev_site = pPrev_site; }//end of _cvInitVoronoiSite template CV_INLINE T _cvSeqPush(CvSeq* Seq, T pElem) { cvSeqPush(Seq, pElem); return (T)(Seq->ptr - Seq->elem_size); // return (T)cvGetSeqElem(Seq, Seq->total - 1,NULL); }//end of _cvSeqPush template CV_INLINE T _cvSeqPushFront(CvSeq* Seq, T pElem) { cvSeqPushFront(Seq,pElem); return (T)Seq->first->data; // return (T)cvGetSeqElem(Seq,0,NULL); }//end of _cvSeqPushFront CV_INLINE void _cvTwinNULLLeft(pCvVoronoiEdge pEdge_left_cur, pCvVoronoiEdge pEdge_left) { while(pEdge_left_cur!=pEdge_left) { if(pEdge_left_cur->twin_edge!=NULL) pEdge_left_cur->twin_edge->twin_edge = NULL; pEdge_left_cur = pEdge_left_cur->next_edge; } }//end of _cvTwinNULLLeft CV_INLINE void _cvTwinNULLRight(pCvVoronoiEdge pEdge_right_cur, pCvVoronoiEdge pEdge_right) { while(pEdge_right_cur!=pEdge_right) { if(pEdge_right_cur->twin_edge!=NULL) pEdge_right_cur->twin_edge->twin_edge = NULL; pEdge_right_cur = pEdge_right_cur->prev_edge; } }//end of _cvTwinNULLRight CV_INLINE void _cvSeqPushInOrder(CvVoronoiDiagramInt* pVoronoiDiagram, pCvVoronoiHole pHole) { pHole = _cvSeqPush(pVoronoiDiagram->HoleSeq, pHole); if(pVoronoiDiagram->HoleSeq->total == 1) { pVoronoiDiagram->top_hole = pHole; return; } pCvVoronoiHole pTopHole = pVoronoiDiagram->top_hole; pCvVoronoiHole pCurrHole; if(pTopHole->x_coord >= pHole->x_coord) { pHole->next_hole = pTopHole; pVoronoiDiagram->top_hole = pHole; return; } for(pCurrHole = pTopHole; \ pCurrHole->next_hole != NULL; \ pCurrHole = pCurrHole->next_hole) if(pCurrHole->next_hole->x_coord >= pHole->x_coord) break; pHole->next_hole = pCurrHole->next_hole; pCurrHole->next_hole = pHole; }//end of _cvSeqPushInOrder CV_INLINE pCvVoronoiEdge _cvDivideRightEdge(pCvVoronoiEdge pEdge,pCvVoronoiNode pNode, CvSeq* EdgeSeq) { CvVoronoiEdgeInt Edge1 = *pEdge; CvVoronoiEdgeInt Edge2 = *pEdge->twin_edge; pCvVoronoiEdge pEdge1, pEdge2; pEdge1 = _cvSeqPush(EdgeSeq, &Edge1); pEdge2 = _cvSeqPush(EdgeSeq, &Edge2); if(pEdge1->next_edge != NULL) pEdge1->next_edge->prev_edge = pEdge1; pEdge1->prev_edge = NULL; if(pEdge2->prev_edge != NULL) pEdge2->prev_edge->next_edge = pEdge2; pEdge2->next_edge = NULL; pEdge1->node1 = pEdge2->node2= pNode; pEdge1->twin_edge = pEdge2; pEdge2->twin_edge = pEdge1; return pEdge2; }//end of _cvDivideRightEdge CV_INLINE pCvVoronoiEdge _cvDivideLeftEdge(pCvVoronoiEdge pEdge,pCvVoronoiNode pNode, CvSeq* EdgeSeq) { CvVoronoiEdgeInt Edge1 = *pEdge; CvVoronoiEdgeInt Edge2 = *pEdge->twin_edge; pCvVoronoiEdge pEdge1, pEdge2; pEdge1 = _cvSeqPush(EdgeSeq, &Edge1); pEdge2 = _cvSeqPush(EdgeSeq, &Edge2); if(pEdge2->next_edge != NULL) pEdge2->next_edge->prev_edge = pEdge2; pEdge2->prev_edge = NULL; if(pEdge1->prev_edge != NULL) pEdge1->prev_edge->next_edge = pEdge1; pEdge1->next_edge = NULL; pEdge1->node2 = pEdge2->node1= pNode; pEdge1->twin_edge = pEdge2; pEdge2->twin_edge = pEdge1; return pEdge2; }//end of _cvDivideLeftEdge template CV_INLINE T _cvWriteSeqElem(T pElem, CvSeqWriter &writer) { if( writer.ptr >= writer.block_max ) cvCreateSeqBlock( &writer); T ptr = (T)writer.ptr; memcpy(writer.ptr, pElem, sizeof(*pElem)); writer.ptr += sizeof(*pElem); return ptr; }//end of _cvWriteSeqElem /* /////////////////////////////////////////////////////////////////////////////////////// // Mathematical functions // /////////////////////////////////////////////////////////////////////////////////////// */ template CV_INLINE void _cvCalcPointImage(pCvPointFloat pImgPoint,pCvPointFloat pPoint,T* A) { pImgPoint->x = (float)(A[0]*pPoint->x + A[1]*pPoint->y + A[2]); pImgPoint->y = (float)(A[3]*pPoint->x + A[4]*pPoint->y + A[5]); }//end of _cvCalcPointImage template CV_INLINE void _cvSwap(T &x, T &y) { T z; z=x; x=y; y=z; }//end of _cvSwap template CV_INLINE int _cvCalcOrtogInverse(T* B, T* A) { int sign_det = SIGN(A[0]*A[4] - A[1]*A[3]); if(sign_det) { B[0] = A[4]*sign_det; B[1] = -A[1]*sign_det; B[3] = -A[3]*sign_det; B[4] = A[0]*sign_det; B[2] = - (B[0]*A[2]+B[1]*A[5]); B[5] = - (B[3]*A[2]+B[4]*A[5]); return 1; } else return 0; }//end of _cvCalcOrtogInverse template CV_INLINE void _cvCalcVectorImage(pCvDirection pImgVector,pCvDirection pVector,T* A) { pImgVector->x = A[0]*pVector->x + A[1]*pVector->y; pImgVector->y = A[3]*pVector->x + A[4]*pVector->y; }//end of _cvCalcVectorImage template CV_INLINE void _cvCalcComposition(T* Result,T* A,T* B) { Result[0] = A[0]*B[0] + A[1]*B[3]; Result[1] = A[0]*B[1] + A[1]*B[4]; Result[3] = A[3]*B[0] + A[4]*B[3]; Result[4] = A[3]*B[1] + A[4]*B[4]; Result[2] = A[0]*B[2] + A[1]*B[5] + A[2]; Result[5] = A[3]*B[2] + A[4]*B[5] + A[5]; }//end of _cvCalcComposition CV_INLINE float _cvCalcDist(pCvPointFloat pPoint, pCvVoronoiSite pSite) { if(pSite->node1==pSite->node2) return _cvPPDist(pPoint,&(pSite->node1->node)); else return _cvPLDist(pPoint,&(pSite->node1->node),pSite->direction); }//end of _cvCalcComposition CV_INLINE float _cvPPDist(pCvPointFloat pPoint1,pCvPointFloat pPoint2) { float delta_x = pPoint1->x - pPoint2->x; float delta_y = pPoint1->y - pPoint2->y; return (float)sqrt((double)delta_x*delta_x + delta_y*delta_y); }//end of _cvPPDist CV_INLINE float _cvPLDist(pCvPointFloat pPoint,pCvPointFloat pPoint1,pCvDirection pDirection) { return (float)fabs(pDirection->x*(pPoint->y - pPoint1->y) - pDirection->y*(pPoint->x - pPoint1->x)); }//end of _cvPLDist template int _cvSolveEqu2thR(T c2, T c1, T c0, T* X) { const T eps = (T)1e-6; if(fabs(c2)=0) { if(c2>0) { X[0] = (-c1 - Discr)/(2*c2); X[1] = -2*c0/(c1+Discr); return 2; } else { X[1] = (-c1 - Discr)/(2*c2); X[0] = -2*c0/(c1+Discr); return 2; } } else { if(c2>0) { X[1] = (-c1 + Discr)/(2*c2); X[0] = -2*c0/(c1-Discr); return 2; } else { X[0] = (-c1 + Discr)/(2*c2); X[1] = -2*c0/(c1-Discr); return 2; } } } }//end of _cvSolveEqu2thR template CV_INLINE int _cvSolveEqu1th(T c1, T c0, T* X) { const T eps = (T)1e-6; if(fabs(c1)