samples/c/delaunay.c

   1 #include <opencv2/imgproc/imgproc_c.h>
   2 #include <opencv2/highgui/highgui.hpp>
   3
   4 #include <stdio.h>
   5
   6 /* the script demostrates iterative construction of
   7    delaunay triangulation and voronoi tesselation */
   8
   9 CvSubdiv2D* init_delaunay( CvMemStorage* storage,
  10                            CvRect rect )
  11 {
  12     CvSubdiv2D* subdiv;
  13
  14     subdiv = cvCreateSubdiv2D( CV_SEQ_KIND_SUBDIV2D, sizeof(*subdiv),
  15                                sizeof(CvSubdiv2DPoint),
  16                                sizeof(CvQuadEdge2D),
  17                                storage );
  18     cvInitSubdivDelaunay2D( subdiv, rect );
  19
  20     return subdiv;
  21 }
  22
  23
  24 void draw_subdiv_point( IplImage* img, CvPoint2D32f fp, CvScalar color )
  25 {
  26     cvCircle( img, cvPoint(cvRound(fp.x), cvRound(fp.y)), 3, color, CV_FILLED, 8, 0 );
  27 }
  28
  29
  30 void draw_subdiv_edge( IplImage* img, CvSubdiv2DEdge edge, CvScalar color )
  31 {
  32     CvSubdiv2DPoint* org_pt;
  33     CvSubdiv2DPoint* dst_pt;
  34     CvPoint2D32f org;
  35     CvPoint2D32f dst;
  36     CvPoint iorg, idst;
  37
  38     org_pt = cvSubdiv2DEdgeOrg(edge);
  39     dst_pt = cvSubdiv2DEdgeDst(edge);
  40
  41     if( org_pt && dst_pt )
  42     {
  43         org = org_pt->pt;
  44         dst = dst_pt->pt;
  45
  46         iorg = cvPoint( cvRound( org.x ), cvRound( org.y ));
  47         idst = cvPoint( cvRound( dst.x ), cvRound( dst.y ));
  48
  49         cvLine( img, iorg, idst, color, 1, CV_AA, 0 );
  50     }
  51 }
  52
  53
  54 void draw_subdiv( IplImage* img, CvSubdiv2D* subdiv,
  55                   CvScalar delaunay_color, CvScalar voronoi_color )
  56 {
  57     CvSeqReader  reader;
  58     int i, total = subdiv->edges->total;
  59     int elem_size = subdiv->edges->elem_size;
  60
  61     cvStartReadSeq( (CvSeq*)(subdiv->edges), &reader, 0 );
  62
  63     for( i = 0; i < total; i++ )
  64     {
  65         CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
  66
  67         if( CV_IS_SET_ELEM( edge ))
  68         {
  69             draw_subdiv_edge( img, (CvSubdiv2DEdge)edge + 1, voronoi_color );
  70             draw_subdiv_edge( img, (CvSubdiv2DEdge)edge, delaunay_color );
  71         }
  72
  73         CV_NEXT_SEQ_ELEM( elem_size, reader );
  74     }
  75 }
  76
  77
  78 void locate_point( CvSubdiv2D* subdiv, CvPoint2D32f fp, IplImage* img,
  79                    CvScalar active_color )
  80 {
  81     CvSubdiv2DEdge e;
  82     CvSubdiv2DEdge e0 = 0;
  83     CvSubdiv2DPoint* p = 0;
  84
  85     cvSubdiv2DLocate( subdiv, fp, &e0, &p );
  86
  87     if( e0 )
  88     {
  89         e = e0;
  90         do
  91         {
  92             draw_subdiv_edge( img, e, active_color );
  93             e = cvSubdiv2DGetEdge(e,CV_NEXT_AROUND_LEFT);
  94         }
  95         while( e != e0 );
  96     }
  97
  98     draw_subdiv_point( img, fp, active_color );
  99 }
 100
 101
 102 void draw_subdiv_facet( IplImage* img, CvSubdiv2DEdge edge )
 103 {
 104     CvSubdiv2DEdge t = edge;
 105     int i, count = 0;
 106     CvPoint* buf = 0;
 107
 108     // count number of edges in facet
 109     do
 110     {
 111         count++;
 112         t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
 113     } while (t != edge );
 114
 115     buf = (CvPoint*)malloc( count * sizeof(buf[0]));
 116
 117     // gather points
 118     t = edge;
 119     for( i = 0; i < count; i++ )
 120     {
 121         CvSubdiv2DPoint* pt = cvSubdiv2DEdgeOrg( t );
 122         if( !pt ) break;
 123         buf[i] = cvPoint( cvRound(pt->pt.x), cvRound(pt->pt.y));
 124         t = cvSubdiv2DGetEdge( t, CV_NEXT_AROUND_LEFT );
 125     }
 126
 127     if( i == count )
 128     {
 129         CvSubdiv2DPoint* pt = cvSubdiv2DEdgeDst( cvSubdiv2DRotateEdge( edge, 1 ));
 130         cvFillConvexPoly( img, buf, count, CV_RGB(rand()&255,rand()&255,rand()&255), CV_AA, 0 );
 131         cvPolyLine( img, &buf, &count, 1, 1, CV_RGB(0,0,0), 1, CV_AA, 0);
 132         draw_subdiv_point( img, pt->pt, CV_RGB(0,0,0));
 133     }
 134     free( buf );
 135 }
 136
 137 void paint_voronoi( CvSubdiv2D* subdiv, IplImage* img )
 138 {
 139     CvSeqReader  reader;
 140     int i, total = subdiv->edges->total;
 141     int elem_size = subdiv->edges->elem_size;
 142
 143     cvCalcSubdivVoronoi2D( subdiv );
 144
 145     cvStartReadSeq( (CvSeq*)(subdiv->edges), &reader, 0 );
 146
 147     for( i = 0; i < total; i++ )
 148     {
 149         CvQuadEdge2D* edge = (CvQuadEdge2D*)(reader.ptr);
 150
 151         if( CV_IS_SET_ELEM( edge ))
 152         {
 153             CvSubdiv2DEdge e = (CvSubdiv2DEdge)edge;
 154             // left
 155             draw_subdiv_facet( img, cvSubdiv2DRotateEdge( e, 1 ));
 156
 157             // right
 158             draw_subdiv_facet( img, cvSubdiv2DRotateEdge( e, 3 ));
 159         }
 160
 161         CV_NEXT_SEQ_ELEM( elem_size, reader );
 162     }
 163 }
 164
 165
 166 void run(void)
 167 {
 168     char win[] = "source";
 169     int i;
 170     CvRect rect = { 0, 0, 600, 600 };
 171     CvMemStorage* storage;
 172     CvSubdiv2D* subdiv;
 173     IplImage* img;
 174     CvScalar active_facet_color, delaunay_color, voronoi_color, bkgnd_color;
 175
 176     active_facet_color = CV_RGB( 255, 0, 0 );
 177     delaunay_color  = CV_RGB( 0,0,0);
 178     voronoi_color = CV_RGB(0, 180, 0);
 179     bkgnd_color = CV_RGB(255,255,255);
 180
 181     img = cvCreateImage( cvSize(rect.width,rect.height), 8, 3 );
 182     cvSet( img, bkgnd_color, 0 );
 183
 184     cvNamedWindow( win, 1 );
 185
 186     storage = cvCreateMemStorage(0);
 187     subdiv = init_delaunay( storage, rect );
 188
 189     printf("Delaunay triangulation will be build now interactively.\n"
 190            "To stop the process, press any key\n\n");
 191
 192     for( i = 0; i < 200; i++ )
 193     {
 194         CvPoint2D32f fp = cvPoint2D32f( (float)(rand()%(rect.width-10)+5),
 195                                         (float)(rand()%(rect.height-10)+5));
 196
 197         locate_point( subdiv, fp, img, active_facet_color );
 198         cvShowImage( win, img );
 199
 200         if( cvWaitKey( 100 ) >= 0 )
 201             break;
 202
 203         cvSubdivDelaunay2DInsert( subdiv, fp );
 204         cvCalcSubdivVoronoi2D( subdiv );
 205         cvSet( img, bkgnd_color, 0 );
 206         draw_subdiv( img, subdiv, delaunay_color, voronoi_color );
 207         cvShowImage( win, img );
 208
 209         if( cvWaitKey( 100 ) >= 0 )
 210             break;
 211     }
 212
 213     cvSet( img, bkgnd_color, 0 );
 214     paint_voronoi( subdiv, img );
 215     cvShowImage( win, img );
 216
 217     cvWaitKey(0);
 218
 219     cvReleaseMemStorage( &storage );
 220     cvReleaseImage(&img);
 221     cvDestroyWindow( win );
 222 }
 223
 224 int main( int argc, char** argv )
 225 {
 226 #ifdef _MSC_VER
 227     argc, argv;
 228 #endif
 229     run();
 230     return 0;
 231 }
 232
 233 #ifdef _EiC
 234 main( 1, "delaunay.c" );
 235 #endif