16acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*M/////////////////////////////////////////////////////////////////////////////////////// 26acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 36acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 46acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 56acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// By downloading, copying, installing or using the software you agree to this license. 66acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// If you do not agree to this license, do not download, install, 76acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// copy or use the software. 86acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 96acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Intel License Agreement 116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// For Open Source Computer Vision Library 126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Copyright (C) 2000, Intel Corporation, all rights reserved. 146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Third party copyrights are property of their respective owners. 156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Redistribution and use in source and binary forms, with or without modification, 176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// are permitted provided that the following conditions are met: 186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's of source code must retain the above copyright notice, 206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer. 216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's in binary form must reproduce the above copyright notice, 236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer in the documentation 246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and/or other materials provided with the distribution. 256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * The name of Intel Corporation may not be used to endorse or promote products 276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// derived from this software without specific prior written permission. 286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// This software is provided by the copyright holders and contributors "as is" and 306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// any express or implied warranties, including, but not limited to, the implied 316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// warranties of merchantability and fitness for a particular purpose are disclaimed. 326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// In no event shall the Intel Corporation or contributors be liable for any direct, 336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// indirect, incidental, special, exemplary, or consequential damages 346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// (including, but not limited to, procurement of substitute goods or services; 356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// loss of use, data, or profits; or business interruption) however caused 366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and on any theory of liability, whether in contract, strict liability, 376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// or tort (including negligence or otherwise) arising in any way out of 386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// the use of this software, even if advised of the possibility of such damage. 396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//M*/ 416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include "_cv.h" 426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSubdiv2D * 446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvCreateSubdiv2D( int subdiv_type, int header_size, 456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int vtx_size, int quadedge_size, CvMemStorage * storage ) 466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2D *subdiv = 0; 486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvCleateSubdiv2D" ); 506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !storage ) 546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( header_size < (int)sizeof( *subdiv ) || 576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quadedge_size < (int)sizeof( CvQuadEdge2D ) || 586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vtx_size < (int)sizeof( CvSubdiv2DPoint )) 596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR ); 606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv = (CvSubdiv2D *) cvCreateGraph( subdiv_type, header_size, 626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn vtx_size, quadedge_size, storage ); 636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return subdiv; 686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* Quad Edge algebra * 736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvSubdiv2DEdge 766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DMakeEdge( CvSubdiv2D * subdiv ) 776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvQuadEdge2D *edge = 0; 796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge edgehandle = 0; 806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvSubdiv2DMakeEdge" ); 826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = (CvQuadEdge2D*)cvSetNew( (CvSet*)subdiv->edges ); 896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CHECK(); 906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( edge->pt, 0, sizeof( edge->pt )); 926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edgehandle = (CvSubdiv2DEdge) edge; 936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge->next[0] = edgehandle; 956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge->next[1] = edgehandle + 3; 966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge->next[2] = edgehandle + 2; 976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge->next[3] = edgehandle + 1; 986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->quad_edges++; 1006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 1036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return edgehandle; 1056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvSubdiv2DPoint * 1096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DAddPoint( CvSubdiv2D * subdiv, CvPoint2D32f pt, int is_virtual ) 1106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *subdiv_point = 0; 1126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv_point = (CvSubdiv2DPoint*)cvSetNew( (CvSet*)subdiv ); 1146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( subdiv_point ) 1156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( subdiv_point, 0, subdiv->elem_size ); 1176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv_point->pt = pt; 1186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv_point->first = 0; 1196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv_point->flags |= is_virtual ? CV_SUBDIV2D_VIRTUAL_POINT_FLAG : 0; 1206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return subdiv_point; 1236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 1276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DSplice( CvSubdiv2DEdge edgeA, CvSubdiv2DEdge edgeB ) 1286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge *a_next = &CV_SUBDIV2D_NEXT_EDGE( edgeA ); 1306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge *b_next = &CV_SUBDIV2D_NEXT_EDGE( edgeB ); 1316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge a_rot = cvSubdiv2DRotateEdge( *a_next, 1 ); 1326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge b_rot = cvSubdiv2DRotateEdge( *b_next, 1 ); 1336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge *a_rot_next = &CV_SUBDIV2D_NEXT_EDGE( a_rot ); 1346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge *b_rot_next = &CV_SUBDIV2D_NEXT_EDGE( b_rot ); 1356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge t; 1366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_SWAP( *a_next, *b_next, t ); 1386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_SWAP( *a_rot_next, *b_rot_next, t ); 1396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 1436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DSetEdgePoints( CvSubdiv2DEdge edge, 1446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint * org_pt, CvSubdiv2DPoint * dst_pt ) 1456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvQuadEdge2D *quadedge = (CvQuadEdge2D *) (edge & ~3); 1476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvSubdiv2DSetEdgePoints" ); 1496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 1516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !quadedge ) 1536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 1546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quadedge->pt[edge & 3] = org_pt; 1566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quadedge->pt[(edge + 2) & 3] = dst_pt; 1576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 1606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 1646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DDeleteEdge( CvSubdiv2D * subdiv, CvSubdiv2DEdge edge ) 1656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvQuadEdge2D *quadedge = (CvQuadEdge2D *) (edge & ~3); 1676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvSubdiv2DDeleteEdge" ); 1696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 1716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv || !quadedge ) 1736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 1746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( edge, cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_ORG )); 1766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge sym_edge = cvSubdiv2DSymEdge( edge ); 1796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( sym_edge, cvSubdiv2DGetEdge( sym_edge, CV_PREV_AROUND_ORG )); 1806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetRemoveByPtr( (CvSet*)(subdiv->edges), quadedge ); 1836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->quad_edges--; 1846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 1876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 1886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvSubdiv2DEdge 1916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DConnectEdges( CvSubdiv2D * subdiv, CvSubdiv2DEdge edgeA, CvSubdiv2DEdge edgeB ) 1926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 1936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge new_edge = 0; 1946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvSubdiv2DConnectPoints" ); 1966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 1986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *orgB, *dstA; 2006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 2026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 2036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_edge = cvSubdiv2DMakeEdge( subdiv ); 2056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( new_edge, cvSubdiv2DGetEdge( edgeA, CV_NEXT_AROUND_LEFT )); 2076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( cvSubdiv2DSymEdge( new_edge ), edgeB ); 2086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dstA = cvSubdiv2DEdgeDst( edgeA ); 2106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn orgB = cvSubdiv2DEdgeOrg( edgeB ); 2116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSetEdgePoints( new_edge, dstA, orgB ); 2126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 2146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return new_edge; 2166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 2176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic void 2206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DSwapEdges( CvSubdiv2DEdge edge ) 2216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 2226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge sym_edge = cvSubdiv2DSymEdge( edge ); 2236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge a = cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_ORG ); 2246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge b = cvSubdiv2DGetEdge( sym_edge, CV_PREV_AROUND_ORG ); 2256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *dstB, *dstA; 2266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( edge, a ); 2286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( sym_edge, b ); 2296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dstA = cvSubdiv2DEdgeDst( a ); 2316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dstB = cvSubdiv2DEdgeDst( b ); 2326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSetEdgePoints( edge, dstA, dstB ); 2336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( edge, cvSubdiv2DGetEdge( a, CV_NEXT_AROUND_LEFT )); 2356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( sym_edge, cvSubdiv2DGetEdge( b, CV_NEXT_AROUND_LEFT )); 2366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 2376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 2406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvIsRightOf( CvPoint2D32f& pt, CvSubdiv2DEdge edge ) 2416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 2426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *org = cvSubdiv2DEdgeOrg(edge), *dst = cvSubdiv2DEdgeDst(edge); 2436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Cv32suf cw_area; 2446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cw_area.f = (float)cvTriangleArea( pt, dst->pt, org->pt ); 2456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return (cw_area.i > 0)*2 - (cw_area.i*2 != 0); 2476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 2486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSubdiv2DPointLocation 2516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdiv2DLocate( CvSubdiv2D * subdiv, CvPoint2D32f pt, 2526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge * _edge, CvSubdiv2DPoint ** _point ) 2536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 2546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge edge = 0; 2556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *point = 0; 2566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPointLocation location = CV_PTLOC_ERROR; 2576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, max_edges; 2596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int right_of_curr = 0; 2606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvSubdiv2DLocate" ); 2626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 2646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 2666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 2676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SUBDIV2D(subdiv) ) 2696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADFLAG_ERR ); 2706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_edges = subdiv->quad_edges * 4; 2726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = subdiv->recent_edge; 2736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( max_edges == 0 ) 2756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR ); 2766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !edge ) 2776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_NOTDEFINED_ERR ); 2786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = CV_PTLOC_OUTSIDE_RECT; 2806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pt.x < subdiv->topleft.x || pt.y < subdiv->topleft.y || 2816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt.x >= subdiv->bottomright.x || pt.y >= subdiv->bottomright.y ) 2826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR ); 2836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = CV_PTLOC_ERROR; 2856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_of_curr = icvIsRightOf( pt, edge ); 2876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right_of_curr > 0 ) 2886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = cvSubdiv2DSymEdge( edge ); 2906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_of_curr = -right_of_curr; 2916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < max_edges; i++ ) 2946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge onext_edge = cvSubdiv2DNextEdge( edge ); 2966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge dprev_edge = cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_DST ); 2976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int right_of_onext = icvIsRightOf( pt, onext_edge ); 2996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int right_of_dprev = icvIsRightOf( pt, dprev_edge ); 3006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right_of_dprev > 0 ) 3026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right_of_onext > 0 || (right_of_onext == 0 && right_of_curr == 0) ) 3046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = CV_PTLOC_INSIDE; 3066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 3076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_of_curr = right_of_onext; 3116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = onext_edge; 3126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right_of_onext > 0 ) 3176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right_of_dprev == 0 && right_of_curr == 0 ) 3196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = CV_PTLOC_INSIDE; 3216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 3226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_of_curr = right_of_dprev; 3266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = dprev_edge; 3276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( right_of_curr == 0 && 3306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvIsRightOf( cvSubdiv2DEdgeDst( onext_edge )->pt, edge ) >= 0 ) 3316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = cvSubdiv2DSymEdge( edge ); 3336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_of_curr = right_of_onext; 3376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = onext_edge; 3386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 3446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->recent_edge = edge; 3466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( location == CV_PTLOC_INSIDE ) 3486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double t1, t2, t3; 3506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f org_pt = cvSubdiv2DEdgeOrg( edge )->pt; 3516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f dst_pt = cvSubdiv2DEdgeDst( edge )->pt; 3526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t1 = fabs( pt.x - org_pt.x ); 3546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t1 += fabs( pt.y - org_pt.y ); 3556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t2 = fabs( pt.x - dst_pt.x ); 3566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t2 += fabs( pt.y - dst_pt.y ); 3576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t3 = fabs( org_pt.x - dst_pt.x ); 3586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t3 += fabs( org_pt.y - dst_pt.y ); 3596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( t1 < FLT_EPSILON ) 3616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = CV_PTLOC_VERTEX; 3636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = cvSubdiv2DEdgeOrg( edge ); 3646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = 0; 3656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( t2 < FLT_EPSILON ) 3676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = CV_PTLOC_VERTEX; 3696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = cvSubdiv2DEdgeDst( edge ); 3706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = 0; 3716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( (t1 < t3 || t2 < t3) && 3736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn fabs( cvTriangleArea( pt, org_pt, dst_pt )) < FLT_EPSILON ) 3746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = CV_PTLOC_ON_EDGE; 3766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = 0; 3776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( location == CV_PTLOC_ERROR ) 3816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = 0; 3836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = 0; 3846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( _edge ) 3876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *_edge = edge; 3886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( _point ) 3896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *_point = point; 3906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return location; 3926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 3936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_INLINE int 3966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvIsPtInCircle3( CvPoint2D32f pt, CvPoint2D32f a, CvPoint2D32f b, CvPoint2D32f c ) 3976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 3986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double val = (a.x * a.x + a.y * a.y) * cvTriangleArea( b, c, pt ); 3996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn val -= (b.x * b.x + b.y * b.y) * cvTriangleArea( a, c, pt ); 4006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn val += (c.x * c.x + c.y * c.y) * cvTriangleArea( a, b, pt ); 4016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn val -= (pt.x * pt.x + pt.y * pt.y) * cvTriangleArea( a, b, c ); 4026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return val > FLT_EPSILON ? 1 : val < -FLT_EPSILON ? -1 : 0; 4046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 4056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSubdiv2DPoint * 4086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvSubdivDelaunay2DInsert( CvSubdiv2D * subdiv, CvPoint2D32f pt ) 4096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 4106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *point = 0; 4116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPointLocation location = CV_PTLOC_ERROR; 4126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *curr_point = 0, *first_point = 0; 4146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge curr_edge = 0, deleted_edge = 0, base_edge = 0; 4156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, max_edges; 4166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvSubdivDelaunay2DInsert" ); 4186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 4206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 4226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 4236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SUBDIV2D(subdiv) ) 4256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADFLAG_ERR ); 4266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn location = cvSubdiv2DLocate( subdiv, pt, &curr_edge, &curr_point ); 4296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch (location) 4316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_PTLOC_ERROR: 4336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADSIZE_ERR ); 4346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_PTLOC_OUTSIDE_RECT: 4366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR ); 4376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_PTLOC_VERTEX: 4396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = curr_point; 4406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_PTLOC_ON_EDGE: 4436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn deleted_edge = curr_edge; 4446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->recent_edge = curr_edge = cvSubdiv2DGetEdge( curr_edge, CV_PREV_AROUND_ORG ); 4456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DDeleteEdge( subdiv, deleted_edge ); 4466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* no break */ 4476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_PTLOC_INSIDE: 4496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( curr_edge != 0 ); 4516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->is_geometry_valid = 0; 4526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_point = cvSubdiv2DAddPoint( subdiv, pt, 0 ); 4546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CHECK(); 4556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn base_edge = cvSubdiv2DMakeEdge( subdiv ); 4576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first_point = cvSubdiv2DEdgeOrg( curr_edge ); 4586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSetEdgePoints( base_edge, first_point, curr_point ); 4596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( base_edge, curr_edge ); 4606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 4626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn base_edge = cvSubdiv2DConnectEdges( subdiv, curr_edge, 4646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSymEdge( base_edge )); 4656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_edge = cvSubdiv2DGetEdge( base_edge, CV_PREV_AROUND_ORG ); 4666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( cvSubdiv2DEdgeDst( curr_edge ) != first_point ); 4686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_edge = cvSubdiv2DGetEdge( base_edge, CV_PREV_AROUND_ORG ); 4706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_edges = subdiv->quad_edges * 4; 4726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < max_edges; i++ ) 4746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *temp_dst = 0, *curr_org = 0, *curr_dst = 0; 4766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge temp_edge = cvSubdiv2DGetEdge( curr_edge, CV_PREV_AROUND_ORG ); 4776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp_dst = cvSubdiv2DEdgeDst( temp_edge ); 4796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_org = cvSubdiv2DEdgeOrg( curr_edge ); 4806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_dst = cvSubdiv2DEdgeDst( curr_edge ); 4816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( icvIsRightOf( temp_dst->pt, curr_edge ) > 0 && 4836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvIsPtInCircle3( curr_org->pt, temp_dst->pt, 4846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_dst->pt, curr_point->pt ) < 0 ) 4856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSwapEdges( curr_edge ); 4876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_edge = cvSubdiv2DGetEdge( curr_edge, CV_PREV_AROUND_ORG ); 4886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( curr_org == first_point ) 4906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 4946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn curr_edge = cvSubdiv2DGetEdge( cvSubdiv2DNextEdge( curr_edge ), 4966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_PREV_AROUND_LEFT ); 4976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 5006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 5016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( 0 ); 5026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_NOTDEFINED_ERR ); 5036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = curr_point; 5066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 5096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //icvSubdiv2DCheck( subdiv ); 5116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return point; 5136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 5146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL void 5176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvInitSubdivDelaunay2D( CvSubdiv2D * subdiv, CvRect rect ) 5186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 5196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float big_coord = 3.f * MAX( rect.width, rect.height ); 5206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f ppA, ppB, ppC; 5216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *pA, *pB, *pC; 5226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge edge_AB, edge_BC, edge_CA; 5236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float rx = (float) rect.x; 5246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn float ry = (float) rect.y; 5256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvSubdivDelaunay2DInit" ); 5276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 5296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 5316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 5326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvClearSet( (CvSet *) (subdiv->edges) ); 5346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvClearSet( (CvSet *) subdiv ); 5356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->quad_edges = 0; 5376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->recent_edge = 0; 5386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->is_geometry_valid = 0; 5396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->topleft = cvPoint2D32f( rx, ry ); 5416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->bottomright = cvPoint2D32f( rx + rect.width, ry + rect.height ); 5426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ppA = cvPoint2D32f( rx + big_coord, ry ); 5446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ppB = cvPoint2D32f( rx, ry + big_coord ); 5456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ppC = cvPoint2D32f( rx - big_coord, ry - big_coord ); 5466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pA = cvSubdiv2DAddPoint( subdiv, ppA, 0 ); 5486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pB = cvSubdiv2DAddPoint( subdiv, ppB, 0 ); 5496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pC = cvSubdiv2DAddPoint( subdiv, ppC, 0 ); 5506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge_AB = cvSubdiv2DMakeEdge( subdiv ); 5526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge_BC = cvSubdiv2DMakeEdge( subdiv ); 5536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge_CA = cvSubdiv2DMakeEdge( subdiv ); 5546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSetEdgePoints( edge_AB, pA, pB ); 5566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSetEdgePoints( edge_BC, pB, pC ); 5576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSetEdgePoints( edge_CA, pC, pA ); 5586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( edge_AB, cvSubdiv2DSymEdge( edge_CA )); 5606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( edge_BC, cvSubdiv2DSymEdge( edge_AB )); 5616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSubdiv2DSplice( edge_CA, cvSubdiv2DSymEdge( edge_BC )); 5626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->recent_edge = edge_AB; 5646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 5676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 5686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL void 5716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvClearSubdivVoronoi2D( CvSubdiv2D * subdiv ) 5726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 5736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int elem_size; 5746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, total; 5756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqReader reader; 5766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvClearVoronoi2D" ); 5786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 5806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 5826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 5836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* clear pointers to voronoi points */ 5856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn total = subdiv->edges->total; 5866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn elem_size = subdiv->edges->elem_size; 5876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( (CvSeq *) (subdiv->edges), &reader, 0 ); 5896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < total; i++ ) 5916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvQuadEdge2D *quadedge = (CvQuadEdge2D *) reader.ptr; 5936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quadedge->pt[1] = quadedge->pt[3] = 0; 5956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( elem_size, reader ); 5966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* remove voronoi points */ 5996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn total = subdiv->total; 6006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn elem_size = subdiv->elem_size; 6016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( (CvSeq *) subdiv, &reader, 0 ); 6036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < total; i++ ) 6056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *pt = (CvSubdiv2DPoint *) reader.ptr; 6076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* check for virtual point. it is also check that the point exists */ 6096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pt->flags & CV_SUBDIV2D_VIRTUAL_POINT_FLAG ) 6106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetRemoveByPtr( (CvSet*)subdiv, pt ); 6126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( elem_size, reader ); 6146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->is_geometry_valid = 0; 6176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 6206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 6216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL void 6246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvCalcSubdivVoronoi2D( CvSubdiv2D * subdiv ) 6256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 6266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqReader reader; 6276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, total, elem_size; 6286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvCalcSubdivVoronoi2D" ); 6306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 6326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 6346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 6356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* check if it is already calculated */ 6376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( subdiv->is_geometry_valid ) 6386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 6396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn total = subdiv->edges->total; 6416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn elem_size = subdiv->edges->elem_size; 6426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvClearSubdivVoronoi2D( subdiv ); 6446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( (CvSeq *) (subdiv->edges), &reader, 0 ); 6466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( total <= 3 ) 6486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 6496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* skip first three edges (bounding triangle) */ 6516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < 3; i++ ) 6526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( elem_size, reader ); 6536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* loop through all quad-edges */ 6556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( ; i < total; i++ ) 6566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvQuadEdge2D *quadedge = (CvQuadEdge2D *) (reader.ptr); 6586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_IS_SET_ELEM( quadedge )) 6606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge edge0 = (CvSubdiv2DEdge) quadedge, edge1, edge2; 6626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double a0, b0, c0, a1, b1, c1; 6636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f virt_point; 6646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint *voronoi_point; 6656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !quadedge->pt[3] ) 6676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge1 = cvSubdiv2DGetEdge( edge0, CV_NEXT_AROUND_LEFT ); 6696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge2 = cvSubdiv2DGetEdge( edge1, CV_NEXT_AROUND_LEFT ); 6706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCreateCenterNormalLine( edge0, &a0, &b0, &c0 ); 6726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCreateCenterNormalLine( edge1, &a1, &b1, &c1 ); 6736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvIntersectLines3( &a0, &b0, &c0, &a1, &b1, &c1, &virt_point ); 6756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs( virt_point.x ) < FLT_MAX * 0.5 && 6766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn fabs( virt_point.y ) < FLT_MAX * 0.5 ) 6776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn voronoi_point = cvSubdiv2DAddPoint( subdiv, virt_point, 1 ); 6796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quadedge->pt[3] = 6816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ((CvQuadEdge2D *) (edge1 & ~3))->pt[3 - (edge1 & 2)] = 6826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ((CvQuadEdge2D *) (edge2 & ~3))->pt[3 - (edge2 & 2)] = voronoi_point; 6836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !quadedge->pt[1] ) 6876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge1 = cvSubdiv2DGetEdge( edge0, CV_NEXT_AROUND_RIGHT ); 6896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge2 = cvSubdiv2DGetEdge( edge1, CV_NEXT_AROUND_RIGHT ); 6906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCreateCenterNormalLine( edge0, &a0, &b0, &c0 ); 6926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCreateCenterNormalLine( edge1, &a1, &b1, &c1 ); 6936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvIntersectLines3( &a0, &b0, &c0, &a1, &b1, &c1, &virt_point ); 6956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs( virt_point.x ) < FLT_MAX * 0.5 && 6976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn fabs( virt_point.y ) < FLT_MAX * 0.5 ) 6986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn voronoi_point = cvSubdiv2DAddPoint( subdiv, virt_point, 1 ); 7006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn quadedge->pt[1] = 7026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ((CvQuadEdge2D *) (edge1 & ~3))->pt[1 + (edge1 & 2)] = 7036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ((CvQuadEdge2D *) (edge2 & ~3))->pt[1 + (edge2 & 2)] = voronoi_point; 7046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( elem_size, reader ); 7096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn subdiv->is_geometry_valid = 1; 7126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 7156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 7166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic int 7196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvIsRightOf2( const CvPoint2D32f& pt, const CvPoint2D32f& org, const CvPoint2D32f& diff ) 7206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 7216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Cv32suf cw_area; 7226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cw_area.f = (org.x - pt.x)*diff.y - (org.y - pt.y)*diff.x; 7236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return (cw_area.i > 0)*2 - (cw_area.i*2 != 0); 7246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 7256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSubdiv2DPoint* 7286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvFindNearestPoint2D( CvSubdiv2D* subdiv, CvPoint2D32f pt ) 7296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 7306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint* point = 0; 7316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f start; 7326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f diff; 7336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPointLocation loc; 7346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge edge; 7356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i; 7366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME("cvFindNearestPoint2D"); 7386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 7406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv ) 7426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 7436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SUBDIV2D( subdiv )) 7456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 7466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !subdiv->is_geometry_valid ) 7486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvCalcSubdivVoronoi2D( subdiv ); 7496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn loc = cvSubdiv2DLocate( subdiv, pt, &edge, &point ); 7516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch( loc ) 7536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_PTLOC_ON_EDGE: 7556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_PTLOC_INSIDE: 7566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 7576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 7586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn EXIT; 7596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = 0; 7626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start = cvSubdiv2DEdgeOrg( edge )->pt; 7646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn diff.x = pt.x - start.x; 7656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn diff.y = pt.y - start.y; 7666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = cvSubdiv2DRotateEdge( edge, 1 ); 7686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < subdiv->total; i++ ) 7706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f t; 7726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(;;) 7746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( cvSubdiv2DEdgeDst( edge )); 7766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = cvSubdiv2DEdgeDst( edge )->pt; 7786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( icvIsRightOf2( t, start, diff ) >= 0 ) 7796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 7806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = cvSubdiv2DGetEdge( edge, CV_NEXT_AROUND_LEFT ); 7826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for(;;) 7856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( cvSubdiv2DEdgeOrg( edge )); 7876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = cvSubdiv2DEdgeOrg( edge )->pt; 7896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( icvIsRightOf2( t, start, diff ) < 0 ) 7906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 7916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_LEFT ); 7936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f tempDiff = cvSubdiv2DEdgeDst( edge )->pt; 7976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = cvSubdiv2DEdgeOrg( edge )->pt; 7986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tempDiff.x -= t.x; 7996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tempDiff.y -= t.y; 8006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( icvIsRightOf2( pt, t, tempDiff ) >= 0 ) 8026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn point = cvSubdiv2DEdgeOrg( cvSubdiv2DRotateEdge( edge, 3 )); 8046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 8056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn edge = cvSubdiv2DSymEdge( edge ); 8096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 8126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return point; 8146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 8156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Removed from the main interface */ 8176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#if 0 8196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Adds new isolated quadedge to the subdivision */ 8206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennOPENCVAPI CvSubdiv2DEdge cvSubdiv2DMakeEdge( CvSubdiv2D* subdiv ); 8216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Adds new isolated point to subdivision */ 8246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennOPENCVAPI CvSubdiv2DPoint* cvSubdiv2DAddPoint( CvSubdiv2D* subdiv, 8256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f pt, int is_virtual ); 8266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Does a splice operation for two quadedges */ 8296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennOPENCVAPI void cvSubdiv2DSplice( CvSubdiv2DEdge edgeA, CvSubdiv2DEdge edgeB ); 8306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Assigns ending [non-virtual] points for given quadedge */ 8336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennOPENCVAPI void cvSubdiv2DSetEdgePoints( CvSubdiv2DEdge edge, 8346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint* org_pt, 8356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DPoint* dst_pt ); 8366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Removes quadedge from subdivision */ 8386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennOPENCVAPI void cvSubdiv2DDeleteEdge( CvSubdiv2D* subdiv, CvSubdiv2DEdge edge ); 8396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Connects estination point of the first edge with origin point of the second edge */ 8426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennOPENCVAPI CvSubdiv2DEdge cvSubdiv2DConnectEdges( CvSubdiv2D* subdiv, 8436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge edgeA, 8446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSubdiv2DEdge edgeB ); 8456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Swaps diagonal in two connected Delaunay facets */ 8476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennOPENCVAPI void cvSubdiv2DSwapEdges( CvSubdiv2DEdge edge ); 8486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#endif 8496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* End of file. */ 851