Many algorithms in computational geometry assume to have as input a complex data structure to represent a geometric object. The most common I know is the Doubly connected edge list, but there're also the halfdge data structure, winged edge etc... I was wondering if such data structure is also used to represent simple object. I know for example there's no need to represent a vertex or a line segment using a DCEL, however in practical implementations this would probably make the interface reusable, and therefore the whole algorithm implemented (unless we want to use some wrapper but I'm assuming I'm not).

So my question is, how can both points and segments be represented using a DCEL?

I would initialize the half_edge_incident field to be NIL and I would keep the list_< HalfEdge* > empty, same as the list< Face* >?

For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

Does this representation work?


1 Answer 1


First of all, while being generic is nice from an user perspective, it is usually the best idea to use the simplest structure that you require from an algorithmic perspective. The proper solution to this problem is simply to offer the user a single interface (or 'wrapper', as you call it).

(Another problem is that unnecessary abstraction is potentially unbounded. Why use a plane when $\mathbb{R}^n$ is more general? Why use that when an abstract metric space is more general, etc.)

Now, for your specific construction:

For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

The problem with this construction is that a lot of fields are empty that I would expect to be filled. Why do some edges have no face, why do some edges have no successor? Both these cases do not occur in a DCEL, so to make this particular structure work you must already define a generalisation of a DCEL that allows for empty fields. Most importantly, you are trying to store something that is not a subdivision of the plane in a DCEL, which is designed to store precisely that!

If you really want to store 'simple geometric objects' in the plane, using a trapezoidal decomposition seems like a decent idea, as it can reasonably store both segments and polygons. (It is even possible to store both a trapezoidal decomposition and a DCEL for the same data) However, this all depends on the actual application, since some operations are more efficient with a DCEL or other structures.

If you insist on storing segments in a DCEL, an approach is to represent a segment by a pair of edges (so 4 half-edges), where one of the 'faces' is the space surrounding the segment and the other the face 'inside' the segment (with 0 area).

  • $\begingroup$ To be honest I find DCEL very difficult to manipulate. Even algorithms that in theory should be simple they become very difficult to implement using a DCEL. I'm talking about algorithms that involves a certain degree of modifying the DCEL. Some of them are very very tedious, even a polygon triangulation, that in theory it shouldn't be that hard (I'm not talking about Dealunay triangulation). $\endgroup$ Feb 25, 2017 at 19:45
  • $\begingroup$ @user8469759 Uh, how does this comment relate to your question or this answer? $\endgroup$
    – Discrete lizard
    Feb 25, 2017 at 21:13
  • $\begingroup$ you suggested to "keep it simple", which is ok. But in general there's no literature explaining how to properly manipulate a DCEL to implement many algorithms in computational geometry, or what kind of transformations are applied in order to to enable code reuse. This is why I'm doing such experiments, and I was trying to justify the "why" I'm not keeping it simple. $\endgroup$ Feb 25, 2017 at 23:04
  • $\begingroup$ @user8469759 Well, apart from 'keeping it simple', I'm saying you are attempting to drive a screw in a wall with a hammer. It might work, but it really isn't the best method. Indeed, there is no literature that describes efficient algorithms for common operations on DCEL's. Implementing a DCEL is not a bad idea, but it is best to do it for algorithms that require the operations on DCEL's. $\endgroup$
    – Discrete lizard
    Feb 26, 2017 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.