我正在尝试查找/创建一种算法来计算两个任意填充的2D对象的交集(一个新的填充对象)。使用直线或者三次方贝塞尔曲线定义对象，这些对象可能具有孔或者自相交。我知道这里列出了几种对多边形执行相同操作的现有算法。但是，我想在不将贝塞尔细分为多边形的情况下支持贝塞尔曲线，并且在没有交集的区域中，输出应该具有与输入大致相同的控制点。

这是用于交互式程序执行某些CSG，但剪辑不需要是实时的。我搜索了一段时间，但没有找到好的起点。

解决方案

关于做贝塞尔曲线修剪，有许多学术研究论文：

http://www.andrew.cmu.edu/user/sowen/abstracts/Se306.html

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.6669

http://www.dm.unibo.it/~casciola/html/research_rr.html

我建议使用间隔方法，因为正如我们所描述的，我们不必划分为多边形，既可以获得保证的结果，又可以为结果集定义自己的任意精度。有关间隔渲染的更多信息，我们也可以参考http://www.sunfishstudio.com

很久很久以前，我编写了代码来做到这一点。我正在使用使用作为PostScipt路径生成的分段Bezier边界处理定义的2D对象的项目。

我使用的方法是：

令曲线p，q由Bezier控制点定义。它们相交吗？

计算控制点的边界框。如果它们不重叠，则两条曲线不会相交。否则：
p.x(t)，p.y(t)，q.x(u)，q.y(u)是0 <= t，u <= 1.0上的三次多项式。
距离平方(p.x q.x)** 2 +(p.y q.y)** 2是(t，u)的多项式。
使用Newton-Raphson尝试将其求解为零。丢弃0 <= t，u <= 1.0以外的任何溶液

N-R可能会收敛，也可能不会收敛。两条曲线可能不相交，或者当两条曲线几乎平行时，N-R可能会爆炸。因此，如果经过任意多次迭代后仍未收敛，请切断N-R。这可能是一个相当小的数字。

如果N-R不能在一个解上收敛，则在t = 0.5时将一条曲线(例如p)分成两条曲线pa，pb。正如链接文章所示，这很容易，它只是计算中点。然后递归测试(q，pa)和(q，pb)的交集。 (请注意，在递归的下一层中，q已变成p，因此p和q在递归的每个层上交替拆分。)

由于边界框是不重叠的，因此大多数递归调用都会快速返回。

我们将不得不在任意深度处切断递归，以处理两条曲线平行且不太接触的怪异情况，但它们之间的距离任意小-可能只有1 ULP的差异。

找到交点后，就没有完成，因为三次曲线可以有多个交点。因此，我们必须在相交点处分割每条曲线，然后递归检查(pa，qa)，(pa，qb)，(pb，qa)，(pb，qb)之间是否存在更多交集。

我知道我有被裁员的风险，但是我正在调查同一问题，找到了我已经在学术论文中阅读过但没有找到可行解决方案的解决方案。

我们可以将贝塞尔曲线改写为两个两个双变量三次方程组，如下所示：

• ？x = ax？* t？^ 3 + bx？* t？^ 2 + cx？* t？ + DX？ -ax？* t？^ 3-bx？* t？^ 2-cx？* t？ -DX？
• ？y = ay？* t？^ 3 + by？* t？^ 2 + cy？* t？ + dy？ -ay？* t？^ 3-by？* t？^ 2-cy？* t？ -dy？

显然，曲线的交点为(t？，t？)的值，其中？x =？y =0。不幸的是，由于很难在二维中找到根，并且近似方法趋于(如另一个)而变得复杂。作家说)炸毁。

但是，如果我们使用整数或者有理数作为控制点，则可以使用Groebner基将双变量3阶多项式重写为(可能是9阶，因此9阶-可能的相交)单变量多项式。之后，我们只需要在一个维度中找到根(例如t？)，然后将结果重新插入一个原始方程式即可找到另一个维度。

Burchburger对Groebner Bases进行了通俗易懂的介绍，称为" Gr？bner Bases：系统理论家简介"，这对我很有帮助。去谷歌上查询。另一篇有用的论文是TF Hain撰写的"快速，精确的三次Bzier路径和偏移曲线的精确平坦化"，其中有许多关于bezier曲线的效用方程，包括如何找到x和y方程的多项式系数。

至于贝塞尔剪裁是否对这种特定方法有所帮助，我对此表示怀疑，但是贝塞尔剪裁是一种缩小交点位置的方法，而不是找到交点位置的最终(尽管可能是近似的)答案。这种方法的大量时间将花费在寻找单变量方程上，并且该任务通过裁剪不会变得更加容易。相比之下，找到根源是微不足道的。

但是，此方法的优点之一是它不依赖于递归地细分曲线，该问题成为一个简单的一维根查找问题，这不容易，但是有据可查。主要的缺点是，如果我们要处理浮点多项式或者使用高阶Bezier曲线，则计算Groebner基的成本很高，并且变得非常笨拙。

如果我们想在Haskell中找到一些完成的代码来找到交点，请告诉我。

我发现以下出版物是有关Bezier Clipping的最佳信息：

T. W. Sederberg，BYU，计算机辅助几何设计课程笔记

有关曲线交点的第7章可在线获得。它概述了找到相交的4种不同方法，并详细描述了Bezier Clipping：

http://www.tsplines.com/technology/edu/CurveIntersection.pdf