ملء المضلع: أداء لف القاعدة ضد القاعدة حتى غريبة

Question

لمضلع معقدة (أي: المتقاطعة الذاتي). الاختيار بين لف أو قواعد ملء حتى ونيف يحدث فرقا في طريقة شغل المضلع

ولكن للمضلعات غير المتقاطعة هناك أي اختلاف الأداء بين لف أو قواعد ملء حتى غريبة. وأنا أفهم أنه سيكون implentation معين ولكن أي من خوارزميات هو أكثر effecient للمضلعات غير معقدة.

ومتابعة السؤال ما هو التعقيد (أي O (ماذا؟)) كل من هذه الخوارزميات. أريد أن أعرف ما إذا كان الأمر يستحق التخلص من بعض النقاط في المضلع (أساسا مكررة أو تلك التي هي على نفس الخط) لتحسين الأداء.

وPS: إذا كان يهم على الإطلاق، وأنا على استخدام xlib

وPPS: أستطيع أن أؤكد أن المشكلة ليست الأجهزة ذات الصلة مثل استخدام بطاقة رسومات مختلفة لا يغير من أداء

Answer 1

واليوم، معظم تطبيقات X استخدام الأجهزة 2D بطاقة الرسومات الخاصة بك وبالتالي فإن الفرق بين الاثنين هو ربما لا تذكر.

وبما أن هذا هو السؤال الأداء، فرص جوابي يجري الصحيح هو حوالي 10٪، على الرغم من (مع الأداء، لديك فرصة 90٪ أن أكون مخطئا دون قياس). إذا كنت تريد أن تكون على يقين، لا توجد وسيلة ولكن لكتابة اختبار أداء صغير وانظر لنفسك.

x11perf قد تساعد.

ويمكنك العثور على خوارزمية لالمضلع مستقل الأجهزة ملء هنا: <لأ href = "http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c؟rev=HEAD" يختلط = "نوفولو noreferrer"> http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c؟rev=HEAD

وهناك نسخة ثانية وهو أسرع بكثير إذا كنت متأكدا من المضلع المحدب هو: <لأ href = "http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c؟ مراجعة = رأس "يختلط =" نوفولو noreferrer "> http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c؟rev=HEAD

والإصدار الثاني يتجاهل حكم التعبئة (الذي لا ينطبق على محدبة المضلعات). تعليقات حول الخوارزمية: HTTP: // cvsweb .xfree86.org / cvsweb / الضاحيه / برامج / خادم إكس / ميل / mipoly.h؟ دوران المحرك = رأس

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

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

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