rotating_calipers
Rotating calipers 1.0
الفرجار الدوار هو وحدة بيثون التي تنفذ خوارزمية مع نفس الاسم.
تم اختراع الخوارزمية لأول مرة من قبل Michalel Shamos في عام 1978 واكتسبت اسمها "الفرجار الدوار" بفضل Godfried Toussant الذي عرضه في ورقته في عام 1983.
تم تسمية هذه الطريقة لأن الفكرة مماثلة لتدوير الفرجار الزراعي المحمّل بنابض حول الجزء الخارجي من مضلع محدب. في كل مرة تقع شفرة واحدة من الفرجار مسطحة على حافة المضلع ، فإنها تشكل زوجًا مضادًا للوحد مع النقطة أو الحافة التي تلمس الشفرة المعاكسة. يكتشف "الدوران" الكامل من الفرجار حول المضلع جميع أزواج مضادات البدود ؛ مجموعة من جميع الأزواج ، التي يُنظر إليها على أنها رسم بياني ، تشكل تقويمًا. يمكن تفسير طريقة الفرجار الدوارة على أنها مزدوجة إسقاط لخوارزمية خط المسح التي تكون فيها عملية المسح عبر منحدرات من الخطوط بدلاً من ذلك عبر X- أو Y-coordinates من النقاط.
تم تكييف الوصف أعلاه من صفحة ويكيبيديا: https://en.wikipedia.org/wiki/rotating_calipers
تم تنفيذ خوارزمية "الفرجار الدوار" من قبل لي لمشروع جامعي. بشكل مدهش ، واجهت الكثير من المتاعب في العثور على حل فعال في بيثون. لهذا السبب أردت مشاركته مع كل من يحتاج إلى تطبيق سريع "الفرجار الدوار" في بيثون.
نظرًا لأن الفرجار الدوار يعمل في الوقت الخطي ، فإنه يحتاج إلى بدن محدب على الإدخال ويتم حسابه هنا باستخدام خوارزمية Graham التي تعمل في O (Nlogn). الكل في جميع الخوارزم (خوارزمية غراهام + الفرجار الدوار) تعقيد الوقت هو o (nlogn) + o (n) = o (nlogn)
لينكس:
مثال على الاستخدام يمكن العثور عليه هنا
