Subject: CGAL users discussion list
List archive
- From: "Wesley Smith" <>
- To:
- Subject: Voronoi_diagram_3 design question
- Date: Tue, 18 Sep 2007 11:06:31 -0700
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=gAGIAoxFhOFy9OdWYQCTQItSNHTt8moESrYe+rkQhmjHAoX/dcZQIexv7B3AJWUAKx/65Pj9Pbzq96QJSvPChFVOvKdOfR/832zUjpivg0OMJJJJ4oCL/NJa+q19/YxeMMe6bIdnK1mgB+wArr8J/PoPyDjLGVObZ5K9ajs/c8s=
Hi,
I'm fairly far along in the desing of a Voronoi_diagram_3 class
similar to Voronoi_diagram_2. Right now I'm implementing iteration of
the voronoi faces and edges and have a few design questions for the
more experienced CGAL developers:
In 3D, what was a face in 2D becomes rather more complicated. Here
I'm defining a 3D face as the set of duals of all of the edges
incident to a Delaunay vertex. Is this the proper term or is there
another name for this construct? I haven't been able to find anything
in the literature about this.
In my current implementation, I have designed a voronoi face
circulator to traverse the edges of the voronoi diagram analogous to
this function in the 2D case: Ccb_halfedge_circulator
vd.ccb_halfedges ( Face_handle f) . It's basically an adaptation of
an iterator of the set of incident facets to the Delaunay vertex dual
of the face. The way the iteration works, if the Delaunay vertex is
on the exterior hull (crust?) of the triangulation, the iterator will
search for facets on the crust (rays in the voronoi diagram) and
follow them (by looking at neighboring facets over incident edges)
until it terminates at another ray. This way, iteration will
guarantee connected rays-segment sequences. The biggest issue with
this approach is avoiding duplication since a ray can be visited via
another ray before the iterator of the incident Delaunay facets
reaches it. To keep track of this, I designed a class called
Dual_halfedge which doesn't have an analogous representation in the 2D
CGAL code. Essentially it represents an edge in the Delaunay
triangulation uniquely. If I have a Dual_halfedge object that
represents a particular edge in one Cell and another in an adjacent
cell that is actually the same edge but with different indices and
Cell_handle values, they will be equivalent according to the ==
operator. In other words, equality is global in scope. This was done
so that when I keep track of visited Voronoi facets it's easy to
compare equality without having to constantly do all of translation of
vertex indices between cells. Does this seem reasonable?
best,
wes
- Voronoi_diagram_3 design question, Wesley Smith, 09/18/2007
- Re: Voronoi_diagram_3 design question, Wesley Smith, 09/19/2007
Archive powered by MHonArc 2.6.16.