All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Public Member Functions | List of all members
kjb::qd::Doubly_connected_edge_list Class Reference

data structure for a planar subdivision made by edges More...

#include <dcel.h>


struct  Edge_record
struct  Face_record
struct  Vertex_record

Public Member Functions

const std::vector
< Vertex_record > & 
get_vertex_table () const
const std::vector< Edge_record > & get_edge_table () const
const std::vector< Face_record > & get_face_table () const
 Doubly_connected_edge_list ()
 Doubly_connected_edge_list (const RatPoint_line_segment &)
 build a DCEL of a single segment. More...
void swap (Doubly_connected_edge_list &dcel)
size_t lookup_vertex (const RatPoint &, bool *=00) const
 look up a vertex index by its location More...
Doubly_connected_edge_list merge (const Doubly_connected_edge_list &d) const
Doubly_connected_edge_listtranslate (const RatPoint &)
 Transform by translation (rigid motion by an x and y offset) More...
Doubly_connected_edge_listtransform (const RatPoint::Rat[])
 Transform using a row-major 3x3 homogeneous matrix on each vertex. More...
Doubly_connected_edge_listtransform (const std::vector< RatPoint::Rat > &x)
 transform using a row-major 3x3 homogeneous matrix on each vertex More...
void build_cycle_table () const
int get_cycle (size_t ei) const
 Query with an edge index, return value is a cycle number. More...
size_t get_edge_of_cycle (int cn) const
 Query with a cycle number, return the index of some edge on it. More...
size_t get_number_of_cycles () const
 Return the number of (real) edge cycles in the DCEL. More...

Detailed Description

data structure for a planar subdivision made by edges

Quick overview

This implements the planar geometric data structure of Muller and Preparata (1978) called the Doubly-connected Edge List, or DCEL for short. The plane is subdivided by non-degenerate line segments into one or more faces (maximal connected sets of points mutually reachable without crossing any segments). The segments are organized into paired structures usually called "half-edges," and their endpoints are called vertices. Every vertex is the endpoint of a line segment. The key insight of this structure, which abbreviate as DCEL, is the use of half-edges, which are incident to only one face, and linked into non-crossing cycles. Isolated segments are supported, but not isolated vertices.

The tables of the DCEL are public, and straighforward. There are few class operations supported by the basic structure:

Merging two DCELs is a nontrivial operation that creates any necessary new vertices, edges, and faces based on the overlay of the input DCELs.

Detailed explanation

Each vertex, half-edge and face gets a record in the respective table below. Faces are maximal connected sets of points mutually reachable without crossing any segments, and including points not in any segment. For brevity I will refer to half-edges simply as edges. Vertex table records are pairwise-distinct, as are edge and face records. Obviously, the tables have finite length. One consequence is that the DCEL cannot represent infinite collections of vertices, edges, or faces. Edges have finite length, and all faces have finite area except for the ever-present unbounded outer face. An empty DCEL has no vertices or edges, just an unbounded outer face.

Edges are directed. Each edge e has an origin vertex, origin(e), and a distinct destination vertex, destination(e), which are the endpoints of the corresponding line segment. Each edge e also has a distinct twin edge, twin(e), such that origin(twin(e)) = destination(e) and destination(twin(e)) = origin(e). Each edge has a valid, distinct previous edge and next edge. Therefore, using a pigeonhole-principle argument, each edge must be a member of some edge cycle. For example, a DCEL made of a single line segment consists of two twinned edges, forming a two-cycle. We write cycle(e) to denote the set of edges in the cycle including e. Naturally, e is a member of cycle(e). The word "distinct" here is meant to exclude the possibility that e=twin(e), or e=next(e), or e=previous(e), or that origin(e)=destination(e): none of those conditions may occur.

Edges are closed: their endpoints are considered part of the edge. Because of twinning, every vertex is an endpoint of at least two edges. Edges do not cross: no point internal to e is in any other edge. The endpoints of an edge are said to be "incident vertices," and the edges touching a vertex are said to be "incident edges."

Since edges are directed, we can identify left and right sides of the edge (when oriented forwards from origin to destination). Because of twinning, we adopt the convention that, for edge e, only the face to the left of e is incident to it (i.e., touches). Whereas the face on the right side of e is incident to twin(e). (I like to say that the right-side face is "twincident" to e.) We denote the face on the left side of e by face(e). In general, face(e) and face(twin(e)) may differ. However, we maintain the invariant that face(e)=face(next(e)) everywhere. By induction, it holds for the whole cycle, and thus we may speak of the face incident to a cycle of edges, since the same face lies to the left of each edge. We denote it face(cycle(e)). However, a cycle does not have a single well-defined twincident face, since possibly every edge may have a different twincident face.

Edge cycles do not cross. As a simple consequence of the property face(e)=face(next(e)), edge cycles of different faces cannot "cross" each other: consider edges e and next(e). There can be no other in-edge or out-edge incident to v = destination(e) from a different cycle lying in the sector centered at v and bounded on the left side of e and next(e). (For the formal sticklers: the sector is really bounded by rays from v coincident with e and next(e).) The reason is simply that if one or more such interlopers did exist, one of them would have face(e) on its left side, contradicting the assumption that it is the of a cycle of a different face. However, we push this idea a step further: we allow no cycles to cross; nor may a cycle cross itself. Thus in the above scenario for e, there are no edges incident to v in that sector. We claim this is not a handicap: when dealing with edges incident to v and the same face, their previous and next fields always may be permuted to preserve the same vertices, edges and faces and all the other invariants, and also not cross previous-next links.

When a set of line segments encloses a face f, there will be an entry for it in the face table, with index of 1 or higher. The index-0 face always denotes the unbounded outer face that surrounds all vertices, edges, and any other faces. The line segments around f will induce at least two edge cycles, one of which, k, will be incident to f and trace around the "outer" border of f in a counter-clockwise direction. (The meaning of "outer" here probably is intuitive, but we define it later just in case.) As argued above, each edge in k is incident to f, thus has points of f to its left. One representative edge of k will have its index recorded in the outer_component field of f's face record. Any edge in k will do. The index-0 face, naturally, does not have a meaningful index in that field since it has no outer component.

If you need it, here is a slightly more formal definition of what makes cycle k an outer border. A cycle k is defined to be a border if there exists an edge e in k such that face(e) and face(twin(e)) differ. (The property needn't hold for all of k's edges. Border cycle k is defined as an outer border of its face when there exists a point p on an edge of k such that there exists a curve c connecting p to "infinity" (say, any point on the circumference of any circle enclosing all vertices), such that the only intersection of c and f is point p. Informally, c does not have to cross any points of f to get away. A finite face f has exactly one outer border, since f must be connected, cycles are disjoint, and edge records are distinct. The index-0 face (the only face that is not finite) is unbounded and lacks an outer border.

If k is border of f but not an outer border of f, we may say it is an inner border of f, but this is not a very useful concept since cycles need not be borders at all. Any cycle that is not an outer border is referred to as an "inner component": perhaps an inner border, or perhaps a cycle tracing the perimeter of a shape without area (like a zig-zag or asterisk). Observe that for every edge on the latter kind of inner component, its incident and "twincident" face are the same face. Even on a border cycle, not every edge in the cycle need be the boundary between two faces (e.g., a "lollipop" shape with a stem segment sticking out or a face with an "ingrown hair"). Each inner component in face f is represented in f's "inner_components" field by the index of one of its edges – any edge in the cycle will do. To be a little more formal, for each face f, its inner_components field is a list, in arbitrary order, of edge indices e1, e2, . . ., en, such that f = face(e1) = face(e2) = . . . = face(en). When regarded as a set of sets of edges, {cycle(e1), cycle(e2), . . . , cycle(en)} is a partition of all edges incident to f that are not members of f's outer border cycle (if any).

For example, if by chance f were the only bounded face, there would also be an edge cycle tracing clockwise, incident to the index-0 face and "twincident" to f on at least a few of its edges. Face f would be a "hole" in the index-0 face. The index-0 face record would store the index of one edge of that index in its inner_components field. Any face can have holes or other inner components. A hole in g is a face h distinct from g, such that a closed curve could be drawn around h consisting only of interior points of g. For each hole h within g, there is a clockwise cycle incident to g that is an inner border of g, and a counterclockwise cycle incident to h that is an outer border of h. One edge index of the clockwise cycle is listed in the "inner_components" list of the face-record for g. Also listed in the "inner_components" list are non-border cycles that lie within g. And, of course, one edge index of the outer border of h is listed in the outer_components field of the face-record of h.

This implementation of the DCEL is based on the exposition by de Berg et al., Computational Geometry, and they refer primarily to the work of Muller and Preparata (1978).

To summarize the above invariants:

Constructor & Destructor Documentation

kjb::qd::Doubly_connected_edge_list::Doubly_connected_edge_list ( )
kjb::qd::Doubly_connected_edge_list::Doubly_connected_edge_list ( const RatPoint_line_segment s)

build a DCEL of a single segment.

If the segment has distinct endpoints, then two vertices and two edges are entered into a blank DCEL.

If the segment is degenerate (i.e., just one point) the single point is NOT entered, and the DCEL is blank, because our DCEL does not support lonesome vertices. Each vertex must be the origin and destination of distinct edges.

Member Function Documentation

void kjb::qd::Doubly_connected_edge_list::build_cycle_table ( ) const
int kjb::qd::Doubly_connected_edge_list::get_cycle ( size_t  ei) const

Query with an edge index, return value is a cycle number.

size_t kjb::qd::Doubly_connected_edge_list::get_edge_of_cycle ( int  cn) const

Query with a cycle number, return the index of some edge on it.

const std::vector< Edge_record >& kjb::qd::Doubly_connected_edge_list::get_edge_table ( ) const
const std::vector< Face_record >& kjb::qd::Doubly_connected_edge_list::get_face_table ( ) const
size_t kjb::qd::Doubly_connected_edge_list::get_number_of_cycles ( ) const

Return the number of (real) edge cycles in the DCEL.

const std::vector< Vertex_record >& kjb::qd::Doubly_connected_edge_list::get_vertex_table ( ) const
size_t kjb::qd::Doubly_connected_edge_list::lookup_vertex ( const RatPoint query,
bool *  found = 00 
) const

look up a vertex index by its location

[in]queryPoint that might be a vertex in the DCEL
[out]foundoptional output parameter indicating whether the query point is a vertex in the DCEL.
If query is a vertex in the DCEL, this returns its index in the vertex table. If not, it returns the size of the vertex table, that is, get_vertex_table().size().

This costs linear time the first time you perform the lookup, because it builds and caches a map from location to index. Second and later lookups to an unchanging DCEL are log time, the query time of the cached map.

Doubly_connected_edge_list kjb::qd::Doubly_connected_edge_list::merge ( const Doubly_connected_edge_list d) const
void kjb::qd::Doubly_connected_edge_list::swap ( Doubly_connected_edge_list dcel)
Doubly_connected_edge_list & kjb::qd::Doubly_connected_edge_list::transform ( const RatPoint::Rat  xform[])

Transform using a row-major 3x3 homogeneous matrix on each vertex.

In this way we can perform any affine transform on the vertices. That means we can translate, rotate, reflect, scale, and skew it. Examples:

  1. Translate all points by x += 3, y -= 17: {1,0,3, 0,1,-17, 0,0,1}.
  2. Rotate points by 90 deg. around origin: {0,-1,0, 1,0,0, 0,0,1}.
  3. Reflect points around line y=x: {0,1,0, 1,0,0, 0,0,1}.
  4. Double size, fixed pt. at origin: {2,0,0, 0,2,0, 0,0,1}.
  5. Skew to the right: {4,1,0, 0,4,0, 0,0,4}.
Doubly_connected_edge_list& kjb::qd::Doubly_connected_edge_list::transform ( const std::vector< RatPoint::Rat > &  x)

transform using a row-major 3x3 homogeneous matrix on each vertex

Doubly_connected_edge_list & kjb::qd::Doubly_connected_edge_list::translate ( const RatPoint delta)

Transform by translation (rigid motion by an x and y offset)

The documentation for this class was generated from the following files: