X-Git-Url: https://vcs.maemo.org/git/?a=blobdiff_plain;f=cvaux%2Fsrc%2Fcvlee.cpp;fp=cvaux%2Fsrc%2Fcvlee.cpp;h=0000000000000000000000000000000000000000;hb=e4c14cdbdf2fe805e79cd96ded236f57e7b89060;hp=58db0d020d300ee8627cf38e70d3c7ca5ec96da6;hpb=454138ff8a20f6edb9b65a910101403d8b520643;p=opencv diff --git a/cvaux/src/cvlee.cpp b/cvaux/src/cvlee.cpp deleted file mode 100644 index 58db0d0..0000000 --- a/cvaux/src/cvlee.cpp +++ /dev/null @@ -1,4718 +0,0 @@ -/*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)