منحنيات بيزير. قليلا عن التقاطعات وبسيطة قدر الإمكان

هل سبق لك أن واجهت بناء مسار (مستمر) لاجتياز منحنى في مستوى محدد بمقاطع الخط ومنحنيات بيزير؟

يبدو أنها ليست مهمة صعبة للغاية: ضم أجزاء المنحنيات في مسار واحد والالتفاف حولها "دون رفع القلم". يمر منحنى مغلق في اتجاه واحد ، وتتأرجح الفروع للأمام وللخلف ، وتبدأ وتنتهي عند نفس العقدة.

كان كل شيء على ما يرام حتى بدأت المسارات الوحشية في الزحف من تحت أيدي المصممين ، حيث يمكن أن تتقاطع المنحنيات الفردية أو لا تلتصق تمامًا. كان التفسير بسيطًا للغاية - بصريًا ، يكذبون جميعًا كما ينبغي ، وبالنسبة للآلة التي ستتجاوز هذا المسار ، فإن هذه الانحرافات غير مرئية.

مسلحًا بمعرفة أقصى انحراف مسموح به ، بدأت البحث الذي أريد مشاركة نتائجه.

أول شيء فعلته هو معرفة كيف تسير الأمور اليوم (أكتوبر 2020) بإيجاد نقاط تقاطع المنحنيات. إما أنني كنت أبحث في المكان الخطأ ، أو ربما كنت أسأل ، لكن لم أجد حلًا بسيطًا. على الرغم من أن الفكرة الناتجة عن زوج من كثيرات الحدود مثيرة للاهتمام للغاية. يتم هنا جمع العديد من الخوارزميات المختلفة المتعلقة بمنحنيات بيزير .

ما لم يعجبني في الطرق المعروفة وما لا أريد فعله هو البحث رقميًا عن جذور كثيرات الحدود ، أو حتى حل المعادلات التربيعية. أنا حقًا لا أرغب في استكشاف منحنيات التطرف. على أي حال ، أود تجنب القسمة والأس ، وكل ما يمكن أن يؤدي إلى سلوك غير محدد.

إذن ما الذي عليك العمل معه.

• يتم تحديد النقاط حسب النوع 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)
{

    if (m_isSimilarCurve)
        return;

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

    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;
}

, , .

.

1. t1و t2يمكن أن يكون أي:
   
   
   • subCurve(curve, 1, 0)سيعطي منحنى "يتحرك" من نقطة النهاية curveإلى نقطة البداية ،
   • subCurve(curve, 1, 2)يستنبط curveأبعد من نقطة الربط الأخيرة.
2. تم حذف بعض عمليات تنفيذ الطرق عمدًا لأنها لا تحتوي على أي شيء مثير للاهتمام بشكل خاص.
3. الوظيفة غير point(curve, t)مناسبة لحساب العديد من النقاط على منحنى (على سبيل المثال ، للتنقيط) ؛ لذلك ، يعد الحساب باستخدام مصفوفة مثلثة أكثر ملاءمة.