Getting path around triangles

I got a list of triangles in a triangular grid like this:

__________________
/\      /\      /\
  \    /  \    /
   \  /    \  /
____\/______\/____
    /\      /\
   /  \    /  \
  /    \  /    \
\/______\/______\/
/\      /\      /\
  \    /  \    /
   \  /    \  /
____\/______\/____

A triangle can either be present or not. I need to get a path around the triangles like:

 ========
\\      /\\
 \\    /  \\
  \\  /    \\
   \\/______\\========
    \\      /\      //
     \\    /  \    //
      \\  /    \ 开发者_开发问答 //
       \\/======\//

I need to get the bold lines in clockwise order around the triangles. What algorithm can I use to get this? I can already classify triangles into groups using disjoint set, but I have no idea how to get the path around a group.

An isolated triangle has three lines round it. If you add another triangle beside it, you lose one line where they merge, and gain two others from the new triangle. So you can keep track of the set of lines that appear as boundaries to a group of triangles placed beside each other, and you can also keep track of which of these lines meet which other lines.

I am assuming here that only sharing a boundary joins two triangles in a group, and not sharing a point. Lines meet at a point, and if only sharing a boundary counts as joining two triangles, then each outer line is connected with just one other outer line at each of its ends.

If you follow (e.g. with depth first search) the graph formed where nodes are lines and links between lines show where a line is adjacent to another line, you will trace a cycle of lines - it can't be more complicated than that because any single line meets at most two other lines, one at each of its end points.

If your group of triangles has no holes inside it you will then retrieve a single cycle which is its outer boundary. If the group of triangles has holes in it you will retrieve the outer boundary and a cycle for each of the holes. The outer boundary must be the cycle that contains the largest area, because it contains all of the holes.

Just iterate through each triangle and for each side of the triangle check if it touch another triangle; if not just make the side bold.

EDIT

if you need an animation that display the lines drawing in a clockwise manner, just compute all the sides to be drawn and then sort the lines by polar angle and display it in this order