 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Michael Olea
Guest
|
 Posted: Tue Aug 22, 2006 5:32 am Post subject: Contour Iterators (or Cursors) |
 |
|
Hi.
Recently I have been working on problems where I need to iterate over a
cyclic structure; the edges of a "face" in a planar map, for example (a
planar map partitions the plane into faces, edges, and vertices). In this
case the planar map is encoded as a "doubly connected edge list". Each edge
has a start vertex and an end vertex (giving it a direction), a left face
and a right face, and next and previous edges. The idea is to iterate over
the edges forming the outer contour of a face, given the face and some edge
on its outer contour. I would like to use the STL start/end approach
(actually, a cursor/property_map approach, but that is not the issue here).
The difficulty is that the start and end are the same edge. A GOF style
iterator (ignoring error checking, and type parameterization issues) is
simple:
class EdgeIterator
{
public:
EdgeIterator(const PlanarFace *pF, const PlanarEdge *pE)
: pFace(pF), pEStart(pE), pENext(0) {}
const PlanarEdge* First()
{
if (! pEStart)
return pEStart;
if ( pEStart->LeftFace() == pFace )
pENext = pEStart->Next();
else
pENext = pEStart->Previous();
return pEStart;
}
const PlanarEdge* Next()
{
if ( pENext == pEStart )
return 0;
const PlanarEdge *pE = pENext;
if ( pENext->LeftFace() == pFace )
pENext = pENext->Next();
else
pENext = pENext->Previous();
return pE;
}
private:
const PlanarFace *pFace;
const PlanarEdge *pEStart;
const PlanarEdge *pENext;
};
The only idea I have had so far for creating a Start/End pair is to make an
adaptor (ignoring many details):
class EdgeIteratorAdaptor : private EdgeIterator
{
public:
EdgeIteratorAdaptor(const PlanarFace *pF, const PlanarEdge *pE)
: EdgeIterator(pF, pE), pEdge(First()) {}
const PlanarEdge operator*() const { return pEdge; }
EdgeIteratorAdaptor& operator++() { pEdge = Next(); return *this; }
bool operator==(const EdgeIteratorAdaptor& x) const
{ return pEdge == x.pEdge; }
bool operator!=(const EdgeIteratorAdaptor& x) const
{ return pEdge != x.pEdge; }
private:
const PlanarEdge *pEdge;
};
class PlanarFace
{
....
EdgeIteratorAdaptor begin(const PlanarEdge *p) const
{ return EdgeIteratorAdaptor(this, p); }
EdgeIteratorAdaptor end() const
{ return EdgeIteratorAdaptor(this, 0); }
....
};
Any better ideas?
-- Michael
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
Michael Olea
Guest
|
| Posted: Tue Aug 22, 2006 11:14 pm Post subject: Re: Contour Iterators (or Cursors) |
|
|
Mike wrote:
| Quote: | Michael Olea wrote:
Hi.
Recently I have been working on problems where I need to iterate over a
cyclic structure; the edges of a "face" in a planar map, for example (a
planar map partitions the plane into faces, edges, and vertices). In this
case the planar map is encoded as a "doubly connected edge list". Each
edge
has a start vertex and an end vertex (giving it a direction), a left face
and a right face, and next and previous edges. The idea is to iterate
over the edges forming the outer contour of a face, given the face and
some
edge
on its outer contour. I would like to use the STL start/end approach
(actually, a cursor/property_map approach, but that is not the issue
here).
The difficulty is that the start and end are the same edge. A GOF style
iterator (ignoring error checking, and type parameterization issues) is
simple:
snip iterator class design
Any better ideas?
If your working on graph algorithms with edges and vertices, you might
want to consider using the Boost Graph Library (see
http://www.boost.org/libs/graph/doc/table_of_contents.html).
|
That does not help in this case. There is, last I checked, no notoion of
"face" in the BGL. A face is an element of planar maps (a particular kind
of graph) but not of graphs in general. I need to iterate the edges
incident on a face. In particular, the iteration can start at any edge on
the face.
The broader question is about iterating cyclic sequences, where "begin" and
"end" are the same location. What approaches are people using?
-- Michael
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Louis Lavery
Guest
|
| Posted: Wed Aug 23, 2006 2:03 am Post subject: Re: Contour Iterators (or Cursors) |
|
|
Michael Olea wrote:
| Quote: | Mike wrote:
Michael Olea wrote:
Hi.
Recently I have been working on problems where I need to iterate over a
cyclic structure; the edges of a "face" in a planar map, for example (a
planar map partitions the plane into faces, edges, and vertices). In this
case the planar map is encoded as a "doubly connected edge list". Each
edge
has a start vertex and an end vertex (giving it a direction), a left face
and a right face, and next and previous edges. The idea is to iterate
over the edges forming the outer contour of a face, given the face and
some
edge
on its outer contour. I would like to use the STL start/end approach
(actually, a cursor/property_map approach, but that is not the issue
here).
The difficulty is that the start and end are the same edge. A GOF style
iterator (ignoring error checking, and type parameterization issues) is
simple:
snip iterator class design
Any better ideas?
If your working on graph algorithms with edges and vertices, you might
want to consider using the Boost Graph Library (see
http://www.boost.org/libs/graph/doc/table_of_contents.html).
That does not help in this case. There is, last I checked, no notoion of
"face" in the BGL. A face is an element of planar maps (a particular kind
of graph) but not of graphs in general. I need to iterate the edges
incident on a face. In particular, the iteration can start at any edge on
the face.
The broader question is about iterating cyclic sequences, where "begin"
and
"end" are the same location. What approaches are people using?
|
I'm using the concept of a Cycle (Cn in graph theory parlance)
i.e. a circular chain of vertices and edges.
It has two types of iterator (actually cursors), one for the
edges and one for the vertices, they are not circular - they
just iterate the edges/vertices (in an undefined order).
An edge cursor dereferences to yield an edge descriptor.
An edge descriptor can be used to obtain its source and target
vertices.
A vertex cursor dereferences to yield a vertex descriptor.
A vertex descriptor can be used to obtain its in and out
edges.
The design is heavily influenced by the BGL.
An alternative is CGAL's circulators.
Louis.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Drew Hall
Guest
|
| Posted: Wed Aug 23, 2006 2:21 am Post subject: Re: Contour Iterators (or Cursors) |
|
|
Michael Olea wrote:
| Quote: |
The broader question is about iterating cyclic sequences, where "begin"
and
"end" are the same location. What approaches are people using?
|
Here's one approach that would probably work:
Within your edge iterator class, you store two edge pointers and a flag
indicating if you've left the "begin" node:
struct edge_iterator
{
edge* cursor;
edge* start_node;
bool left_home;
edge_iterator& operator++()
{
cursor = cursor->next;
left_home = true;
}
};
struct face
{
edge* first;
edge_iterator begin() const
{
return edge_iterator(first, first, false);
}
edge_iterator end() const
{
return edge_iterator(first, first, true);
}
};
So, the idea is that the edge iterator remembers where it started,
where it is currently, and whether it ever left (indicated by toggling
the "left home" flag during the first increment operation). My
implementation leaves something to be desired for brevity's sake, but I
think the idea is solid enough (if a tad inelegant).
HTH,
Drew
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
