我在StackOverflow上找到了几个答案，这些答案使用曲线的边界框进行测试：这不是我所追求的即使曲线不相交，测试也可能报告相交。
到目前为止，我发现的最接近的东西是Sederberg和Meyers的“边界楔形”，但“仅”区分了最多一个和两个或多个交叉点，而我想知道是否存在最多零个和一个或多个交叉点。
#1 楼
解决问题的另一种方法是定义一个函数，该函数给出两条曲线上的点之间的距离，作为曲线参数的函数。然后尝试找到该函数的全局最小值。如果曲线相交，最小值将为零；否则，最小值将为零。要明确，给定由$ c_1，c_2定义的一对2D曲线：[0，1] \至\ mathbb {R} ^ 2 $，将距离平方定义为
$$ f（u，v）：[0,1] ^ 2 \至\ mathbb {R} _ {\ geq 0} \ equiv \ bigl | c_2（ v）-c_1（u）\ bigr | ^ 2 $$
对于三次曲线，函数$ f $是两个变量的六次多项式。然后，您可以应用数值优化技术，例如单纯形法或共轭梯度下降法。不幸的是，该函数可以具有多个局部最小值（不是凸的），因此优化并不容易。多项式可能有更专业的优化方法，但这对我来说不是专业领域。
评论
$ \ begingroup $
如果我们谈论三次贝塞尔曲线，为什么它是6阶多项式而不是3阶？和您链接的两种方法，它们是否只能在$ [0,1] ^ 2 $而不是整个$ R ^ 2 $中找到解决方案？
$ \ endgroup $
– Ecir Hana
16年1月31日，19：51
$ \ begingroup $
@EcirHana这是6度，因为它是平方距离。 （您可以对它进行平方根运算，但是它不再是多项式，并且在零处将变得不平滑。）请注意，$ [0,1] $是参数空间，而不是样条线所在的空间，即这些是带有端点的样条线。在任何情况下，这些方法在$ \ mathbb {R} ^ 2 $中都可以正常工作，但是它们只能从初始猜测中“走下坡路”，并找到一个局部最小值。还需要更多检查整个参数区域并找到全局最小值。在那里限制参数空间可能会有所帮助。
$ \ endgroup $
–内森·里德（Nathan Reed）
16年1月31日下午22:00
$ \ begingroup $
内森-很好的配方！我很生疏，但是：我认为您可以将每个贝塞尔曲线最多划分为5个分段，通过这些分段$ x $或$ y $改变曲线的方向。作为$ c_i $的函数，$ x $最多会改变方向两次（导数的根），将曲线分为3个部分，其中2个可以再由$ y $方向的改变来划分。现在，您有了的不是直线段，而是“不要弯曲太多”的段。我认为，如果您按细分对选择的25个点开始搜索，可能总能找到全局最小值，但是我不太清楚如何证明（或反对）它。
$ \ endgroup $
–丹尼尔·格塞尔（Daniel M Gessel）
16年1月1日，下午3:47
$ \ begingroup $
@Nathan：我曾经考虑过，但是花了很多时间编写代码以找到纹理压缩格式的最小值，这一切似乎都有些可怕。
$ \ endgroup $
–西蒙F
16年2月1日在13:30
#2 楼
[免责声明：我认为以下内容应该可行，但我自己没有实际编码]我想不出一种“简单”的方法来产生是/否的答案，但是以下内容很合理
让我们假设曲线是A（s）和B（t），控制点分别为{A0，A1..An}和{B0，.. Bm}
在我看来，给定一对我们希望确定其相交或不相交的二维贝塞尔曲线，有六种情况需要考虑：
在这种情况下，我们可以“平凡”地确定它们不相交。请注意那些交点发生的地方。
一个贝塞尔曲线是简并的，即一个点（如果所有控制点都相同，就会出现）。我们可以假设已经处理了两个都是点的情况。
一条或多条曲线是闭合的，例如A0 == An。为了简化生活，我们将细分这些曲线并重新开始。
有无限多个交点，因为每个交点都是“父”贝塞尔曲线的子集，并且它们重叠。
我们不是确定上述情况并需要进一步调查
暂时我们将忽略3和4，但稍后再返回。
案例1
当您在问题中暗示时，如果A和B的控制点的相应边界框不相交，则曲线将不相交。显然，这是一个快速剔除测试，但过于保守。
您可能知道，对于Bezier曲线，其控制点的凸包在曲线上形成（更紧）边界。因此，我们可以使用分离轴技术来确定A和B的外壳是否不相交。 （例如，如Wikipedia中所示：）
如果案例1测试失败，则可以检查相交的“平凡”存在。现在可能有更好的方法可以执行此操作，但是以下相对便宜的方法出现在我的脑海中：
考虑曲线A：
我们知道曲线的起点是$ A_0 $，终点是$ A_n $，位于凸包内。为简单起见，让我们计算线段$ \ overline {A_0A_n} $的方向，并计算两边的边界（即，将其余控制点的点积与垂直于$ \ overline {A_0A_n} $的点相乘）。 br />
如果对曲线B进行相同操作，将得到以下（可能的）情况：
如果我们发现$ A_0 $和$ A_n $在对面之外B的边界以及$ B_0 $和$ B_m $在A的边界之外，那么，根据Beziers的连续性，必须至少有一个交点。
情况6
如果我们不能立即显示上述两种情况，则将每个贝塞尔曲线分成两个“一半”，即$ A ^ 1，A ^ 2，B ^ 1，B ^ 2 $。这是相对简单的（留给读者练习），但对于二次贝塞尔曲线则特别琐碎：
递归地比较这4种组合：$（A ^ 1，B ^ 1），（A ^ 2 ，B ^ 1）...（A ^ 2，B ^ 2）$。
很显然，如果所有通过情况1都没有相交。具有减少的子集的测试。
情况3和5
这会变得更加乏味。
如果“案例3”通过“案例1”测试，在我看来，您需要解决一个实际的交集。假设有一个简单的过程可以将贝塞尔曲线的N个控制点A（s）映射到贝塞尔曲线的N-1个点A'（s），代表它们的一阶导数（但要注意相对罕见的所谓的“退化”情况，其中一阶导数确实为零），则可以使用牛顿迭代（在一维上）来找到潜在的解。 （s）是微分值的约束，有可能尽早消除某些情况。
情况5似乎相对不太可能，所以也许只有在几次递归之后没有确凿的证据，可以针对曲线B尝试A的每个端点，反之亦然。这只会提供相交的证明，而不是不相交的证明。
评论
$ \ begingroup $
是的，但是我个人更感兴趣Bm和/或B0都在A的最大和最小范围之内但不刺穿的情况，那么您需要细分，在最坏的情况下场景计算交点。更好的方法是使用最小边界框，也称为粗线近似。
$ \ endgroup $
– joojaa
16 Jan 29 '15：23
$ \ begingroup $
鉴于每个二进制细分，曲线和连接端点的线段之间的差会以合理的系数下降（而且，从我的头上看，我认为二次方可能是4倍）边界将很快收敛到一条“细”丝带。
$ \ endgroup $
–西蒙F
16年1月29日在15:44
$ \ begingroup $
是的，但最坏的情况是另一个贝塞尔曲线从另一个开始。
$ \ endgroup $
– joojaa
16年1月29日在15:54
$ \ begingroup $
例如，您的意思是An == B0。您是否将其定义为交叉点？
$ \ endgroup $
–西蒙F
16年1月29日在16:01
$ \ begingroup $
不再像B0在曲线上的某处。甚至只是最小的穿越
$ \ endgroup $
– joojaa
16年1月29日在16:08
评论
我不确定它是否存在，确定周长或存在0-1或2或更大的可能性是微不足道的，但是该公式并不能真正确保不经过实际检查即可确定其0或1。运行时要求是什么？一种应该能够产生相当准确的结果的解决方案是通过大量短的直线段近似两条曲线，然后以成对的方式相交。但这会花费大量时间和内存。
@Dragonseel好吧，我真的很乐意提供任何解决方案，但是既然您问O（1）会很好。但是用线段近似曲线会导致与边界框重叠测试相同的问题...
有趣的问题。我认为没有一个简单的答案，但我想错了。您是否有Sederberg和Meyers论文的链接？
@DanielMGessel是的，请参见上面的编辑。