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 ));
added
removed
modules/legacy/src/subdiv2.cpp
