介绍
作为较大程序（与渲染体积图形相关）的一部分，我有一个小但棘手的子问题，其中需要以特定方式标记任意（但有限）三角形 2D 网格。不久前，我写了一个解决方案（见下文），这对于我当时的测试网格来说已经足够好了，尽管我意识到这种方法可能不适用于人们能想到的每一个可能的网格。现在我终于遇到了一个网格，目前的解决方案根本不能很好地执行它——看起来我应该想出一种完全不同的方法。不幸的是，我似乎无法重新调整我的思路，这就是为什么我想在这里问的原因。
问题
考虑下面的图片。（颜色不是问题的一部分；我只是添加它们以改善（？）可视化。此外，变化的边缘宽度是完全不相关的伪影。）
对于每个三角形（例如，橙色 ABC 和绿色 ABD），三个边中的每一个都需要被赋予两个标签之一，例如“0”或“1”。只有两个要求：
- 并非三角形的所有边都可以具有相同的标签。换句话说，对于每个三角形，必须有两个“0”和一个“1”，或者两个“1”和一个“0”。
- 如果一条边由两个三角形共享，则两者的标签必须相同。换句话说，如果图片中的边 AB 为三角形 ABC 标记为“0”，那么它也必须为 ABD 标记为“0”。
网格是真正的 2D 网格，它是有限的：即，它不包裹，并且具有明确定义的外边界。显然，在边界上满足要求很容易——但在内部就变得更加困难。
直觉上，看起来至少应该存在一种解决方案，即使我无法证明这一点。（通常有几个——任何一个都足够了。）
当前解决方案
我目前的解决方案是一个非常强力的解决方案（此处提供只是为了完整性——请随意跳过本节）：
- 维护四组三角形——每个可能计数 (0..3) 的剩余边要标记一组。一开始，每个三角形都在其中三个边需要标记的集合中。
- 只要存在带有未标记边的三角形：
找到仍然存在三角形的最小非零数量的未分配边。换句话说：在任何给定时间，我们都尽量减少已部分完成标记的三角形的数量。剩余的边数将在 1 到 3 之间。然后，只需选择一个这样的三角形，其中剩余的特定边数要分配。对于此三角形，请执行以下操作：- 看看是否有任何剩余边的标签已经被其他三角形的标签强加了。如果是这样，请按照上述要求 #2 所暗示的方式分配标签。
- 如果这导致了死胡同（即，对于当前三角形，要求#1 不能再满足），那么从头开始整个过程。
- 按如下方式分配任何剩余边：
- 如果到目前为止还没有标记边缘，则随机分配第一个。
- 当一个边缘已经分配时，分配第二个边缘，使其具有相反的标签。
- 当分配两条边时：如果它们具有相同的标签，则分配第三条具有相反的标签（显然）；如果两者有不同的标签，则随机分配第三个。
- 为不同数量的未分配边更新三角形集。
- 如果我们到达这里，那么我们有一个解决方案——万岁！
通常这种方法只需要几次迭代就可以找到解决方案，但最近我遇到了一个网格，该算法仅在重试一两千次后才会终止......这显然表明可能存在它永远不会终止的网格.
现在，我希望有一个确定性算法，可以保证总能找到解决方案。计算复杂度不是那么大的问题，因为网格不是很大，并且标记基本上只需要在加载新网格时完成，这不会一直发生 - 所以具有（例如）指数的算法复杂性应该没问题，只要它有效。（当然：效率越高越好。）
谢谢你读到这里。现在，任何帮助将不胜感激！
编辑：基于建议解决方案的结果
不幸的是，我无法让Dialecticus 建议的方法起作用。也许我没弄对……不管怎样，考虑下面的网格，起点用绿点表示：
让我们放大一点……
现在，让我们开始算法。第一步之后，标签看起来像这样（红色=“星号路径”，蓝色=“环形路径”）：
到目前为止一切都很好。第二步之后：
第三
步： 
……第四
步：
但是现在我们有问题了！让我们再做一轮 - 但请注意以洋红色绘制的三角形：
根据我目前的实现，洋红色三角形的所有边都在环形路径上，所以它们应该是蓝色的——这实际上是一个反例。现在也许我弄错了……但无论如何，最接近起始节点的两条边显然不能是红色的；如果第三个被标记为红色，那么该解决方案似乎不再适合这个想法。
顺便说一句，这是使用的数据。每行代表一条边，列解释如下：
- 第一个节点的索引
- 第二个节点的索引
- 第一个节点的x坐标
- 第一个节点的y坐标
- 第二个节点的x坐标
- 第二个节点的y坐标
起始节点是索引为 1 的节点。
我想接下来我应该尝试Rafał Dowgird 建议的方法......但也许我应该在一段时间内做一些完全不同的事情:)