بالنظر إلى مجموعة من النقاط، كيف يمكنني العثور على النقطتين الأبعد عن بعضهما البعض؟[ينسخ]

Question

التكرار المحتمل:
أكبر مجموعة من النقاط ذات البعد الخطي ثنائي الأبعاد

يمكنني حساب المسافة بين كل نقطة وأخذ أكبرها، لكن هذا لا يبدو طريقة فعالة جدًا للقيام بذلك عندما يكون هناك عدد كبير (> 1000) من النقاط.

ملحوظة:هذا لجهاز iPhone لذا ليس لدي الكثير من قوة المعالجة.

Answer 1

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

وهنا أ مناقشة قابلة للقراءة إلى حد ما لخوارزمية O(n) الصحيحة للمهمة (حيث n هو عدد النقاط في الهيكل المحدب).

لاحظ أيضًا أن جهاز iPhone ليس كذلك الذي - التي محدود؛يمكن للتنفيذ المكتوب بعناية حتى للخوارزمية الساذجة تمامًا التعامل مع 1000 نقطة في أقل من عُشر الثانية.وبطبيعة الحال، فإن استخدام الخوارزمية الصحيحة سوف يتيح لك التحرك بشكل أسرع =)

Answer 2

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

Answer 3

ابدأ بالنقطة ذات التنسيق x الأدنى.(Call It Point X) إنشاء مجموعة من "نقاط الحدود" التي تبدأ بالنقطة X ، والخط العمودي خلال النقطة ، يجب ألا تكون هناك نقاط أخرى إلى اليسار من PointX) تجد النقطة التالية في الحدود عن طريق تدوير الخط ببطء في اتجاه عقارب الساعة (أو عكس اتجاه عقارب الساعة) حتى يلمس الخط نقطة أخرى ، (انظر أدناه).أضف هذه النقطة إلى المجموعة وكرر ذلك مع النقطة التالية للحصول على النقطة التالية، حتى تعود في النهاية إلى النقطة الأصلية x.لديك npw مجموعة من النقاط التي تشكل حدود المجموعة الكاملة.قارن المسافة بين كل زوج في هذه المجموعة المختصرة للعثور على الزوج الأكثر تباعدًا.

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

Answer 4

يرى هذه الصفحات (الصفحة المرتبطة بها والصفحات التي يمكن الوصول إليها بالضغط على الروابط "التالي") على حساب قطر الهيكل المحدب لمجموعة من النقاط.

ملخصي السريع:

1. حساب مجموعة من النقاط في بدن محدب (= O(n log n)، المرة الوحيدة التي تحصل فيها على O(n) هي إذا قمت بفرز القائمة أولاً والتي تأخذ O(n log n) على أي حال)
2. اطلب على طول الحدود (تحصل على هذا مجانًا إذا كنت تستخدم ملف مسح غراهام ل 1)
3. استخدم إحدى خوارزميات قطر O(n) للبحث عن النقاط المضادة ذات القطر الأكبر. خوارزمية شاموس تبدو جيدة بالنسبة لي لأنها واحدة من الفرجار الدوارة خوارزميات.