samples/c/delaunay.c

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