所以我有近似曲面的三角形网格。
它就像具有以下属性的图表：
- 图边界上的顶点是可以轻易识别的。 （相邻顶点的数量 > 包含三角形的数量）
- 您可以轻松计算任意两个顶点之间的距离。 （欧几里德距离）
- 对于任意顶点v，任何不是邻居的顶点v必须有更远的距离v至少比其中之一v的邻居。换句话说，非相邻顶点不能出现在v的邻里环。
对于每个顶点v，我想计算从 v 到任意边界顶点的最小距离。
我可以通过暴力来做到这一点，建立所有边界顶点的列表，比较v与每个的距离，并保持最小。但这是低效的。
我相信对于每个顶点来说最有效的方法v是要有一个优先级队列，其中顶部元素最接近v。队列初始化为v的邻居。当队列顶部不是边界顶点时，弹出顶部并推送弹出顶点的所有邻居。
比如说顶点v有 6 个邻居，我计算了 6 个邻居中每一个的最小边界距离，并记录了为 6 个邻居提供最小值的确切边界顶点。我知道其中之一也必须给出v的最小边界值。我无法真正证明这一点，但我认为这是直观的。如果v被它的邻居包围，即距离它最近的边界顶点v也必须是距其邻居之一最近的边界顶点。
我想知道是否有一种方法可以利用这些知识来有效地计算图中每个点的最小值。比从每个顶点进行广度优先搜索更有效。
如果您进行广度优先搜索直到找到边界顶点，这并不能保证这是最近的边界顶点。要看到这一点，请注意，对于二维中的任何三角平面图，您可以向每个顶点添加一个非常小的不同 z 坐标，并定义一个 3-d 表面，其自然最简单的良好近似三角形网格（给出完美的近似）只是与原始平面图对应的网格。因此，给出一个三角平面图的示例就足够了，其中存在顶点 v，其在连接 v 到边界顶点的路径上的最小#edges 方面最接近的边界顶点不是就欧几里德距离而言最接近的边界顶点。这是此类平面图的示例。
首先画一个直角三角形，顶点为(0,0)、(1,0)、(0,1)。然后沿边从 (1,0) 到 (0,1) 选择大量顶点，使顶点将边分成相等大小的线段。将所有这些顶点连接到 (0,0)。然后，对于您添加的所有顶点，为每对相邻顶点绘制一个等边三角形，将这两个顶点用作等边三角形顶点中的两个。用直线连接等边三角形的所有“顶部”。现在您应该有一个看起来像纸牌屋第一层的区域。同样，将纸牌屋的第二层添加到第一层之上。这就是图表，它满足您的属性。现在请注意，对于沿着从 (1,0) 到 (0,1) 的边添加的所有顶点，它们将 (0,0) 作为邻居，这是边界顶点。然而，就欧几里德距离而言，最近的边界顶点将是沿着 2 层纸牌屋周长的边界顶点之一，它几乎总是相距 2 个边。从这些内部顶点之一进行广度优先搜索将返回 (0,0) 作为最近的边界顶点，这是不正确的。我认为这个例子只是让事情变得多么复杂的一瞥，这样你的假设仍然可以得到满足。最快的算法确实可能只是枚举所有边界顶点，然后针对每个顶点测试所有边界顶点以找到最接近的顶点。如果你有一个漂亮的“胖”网格，其中大多数顶点不是边界顶点，那么至少边界顶点的数量将比顶点总数小得多，因此复杂性至少比最坏情况降低了一些如果有 N 个顶点，则为 O(N^2)。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
