خوارزمية لخرائط التخطيط (المترو)

Question

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

لقد حصلت على مشروع لإنشاء تطبيق سوف ، بالنسبة لمحطات الإدخال المحددة (الرؤوس) والخطوط (الحواف) ، أي خريطة حقيقية لبعض وسائل النقل العام ، تخطط لخريطة معينة في خريطة المترو. لقد أجريت بعض الأبحاث حول المشكلة وهي مشكلة مكتملة NP تعادل مشكلة 3-SAT. لدي أيضًا بعض الأفكار النظرية حول كيفية إنشاء مثل هذه الخريطة ، لكنها ليست مفصلة بما فيه الكفاية.

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

إذا كان أي شخص قد رأى أي شيء يمكن أن يساعدني ، فسأقدر ذلك كثيرًا.

Answer 1

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

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

على أي حال ، إليك ثلاثة منشورات وجدتها مثيرة للاهتمام لتبدأ بها (من بين العديد من الآخرين):

تخطيط خريطة المترو باستخدام تحسين متعدد المعايير

تقليل خط عبور الخط على خرائط المترو

مشكلة تخطيط خريطة المترو

هول!

Answer 2

البحث الذي يشبه موضوعك: http://graphics.stanford.edu/papers/routemaps/

Answer 3

هذا مجرد بعض الاقتراحات مع الموفرة اليدوية - خذ بقرصة من الملح.

إن فكرتي لخريطة "المترو" هي واحدة حيث تميل الخطوط إلى أحد الاتجاهات الأساسية الثمانية والمحطات متباعدة بانتظام.

أفترض أنك تحاول تحويل مجموعة من الإحداثيات الحقيقية إلى إحداثيات "مترو".

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

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

بعد القيام بذلك ، قم بتوسيع نطاق كل سطر بحيث تكون المحطات المتتالية هي نفس المسافة على عرض "مترو".

أظن أنك ستظل ترغب في دعم التغيير والتبديل اليدوي للنتيجة.

حظا طيبا وفقك الله!

Answer 4

يبدو وكأنه مشكلة التخطيط. يبدو أن قيودك الصعبة هي:

• يجب أن تكون كل محطة على نقطة. النقاط على شبكة مع مسافة x بين النقاط (سأجعل هذا ثابت على 2 سم)

• لا ينبغي أن يكون هناك محطتان في نفس المكان

• يجب أن يكون هناك مساحة كافية لرسم ملصق المحطة. لاحظ أنه يمكن تعيين التسمية اتجاهات مختلفة من النقطة التي يتم تعيين المحطة إليها.

• يجب أن يكون هناك مساحة كافية لرسم خطوط المترو.

يبدو أن قيودك الناعمة هي:

• لكل محطة ، قلل من مسافة الموقع الجغرافي فعليًا إلى النقطة المخصصة للمحطة.

ثم قم برمي شيء مثل مخطط اللقط عليه ، إليك مثال على القيود الصعبة والنعومة لقائمة الممرضة.