三角形网格边缘标记算法

介绍

作为一个更大的程序的一部分(与体积图形的渲染相关),我有一个小但复杂的子问题,其中一个任意(但有限)的三角形二维网格需要以特定的方式进行标记。早在不久前,我就写了一个解决方案(见下文),它对当时的测试网格来说已经足够好了,尽管我意识到这种方法对于人们所能想到的每一个可能的网格都可能不是很好。现在,我终于遇到了一个网格,对于这个网格,当前的解决方案根本不能很好地执行——看起来我应该想出一种完全不同的方法。不幸的是,我似乎不能真正地重新设置我的思维方式,这就是为什么我认为我会问这里。

问题

请看下面的图片。(颜色不是问题的一部分,我只是添加了它们来改进(?)可视化。同样,变化的边缘宽度是完全不相关的伪影。)

对于每个三角形(例如橙色ABC和绿色ABD),三条边中的每一条都需要给出两个标签中的一个,即“0”或“1”。只有两个要求:

1. 并非三角形的所有边都可以有相同的标签。换句话说,每个三角形必须有两个“0”和一个“1”, 或 两个“1”和一个“0”。
2. 如果一条边由两个三角形共享,则两个边的标签必须相同。换言之,如果图片中的ab边对于三角形abc标记为“0”,那么对于abd也必须标记为“0”。

网格是一个真正的二维网格,它是有限的:即,它不包裹,它有一个明确的外部边界。显然,在边界上,很容易满足需求——但在内部却变得更加困难。

从直觉上看,至少应该有一个解决方案存在,即使我不能证明它。(通常有几个——任何一个都足够了。)

当前解决方案

我当前的解决方案是一个非常暴力的解决方案(这里提供的只是为了完整性)-- 请随意跳过此部分 ):

• 保留四组三角形——每一个可能的边缘计数(0..3)保留一个三角形。在开始时,每个三角形都在一个集合中,其中三个边仍要标记。
• 只要有带非标记边的三角形:
  找到最小的非零数量的未分配边,其中仍有三角形。换言之:在任何给定的时间,我们都会尽量减少标签的三角形数量。 部分 完整的。剩余的边数在1到3之间。然后,只需选择一个这样的三角形,并指定剩余的边数。对于这个三角形,请执行以下操作:
  • 看看是否任何剩余边的标签已经由其他三角形的标签强加。如果是这样,请按照上述要求2所暗示的方式指定标签。
  • 如果这导致了一个死胡同(即要求1不能满足当前三角形),那么 从一开始就重新开始整个过程 .
  • 按如下方式分配任何剩余边:
    • 如果到目前为止还没有标记任何边,请随机分配第一个边。
    • 当已经分配了一个边时,分配第二个边,使其具有相反的标签。
    • 分配两个边时:如果两个边有相同的标签,则分配第三个边有相反的标签(显然);如果两个边有不同的标签,则随机分配第三个边。
  • 为不同数量的未分配边更新三角形集。
• 如果我们到了这里,我们就有了解决办法——万岁!

通常这种方法只在几次迭代中找到一个解决方案,但是最近我遇到了一个网格,对于这个网格,算法往往只在一两次迭代后终止。 千 重试次数…这显然表明可能有网格 从未 终止。

现在,我希望有一个确定性的算法,保证总是找到一个解决方案。计算复杂度并不是那么大的问题,因为网格不是很大,标签基本上只需要在加载新网格时进行,而这并不是一直都发生的——因此,具有(例如)指数复杂度的算法应该是很好的,只要它能工作。(当然,效率越高越好。)

谢谢你读到这里。现在,任何帮助都将不胜感激!

编辑:基于建议解决方案的结果

不幸的是,我不能 the approach suggested by Dialecticus 去工作。也许我没搞好…无论如何,考虑以下网格,其起点由绿点表示: 让我们放大一点… 现在,让我们开始算法。第一步之后,标签如下(red=“Starred Paths”,blue=“Ringed Paths”): 到现在为止,一直都还不错。第二步之后: 第三个: …第四个: 但现在我们有问题了!让我们再做一次-但请注意用洋红绘制的三角形: 根据我当前的实现,洋红色三角形的所有边都在一个环形路径上,所以它们应该是蓝色的——这实际上就是一个反例。也许我搞错了…但是,在任何情况下,最接近开始节点的两条边显然不能是红色的;如果第三条边被标记为红色,那么解决方案似乎不再适合这个想法了。

顺便说一句, here is the data used . 每一行代表一条边,各列解释如下:

1. 第一节点索引
2. 第二节点索引
3. X 第一节点坐标
4. Y 第一节点坐标
5. X 第二节点坐标
6. Y 第二节点坐标

开始节点是具有索引1的节点。

我想接下来我应该试试 the method suggested by Rafał Dowgird …但也许我应该做些完全不同的事情。