تحقق مما إذا كان المضلع متماثلًا

Question

بالنظر إلى المضلع (ليس محدبًا بالضرورة) في الإحداثيات الديكارتية ، أتساءل عما إذا كان هناك أي طريقة للتحقق من تناسق هذا المضلع؟

يمكنني التفكير في حل O (N): استخدام ملاقط دوارة للتحقق مما إذا كان كل زوج من الحافة المقابلة متوازيًا ومتساويًا في الحجم.ومع ذلك ، لا يمكنني إثبات صحة تلك الخوارزمية.هل يمكنك اقتراح أي حل أفضل؟

Answer 1

• أنت تحسب مركز ثقل المضلع.
• أنت تترجمها إلى الأصل بحيث يكون مركز الثقل لديك (0،0) على شكل إحداثيات.
• ثم بالنسبة لكل رأس إحداثيات (i ، j) ، عليك التحقق من وجود رأس به إحداثيات (-i، -j).

سيثبت هذا أن المضلع متماثل بالفعل.

التعقيد: N ، بافتراض أنه يمكنك الوصول مباشرة إلى الرؤوس من إحداثياتها.

Answer 2

يجب أن توضح نوع التناظر المسموح به.التناظر المركزي (دوران 180 درجة)؟التناظر المرآة على أحد المحاور؟التناوب بأي درجة؟في بعض التطبيقات ، يُسمح فقط بالتناوب بنسبة 0،90،180،270 + الانعكاس ... ستكون الإجابة مختلفة في كل حالة.

بالنسبة إلى التناظر المركزي فقط ، إذا افترضت أن المضلع ممثل بشكل جيد (على سبيل المثال ، لا توجد رؤوس إضافية على الحواف ، ويتم الاحتفاظ بالرؤوس في أحد العناصر المضمنة باستخدام عامل تشغيل أمامي ، فسيكون للمضلع المتماثل مركزيًا عدد زوجي 2 * N تحقق، ويمكنك القيام بذلك:

1. عيّن iter1 لمرجع الرأس 0 ، و iter2 للإشارة إلى الرأس N.

2. كرر N مرات:

   if (* iter1!= * iter2) ترجع خطأ ؛

3. عودة صحيحة ؛

Answer 3

تحتاج أولاً إلى تحديد نوع التناظر الذي تريد التحقق منه (ما هو التحول الذي يجب أن يكون مضلعك ثابتًا عليه).ستتحقق الخوارزمية التي تقدمها من التناظر المركزي للمضلعات المحدبة (حيث تعمل الفرجار الدوارة فقط مع المضلعات المحدبة).