|
KJB
|
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
|
KJB
|
data structure for a planar subdivision made by edges More...
#include <dcel.h>
Classes | |
| 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_list & | translate (const RatPoint &) |
| Transform by translation (rigid motion by an x and y offset) More... | |
| Doubly_connected_edge_list & | transform (const RatPoint::Rat[]) |
| Transform using a row-major 3x3 homogeneous matrix on each vertex. More... | |
| Doubly_connected_edge_list & | transform (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... | |
data structure for a planar subdivision made by edges
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.
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:
|
inline |
| 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.
| void kjb::qd::Doubly_connected_edge_list::build_cycle_table | ( | ) | const |
|
inline |
Query with an edge index, return value is a cycle number.
|
inline |
Query with a cycle number, return the index of some edge on it.
|
inline |
|
inline |
|
inline |
Return the number of (real) edge cycles in the DCEL.
|
inline |
| 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] | query | Point that might be a vertex in the DCEL |
| [out] | found | optional output parameter indicating whether the query point is a vertex in the DCEL. |
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.
|
inline |
|
inline |
| 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:
|
inline |
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)
1.8.6