algorithm - 获取三角形周围的路径

Question

我得到了三角形网格中的三角形列表，如下所示:

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

三角形可以存在也可以不存在。我需要在三角形周围找到一条路径，例如:

 ========
\\      /\\
 \\    /  \\
  \\  /    \\
   \\/______\\========
    \\      /\      //
     \\    /  \    //
      \\  /    \  //
       \\/======\//

我需要在三角形周围按顺时针顺序绘制粗线。我可以使用什么算法来得到这个？我已经可以使用不相交集将三角形分类为组，但我不知道如何获得围绕组的路径。

Answer 1

一个孤立的三角形周围有三条线。如果你在它旁边添加另一个三角形，你会在它们合并的地方失去一条线，并从新三角形中获得另外两条线。因此，您可以跟踪显示为一组相邻三角形边界的线集，还可以跟踪其中哪些线与其他线相交。

我在这里假设仅共享边界将两个三角形连接到一个组中，而不共享一个点。线在一点相交，如果只共享一个边界算作连接两个三角形，则每条外线在其两端仅与另一条外线相连。

如果您遵循(例如深度优先搜索)形成的图形，其中节点是线，线之间的链接显示一条线与另一条线的相邻位置，您将追踪线的循环 - 它不会比那是因为任何一条线最多与另外两条线相交，每条线在它的端点。

如果您的三角形组内部没有孔洞，您将检索到作为其外边界的单个循环。如果三角形组中有孔，您将检索外边界和每个孔的循环。外边界必须是包含最大面积的环，因为它包含所有孔。