寻找没有被面包围的顶点

Question

我正在处理一个网格，它大致表示为

{
   vertices: [{
      x: number,
      y: number,
      z: number
   }, ...],
   faces: [{
      verticeIndices: [number, number, number]
   }, ...]
}

现在给定一个顶点，我想知道这个顶点是否被面包围。问题是我甚至不知道从哪里开始。这似乎是很简单的事情（因为在可视化网格时，很容易知道一个顶点是否被面包围），但我不知道如何表达。

所以这里有一张2D的例子图。

很容易看到绿色的顶点没有被面包围 如果我们把左下角的两个顶点连接起来，那么中间的顶点就会变成红色。

在这种2D的情况下(可能更简单?)，我想象的唯一方法是通过。

1. 找到所有相邻的面
2. 找到每个面在该顶点上的角度。
3. 如果它加起来是360，那么它就全部被覆盖了，否则就不是。

但我认为这在3D工作时并不成立...... 有什么简单的方法可以找出一个顶点在3D中是否被面包围？

Answer 1

我只是找到了一个可能的答案，但我想看看是否有更简单的方法。

有另一种方法可以在二维中找到这个答案，而且可以扩展到三维中

1. 找到目标顶点的相邻顶点。
2. 做一个只有这些顶点的图（没有目标顶点）。
3. 看看该图是否有一个循环。

如果所有相邻的顶点都构成了一个循环，那么就意味着该顶点被包围了（如果我没有说错，我漏掉了一个边缘的情况下）。

而且看样子这个应该是可以放大到3D的。

我把这个问题留着，以防有人有其他更好的想法。

Answer 2

如果一个顶点上相邻的一条边是一个叫 边沿那么，顶点没有被面所包围.

边界边只在一个面上相邻，而内边则在两个面上相邻。(有时会超过2个，当非manifoldness发生时。)

要使用这些信息，你需要访问一个顶点周围的边。

如果你没有听说过 半边数据结构你可能想看看 本介绍.

如果不容易访问顶点周围的边缘，你的方法就很好用。