Boost logo

Boost :

From: Huseyin Akcan (huseyinakcan_at_[hidden])
Date: 2007-08-29 21:41:01


As SoC officially ended, I wanted to summarize what has been done and
not done in the halfedge data structure project ( also the generic
geometry library project).

- First the concept classes for the different halfedge data structures
are implemented. The concepts are
   hds_concept, forward_hds_concept, backward_hds_concept,
bidirectional_hds_concept, facet_hds_concept, vertex_hds_concept,
facet_list_hds_concept, vertex_list_hds_concept,
halfedge_list_hds_concept, and mutable versions of all these concepts.

Each concept class is created in its own file (component), which
allowed us to add class level
doxygen documentation to all the components and create test files for
each component separately.

- Archetypes are implemented including the class level documentation
and test files for each archetype.
- After the concepts and archetypes are implemented and fully tested,
we implemented the halfedge data structure itself, which is composed
of the following components:
-- container_selectors and container_gen: these handle the selection
of the containers for different value types, and helper functions for
low level manipulation of the STL containers, such as add, delete etc.
-- halfedge_selectors and halfedge_functions : the concrete
implementation of stored halfedge for various configurations of
halfedge data structure, along with various functions to access and
manipulate the halfedges.
-- facet_selectors and facet_functions : concrete implementation of
stored facets along with various functions to access and manipulate
-- vertex_selectors and vertex_functions: similar to facets.

All the components are again has its own class level documentation,
usage example, in code documentation and test files to test all
possible selections and manipulations.

- Having implemented the main halfedge data structure, along with
documentation and full tests, we started adding Euler operators to
access and manipulate the halfedge data structure. We first
implemented the small functions that are commonly used in Euler
operators (stitch functions as its called in code) along with
documentation and test cases, later the baseline of the Euler
operators are added.

The above mentioned implementation took more time than anticipated so
although it was in the original proposal, I could not complete the
following parts of the project:
- Test classes for Euler operators
- High level example algorithms such as Delaunay triangulation, and others.
- Adapters for existing libraries such as CGAL and LEDA
- Full documentation for the project (although currently each
component is well documented on its own )

Although the summer of code is officially over, I do plan to work on
the project for the next couple of months. I wish to finish the
proposed parts and put it in a more complete shape.

Finally, I really enjoyed working on the project, learned a lot and
gained a lot of experience.
I would like to thank the Boost community, and especially my mentor
Herve for the opportunity and support.



PS: the source code can be accessed from here (from Trac interface):

Boost list run by bdawes at, gregod at, cpdaniel at, john at