发现从任何顶点的最小距离，以图形的边界 [英] Finding the smallest distance from any vertex to the border of the graph

问题描述

所以，我有三角形网格近似一个表面。

So I have triangular mesh approximating a surface.

这就像一个曲线图具有以下属性：

It's like a graph with the following properties:

• 在图形边框的顶点平凡身份。 （相邻顶点的数量>含三角形数）
• 您可以平凡计算任意两个顶点之间的距离。 （欧​​氏距离）
• 对于任何顶点的 v 的，任何一个顶点，其不是邻居的 v 的必须具有更大的距离的 v 的比中的至少一个 v 的的邻国。换句话说，没有非相邻顶点可能出现在 v 的的邻居环。

• The vertices on the graph border are trivially identifiable. (Number of neighbor vertices > number of containing triangles)
• You can trivially calculate the distance between any two vertices. (Euclidean distance)
• For any vertex v, any vertex that is not a neighbor of v must have a greater distance to v than at least one of v's neighbors. In other words, no non-neighbor vertices may appear within v's neighborhood ring.

有关每个顶点的 v 的，我要计算从v到任何边界顶点的最小距离。

For each vertex v, I want to calculate the smallest distance from v to any border vertex.

我可以用蛮力为此，构建所有的边界顶点列表， v 的的距离比较各，并保持最低。但是，这是低效率的。

I can do this by brute force, build a list of all border vertices, compare v's distance to each, and keep the minimum. But this is inefficient.

相信最有效的方式为每个单独的顶点的 v 的是做有一个优先级队列，其中所述顶部元件是最接近的 v 的。队列用的 v 的邻居初始化。而该队列的顶部是把边界顶点，弹出顶部和推弹出顶点的所有邻居。

I believe the most efficient way for each single vertex v is to do have a priority queue where the top element is the closest to v. The queue is initialized with v's neighbors. While the top of the queue is not a border vertex, pop the top and push all the neighbors of the popped vertex.

假设顶点的 v 的有6个邻居，和我计算的最小边界距离为每个6，和我录这给了最低的6邻居的确切边界顶点。我知道，这些必须也给的 v 的的最小边界值。我真的不能证明这一点，但我认为这是直观的。如果的 v 的的被它的邻国包围，最近的边界顶点的 v 的也必须是最靠近边界顶点到其邻国之一。

Let's say vertex v has 6 neighbors, and I calculate the minimum border distance for each of the 6, and I recorded the exact border vertex that gave the minimum for the 6 neighbors. I know that one of these must also give v's minimum border value. I can't really prove this, but I think it's intuitive. If v's surrounded by it's neighbors, the closest border vertex to v must also be the closest border vertex to one of its neighbors.

我想知道如果有一种方式来利用这些知识来有效计算的最低图中的每个点。效率比广度优先，从每个顶点搜索。

I want to know if there is a way to use this knowledge to efficiently computing the minimum for each point in the graph. More efficient than a breadth first search from each vertex.

推荐答案

如果你这样做广度优先搜索，直到找到一个边框的顶点，这并不能保证这是最接近的边界顶点。看到这一点，请注意，对于2-D任何三角平面图形，你可以添加一个非常小的独特的Z坐标的每个顶点，并定义一个三维表面的自然简单的很好近似三角形网格（给人一种完美的近似值）是简单地对应于原始平面图形的网格。所以它足以得到三角平面图形，那里有顶点v的接近的边界顶点中最小#edges方面连接v到边界顶点的路径上的一个例子是不是在欧氏距离方面最接近的边界顶点。下面是这样一个平面图形的一个例子。

If you do breadth-first search until you find a border vertex, this does not guarantee that this is the closest border vertex. To see this, note that for any triangulated planar graph in 2-d, you could add a very small distinct z-coordinate to each vertex, and define a 3-d surface whose natural simplest good approximating triangular mesh (giving a perfect approximation) is simply the mesh corresponding to the original planar graph. So it suffices to give an example of a triangulated planar graph where there are vertices v whose closest border vertex in terms of minimum #edges on a path connecting v to the border vertex is not the closest border vertex in terms of euclidean distance. Here's an example of such a planar graph.

首先画一个直角三角形的顶点（0,0），（1,0），（0,1）。然后，选择了大批沿着从（1,0）的边缘顶点至（0,1），使得该顶点分手边缘成相等大小的段。将所有这些顶点为（0,0）。然后，对于所有添加的顶点，对于每对相邻顶点的绘制使用该两个顶点为两个等边三角形顶点的等边三角形。连接等边三角形的所有的顶部用一条直线。现在，你应该有一个看起来像纸牌做的房子的第一层的区域。同样添加卡的房子的第二级上的第一个的上面。这是曲线图，它满足的性能。现在注意，对于所有从（1,0）一起加入边缘到顶点（0,1），它们具有（0,0），为邻居，这是一个边界顶点。然而，在欧氏距离方面最接近的边界顶点将沿着卡的2级房屋的周边边界顶点，这将是几乎总是2的边缘远离之一。从这些内部顶点之一的广度优先搜索将返回（0,0）作为最接近边境的顶点，这是不正确。我觉得这个例子只是惊鸿一瞥的多么复杂的事情都能搞定，这样你的假设都还满意。最快的算法可能确实是只列举所有边界顶点，然后为每个顶点测试所有边界顶点找到最接近的。如果有一个很好的胖啮合最顶点不是边界顶点，至少边界顶点的数目会比顶点的总数小得多，因此复杂性是至少减少一些从最坏情况下的O（N ^ 2）如果你有N个顶点。

First draw a right triangle with vertices (0,0), (1,0), (0,1). Then choose a large number of vertices along the edge from (1,0) to (0,1), such that the vertices break up the edge into equal sized segments. Connect all these vertices to (0,0). Then, for all the vertices you added, for each pair of neighboring vertices draw an equilateral triangle that uses the two vertices as two of the equilateral triangle vertices. Connect all the "tops" of the equilateral triangles with a straight line. Now you should have a region that looks like the first level of a house of cards. Similarly add the second level of the house of cards on top of the first. This is the graph, and it satisfies your properties. Now note, for all of the vertices you added along the edge from (1,0) to (0,1), they have (0,0) as a neighbor and this is a border vertex. However, the closest border vertex in terms of euclidean distance will be one of the border vertices along the perimeter of your 2-level house of cards, which will be almost always be 2 edges away. A breadth first search from one of these interior vertices would return (0,0) as the closest border vertex, which is incorrect. I think this example is just a glimpse of how complicated things can get, such that your assumptions are still satisfied. The fastest algorithm may indeed be to just enumerate all border vertices, and then for each vertex test all border vertices to find the closest. If you have a nice "fat" mesh with most of the vertices not being border vertices, at least the number of border vertices will be much smaller than the total number of vertices, so the complexity is at least reduced some from the worst-case O(N^2) if you have N vertices.

这篇关于发现从任何顶点的最小距离，以图形的边界的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！