What is a smart way to fill in the 'next' pointer of a opposite half-edge of a boundary?

Question

I was reading this question regarding half edges from 3 years ago and the selected answer seemed pretty smart to me. However, while actually implementing it I'm confused at the part where I have to fill in the next pointer of an opposite half-edge of a half-edge.

So the boundary edge actually does have an opposite (or pair pointer) and that opposite is fully integrated into the pointer structure, complete with next pointer and everything. Just that its face pointer in null, thus denoting an empty face or hole. So basically every hole is represented by a null face with half edges going around it.

So say that the half edges of a face are winded counter-clockwise (blue arrows). For the red half edge, the 'next' pointer of the edge should be the next purple half edge... But how do I obtain the purple half edge from the red half edge? For this case, I can get it from the red half edge by the sequence of the following operations: opposite - previous - opposite - next - next - opposite, but is this the best approach and is it scalable? I would appreciate it if someone could guide me to a smarter method.

Answer 1

Assuming that all blue half edges have their twin, next and prev correctly set and assuming that all blue half edges have their purple twin assigned.

Then assigning the next to the red half edge boils down to:

runner = red
while(runner->twin->prev) 
   runner = runner->twin->prev

runner->twin->prev = red
(red->next = runner->twin)

While building the mesh keep a list of all half edges which do not have a twin. Then when finished processing all faces create a new half edges for all half edges which have no twin (these are the purple edges). Then afterwards run this procedure.