git.maemo.org Git - opencv/blob - apps/Hawk/demos/delaunay.c

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