检查两条立方贝塞尔曲线是否相交

Question

对于个人项目,我需要找出两条立方Bézier曲线是否相交.我不需要知道在哪里:我只需要知道他们是否这样做.但是,我需要快速完成.

我一直在清理这个地方,我找到了几个资源.大多数情况下,这里的问题有一个很有希望的答案.

所以在我想出什么是西尔维斯特矩阵之后,什么是决定因素,什么是结果以及为什么它有用,我想我认为解决方案是如何工作的.然而,现实不同,它不能很好地工作.

---

到处乱混

我用我的图形计算器绘制了两个相交的Bézier样条(我们称之为B ₀和B ₁).它们的坐标如下(P ₀,P ₁,P ₂,P ₃):

(1, 1) (2, 4) (3, 4) (4, 3)
(3, 5) (3, 6) (0, 1) (3, 1)

结果如下,B ₀是"水平"曲线而B ₁是另一个:

根据上述问题的最高投票答案的指示,我将B ₀减去B ₁.根据我的计算器,它给我留下了两个方程式(X轴和Y轴):

x = 9t^3 - 9t^2 - 3t + 2
y = 9t^3 - 9t^2 - 6t + 4

---

西尔维斯特矩阵

从那以后我构建了以下的西尔维斯特矩阵:

9  -9  -3   2   0   0
0   9  -9  -3   2   0
0   0   9  -9  -3   2
9  -9  -6   4   0   0
0   9  -9  -6   4   0
0   0   9  -9  -6   4

之后,我使用拉普拉斯扩展计算了一个C++函数来计算矩阵的行列式:

template<int size>
float determinant(float* matrix)
{
    float total = 0;
    float sign = 1;
    float temporaryMatrix[(size - 1) * (size - 1)];
    for (int i = 0; i < size; i++)
    {
        if (matrix[i] != 0)
        {
            for (int j = 1; j < size; j++)
            {
                float* targetOffset = temporaryMatrix + (j - 1) * (size - 1);
                float* sourceOffset = matrix + j * size;
                int firstCopySize = i * sizeof *matrix;
                int secondCopySize = (size - i - 1) * sizeof *matrix;
                memcpy(targetOffset, sourceOffset, firstCopySize);
                memcpy(targetOffset + i, sourceOffset + i + 1, secondCopySize);
            }
            float subdeterminant = determinant<size - 1>(temporaryMatrix);
            total += matrix[i] * subdeterminant * sign;
        }
        sign *= -1;
    }
    return total;
}

template<>
float determinant<1>(float* matrix)
{
    return matrix[0];
}

它似乎在相对较小的矩阵(2x2,3x3和4x4)上工作得很好,所以我希望它也适用于6x6矩阵.然而,我并没有进行大量的测试,而且它有可能被打破.

---

问题

如果我从另一个问题中正确理解了答案,那么因为曲线相交,行列式应该是0.然而,为我的程序提供我上面制作的西尔维斯特矩阵,它是-2916.

这是我的错误还是结束？找出两条立方贝塞尔曲线是否相交的正确方法是什么？

Answer 1

Bezier曲线的交点由(非常酷)渐近线矢量图形语言完成:在intersect() 这里查找.

虽然他们没有解释他们实际使用的算法,除了说它来自p."The Metafont Book"的第137页,它的关键似乎是Bezier曲线的两个重要属性(虽然我现在找不到该页面,但在该网站的其他地方对此进行了解释):

• 贝塞尔曲线始终包含在由其4个控制点定义的边界框内
• 贝塞尔曲线总是可以将任意t值细分为2个子贝塞尔曲线

使用这两个属性和交叉多边形的算法,您可以递归到任意精度:

bezInt(B ₁,B ₂):

2. bbox(B ₁)是否与bbox(B ₂)相交？
   • 不:返回错误.
   • 是的:继续.
3. 面积(bbox(B ₁))+面积(bbox(B ₂))<阈值？
   • 是的:回归真实.
   • 不:继续.
4. 在t = 0.5时将B ₁分成B _1a和B _1b
5. 在t = 0.5时将B ₂分成B _2a和B _2b
6. 返回bezInt(B _1a,B _2a)|| bezInt(B _1a,B _2b)|| bezInt(B _1b,B _2a)|| bezInt(B _1b,B _2b).

如果曲线不相交,这将是快速的 - 这是通常的情况吗？

[编辑]看起来将贝塞尔曲线分成两部分的算法称为de Casteljau算法.

Answer 2

如果您正在为生产代码执行此操作,我建议使用Bezier剪切算法.这个免费在线CAGD文本(pdf)的第7.7节对此进行了解释,适用于任何程度的贝塞尔曲线,并且快速而稳健.

虽然从数学角度来看,使用标准的根探测器或矩阵可能更直接,但Bezier削波相对容易实现和调试,并且实际上具有较少的浮点误差.这是因为每当它创建新数字时,它都在进行加权平均(凸组合),因此没有机会根据噪声输入进行外推.