I am currently working on a city generator, and I've ran into some issues with data storage while working on the roads. I currently use a doubly-connected edge list (DCEL for short), to store the road data. Each road would consist of two half edges, each connecting to a vertex.

The advantage of a DCEL is that I can easily access the space partitions of the roads, or the faces contained by the half edges. However, I am running into trouble storing additional data for roads.

I currently store (alongside the DCEL) a vector that simple contains all the roads as simple pairs of the indices of their beginnings and ends. However, I only use this vector to access data in bulk (for a bounding box test or rendering), nothing specific.

I want to store additional information about roads as some struct, but I don't know where to store it. I would need to access it easily through the DCEL, but I don't want to duplicate the data between the two half edges. What should I do?


Store road attributes in separate structs and have pointers to them from your DCEL edges. It doesn't matter if some edges point to the same location in memory—the attribute data has still been allocated only once.

  • \$\begingroup\$ What sort of a pointer would be a good idea? shared_ptr? \$\endgroup\$ – user975989 Apr 22 '15 at 18:00

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.