1 /* the script demostrates iterative construction of
\r
2 delaunay triangulation and voronoi tesselation */
\r
4 CvSubdiv2D* init_delaunay( CvMemStorage* storage,
\r
9 subdiv = cvCreateSubdiv2D( CV_SEQ_KIND_SUBDIV2D, sizeof(*subdiv),
\r
10 sizeof(CvSubdiv2DPoint),
\r
11 sizeof(CvQuadEdge2D),
\r
13 cvInitSubdivDelaunay2D( subdiv, rect );
\r
19 void draw_subdiv_point( IplImage* img, CvPoint2D32f fp, int color )
\r
21 cvCircle( img, cvPoint(cvRound(fp.x), cvRound(fp.y)), 3, color, CV_FILLED );
\r
25 void draw_subdiv_edge( IplImage* img, CvSubdiv2DEdge edge, int color )
\r
27 CvSubdiv2DPoint* org_pt;
\r
28 CvSubdiv2DPoint* dst_pt;
\r
33 org_pt = cvSubdiv2DEdgeOrg(edge);
\r
34 dst_pt = cvSubdiv2DEdgeDst(edge);
\r
36 if( org_pt && dst_pt )
\r
41 iorg = cvPoint( cvRound( org.x ), cvRound( org.y ));
\r
42 idst = cvPoint( cvRound( dst.x ), cvRound( dst.y ));
\r
44 cvLineAA( img, iorg, idst, color, 0 );
\r
49 void draw_subdiv( IplImage* img, CvSubdiv2D* subdiv,
\r
50 int delaunay_color, int voronoi_color )
\r
53 int i, total = subdiv->edges->total;
\r
54 int elem_size = subdiv->edges->elem_size;
\r
57 cvStartReadSeq( (CvSeq*)(subdiv->edges), &reader, 0 );
\r
59 for( i = 0; i < total; i++ )
\r
61 CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
\r
63 if( CV_IS_SET_ELEM_EXISTS( edge ))
\r
65 draw_subdiv_edge( img, (CvSubdiv2DEdge)edge + 1, voronoi_color );
\r
66 draw_subdiv_edge( img, (CvSubdiv2DEdge)edge, delaunay_color );
\r
69 CV_NEXT_SEQ_ELEM( elem_size, reader );
\r
74 void locate_point( CvSubdiv2D* subdiv, CvPoint2D32f fp, IplImage* img,
\r
77 CvSubdiv2DEdge e = 0;
\r
78 CvSubdiv2DEdge e0 = 0;
\r
79 CvSubdiv2DPoint* p = 0;
\r
80 CvSubdiv2DPointLocation location = cvSubdiv2DLocate( subdiv, fp, &e0, &p );
\r
87 draw_subdiv_edge( img, e, active_color );
\r
88 e = cvSubdiv2DGetEdge(e,CV_NEXT_AROUND_LEFT);
\r
93 draw_subdiv_point( img, fp, active_color );
\r
97 void draw_subdiv_facet( IplImage* img, CvSubdiv2DEdge edge )
\r
99 CvSubdiv2DEdge t = edge;
\r
103 // count number of edges in facet
\r
107 t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
\r
108 } while (t != edge );
\r
110 buf = (CvPoint*)malloc( count * sizeof(buf[0]));
\r
114 for( i = 0; i < count; i++ )
\r
116 CvSubdiv2DPoint* pt = cvSubdiv2DEdgeOrg( t );
\r
118 buf[i] = cvPoint( cvRound(pt->pt.x), cvRound(pt->pt.y));
\r
119 t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
\r
124 CvSubdiv2DPoint* pt = cvSubdiv2DEdgeDst( cvSubdiv2DRotateEdge( edge, 1 ));
\r
125 cvFillConvexPoly( img, buf, count, CV_RGB(rand(),rand(),rand()));
\r
126 cvPolyLineAA( img, &buf, &count, 1, 1, CV_RGB(0,0,0), 0);
\r
127 draw_subdiv_point( img, pt->pt, CV_RGB(0,0,0));
\r
132 void paint_voronoi( CvSubdiv2D* subdiv, IplImage* img )
\r
134 CvSeqReader reader;
\r
135 int i, total = subdiv->edges->total;
\r
136 int elem_size = subdiv->edges->elem_size;
\r
138 cvCalcSubdivVoronoi2D( subdiv );
\r
140 cvStartReadSeq( (CvSeq*)(subdiv->edges), &reader, 0 );
\r
142 for( i = 0; i < total; i++ )
\r
144 CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
\r
146 if( CV_IS_SET_ELEM_EXISTS( edge ))
\r
148 CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
\r
150 draw_subdiv_facet( img, cvSubdiv2DRotateEdge( e, 1 ));
\r
153 draw_subdiv_facet( img, cvSubdiv2DRotateEdge( e, 3 ));
\r
156 CV_NEXT_SEQ_ELEM( elem_size, reader );
\r
163 char win[] = "source";
\r
167 CvRect rect = { 0, 0, 600, 600 };
\r
168 CvMemStorage* storage;
\r
169 CvSubdiv2D* subdiv;
\r
171 int active_facet_color, delaunay_color, voronoi_color, bkgnd_color;
\r
173 active_facet_color = CV_RGB( 255, 0, 0 );
\r
174 delaunay_color = CV_RGB( 0,0,0);
\r
175 voronoi_color = CV_RGB(0, 180, 0);
\r
176 bkgnd_color = CV_RGB(255,255,255);
\r
178 img = cvCreateImage( cvSize(rect.width,rect.height), 8, 3 );
\r
180 named_window( win, 0 );
\r
181 cvFillImage( img, bkgnd_color );
\r
183 storage = cvCreateMemStorage(0);
\r
184 subdiv = init_delaunay( storage, rect );
\r
186 printf("Delaunay triangulation will be build now interactively.\n"
\r
187 "To stop the process, press Escape\n\n");
\r
189 for( i = 0; i < 200; i++ )
\r
191 CvPoint2D32f fp = cvPoint2D32f( (float)(rand()%(rect.width-10)+5),
\r
192 (float)(rand()%(rect.height-10)+5));
\r
194 locate_point( subdiv, fp, img, active_facet_color );
\r
195 show_iplimage( win, img );
\r
197 q_flag = wait_key_ex( win, 100 ) == 27;
\r
198 if( q_flag ) break;
\r
200 cvSubdivDelaunay2DInsert( subdiv, fp );
\r
201 cvCalcSubdivVoronoi2D( subdiv );
\r
202 cvFillImage( img, bkgnd_color );
\r
203 draw_subdiv( img, subdiv, delaunay_color, voronoi_color );
\r
204 show_iplimage( win, img );
\r
206 q_flag = wait_key_ex( win, 100 ) == 27;
\r
207 if( q_flag ) break;
\r
210 if( !q_flag ) wait_key( win );
\r
211 cvFillImage( img, bkgnd_color );
\r
212 paint_voronoi( subdiv, img );
\r
213 show_iplimage( win, img );
\r
215 cvReleaseMemStorage( &storage );
\r
216 cvReleaseImage(&img);
\r