كيفية العثور على دائرة نصف قطرها الحد الأدنى الذي يحفز كل النقاط المحددة؟

Question

لنفترض أن لدي حوالي 1000 نقطة فردية على متن طائرة.

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

الآن من هنا، ما الذي يمكن القيام به للعثور على الحد الأدنى من دائرة نصف قطرها؟

أبحث عن تعميم هذا من أجل الحذف مرة واحدة أفهم كيف يمكن القيام به للدوائر.

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

Answer 1

خيار واحد هو مكتبة خوارزميات الهندسة الحاسوبية CGAL. وبعد إنه مفتوح المصدر، لكنه كبير أيضا - المشكلة الأكبر التي ستكون لديك، أظن أن إيجاد الإبرة في كومة القش.

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

Answer 2

هذا هو المعروف باسم مشكلة الحد الأدنى لمشكلة دائرة (أنا في حيرة لماذا لم تظهر بحث Google الخاص بك أي شيء)، ومناقشتها هنا, هنا, هنا, وفي العديد من الأماكن الأخرى.