c++ - 检查两条三次贝塞尔曲线是否相交

Question

对于个人项目，我需要确定两条三次贝塞尔曲线是否相交。我不需要知道在哪里:我只需要知道他们是否这样做。不过，我需要尽快完成。

我一直在搜寻这个地方，并找到了一些资源。大多数情况下，有 this question here有一个有希望的答案。

所以在我弄清楚 Sylvester matrix 是什么之后, 什么是 determinant , 什么是 resultant和 why it's useful ，我想我知道解决方案是如何工作的。然而，现实有所不同，而且效果并不好。

---

乱七八糟

我使用图形计算器绘制了两条相交的贝塞尔样条曲线(我们将其称为 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

---

西尔维斯特矩阵

据此，我构建了以下 Sylvester 矩阵:

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++ 函数来使用 Laplace expansion 计算矩阵的行列式。 :

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，因为曲线相交。但是，为我的程序提供我上面制作的 Sylvester 矩阵，它是 -2916。

这是我的错误还是他们的错误？找出两条三次贝塞尔曲线是否相交的正确方法是什么？

Answer 1

贝塞尔曲线的交点由(非常酷的)Asymptote 完成 vector 图形语言:寻找 intersect() here .

虽然他们没有解释他们在那里实际使用的算法，只是说它来自 p。 “The Metafont Book”的第 137 页，它的关键似乎是贝塞尔曲线的两个重要属性(尽管我现在找不到该页面，但该网站的其他地方对此进行了解释):

• 贝塞尔曲线始终包含在由其 4 个控制点定义的边界框内
• Bezier 曲线总是可以在任意 t 值处 segmentation 为 2 个 sub-Bezier 曲线

有了这两个属性和一个相交多边形的算法，你可以递归到任意精度:

bezInt(B₁, B₂):

1. bbox(B₁) 是否与 bbox(B₂) 相交？
   • 否:返回 false。
   • 是:继续。
2. area(bbox(B₁)) + area(bbox(B₂)) 是不是阈值？
   • 是:返回 true。
   • 否:继续。
3. 在 t = 0.5
处将 B ₁ 拆分为 B _1a 和 B _1b
4. 在 t = 0.5
处将 B ₂ 拆分为 B _2a 和 B _2b
5. 返回 bezInt(B_1a, B_2a) ||bezInt(B_1a, B_2b) ||bezInt(B_1b, B_2a) ||bezInt(B_1b, B_2b).

如果曲线不相交，这会很快——这是通常的情况吗？

[编辑] 看起来将贝塞尔曲线一分为二的算法称为 de Casteljau's algorithm .