Suppose I have a quad-edge data-structure, and I want to be able to perform the operations of DCEL (twin, next, prev) on the quad-edge data structure. Let the current edge I am operating on be e. I know that e.twin would simply be e.rot.rot. I am just unsure about next and prev.

(Quad-Edge visualization given below.)

Quad Edge Visualization

next should be equivalent to Lnext in the picture. Thus I tried to derive it and got e.rot.rot.rot.Onext.rot. prev should be equivalent to Lprev, which is the twin of Onext, i.e. e.Onext.rot.rot.

Is this correct? I am using quad-edges to prove properties on half-edges, so I want to make sure I got the basics correct before I proceed.


It looks like you took these diagrams from this CMU publication. This publication also refers to the C++ header cell/edge.hh, describing basic and derived operations on edges.

So, according to this header, operations Rot, InvRot, Sym and Onext are considered basic ones, and all the other operations - derived ones. The DCEL operations next and prev are equivalent to quad-edge operations Lnext and Lprev, which are defined in this header as inline functions (I'm dropping the C++ syntax and keeping the meaning):

e.Lnext = e.InvRot.Onext.Rot
e.Lprev = e.Onext.Sym

So, your formulas look correct, with slightly overused operation Rot.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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