تسمية هذه الخوارزمية: مقارنة ونقاط الاستقبال؟

Question

سؤالي قد يكون غريبا بعض الشيء. لقد طورت "خوارزمية ولا أعرف إذا كانت هناك خوارزمية مماثلة بالفعل هناك.

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

لذلك يتناول أساسا مسافات الفاصل ومحاولة تناسبها هناك. أحاول تتبع كائن يتحرك تقريبا على طول هذا المسار.

هل هذا يبدو مألوفا لشخص ما؟ هل يمكن لشخص ما التوصل إلى اقتراح للخوارزمية الموجودة؟

تعديل: من ما ذكرته حتى الآن، أريد أن أوضح أن الموقف لا يضاعف مرتبط بالنقاط. النظر في رسم ASCII الجميلة جوناثان صنع:

تم العثور على موقف X ضمن القطاع 1 و 2 (S12). الآن الموقع التالي هو Y، الذي لا ينبغي اعتباره قريبا بما يكفي لتكون في S12. سأنتقل إلى S23، والتحقق مما إذا كان ذلك في.

إذا كان ذلك، فلن أتحقق من S12 لأي قيمة أخرى، لأنني وجدت واحدة في الجزء التالي بالفعل. الخوارزمية "لا تنظر إلى الوراء".

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

الحلقة لا تزال مشكلة. فكر في أنني أحصل على Y ل S23 ثم تخطي مواقع أو ثلاث وظائف (لأنها بعيدة جدا)، قد أفقد المسار. يمكنني تحديد موقع واحد في S34 حيث سيكون بالفعل في S56.

ربما يمكنني التوصل إلى بعض السرعة المتوسطة لتحديد Vage في أي قسم يجب أن يكون.

يبدو أن أكبر القطاعات هي، أكبر فرصة لاتخاذ القرار الصحيح.

Answer 1

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

حان الوقت لدفع ASCII Art إلى حدود. النظر في المسار التالي (تمثل الأرقام التسلسل في قائمة نقاط المسار)، والتنسيق X (وبعد ذلك، Y).

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

كيف يفترض أن نفسر وصفك؟

C] أزال المسافة من نقطة المسار الأول إلى الإحداثيات الجديدة ومسافة الفاصل الزمني لأول نقطة اثنين. إذا كانت المسافة إلى الإحداثيات المقاسة أقصر من المسافة من أول إلى نقطة المسار الثانية، [افترض أن هذه النقطة تكمن بين هذا الفاصل؛ [...] [i] F أنها أكبر، [...] تحقق مع الفاصل الزمني التالي.

أعتقد أن الجملة الأولى تعني:

• احسب المسافة من TP1 (Track Point 1) إلى TP2 - اتصل به D12.
• احسب المسافة من TP1 إلى x (اتصل بها D1X) ومن TP2 إلى x (اتصل بها D2X).

الجزء الصعب هو تفسير الجملة الشرطية.

انطباعي هو أنه إذا كان D1X أو D2X أقل من D12، فسيتم افتراض X في (أو الأقرب أيضا) الجزء TP1 TP1 إلى TP2 (إتصل بقطاع S12).

بالنظر إلى موضع X في الرسم البياني، فمن الواضح بشكل معتدل أن كل من D1X و D2X أصغر من D12، لذلك فإن تفسير الخوارزمية الخاصة بك سوف يفسر X كما هو مرتبط ب S12، ومع ذلك، فإن x أقرب إلى S23 أو S56 منه هو S12 (ولكن يتم التخلص من تلك دون النظر إليها).

هل أسيء فهم شيء عن خوارزمية الخاص بك؟

التفكير في الأمر قليلا: ما قمت بتفسير الخوارزمية الخاصة بك يعني أنه إذا تكمن النقطة x داخل دائرة RADIUS D12 التي تركز على TP1 أو دائرة RADIUS D12 التي تركز على TP2، فأنت تنضم X باستخدام S12. ومع ذلك، إذا كنا أيضا تفكر في النقطة Y، فإن الخوارزمية التي أقترح عليك أن تستخدمها أيضا مع S12.

إذا تم تنقيح الخوارزمية القول MAX(D1Y, D2Y) < D12, ، ثم لا يعتبر y يرتبط ب S12. ومع ذلك، ربما لا يزال X يعتبر مرتبطا ب S12 بدلا من S23 أو S56.

Answer 2

الجزء الأول من هذه الخوارزمية يذكرني بالتحرك من خلال مساحة تقديرية. مثال على تمثيل مثل هذه المساحة هو z-order. منحنى ملء الفضاء. لقد استخدمت هذه التقنية لتمثيل quadtree, ، هيكل البيانات ل صقل شبكة التكيف رمز عملت مرة واحدة، واستخدمت خوارزمية مثل الوحدة التي تصفها لاجتياز الشبكة وتحديد المسافات بين الجزيئات.

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