作为一个更大的程序（与渲染体积图形相关）的一部分，我有一个小而棘手的子问题，其中任意（但有限）三角形2D网格需要以特定方式进行标记。我刚刚写了一个解决方案（见下文），它对我当时的测试网格来说已经足够好了，尽管我意识到这种方法对于人们可以想到的每个可能的网格都可能不会很好。现在我终于遇到了一个网格，目前的解决方案根本不能很好地执行 - 看起来我应该想出一种完全不同的方法。不幸的是，我似乎无法重置我的思路，这就是为什么我以为我会问这里。
请看下面的图片。 （颜色不是问题的一部分;我只是添加它们来改进（？）可视化。而且变化的边缘宽度是一个完全不相关的工件。）
对于每个三角形（例如，橙色ABC和绿色AND），三个边缘中的每一个都需要被赋予两个标签中的一个，例如“0”或“1”。只有两个要求：
网格是真正的2D网格，它是有限的：即，它不包裹，并且它具有明确定义的外边界。显然，在边界上很容易满足要求 - 但内部变得更加困难。
直观地说，看起来至少应该存在一个解决方案，即使我无法证明它。 （通常有几个 - 其中任何一个都足够了。）
我目前的解决方案是一个非常强力的解决方案（此处仅为完整性而提供 - 可以跳过本节）：
通常这种方法只需几次迭代即可找到解决方案，但最近我遇到了一个网格，算法只在经过一两次重试后才会终止...这显然表明可能存在网格永远不会终止的网格。
现在，我希望有一个确定性的算法，保证总能找到解决方案。计算复杂性不是一个大问题，因为网格不是很大，并且标签基本上只需要在加载新网格时完成，这不会一直发生 - 所以一个算法（例如）指数复杂性应该没问题，只要它有效。 （但当然：效率越高越好。）
感谢您阅读此内容。现在，任何帮助将不胜感激！
不幸的是，我无法让the approach suggested by Dialecticus工作。也许我没弄错......无论如何，考虑下面的网格，用绿点表示起点：让我们放大一点......现在，让我们开始算法吧。在第一步之后，标签看起来像这样（红色=“星号路径”，蓝色=“环形路径”）：到目前为止一直很好。第二步之后：第三步：......第四步：但现在我们遇到了问题！让我们再做一轮 - 但是请注意以洋红色绘制的三角形：根据我目前的实现，洋红色三角形的所有边缘都在环形路径上，因此它们应该是蓝色的 - 这实际上使这成为一个反例。现在也许我以某种方式弄错了......但无论如何，最接近起始节点的两条边显然不能是红色;如果第三个标记为红色，那么似乎解决方案不再符合这个想法。
顺便说一句，here is the data used。每行代表一条边，列的解释如下：
起始节点是索引为1的节点。
我想接下来我应该尝试the method suggested by Rafał Dowgird ......但也许我应该做一些完全不同的事情一段时间:)
如果您对三角形进行排序，以便对于每个三角形，其中最多2个邻居按顺序排在它之前，则设置为：只按此顺序着色它们。条件保证对于每个被着色的三角形，您将始终至少有一个未着色的边缘，您可以选择其颜色以满足条件。
这样的订单存在并且可以通过以下方式构建：
给定网格中的任何节点，网格可以被视为围绕该节点的同心环集（如蜘蛛网）。给不在环中的所有边（星号路径）赋值为0，并给出环中的所有边（环形路径）的值为1.我无法证明它，但我确定你会得到正确的标签。每个三角形都只有一条边是某个环的一部分。