git.maemo.org Git - opencv/blob - samples/c/delaunay.c

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