检查两个立方贝塞尔曲线是否相交 [英] Checking if two cubic Bézier curves intersect

问题描述

对于个人项目，我需要找出两个三次贝塞尔曲线是否相交。我不需要知道在哪里：我只需要知道他们是否。但是，我需要做得很快。

我一直在清理这个地方，我找到了几个资源。大多数情况下，这里有：

 模板< int size> 
 float determinant（float * matrix）
 {
 float total = 0; 
 float sign = 1; 
 float temporaryMatrix [（size  -  1）*（size  -  1）]; 
 for（int i = 0; i  {
 if（matrix [i]！= 0）
 {
 for = 1; 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; 
} 
 
模板<> 
 float determinant< 1>（float * matrix）
 {
 return matrix [0]; 
} 
  

似乎在相对较小的矩阵（2x2,3x3和4x4 ），所以我希望它也能在6x6矩阵上工作。

---

问题

如果我正确理解了另一个问题的答案，行列式应为0，因为曲线相交。但是，喂给我的程序上面的Sylvester矩阵，是-2916。

这是我的结束还是结束的错误？

解决方案

Bezier曲线的交点是由） Asymptote 矢量图形语言：查找 intersect（） 在这里。

虽然他们不解释算法他们实际上在那里使用，除了说它是从p。 The Metafont Book的第137页，看起来它的关键是Bezier曲线的两个重要属性（在该网站的其他地方解释，虽然我现在找不到页面）：

• 贝塞尔曲线总是包含在由其4个控制点定义的边界框内


• 贝塞尔曲线可以总是被细分为任意的 t 值转换成2个子贝塞尔曲线

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

bezInt（B ₁ ，B ₂ ）：

1. bbox（B ₁ ）与bbox（B ₂ ）相交吗？
   
   
   
   • 否：返回false。
   
   
   • 是：继续。
   
   


2. 是区域（bbox（B ₁ ））+ area（bbox（B <2>阈？
   
   
   
   • 是：返回真实的。
   
   
   • 否：继续。
   
   
   
   
3. 在 t = 0.5 将B <1>分割成B <1a>和
4. 
   
5. 在 t = 0.5时将B <2>分割成B <2a>和<2b>


6. 返回bezInt（B _1a ，B <2a>）
   bezInt（B
，<2b> ）。
bezInt（B ，B <2a>）。
bezInt（B ，B <2b> ）。

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

将贝塞尔曲线分成两部分，称为 de Casteljau的算法。

For a personal project, I'd need to find out if two cubic Bézier curves intersect. I don't need to know where: I just need to know if they do. However, I'd need to do it fast.

I've been scavenging the place and I found several resources. Mostly, there's this question here that had a promising answer.

So after I figured what is a Sylvester matrix, what is a determinant, what is a resultant and why it's useful, I thought I figured how the solution works. However, reality begs to differ, and it doesn't work so well.

---

Messing Around

I've used my graphing calculator to draw two Bézier splines (that we'll call B₀ and B₁) that intersect. Their coordinates are as follow (P₀, P₁, P₂, P₃):

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

The result is the following, B₀ being the "horizontal" curve and B₁ the other one:

Following directions from the aforementioned question's top-voted answer, I've subtracted B₀ to B₁. It left me with two equations (the X and the Y axes) that, according to my calculator, are:

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

---

The Sylvester Matrix

And from that I've built the following Sylvester matrix:

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

After that, I've made a C++ function to calculate determinants of matrices using 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];
}

It seems to work pretty well on relatively small matrices (2x2, 3x3 and 4x4), so I'd expect it to work on 6x6 matrices too. I didn't conduct extensive tests however, and there's a possibility that it's broken.

---

The Problem

If I understood correctly the answer from the other question, the determinant should be 0 since the curves intersect. However, feeding my program the Sylvester matrix I made above, it's -2916.

Is it a mistake on my end or on their end? What's the correct way to find out if two cubic Bézier curves intersect?

解决方案

Intersection of Bezier curves is done by the (very cool) Asymptote vector graphics language: look for intersect() here.

Although they don't explain the algorithm they actually use there, except to say that it's from p. 137 of "The Metafont Book", it appears that the key to it is two important properties of Bezier curves (which are explained elsewhere on that site though I can't find the page right now):

• A Bezier curve is always contained within the bounding box defined by its 4 control points
• A Bezier curve can always be subdivided at an arbitrary t value into 2 sub-Bezier curves

With these two properties and an algorithm for intersecting polygons, you can recurse to arbitrary precision:

bezInt(B₁, B₂):

1. Does bbox(B₁) intersect bbox(B₂)?
   • No: Return false.
   • Yes: Continue.
2. Is area(bbox(B₁)) + area(bbox(B₂)) < threshold?
   • Yes: Return true.
   • No: Continue.
3. Split B₁ into B_1a and B_1b at t = 0.5
4. Split B₂ into B_2a and B_2b at t = 0.5
5. Return bezInt(B_1a, B_2a) || bezInt(B_1a, B_2b) || bezInt(B_1b, B_2a) || bezInt(B_1b, B_2b).

This will be fast if the curves don't intersect -- is that the usual case?

[EDIT] It looks like the algorithm for splitting a Bezier curve in two is called de Casteljau's algorithm.

这篇关于检查两个立方贝塞尔曲线是否相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！