بيزيه لقطة

Question

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

هذا هو برنامج تفاعلي لعمل بعض CSG ولكن لقطة لا تحتاج إلى أن تكون في الوقت الحقيقي.لقد بحثت لفترة من الوقت ولكن لم يتم العثور على نقطة انطلاق جيدة.

Answer 1

لقد وجدت بعد نشر من معلومات بشأن بيزيه لقطة:

T.W.Sederberg, جامعة بريغهام يونغ, بمساعدة الحاسوب تصميم هندسي الحال الملاحظات

الفصل 7 التي تتحدث عن منحنى تقاطع متاح على الإنترنت.ويوجز 4 أساليب مختلفة للعثور على التقاطعات يصف بيزيه لقطة في التفاصيل:

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

Answer 2

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

يمكنك كتابة منحنيات بيزيه مجموعة من اثنين ثنائية variate مكعب المعادلات مثل هذا:

• ∆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 قواعد أن تعيد ثنائية variate النظام-3 متعددو الحدود في (ربما-إلى أجل-9-وهكذا-your-تسعة-ممكن-التقاطعات) monovariate متعدد الحدود.بعد ذلك تحتاج فقط إلى العثور على جذور (،يقول t₂) في بعد واحد ، وتوصيل النتائج الخاصة بك مرة أخرى إلى واحد من الأصلي المعادلات لإيجاد البعد الآخر.

Burchburger لديه عاديا الصديقة مقدمة Groebner قواعد تسمى "قواعد غروبنر:مقدمة قصيرة عن أنظمة المنظرين"هذا كان مفيدا جدا بالنسبة لي.جوجل ذلك.الورق الأخرى التي كانت مفيدة واحدة تسمى "سريعة ودقيقة تسطيح مكعب قوس المسار وتعويض المنحنيات"قبل TF هين ، والتي لديها الكثير من المرافق المعادلات منحنيات بيزيه ، بما في ذلك كيفية العثور على متعدد الحدود معاملات x و y المعادلات.

أما إذا كانت بيزيه لقطة تساعد هذه الطريقة على وجه الخصوص ، أشك في ذلك, ولكن بيزيه القطع هو طريقة تضييق حيث التقاطعات قد يكون ليس من أجل إيجاد النهائي (على الرغم ربما تقريبي) الجواب من حيث هو.الكثير من الوقت مع هذا الأسلوب سوف تنفق في إيجاد أحادية variate المعادلة المهمة لا تحصل على أي أسهل مع لقطة.العثور على الجذور من خلال المقارنة تافهة.

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

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

Answer 3

كتبت البرمجية للقيام بذلك طويلة مضت.مشروع كنت تعمل على تعريف 2D الكائنات باستخدام piecewise بيزيه الحدود التي تم إنشاؤها كما PostScipt مسارات.

نهج اعتدت كان:

اسمحوا منحنيات p, q, يحددها بيزيه نقاط التحكم.هل التداخل ؟

حساب المربعات المحيطة نقاط التحكم.إذا أنها لا تتداخل ، ثم المنحنيين لا تتقاطع.خلاف ذلك:

p.x(t) ، ص.y(t) q.x(u) ، q.y(u) هي مكعب متعددو الحدود على 0 <= t,u <= 1.0.المسافة تربيع (p.x - q.x) ** 2 + (p.ذ - س.y) ** 2 هو متعدد الحدود على (t,u).استخدام نيوتن-رافسون في محاولة حل هذا الصفر.تجاهل أي حلول من الخارج 0 <= t,u <= 1.0

N-R قد أو قد لا تتلاقى.منحنيات قد لا تتقاطع أو N-R يمكن أن ينفجر عندما المنحنيين هي موازية تقريبا.حتى قطع N-R إذا كان لا تتلاقى بعد بعض التعسفي عدد التكرارات.هذا يمكن أن يكون إلى حد ما صغيرة العدد.

إذا كان N-R لا تتلاقى على الحل ، سبليت واحد منحنى (أقول, p) في اثنين من منحنيات pa pb في t = 0.5.هذا هو السهل, انها مجرد الحوسبة نقاط المنتصف ، كما ربط المقالة.ثم متكرر اختبار (ف, pa) و (س, pb) على التقاطعات.(لاحظ أنه في الطبقة التالية من العودية التي س أصبح p, حيث أن p و q هي بالتناوب على تقسيم كل طبقة من العودية.)

معظم دعوات متكررة العودة بسرعة لأن إحاطة مربعات غير متداخلة.

سيكون لديك لقطع العودية في بعض التعسفي عمق التعامل مع غريب الحالات التي يكون فيها اثنين من منحنيات موازية و لا تعمل باللمس ، ولكن المسافة بينهما صغيرة بشكل عشوائي ربما فقط 1 ULP من الفرق.

عندما كنت لا تجد تقاطع أنت لم تفعل, لأن مكعب المنحنيات يمكن أن يكون متعددة المعابر.لذلك عليك أن تقسيم كل المنحنى في نقطة تقاطع و بشكل متكرر البحث عن المزيد من interections بين (السلطة الفلسطينية ، سؤال وجواب), (pa, qb), (pb, qa), (pb, qb).

Answer 4

هناك عدد من البحوث الأكاديمية الأوراق على القيام بيزيه لقطة:

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

أوصي الفاصل أساليب لأنه كما ذكرت لا يجب أن الانقسام وصولا إلى المضلعات و يمكنك الحصول على نتائج مضمونة وكذلك تحديد الخاصة بك التعسفي الدقة resultset.لمزيد من المعلومات عن فترة التقديم ، قد تشير أيضا إلى http://www.sunfishstudio.com