algorithm - 在基于 DCEL/半边的图中动态添加边？

Question

我正在尝试实现矢量图形“绘图”系统，本质上，用户可以在屏幕上绘制线条并与相交线创建的区域进行交互。我正在努力确定/评估这些区域是什么。

我尝试了几种不同的解决方案来解决这个问题，主要是保留一个边缘列表并运行 BFS 以找到最短周期，但这带来了无数问题，BFS 会以非法方式快捷，并且导致孔和退化边缘问题多到我数不清，所以我转向 DCEL 半边缘系统。

我似乎已经阅读了关于这个主题的所有内容，包括在这里经常引用的两篇文章：http: //kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm和http://www.flipcode.com/档案/The_Half-Edge_Data_Structure.shtml。但是，这些似乎都没有解决我在动态向图中添加边时遇到的这个问题。

假设我从这个单一的边缘开始。图片

半边在一个循环中相互连接，全局的、无界的“外表面”连接到半边之一。简单，明白了。

然后我们添加另一条边，附加到中心顶点：Image

新的半边工作正常，我们将流入 v1 的 next 指针的边更新为唯一不是它们的孪生的其他可用边。再一次，对我来说很有意义。

当我们向中心顶点添加第三条边时，让我感到困惑的是这里发生的事情：图片

我知道这就是它应该看起来和链接起来的样子，但是我对如何以编程方式实现这一点感到非常困惑，因为我不确定如何确定边缘 (4,1) 是否应该指向边缘 ( 1,2) 或边 (1,3)（类似于边应指向 (1,4)）。

查看图像时，答案似乎很明显，但是当您尝试以稳健、密闭的算法方式对其进行合理化时，我的大脑会融化，我无法弄清楚。我正在阅读的教科书（计算几何，Mark de Berg 等人，第 35 页），只是说

“[测试边缘] 应该在顶点 v 周围边缘的循环顺序中”。

hilvi.org 文章中给出的用于查找要连接的传出和传入边的算法似乎甚至不起作用，因为它需要顶点 1，并跟随其传出边的孪生体，直到找到“自由”边，在这种情况下，是 (2,1) 这是错误的。（除非我理解不正确，否则我可能会错误地理解整个问题。）

所以我完全被难住了。我现在唯一的想法是为每个半边创建某种航向属性，在这里我测量边创建的角度，然后以这种方式选择边，也许这是对的，但这似乎与半边结构相反似乎支持，至少在我正在阅读的文章中，似乎没有提到类似的东西。任何帮助将不胜感激。我已经解决这个问题一个多星期了，但似乎无法摆脱困境。

标签： algorithmgraphicsgraph-theory

Answer 1

是的，所以我花了很多时间思考这个问题，老实说，我有点惊讶我找不到这个问题的直接答案。因此，如果将来有人遇到想要从头开始填充半边图的类似问题，这里有一个可行的解决方案。我没有博客，所以在这里写。

我不知道这是否是最好的答案，但它在线性时间内有效，对我来说似乎很简单。

我将处理以下与传统 DCEL 略有不同的对象/类：

class Vertex {
    x;
    y;

    edges = []; //A list of all Half Edges with their origin at this vertex.
                //Technically speaking this could be calculated as needed, 
                  and you could just keep a single outgoing edge, but I'm not 
                  in crucial need of space in my application so I'm just 
                  using an array of all of them.
}


class HalfEdge {
    origin; //The Vertex which this half-edge emanates from

    twin; // The half-edge pair to this half-edge

    face; // The region/face this half-edge is incident to

    next; // The half-edge that this half-edge points to
    prev; // The half-edge that points to this half-edge

    angle; //The number of degrees this hedge is CW from the segment (0, 0) -> (inf, 0)
}


class Face {
    outer_edge; //An arbitrary half-edge on the outer boundary defining this face.
    inner_edges = []; //A collection of arbitrary half-edges, each defining
                      //A hole in the face.

    global; //A boolean describing if the face is the global face or not.
            //This could also be done by having a single "global face" Face instance. 
            //This is simply how I did it.
}

在 (x,y) 处初始化一个顶点：

1. 验证具有给定 (x,y) 坐标的顶点是否不存在。如果是这样，您不必做任何事情（如果您立即使用它，可能会返回这个现有顶点）。

2. 如果不是，则分配空间并创建一个具有相应 x,y 值的新顶点，并且其入射边为空。

初始化从顶点 A 到顶点 B 的边：

1. 与有关该主题的许多文章类似，我们创建了 HalfEdge 的两个新实例，一个从顶点 A 到 B，一个从 B 到 A。它们相互链接，因为我们将它们的孪生、上一个和下一个指针都设置为另一半边（对冲）。

2. 我们还设置了树篱的角度。从正 x 轴顺时针计算角度。我实现的功能如下。这对于使这个数据结构正常工作非常重要，而且我没有阅读任何关于这一点的重要文献的事实让我认为必须有更好的方法，但我离题了。

       setAngle(){
           const dx = this.destination().x - this.origin.x;
           const dy = this.destination().y - this.origin.y;
   
           const l = Math.sqrt(dx * dx + dy * dy);
           if (dy > 0) {
               this.angle = toDeg(Math.acos(dx / l));
           } else {
               this.angle = toDeg(Math.PI * 2 - Math.acos(dx / l));
           }
   
            function toDeg(rads) {
                return 180 * rads / Math.PI;
            }
   
        }
   

3. 接下来，我们将顶点与它们的新边配对，将它们添加到顶点的边列表中，然后按照对冲的角度从最小 (0) 到最大 (359) 对边列表进行排序。

4. 然后这是关键步骤，为了正确连接所有内容，我们获取最接近我们试图以 CCW 顺序连接的新对冲的对冲。基本上，无论我们的新对冲最终出现在边缘列表中的哪个位置，就是这样index - 1（如果index = 0，我们返回edges[edges.length - 1]）。拿那个边缘的双胞胎来说，这就是我们在上面的 hivli 文章中描述的 AIn。BOut = AIn.next.

5. 我们设置AIn.next = hedgeAB和 类似地，hedgeAB.prev = AIn，然后hedgeBA.next = AOut，AOut.prev = hedgeBA。除了在顶点 B 上运行 CCW 搜索外，还对 hashBA 执行步骤 3-5。

6. 然后，如果顶点 A 和 B 都是“旧”顶点，这意味着它们的边列表现在每个至少有 2 个元素，则可能会添加一个新面，我们需要找到它（边缘情况有两个孤立的边和连接它们以创建无界桶形或帽形）

用于初始化人脸：

1. 我们需要找到图中的所有循环。对于我的第一次实现，我每次都重新计算所有周期，重置所有面。这不是必需的，但也不是太昂贵，因为我们没有运行搜索，所以关于循环数和每个循环中的顶点数，一切都是线性时间。

2. 为此，我们得到了图中所有对冲的列表。你如何做到这一点并不重要，我决定保留我每次传递给我的循环查找器功能的每个对冲的数组。

3. 然后我们查看该列表，当列表不为空时，我们取出第一项并运行它的循环，从列表中删除我们沿途找到的所有对冲，并将其添加到一个新循环中，我们将其添加到另一个列表

4. 有了这个新的循环列表，我们需要确定循环是内循环还是外循环。有很多方法可以做到这一点，上面提到的《计算几何》一书中有很多关于它的部分。我使用的是计算每个周期定义的面积。如果面积 >= 0，则循环由“内部”对冲定义。否则，它由“外部”对冲定义。

5. 最后一步是设置所有的人脸记录，同样，上述教科书对此有很多很好的细节，但基本思想是基本上创建这些循环的虚拟“图”，并连接外部循环（这是孔在面中），到它们对应的内部循环，这是面的外边界。为此，您查看循环的最左侧顶点并将射线无限延伸到左侧，然后将循环与射线命中的循环的第一个向下的树篱“连接”（我将保留实现对你来说，我不知道我的方法是否是最好的，简而言之，我检查了每个循环与当前循环左侧最左边的顶点并计算最右边与当前循环最左边顶点的y值的交点，然后检查是否朝下）。

6. 使用此循环图，从每个“内对冲”循环（不是孔）开始运行 BFS/DFS，并从内对冲循环创建一个具有任意对冲作为外边缘的面，（如果是，则为 null全局面），以及从每个找到的孔循环到面的内部组件的任意对冲。

嘿presto，就是这样。如果您每次都检查所有内容，则可以处理所有内容。它像魅力一样处理面部分裂，并且非常强大和快速。我不知道它是否正确，但它有效。