I have implemented the half-edge data structure several times now for mesh representation. Basically there are three main data structures (vertex, edge, face). I'll explain them a bit, but I think this is a more functional programming/Clojure question than actual geometry.
A vertex is a corner of a polygon, which is shared among the intersecting faces. It has a position in space (x,y,z) and an edge reference that connects to it. It can be any edge that touches it. A face is a polygon, who's shape is determined by a loop of edge structures. It only needs one edge reference. A edge is the most complex structure. It is a loop around a face, so it has a next and a previous preference to the next and previous edge in the looped, linked-list. It also has a "pair" reference that references the edge structure on the adjacent face. Thus for two connect vertices, there are two edges along it. One for each face, unless the face isn't connect to an adjoining face at that edge (like the edge of a plane) and the "pair" reference is then null. And edge also holds a vertex and face reference that is attached to it. So two edges can be on the same face, but will have different vertex references and two edges can be on different faces and the same vertex. A better description of all this is here: http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml Anyway, my question is how to efficiently work with this kind of structure in Clojure or any other functional language using immutable data structures? If I make a face, it needs an edge reference. If I make a vertex, it needs a vertex reference. I've rigged it up before using integer indices instead of references and just "planned ahead" for which new edge will have what index. However, this seems to have gotten more difficult when I start modifying the topology of the mesh. For example, if I have a cube and a delete a face, I would normally delete the face and change the neighboring edges since they're mutable. However, this seems a lot trickier with immutable structures. I think I can generalize the question into a graph question. I have three kinds structures that link together as I described. How could a delete and add new connections efficiently and intuitively? -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en
