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

Question

我正在尝试实现一个矢量图形“绘图”系统，从本质上说，用户可以在屏幕上画线，并与相交线创建的区域交互。我正在努力确定/评估这些区域是什么。
我试过一些不同的方法来解决这个问题，主要是保留一个边的列表，运行一个bfs来寻找最短的循环，但是这带来了无数的问题，bfs会以非法的方式走捷径，而空洞和退化的边导致的问题比我能计算的要多，所以我转向了dcel，半边系统。
我似乎已经阅读了关于这个主题的所有内容，包括这里经常引用的两篇文章：http://kaba.hilvi.org/homepage/blog/halfedge/halfedge.htm和http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml。然而，这两种方法似乎都不能解决我在动态地向图中添加边时遇到的问题。
假设我从这条边开始。Image
半边在一个循环中相互连接，全局的、无边界的“外表面”连接到其中一个半边。别紧张，明白了。
然后我们添加另一条边，附加到中心顶点：Image
新的半边工作得很好，我们更新流入v1下一个指针的边，使之成为唯一可用的非孪生边。再说一次，对我来说很有意义。
令我困惑不已的是，当我们在中心顶点添加第三条边时，这里会发生什么：Image
我知道这就是它应该看起来和连接的样子，但是我对如何通过编程实现这一点非常困惑，因为我不确定如何确定边（4,1）应该指向边（1,2）还是边（1,3）（类似地，边应该指向什么（1,4））。
当你看着这张图片时，答案似乎很明显，但是当你试图用一种健壮的、不透风的算法来合理化它时，我的大脑融化了，我想不出来我正在读的教科书（计算几何，Mark de Berg等人，第35页）只是说
“[测试边的位置]应按边的循环顺序
围绕顶点V“。
在hilvi.org文章中给出的查找要链接的传出边和传入边的算法似乎都不起作用，因为它将采用顶点1，并跟随其传出边的孪生边，直到找到一个“空闲”边，在本例中是（2,1），这是错误的（除非我理解错了，否则我可能理解错了整个问题。）
所以我完全被难住了我现在唯一的想法是为每一个半边创建某种标题属性，在这里我测量由边创建的角度，然后选择这样的边，也许这是对的，但这似乎与半边结构似乎支持的相反，至少在我读到的文章中，似乎没有提到类似的东西。任何帮助都将不胜感激。我在这个问题上已经有一个多星期了，但似乎无法摆脱。

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）处初始化顶点：
验证给定的（x，y）坐标的顶点是否已经存在。如果是这样，你就不需要做任何事情（除非你立即使用这个顶点）。
如果没有，则为其分配空间，并使用相应的x、y值创建一个新顶点，其入射边为空。
要初始化从顶点A到顶点B的边：
与本主题的许多文章类似，我们创建了两个新的半边实例，一个从顶点A到顶点B，一个从顶点B到顶点A。它们相互链接，因为我们将它们的孪生指针、prev指针和next指针都设置到另一个半边（hedge）。
我们还设置了树篱的角度。角度是从正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;
         }

     }

接下来，通过将顶点添加到顶点的边列表中，将顶点与其新边配对，然后根据树篱从最小（0）到最大（359）的角度对边列表进行排序。
然后，这是关键的一步，为了把所有的东西都连接起来，我们按照《特定常规武器公约》的顺序，把最接近的树篱与我们试图连接的新树篱连接起来基本上，不管我们的新对冲在边缘列表中的位置是什么，它都是 index - 1（如果 index = 0，则返回 edges[edges.length - 1]）。拿那个边缘的双胞胎来说，这就是我们在上面的hivli文章中描述的。 BOut = AIn.next。
我们设置 AIn.next = hedgeAB和类似的， hedgeAB.prev = AIn，然后 hedgeBA.next = AOut， AOut.prev = hedgeBA。对hedgeBA也执行步骤3-5，除了在顶点B上运行CCW搜索。
然后，如果顶点A和B都是“旧”顶点，这意味着它们的边列表现在每个至少有2个元素，则可能添加了一个新的面，我们需要找到它（边的情况是有两个独立的边，并将它们连接起来以创建一个无边界的桶形或帽形）
用于初始化面：
我们需要在图中找到所有的周期。对于我的第一个实现，我每次都重新计算所有的循环，重置所有的面。这是不必要的，但也不太昂贵，因为我们不运行搜索，所有的时间都是线性的，与周期数和每个周期中的顶点数有关。
为了做到这一点，我们得到了图中所有树篱的列表你怎么做并不重要，我决定保留一个数组，每次我传递到循环查找函数中的每个树篱。
然后我们查看这个列表，当列表不为空时，我们取第一个项目并运行它的循环，从列表中移除沿途找到的所有对冲，并将其添加到新的循环中，然后将其添加到另一个列表中
有了这个新的循环列表，我们需要确定这个循环是否是一个内/外循环有很多方法可以做到这一点，上面提到的《计算几何》一书中有很多关于它的章节。我用的是计算每个周期定义的面积如果面积大于等于0，则周期由“内部”树篱定义否则，它的定义是“外部”对冲。
最后一步是设置所有的人脸记录，同样，前面提到的教科书对此有很多非常详细的内容，但是基本的想法是基本上创建这些循环的虚拟“图形”，并将外部循环（即面上的孔）与其对应的内部循环（即面的外部边界）连接起来。要做到这一点，你可以看到循环的最左边的顶点，并将一条光线无限延伸到左边，然后将循环“连接”到光线击中的循环的第一个向下的树篱上（我将把实现留给你，我不知道我的方法是否是最好的，简而言之，我使用当前循环最左边的顶点检查每个循环，并计算最右边与当前循环最左边顶点的y值的交点，然后检查该交点是否朝下）。
使用这个周期图，从每个“内对冲”周期（而不是洞）开始运行一个bfs/dfs，并创建一个以内对冲周期中的任意对冲为外缘的面（如果是全局面，则为空），以及从每个找到的洞周期到面的内部组件的任意对冲。
嘿，普雷斯托，就这样。如果你每次都检查所有的东西，那就可以处理所有的事情。它处理脸分裂像一个魅力，是非常健壮和迅速。我不知道这是不是对的，但它起作用了。