1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
42 #include "precomp.hpp"
45 cvCreateSubdiv2D( int subdiv_type, int header_size,
46 int vtx_size, int quadedge_size, CvMemStorage * storage )
49 CV_Error( CV_StsNullPtr, "" );
51 if( header_size < (int)sizeof( CvSubdiv2D ) ||
52 quadedge_size < (int)sizeof( CvQuadEdge2D ) ||
53 vtx_size < (int)sizeof( CvSubdiv2DPoint ))
54 CV_Error( CV_StsBadSize, "" );
56 return (CvSubdiv2D *)cvCreateGraph( subdiv_type, header_size,
57 vtx_size, quadedge_size, storage );
61 /****************************************************************************************\
63 \****************************************************************************************/
66 cvSubdiv2DMakeEdge( CvSubdiv2D * subdiv )
69 CV_Error( CV_StsNullPtr, "" );
71 CvQuadEdge2D* edge = (CvQuadEdge2D*)cvSetNew( (CvSet*)subdiv->edges );
72 memset( edge->pt, 0, sizeof( edge->pt ));
73 CvSubdiv2DEdge edgehandle = (CvSubdiv2DEdge) edge;
75 edge->next[0] = edgehandle;
76 edge->next[1] = edgehandle + 3;
77 edge->next[2] = edgehandle + 2;
78 edge->next[3] = edgehandle + 1;
85 static CvSubdiv2DPoint *
86 cvSubdiv2DAddPoint( CvSubdiv2D * subdiv, CvPoint2D32f pt, int is_virtual )
88 CvSubdiv2DPoint* subdiv_point = (CvSubdiv2DPoint*)cvSetNew( (CvSet*)subdiv );
91 memset( subdiv_point, 0, subdiv->elem_size );
92 subdiv_point->pt = pt;
93 subdiv_point->first = 0;
94 subdiv_point->flags |= is_virtual ? CV_SUBDIV2D_VIRTUAL_POINT_FLAG : 0;
95 subdiv_point->id = -1;
103 cvSubdiv2DSplice( CvSubdiv2DEdge edgeA, CvSubdiv2DEdge edgeB )
105 CvSubdiv2DEdge *a_next = &CV_SUBDIV2D_NEXT_EDGE( edgeA );
106 CvSubdiv2DEdge *b_next = &CV_SUBDIV2D_NEXT_EDGE( edgeB );
107 CvSubdiv2DEdge a_rot = cvSubdiv2DRotateEdge( *a_next, 1 );
108 CvSubdiv2DEdge b_rot = cvSubdiv2DRotateEdge( *b_next, 1 );
109 CvSubdiv2DEdge *a_rot_next = &CV_SUBDIV2D_NEXT_EDGE( a_rot );
110 CvSubdiv2DEdge *b_rot_next = &CV_SUBDIV2D_NEXT_EDGE( b_rot );
113 CV_SWAP( *a_next, *b_next, t );
114 CV_SWAP( *a_rot_next, *b_rot_next, t );
119 cvSubdiv2DSetEdgePoints( CvSubdiv2DEdge edge,
120 CvSubdiv2DPoint * org_pt, CvSubdiv2DPoint * dst_pt )
122 CvQuadEdge2D *quadedge = (CvQuadEdge2D *) (edge & ~3);
125 CV_Error( CV_StsNullPtr, "" );
127 quadedge->pt[edge & 3] = org_pt;
128 quadedge->pt[(edge + 2) & 3] = dst_pt;
133 cvSubdiv2DDeleteEdge( CvSubdiv2D * subdiv, CvSubdiv2DEdge edge )
135 CvQuadEdge2D *quadedge = (CvQuadEdge2D *) (edge & ~3);
137 if( !subdiv || !quadedge )
138 CV_Error( CV_StsNullPtr, "" );
140 cvSubdiv2DSplice( edge, cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_ORG ));
142 CvSubdiv2DEdge sym_edge = cvSubdiv2DSymEdge( edge );
143 cvSubdiv2DSplice( sym_edge, cvSubdiv2DGetEdge( sym_edge, CV_PREV_AROUND_ORG ));
145 cvSetRemoveByPtr( (CvSet*)(subdiv->edges), quadedge );
146 subdiv->quad_edges--;
150 static CvSubdiv2DEdge
151 cvSubdiv2DConnectEdges( CvSubdiv2D * subdiv, CvSubdiv2DEdge edgeA, CvSubdiv2DEdge edgeB )
154 CV_Error( CV_StsNullPtr, "" );
156 CvSubdiv2DEdge new_edge = cvSubdiv2DMakeEdge( subdiv );
158 cvSubdiv2DSplice( new_edge, cvSubdiv2DGetEdge( edgeA, CV_NEXT_AROUND_LEFT ));
159 cvSubdiv2DSplice( cvSubdiv2DSymEdge( new_edge ), edgeB );
161 CvSubdiv2DPoint* dstA = cvSubdiv2DEdgeDst( edgeA );
162 CvSubdiv2DPoint* orgB = cvSubdiv2DEdgeOrg( edgeB );
163 cvSubdiv2DSetEdgePoints( new_edge, dstA, orgB );
170 cvSubdiv2DSwapEdges( CvSubdiv2DEdge edge )
172 CvSubdiv2DEdge sym_edge = cvSubdiv2DSymEdge( edge );
173 CvSubdiv2DEdge a = cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_ORG );
174 CvSubdiv2DEdge b = cvSubdiv2DGetEdge( sym_edge, CV_PREV_AROUND_ORG );
175 CvSubdiv2DPoint *dstB, *dstA;
177 cvSubdiv2DSplice( edge, a );
178 cvSubdiv2DSplice( sym_edge, b );
180 dstA = cvSubdiv2DEdgeDst( a );
181 dstB = cvSubdiv2DEdgeDst( b );
182 cvSubdiv2DSetEdgePoints( edge, dstA, dstB );
184 cvSubdiv2DSplice( edge, cvSubdiv2DGetEdge( a, CV_NEXT_AROUND_LEFT ));
185 cvSubdiv2DSplice( sym_edge, cvSubdiv2DGetEdge( b, CV_NEXT_AROUND_LEFT ));
190 icvIsRightOf( CvPoint2D32f& pt, CvSubdiv2DEdge edge )
192 CvSubdiv2DPoint *org = cvSubdiv2DEdgeOrg(edge), *dst = cvSubdiv2DEdgeDst(edge);
193 double cw_area = cvTriangleArea( pt, dst->pt, org->pt );
195 return (cw_area > 0) - (cw_area < 0);
199 CV_IMPL CvSubdiv2DPointLocation
200 cvSubdiv2DLocate( CvSubdiv2D * subdiv, CvPoint2D32f pt,
201 CvSubdiv2DEdge * _edge, CvSubdiv2DPoint ** _point )
203 CvSubdiv2DPoint *point = 0;
204 int right_of_curr = 0;
207 CV_Error( CV_StsNullPtr, "" );
209 if( !CV_IS_SUBDIV2D(subdiv) )
210 CV_Error( CV_StsBadFlag, "" );
212 int i, max_edges = subdiv->quad_edges * 4;
213 CvSubdiv2DEdge edge = subdiv->recent_edge;
216 CV_Error( CV_StsBadSize, "" );
217 CV_Assert(edge != 0);
219 if( pt.x < subdiv->topleft.x || pt.y < subdiv->topleft.y ||
220 pt.x >= subdiv->bottomright.x || pt.y >= subdiv->bottomright.y )
221 CV_Error( CV_StsOutOfRange, "" );
223 CvSubdiv2DPointLocation location = CV_PTLOC_ERROR;
225 right_of_curr = icvIsRightOf( pt, edge );
226 if( right_of_curr > 0 )
228 edge = cvSubdiv2DSymEdge( edge );
229 right_of_curr = -right_of_curr;
232 for( i = 0; i < max_edges; i++ )
234 CvSubdiv2DEdge onext_edge = cvSubdiv2DNextEdge( edge );
235 CvSubdiv2DEdge dprev_edge = cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_DST );
237 int right_of_onext = icvIsRightOf( pt, onext_edge );
238 int right_of_dprev = icvIsRightOf( pt, dprev_edge );
240 if( right_of_dprev > 0 )
242 if( right_of_onext > 0 || (right_of_onext == 0 && right_of_curr == 0) )
244 location = CV_PTLOC_INSIDE;
249 right_of_curr = right_of_onext;
255 if( right_of_onext > 0 )
257 if( right_of_dprev == 0 && right_of_curr == 0 )
259 location = CV_PTLOC_INSIDE;
264 right_of_curr = right_of_dprev;
268 else if( right_of_curr == 0 &&
269 icvIsRightOf( cvSubdiv2DEdgeDst( onext_edge )->pt, edge ) >= 0 )
271 edge = cvSubdiv2DSymEdge( edge );
275 right_of_curr = right_of_onext;
282 subdiv->recent_edge = edge;
284 if( location == CV_PTLOC_INSIDE )
287 CvPoint2D32f org_pt = cvSubdiv2DEdgeOrg( edge )->pt;
288 CvPoint2D32f dst_pt = cvSubdiv2DEdgeDst( edge )->pt;
290 t1 = fabs( pt.x - org_pt.x );
291 t1 += fabs( pt.y - org_pt.y );
292 t2 = fabs( pt.x - dst_pt.x );
293 t2 += fabs( pt.y - dst_pt.y );
294 t3 = fabs( org_pt.x - dst_pt.x );
295 t3 += fabs( org_pt.y - dst_pt.y );
297 if( t1 < FLT_EPSILON )
299 location = CV_PTLOC_VERTEX;
300 point = cvSubdiv2DEdgeOrg( edge );
303 else if( t2 < FLT_EPSILON )
305 location = CV_PTLOC_VERTEX;
306 point = cvSubdiv2DEdgeDst( edge );
309 else if( (t1 < t3 || t2 < t3) &&
310 fabs( cvTriangleArea( pt, org_pt, dst_pt )) < FLT_EPSILON )
312 location = CV_PTLOC_ON_EDGE;
317 if( location == CV_PTLOC_ERROR )
333 icvIsPtInCircle3( CvPoint2D32f pt, CvPoint2D32f a, CvPoint2D32f b, CvPoint2D32f c )
335 const double eps = FLT_EPSILON*0.125;
336 double val = ((double)a.x * a.x + (double)a.y * a.y) * cvTriangleArea( b, c, pt );
337 val -= ((double)b.x * b.x + (double)b.y * b.y) * cvTriangleArea( a, c, pt );
338 val += ((double)c.x * c.x + (double)c.y * c.y) * cvTriangleArea( a, b, pt );
339 val -= ((double)pt.x * pt.x + (double)pt.y * pt.y) * cvTriangleArea( a, b, c );
341 return val > eps ? 1 : val < -eps ? -1 : 0;
345 CV_IMPL CvSubdiv2DPoint *
346 cvSubdivDelaunay2DInsert( CvSubdiv2D * subdiv, CvPoint2D32f pt )
348 CvSubdiv2DPointLocation location = CV_PTLOC_ERROR;
350 CvSubdiv2DPoint *curr_point = 0, *first_point = 0;
351 CvSubdiv2DEdge curr_edge = 0, deleted_edge = 0, base_edge = 0;
355 CV_Error( CV_StsNullPtr, "" );
357 if( !CV_IS_SUBDIV2D(subdiv) )
358 CV_Error( CV_StsBadFlag, "" );
360 location = cvSubdiv2DLocate( subdiv, pt, &curr_edge, &curr_point );
365 CV_Error( CV_StsBadSize, "" );
367 case CV_PTLOC_OUTSIDE_RECT:
368 CV_Error( CV_StsOutOfRange, "" );
370 case CV_PTLOC_VERTEX:
373 case CV_PTLOC_ON_EDGE:
374 deleted_edge = curr_edge;
375 subdiv->recent_edge = curr_edge = cvSubdiv2DGetEdge( curr_edge, CV_PREV_AROUND_ORG );
376 cvSubdiv2DDeleteEdge( subdiv, deleted_edge );
379 case CV_PTLOC_INSIDE:
381 assert( curr_edge != 0 );
382 subdiv->is_geometry_valid = 0;
384 curr_point = cvSubdiv2DAddPoint( subdiv, pt, 0 );
385 base_edge = cvSubdiv2DMakeEdge( subdiv );
386 first_point = cvSubdiv2DEdgeOrg( curr_edge );
387 cvSubdiv2DSetEdgePoints( base_edge, first_point, curr_point );
388 cvSubdiv2DSplice( base_edge, curr_edge );
392 base_edge = cvSubdiv2DConnectEdges( subdiv, curr_edge,
393 cvSubdiv2DSymEdge( base_edge ));
394 curr_edge = cvSubdiv2DGetEdge( base_edge, CV_PREV_AROUND_ORG );
396 while( cvSubdiv2DEdgeDst( curr_edge ) != first_point );
398 curr_edge = cvSubdiv2DGetEdge( base_edge, CV_PREV_AROUND_ORG );
400 max_edges = subdiv->quad_edges * 4;
402 for( i = 0; i < max_edges; i++ )
404 CvSubdiv2DPoint *temp_dst = 0, *curr_org = 0, *curr_dst = 0;
405 CvSubdiv2DEdge temp_edge = cvSubdiv2DGetEdge( curr_edge, CV_PREV_AROUND_ORG );
407 temp_dst = cvSubdiv2DEdgeDst( temp_edge );
408 curr_org = cvSubdiv2DEdgeOrg( curr_edge );
409 curr_dst = cvSubdiv2DEdgeDst( curr_edge );
411 if( icvIsRightOf( temp_dst->pt, curr_edge ) > 0 &&
412 icvIsPtInCircle3( curr_org->pt, temp_dst->pt,
413 curr_dst->pt, curr_point->pt ) < 0 )
415 cvSubdiv2DSwapEdges( curr_edge );
416 curr_edge = cvSubdiv2DGetEdge( curr_edge, CV_PREV_AROUND_ORG );
418 else if( curr_org == first_point )
424 curr_edge = cvSubdiv2DGetEdge( cvSubdiv2DNextEdge( curr_edge ),
425 CV_PREV_AROUND_LEFT );
430 CV_Error_(CV_StsError, ("cvSubdiv2DLocate returned invalid location = %d", location) );
438 cvInitSubdivDelaunay2D( CvSubdiv2D * subdiv, CvRect rect )
440 float big_coord = 3.f * MAX( rect.width, rect.height );
441 CvPoint2D32f ppA, ppB, ppC;
442 CvSubdiv2DPoint *pA, *pB, *pC;
443 CvSubdiv2DEdge edge_AB, edge_BC, edge_CA;
444 float rx = (float) rect.x;
445 float ry = (float) rect.y;
448 CV_Error( CV_StsNullPtr, "" );
450 cvClearSet( (CvSet *) (subdiv->edges) );
451 cvClearSet( (CvSet *) subdiv );
453 subdiv->quad_edges = 0;
454 subdiv->recent_edge = 0;
455 subdiv->is_geometry_valid = 0;
457 subdiv->topleft = cvPoint2D32f( rx, ry );
458 subdiv->bottomright = cvPoint2D32f( rx + rect.width, ry + rect.height );
460 ppA = cvPoint2D32f( rx + big_coord, ry );
461 ppB = cvPoint2D32f( rx, ry + big_coord );
462 ppC = cvPoint2D32f( rx - big_coord, ry - big_coord );
464 pA = cvSubdiv2DAddPoint( subdiv, ppA, 0 );
465 pB = cvSubdiv2DAddPoint( subdiv, ppB, 0 );
466 pC = cvSubdiv2DAddPoint( subdiv, ppC, 0 );
468 edge_AB = cvSubdiv2DMakeEdge( subdiv );
469 edge_BC = cvSubdiv2DMakeEdge( subdiv );
470 edge_CA = cvSubdiv2DMakeEdge( subdiv );
472 cvSubdiv2DSetEdgePoints( edge_AB, pA, pB );
473 cvSubdiv2DSetEdgePoints( edge_BC, pB, pC );
474 cvSubdiv2DSetEdgePoints( edge_CA, pC, pA );
476 cvSubdiv2DSplice( edge_AB, cvSubdiv2DSymEdge( edge_CA ));
477 cvSubdiv2DSplice( edge_BC, cvSubdiv2DSymEdge( edge_AB ));
478 cvSubdiv2DSplice( edge_CA, cvSubdiv2DSymEdge( edge_BC ));
480 subdiv->recent_edge = edge_AB;
485 cvClearSubdivVoronoi2D( CvSubdiv2D * subdiv )
492 CV_Error( CV_StsNullPtr, "" );
494 /* clear pointers to voronoi points */
495 total = subdiv->edges->total;
496 elem_size = subdiv->edges->elem_size;
498 cvStartReadSeq( (CvSeq *) (subdiv->edges), &reader, 0 );
500 for( i = 0; i < total; i++ )
502 CvQuadEdge2D *quadedge = (CvQuadEdge2D *) reader.ptr;
504 quadedge->pt[1] = quadedge->pt[3] = 0;
505 CV_NEXT_SEQ_ELEM( elem_size, reader );
508 /* remove voronoi points */
509 total = subdiv->total;
510 elem_size = subdiv->elem_size;
512 cvStartReadSeq( (CvSeq *) subdiv, &reader, 0 );
514 for( i = 0; i < total; i++ )
516 CvSubdiv2DPoint *pt = (CvSubdiv2DPoint *) reader.ptr;
518 /* check for virtual point. it is also check that the point exists */
519 if( pt->flags & CV_SUBDIV2D_VIRTUAL_POINT_FLAG )
521 cvSetRemoveByPtr( (CvSet*)subdiv, pt );
523 CV_NEXT_SEQ_ELEM( elem_size, reader );
526 subdiv->is_geometry_valid = 0;
531 icvCreateCenterNormalLine( CvSubdiv2DEdge edge, double *_a, double *_b, double *_c )
533 CvPoint2D32f org = cvSubdiv2DEdgeOrg( edge )->pt;
534 CvPoint2D32f dst = cvSubdiv2DEdgeDst( edge )->pt;
536 double a = dst.x - org.x;
537 double b = dst.y - org.y;
538 double c = -(a * (dst.x + org.x) + b * (dst.y + org.y));
547 icvIntersectLines3( double *a0, double *b0, double *c0,
548 double *a1, double *b1, double *c1, CvPoint2D32f * point )
550 double det = a0[0] * b1[0] - a1[0] * b0[0];
555 point->x = (float) ((b0[0] * c1[0] - b1[0] * c0[0]) * det);
556 point->y = (float) ((a1[0] * c0[0] - a0[0] * c1[0]) * det);
560 point->x = point->y = FLT_MAX;
566 cvCalcSubdivVoronoi2D( CvSubdiv2D * subdiv )
569 int i, total, elem_size;
572 CV_Error( CV_StsNullPtr, "" );
574 /* check if it is already calculated */
575 if( subdiv->is_geometry_valid )
578 total = subdiv->edges->total;
579 elem_size = subdiv->edges->elem_size;
581 cvClearSubdivVoronoi2D( subdiv );
583 cvStartReadSeq( (CvSeq *) (subdiv->edges), &reader, 0 );
588 /* skip first three edges (bounding triangle) */
589 for( i = 0; i < 3; i++ )
590 CV_NEXT_SEQ_ELEM( elem_size, reader );
592 /* loop through all quad-edges */
593 for( ; i < total; i++ )
595 CvQuadEdge2D *quadedge = (CvQuadEdge2D *) (reader.ptr);
597 if( CV_IS_SET_ELEM( quadedge ))
599 CvSubdiv2DEdge edge0 = (CvSubdiv2DEdge) quadedge, edge1, edge2;
600 double a0, b0, c0, a1, b1, c1;
601 CvPoint2D32f virt_point;
602 CvSubdiv2DPoint *voronoi_point;
604 if( !quadedge->pt[3] )
606 edge1 = cvSubdiv2DGetEdge( edge0, CV_NEXT_AROUND_LEFT );
607 edge2 = cvSubdiv2DGetEdge( edge1, CV_NEXT_AROUND_LEFT );
609 icvCreateCenterNormalLine( edge0, &a0, &b0, &c0 );
610 icvCreateCenterNormalLine( edge1, &a1, &b1, &c1 );
612 icvIntersectLines3( &a0, &b0, &c0, &a1, &b1, &c1, &virt_point );
613 if( fabs( virt_point.x ) < FLT_MAX * 0.5 &&
614 fabs( virt_point.y ) < FLT_MAX * 0.5 )
616 voronoi_point = cvSubdiv2DAddPoint( subdiv, virt_point, 1 );
619 ((CvQuadEdge2D *) (edge1 & ~3))->pt[3 - (edge1 & 2)] =
620 ((CvQuadEdge2D *) (edge2 & ~3))->pt[3 - (edge2 & 2)] = voronoi_point;
624 if( !quadedge->pt[1] )
626 edge1 = cvSubdiv2DGetEdge( edge0, CV_NEXT_AROUND_RIGHT );
627 edge2 = cvSubdiv2DGetEdge( edge1, CV_NEXT_AROUND_RIGHT );
629 icvCreateCenterNormalLine( edge0, &a0, &b0, &c0 );
630 icvCreateCenterNormalLine( edge1, &a1, &b1, &c1 );
632 icvIntersectLines3( &a0, &b0, &c0, &a1, &b1, &c1, &virt_point );
634 if( fabs( virt_point.x ) < FLT_MAX * 0.5 &&
635 fabs( virt_point.y ) < FLT_MAX * 0.5 )
637 voronoi_point = cvSubdiv2DAddPoint( subdiv, virt_point, 1 );
640 ((CvQuadEdge2D *) (edge1 & ~3))->pt[1 + (edge1 & 2)] =
641 ((CvQuadEdge2D *) (edge2 & ~3))->pt[1 + (edge2 & 2)] = voronoi_point;
646 CV_NEXT_SEQ_ELEM( elem_size, reader );
649 subdiv->is_geometry_valid = 1;
654 icvIsRightOf2( const CvPoint2D32f& pt, const CvPoint2D32f& org, const CvPoint2D32f& diff )
656 double cw_area = ((double)org.x - pt.x)*diff.y - ((double)org.y - pt.y)*diff.x;
657 return (cw_area > 0) - (cw_area < 0);
661 CV_IMPL CvSubdiv2DPoint*
662 cvFindNearestPoint2D( CvSubdiv2D* subdiv, CvPoint2D32f pt )
664 CvSubdiv2DPoint* point = 0;
667 CvSubdiv2DPointLocation loc;
672 CV_Error( CV_StsNullPtr, "" );
674 if( !CV_IS_SUBDIV2D( subdiv ))
675 CV_Error( CV_StsNullPtr, "" );
677 if( subdiv->edges->active_count <= 3 )
680 if( !subdiv->is_geometry_valid )
681 cvCalcSubdivVoronoi2D( subdiv );
683 loc = cvSubdiv2DLocate( subdiv, pt, &edge, &point );
687 case CV_PTLOC_ON_EDGE:
688 case CV_PTLOC_INSIDE:
696 start = cvSubdiv2DEdgeOrg( edge )->pt;
697 diff.x = pt.x - start.x;
698 diff.y = pt.y - start.y;
700 edge = cvSubdiv2DRotateEdge( edge, 1 );
702 for( i = 0; i < subdiv->total; i++ )
708 assert( cvSubdiv2DEdgeDst( edge ));
710 t = cvSubdiv2DEdgeDst( edge )->pt;
711 if( icvIsRightOf2( t, start, diff ) >= 0 )
714 edge = cvSubdiv2DGetEdge( edge, CV_NEXT_AROUND_LEFT );
719 assert( cvSubdiv2DEdgeOrg( edge ));
721 t = cvSubdiv2DEdgeOrg( edge )->pt;
722 if( icvIsRightOf2( t, start, diff ) < 0 )
725 edge = cvSubdiv2DGetEdge( edge, CV_PREV_AROUND_LEFT );
729 CvPoint2D32f tempDiff = cvSubdiv2DEdgeDst( edge )->pt;
730 t = cvSubdiv2DEdgeOrg( edge )->pt;
734 if( icvIsRightOf2( pt, t, tempDiff ) >= 0 )
736 point = cvSubdiv2DEdgeOrg( cvSubdiv2DRotateEdge( edge, 3 ));
741 edge = cvSubdiv2DSymEdge( edge );
748 icvSubdiv2DCheck( CvSubdiv2D* subdiv )
750 int i, j, total = subdiv->edges->total;
751 CV_Assert( subdiv != 0 );
753 for( i = 0; i < total; i++ )
755 CvQuadEdge2D* edge = (CvQuadEdge2D*)cvGetSetElem(subdiv->edges,i);
757 if( edge && CV_IS_SET_ELEM( edge ))
759 for( j = 0; j < 4; j++ )
761 CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge + j;
762 CvSubdiv2DEdge o_next = cvSubdiv2DNextEdge(e);
763 CvSubdiv2DEdge o_prev = cvSubdiv2DGetEdge(e, CV_PREV_AROUND_ORG );
764 CvSubdiv2DEdge d_prev = cvSubdiv2DGetEdge(e, CV_PREV_AROUND_DST );
765 CvSubdiv2DEdge d_next = cvSubdiv2DGetEdge(e, CV_NEXT_AROUND_DST );
768 if( cvSubdiv2DEdgeOrg(e) != cvSubdiv2DEdgeOrg(o_next))
770 if( cvSubdiv2DEdgeOrg(e) != cvSubdiv2DEdgeOrg(o_prev))
772 if( cvSubdiv2DEdgeDst(e) != cvSubdiv2DEdgeDst(d_next))
774 if( cvSubdiv2DEdgeDst(e) != cvSubdiv2DEdgeDst(d_prev))
778 if( cvSubdiv2DEdgeDst(o_next) != cvSubdiv2DEdgeOrg(d_prev))
780 if( cvSubdiv2DEdgeDst(o_prev) != cvSubdiv2DEdgeOrg(d_next))
782 if( cvSubdiv2DGetEdge(cvSubdiv2DGetEdge(cvSubdiv2DGetEdge(
783 e,CV_NEXT_AROUND_LEFT),CV_NEXT_AROUND_LEFT),CV_NEXT_AROUND_LEFT) != e )
785 if( cvSubdiv2DGetEdge(cvSubdiv2DGetEdge(cvSubdiv2DGetEdge(
786 e,CV_NEXT_AROUND_RIGHT),CV_NEXT_AROUND_RIGHT),CV_NEXT_AROUND_RIGHT) != e)
799 draw_subdiv_facet( CvSubdiv2D * subdiv, IplImage * dst, IplImage * src, CvSubdiv2DEdge edge )
801 CvSubdiv2DEdge t = edge;
803 CvPoint local_buf[100];
804 CvPoint *buf = local_buf;
806 // count number of edges in facet
810 t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
812 while( t != edge && count < subdiv->quad_edges * 4 );
814 if( count * sizeof( buf[0] ) > sizeof( local_buf ))
816 buf = (CvPoint *) malloc( count * sizeof( buf[0] ));
821 for( i = 0; i < count; i++ )
823 CvSubdiv2DPoint *pt = cvSubdiv2DEdgeOrg( t );
827 assert( fabs( pt->pt.x ) < 10000 && fabs( pt->pt.y ) < 10000 );
828 buf[i] = cvPoint( cvRound( pt->pt.x ), cvRound( pt->pt.y ));
829 t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
834 CvSubdiv2DPoint *pt = cvSubdiv2DEdgeDst( cvSubdiv2DRotateEdge( edge, 1 ));
835 CvPoint ip = cvPoint( cvRound( pt->pt.x ), cvRound( pt->pt.y ));
838 //printf("count = %d, (%d,%d)\n", ip.x, ip.y );
840 if( 0 <= ip.x && ip.x < src->width && 0 <= ip.y && ip.y < src->height )
842 uchar *ptr = (uchar*)(src->imageData + ip.y * src->widthStep + ip.x * 3);
843 color = CV_RGB( ptr[2], ptr[1], ptr[0] );
846 cvFillConvexPoly( dst, buf, count, color );
847 //draw_subdiv_point( dst, pt->pt, CV_RGB(0,0,0));
850 if( buf != local_buf )
856 icvDrawMosaic( CvSubdiv2D * subdiv, IplImage * src, IplImage * dst )
858 int i, total = subdiv->edges->total;
860 cvCalcSubdivVoronoi2D( subdiv );
862 //icvSet( dst, 255 );
863 for( i = 0; i < total; i++ )
865 CvQuadEdge2D *edge = (CvQuadEdge2D *) cvGetSetElem( subdiv->edges, i );
867 if( edge && CV_IS_SET_ELEM( edge ))
869 CvSubdiv2DEdge e = (CvSubdiv2DEdge) edge;
872 draw_subdiv_facet( subdiv, dst, src, cvSubdiv2DRotateEdge( e, 1 ));
874 draw_subdiv_facet( subdiv, dst, src, cvSubdiv2DRotateEdge( e, 3 ));