☝️ 🙅🏻 👋🏼 贝塞尔曲线。关于交叉点的一些知识，并且尽可能简单 ✌🏾 🤲🏾 🌵

您是否曾经遇到过构建（连续）路径以在由线段和贝塞尔曲线定义的平面中遍历曲线？

这似乎不是一件困难的任务：将一条曲线的各段连接到一条路径中并“不抬起笔”就绕过它。一条闭合曲线沿一个方向移动，分支向前和向后移动，并在同一节点处开始和结束。

一切都很好，直到可怕的路径开始从设计师的手下爬出来，那里的单个曲线可能相交或不完全对接。解释非常简单-视觉上它们都应有的谎言，而对于绕过这条路的机器而言，这种偏差是不可见的。

有了最大允许偏差的知识，我开始了研究，我想分享其结果。

我做的第一件事是找到曲线的交点，从而弄清楚今天（2020年10月）的情况。我在找错地方了，或者我在问，但是找不到简单的解决方案。虽然，带有一对多项式的结果的想法非常有趣。这里收集了许多与Bezier曲线有关的算法。

我不喜欢已知的方法，也不想做的是，在数值上搜索多项式的根，甚至求解二次方程。我真的不想探索极端的曲线。无论如何，我想避免除法，取幂和所有可能导致不确定行为的事物。

例

如果尝试继续曲线，则尽管它们足够靠近，但根本不会与另一条曲线相交

因此，您必须使用什么。

点由type指定Point，如下所示：
```
using Point = std::array<double, 2>;
```
对于Point加法，减法，标量乘法，标量乘法的运算符进行了定义。
R设置点的允许偏差值。
曲线由控制点组成std::vector<Point>。
应标记几乎重合的曲线，并在可能的情况下将其删除，例如，如果曲线被遗忘（复制粘贴是邪恶的）。

, , . ( ):

Point point(const std::vector<Point> &curve, double t, int n, int i)
{
    return n == 0 ? curve[i] : (point(curve, t, n - 1, i - 1) * (1 - t) + point(curve, t, n - 1, i) * t);
}

— , :

Point point(const std::vector<Point> &curve, double t)
{
    return point(curve, t, curve.size() - 1, curve.size() - 1);
}

, curve — : , .

— - , R:

template <>
struct std::less<Point>
{
    bool operator()(const Point &a, const Point &b, const double edge = R) const
    {
        for (auto i = a.size(); i-- > 0;) {
            if (a[i] + edge < b[i])
                return true;
            if (a[i] > b[i] + edge)
                return true;
        }
        return false;
    }
};

. , , , . — :

struct Rect
{
    Point topLeft, bottomRight;
    Rect(const Point &point);
    Rect(const std::vector<Point> &curve);
    bool isCross(const Rect &rect, const double edge) const
    {
        for (auto i = topLeft.size(); i-- > 0;) {
            if (topLeft[i] > rect.bottomRight[i] + edge
                || bottomRight[i] + edge < rect.topLeft[i])
                return false;
        }
        return true;
    }
};

void find(const std::vector<Point> &curveA, const std::vector<Point> &curveB,
          double tA, double tB, double dt)
{

1. , .

    if (m_isSimilarCurve)
        return;

2. ,

    Rect aRect(curveA);
    Rect bRect(curveB);
    if (!aRect.isCross(bRect, R))
        return;

3. R/2, ,

    if (isNear(aRect.tl, aRect.br, R / 2) && isNear(bRect.tl, bRect.br, R / 2)) {
        // 3.1        
        addBest(curveA.front(), curveA.back(), curveB.front(), curveB.back(), tA, tB, dt);
        m_isSimilarCurve = (m_result.size() > curveA.size() * curveB.size());
        return;
    }

    const auto curveALeft = subCurve(curveA, 0, 0.5);
    const auto curveARight = subCurve(curveA, 0.5, 1.0);
    const auto curveBLeft = subCurve(curveB, 0, 0.5);
    const auto curveBRight = subCurve(curveB, 0.5, 1.0);

    const auto dtHalf = dt / 2;
    find(curveALeft, curveBLeft, tA, tB, dtHalf);
    find(curveALeft, curveBRight, tA, tB + dtHalf, dtHalf);
    find(curveARight, curveBLeft, tA + dtHalf, tB, dtHalf);
    find(curveARight, curveBRight, tA + dtHalf, tB + dtHalf, dtHalf);

- : , t t1 t2?

t = (t2 - t1) t' + t1 . t = t1, t = t2. , ( ) . : k t2 t1, k:

Point point(const std::vector<Point> &curve, double t1, int n, int i, double t2, int k)
{
    return n > k ? (point(curve, t1, n - 1, i - 1, t2, k) * (1 - t2) +
                    point(curve, t1, n - 1, i, t2, k) * t2)
                 : point(curve, t1, n, i);
}

, :

std::vector<Point> subCurve(const std::vector<Point> &curve, double t1, double t2)
{
    std::vector<Point> result(curve.size());
    for (auto k = result.size(); k-- > 0;) {
        result[k] = point(curve, t1, curve.size() - 1, curve.size() - 1, t2, curve.size() - 1 - k);
    }
    return result;
}

, , .

.

t1并且t2可以是任何：
- subCurve(curve, 1, 0)将给出一条从端点curve到起点“移动”的曲线，
- subCurve(curve, 1, 2)推断curve超出最后一个锚点。
有意省略一些方法实现，因为它们不包含任何特别有趣的内容。
该函数point(curve, t)不适用于计算曲线上的许多点（例如，用于栅格化）;因此，使用三角矩阵进行的计算更为合适。

贝塞尔曲线。关于交叉点的一些知识，并且尽可能简单

.

More articles: