如何在插入新的半边对时找到正确的半边 link 进行拆分？

Question

我正在从事一个程序化城市建设项目，该项目使用 half-edge/doubly 连接的边列表数据结构来表示道路。在下图中，预先存在的连接是实线。有两个半边 links：A 到 B 和 X 到 Y。我需要插入一个新的连接（虚线），它由两个新的半边组成：1 和 2。箭头代表所讨论的半边的方向，最近的节点（实心圆）是该半边的起点。

我需要以编程方式确定是否拆分半边 link AB 或 XY。在这种情况下，link AB 应该被拆分，创建两个新的半边 links：A1 和 2B。您将如何确定这一点？

Answer 1

我想我找到了解决办法。 links X1/2Y 无效的原因是，当您从头到尾绘制 links 时，它们会相互交叉。这让我想到交集测试应该可行。

这样做的第一步是找到正在建立的新连接的 "creation vector"（虚线）。在这种情况下，node2 是 startPosition，endPosition 是中心节点。这是按如下方式完成的：

creationVector = normalize(endPosition - startPosition);

接下来需要计算图中与node2相关的两个点：incomingPoint和outgoingPoint。为了保持顺时针方向，incomingPoint 需要位于创建向量的左侧，outgoingPoint 需要位于右侧。在下图中，incomingPoint 是红色的，而 outgoingPoint 是蓝色的。这是按如下方式完成的：

incomingPoint = nodeAPosition + new float2(-creationVector.y, creationVector.x);
outgoingPoint = nodeAPosition + new float2(creationVector.y, -creationVector.x);

最后一点是绘制两条线并测试它们之间是否有交集。我们将从无效的 link、X1/2Y 开始。在本例中，我们绘制的两条线是：nodeX 到 incomingPoint，outgoingPoint 到 nodeA。我找到的用于测试交集的解决方案来自 this blog post。为了完整起见，我将在下面包含我的版本：

private float2 IntersectionPointGet(
        float2 a1,
        float2 a2,
        float2 b1,
        float2 b2,
        out bool isIntersection)
{
    float tmp = (b2.x - b1.x) * (a2.y - a1.y) - (b2.y - b1.y) * (a2.x - a1.x);

    if (tmp == 0)
    {
        isIntersection = false;
        return float2.zero;
    }

    float mu = ((a1.x - b1.x) * (a2.y - a1.y) - (a1.y - b1.y) * (a2.x - a1.x)) / tmp;

    isIntersection = true;
    return new float2(
        b1.x + (b2.x - b1.x) * mu,
        b1.y + (b2.y - b1.y) * mu
    );
}

如您所见，links X1/2Y 相交因此无效：

现在将其与 A1/2B 进行比较，它们不相交，因此是有效的：

此解决方案的优点在于您只需要测试一对 link。如果 X1/2Y 无效，我们可以假设 A1/2B 有效。这意味着 link AB 是需要拆分的那个，而 link XY 应该单独保留。

如何在插入新的半边对时找到正确的半边 link 进行拆分？

How to find the correct half-edge link to split when inserting a new half-edge pair?

algorithm

procedural-generation