RomanStanchak - OpenCV Library Wiki

Roman Stanchak

Email: <rstancha AT SPAMFREE cse DOT wustl DOT edu>

CvSubdiv2D

I'm continually hung up figuring out how to navigate the CvSubdiv2D data structure. I've tried to settle this for my benefit and others' here.

Iterating through elements

First some helper macros

   1 #define CV_SUBDIV2D_POINT_IS_DELAUNAY( pt ) \
   2 (CV_IS_SET_ELEM(pt) && ((pt)->flags & CV_SUBDIV2D_VIRTUAL_POINT_FLAG)==0)
   3 #define CV_SUBDIV2D_POINT_IS_VORONOI( pt ) \
   4 (CV_IS_SET_ELEM(pt) && ((pt)->flags & CV_SUBDIV2D_VIRTUAL_POINT_FLAG)!=0)

=== Iterating through Delaunay vertices (input point set + 3 boundary points)===

   1     cvStartReadSeq((CvSeq *)subdiv, &reader);
   2     for(int i=0; i<subdiv->total; i++){
   3         CvSubdiv2DPoint * pt = (CvSubdiv2DPoint *) reader.ptr;
   4         if(CV_SUBDIV2D_POINT_IS_DELAUNAY(pt)){
   5             printf("%f %f\n", pt->pt.x, pt->pt.y);
   6         }
   7         CV_NEXT_SEQ_ELEM(subdiv->elem_size, reader);
   8     }

==== Iterating through Delaunay edges (triangulation of original point set)====

   1     cvStartReadSeq((CvSeq *)subdiv->edges, &reader);
   2     for(int i=0; i<subdiv->edges->total; i++){
   3         CvQuadEdge2D * edge = (CvQuadEdge2D *) reader.ptr;
   4         if(CV_IS_SET_ELEM(edge)){
   5             CvSubdiv2DPoint * org = cvSubdiv2DEdgeOrg( (CvSubdiv2DEdge) edge );
   6             CvSubdiv2DPoint * dst = cvSubdiv2DEdgeDst( (CvSubdiv2DEdge) edge );
   7             if(org && dst && CV_SUBDIV2D_POINT_IS_DELAUNAY(org)){
   8                 printf("[%f %f] -> [%f %f]\n", org->pt.x, org->pt.y, dst->pt.x, dst->pt.y);
   9             }
  10         }
  11         CV_NEXT_SEQ_ELEM(subdiv->edges->elem_size, reader);
  12     }

Voronoi Vertices

   1     cvStartReadSeq((CvSeq *)subdiv, &reader);
   2     for(int i=0; i<subdiv->total; i++){
   3         CvSubdiv2DPoint * pt = (CvSubdiv2DPoint *) reader.ptr;
   4         if(CV_SUBDIV2D_POINT_IS_VORONOI(pt)){
   5             printf("%f %f\n", pt->pt.x, pt->pt.y);
   6         }
   7         CV_NEXT_SEQ_ELEM(subdiv->elem_size, reader);
   8     }

Voronoi Edges

   1     printf("Voronoi Edges ----------------------\n");
   2     cvStartReadSeq((CvSeq *)subdiv->edges, &reader);
   3     for(int i=0; i<subdiv->edges->total; i++){
   4         CvQuadEdge2D * edge = (CvQuadEdge2D *) reader.ptr;
   5         if(CV_IS_SET_ELEM(edge)){
   6             CvSubdiv2DPoint * org = cvSubdiv2DEdgeOrg( cvSubdiv2DRotateEdge((CvSubdiv2DEdge) edge, 1) );
   7             CvSubdiv2DPoint * dst = cvSubdiv2DEdgeDst( cvSubdiv2DRotateEdge((CvSubdiv2DEdge) edge, 1) );
   8             if(org && dst && CV_SUBDIV2D_POINT_IS_VORONOI(org)){
   9                 printf("[%f %f] -> [%f %f]\n", org->pt.x, org->pt.y, dst->pt.x, dst->pt.y);
  10             }
  11         }
  12         CV_NEXT_SEQ_ELEM(subdiv->edges->elem_size, reader);
  13     }

Coming soon -- how to iterate through faces

NOTE: One can't use CvGraphScanner on CvSubdiv2D because it modifies the 'flags' field of CvSubdiv2DPoint, presumably to determine if the vertex has been visited.

CategoryHomepage