• 0
هاني الأتاسي

سلسلة شغل مخك - العودة - 1

سؤال

معظمكم يعرف سلسلتي شغل مخك في أيام الخوالي .. أحببت أن أعيدها وأقدم أسئلة أقوى وبتحدي أكبر :) الحلول ممكن أن تكون بأي لغة سي ، سي++، سي# ، psuedo code ، ...

أبدأ الجزء الثاني من السلسلة بهذا السؤال ..

مهمتك برمجة جزء من برناج رسم ثنائي الأبعاد .. لنقل smart paint .. يمكنك من خلال البرنامج ان تضع اشكال مثلا مربع دائرة خط نقطة .. الخ .. ووظيفتك أن تصمم الكود المسؤول عن اختيار الأشكال أي الكود داخل mouse click event .. مهمتك كتابة كود للتابع التالي:

Shape Select(int x, int y) {
};

للتسهيل ، يمكنك ان تعتبر أي شكل محاط بمستطيل وبالتالي تسهل عملية فحص إذا كانت الكليك تابعة للشكل ام لا.. أي أن كل shape يحتوي على التالي:


class Shape {
public int x1, y1, x2, y2; // boundry
public bool IsInside(int x, int y);
}

المطلوب منك تصميم ال data structure لحفظ ال shapes ، أي كيف سوف تحفظ الأشكال بالذاكرة وكتابة الكود الذي يحقق أسرع وقت من أجل ملاقاة الشكل ..

:wacko:

تم تعديل بواسطه هاني الأتاسي
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

12 إجابة على هذا السؤال .

  • 0

يعني المطلوب pattern recognition ؟

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
يعني المطلوب pattern recognition ؟

لا.. فقط معرفة اي shape تم الضغط عليه .. مثال لدينا شكل shape1 احداثياته 10,10,100,100 وشكل shape2 احداثياته 200,200,250,250 والمستخدم نقر على الاحداثيات 50,50 فالكود المطلوب يجب ان يرجع shape1 ..

أريد أي حل يحقق المطلوب وكودوز لأسرع خوارزمية :)

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

هذه محاولة أولي :

انسخ الكود
  1. shape select(int x,int y)
  2. {
  3. vector<shape> shapes;
  4. int i;
  5. for(i=0;i<shapes.size();i++)
  6. {
  7. if( shapes[i].IsInside(x,y)) return shapes[i];
  8. }
  9.  
  10. }
  11.  

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
هذه محاولة أولي :

انسخ الكود
  1. shape select(int x,int y)
  2. {
  3. vector<shape> shapes;
  4. int i;
  5. for(i=0;i<shapes.size();i++)
  6. {
  7. if( shapes[i].IsInside(x,y)) return shapes[i];
  8. }
  9.  
  10. }
  11.  
  12.  

شكرا للمشاركة أخ فهد .. فقط للتوضيح في حلك ال vector يكون في الخارج ويتم اضافه له عند وضع الshapes على لوحة الرسم .. حلك صحيح ولكن:

1- في حال ليدنا المئات من الshapes هل يوجد حل أسرع؟

2- ماذا لو يوجد أشكال فوق بعضها ، أيها سوف تعيد؟

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

هذا كود بسيط بالمقارنات العادية دون استخدام أى خوارزمية

انسخ الكود
  1. using System;
  2. using System.Collections;
  3.  
  4. namespace ConsoleApplication1
  5. {
  6. class Shape
  7. {
  8. public string Shapename;
  9. public int x1, y1, x2, y2;
  10.  
  11. public bool IsInside(int x, int y)
  12. {
  13. if (x >= x1 && x <= x2 && y >= y1 && y <= y2)
  14. return true;
  15.  
  16. return false;
  17. }
  18. }
  19.  
  20. class Program
  21. {
  22. public static ArrayList Shapes = new ArrayList();
  23.  
  24. static void Main(string[] args)
  25. {
  26. int x, y;
  27.  
  28. GetShapes();
  29.  
  30. if (Shapes.Count > 0)
  31. while (GetXY(out x, out y) == true)
  32. for (int n = (Shapes.Count - 1); n >= 0; n--)
  33. if (((Shape)Shapes[n]).IsInside(x, y) == true)
  34. {
  35. Console.WriteLine("({0}, {1}) Exist in Shape: {2}", x, y, ((Shape)Shapes[n]).Shapename);
  36. break;
  37. }
  38. }
  39.  
  40. private static void GetShapes()
  41. {
  42. string sName = "";
  43.  
  44. Console.WriteLine("nEnter Shapes... ");
  45. do
  46. {
  47. Console.Write("nEnter name: ");
  48. sName = Console.ReadLine();
  49. if (sName.Length > 0)
  50. {
  51. Shape shape = new Shape();
  52.  
  53. shape.Shapename = sName;
  54.  
  55. Console.Write("x1: ");
  56. shape.x1 = Convert.ToInt32(Console.ReadLine());
  57. Console.Write("y1: ");
  58. shape.y1 = Convert.ToInt32(Console.ReadLine());
  59. Console.Write("x2: ");
  60. shape.x2 = Convert.ToInt32(Console.ReadLine());
  61. Console.Write("y2: ");
  62. shape.y2 = Convert.ToInt32(Console.ReadLine());
  63.  
  64. Shapes.Add(shape);
  65. }
  66. else
  67. break;
  68. }
  69. while (sName.Length > 0);
  70. }
  71.  
  72. private static bool GetXY(out int x, out int y)
  73. {
  74. Console.WriteLine("nCoordinates... ");
  75. Console.Write("Enter x: ");
  76. x = Convert.ToInt32(Console.ReadLine());
  77. Console.Write("Enter y: ");
  78. y = Convert.ToInt32(Console.ReadLine());
  79.  
  80. if (x >= 0 && y >= 0)
  81. return true;
  82. return false;
  83. }
  84. }
  85. }
  86.  

وحيث أن #C تستخدم Short Path فالكود

انسخ الكود
  1. public bool IsInside(int x, int y)
  2. {
  3. if (x >= x1 && x <= x2 && y >= y1 && y <= y2)
  4. return true;
  5.  
  6. return false;
  7. }
  8.  

يتماثل اداءة مع الكود
انسخ الكود
  1. public bool IsInside(int x, int y)
  2. {
  3. if (x >= x1)
  4. if (x <= x2)
  5. if (y >= y1)
  6. if (y <= y2)
  7. return true;
  8.  
  9. return false;
  10. }
  11.  

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

شكرا أخ دحدوح على الكود وعلى توضيح الكود ل IsInShape .. طريقتك هي نفسها طريقة فهد في الكود المطلوب كتابته وهو Select ..

ولكن هل يوجد طريقة أسرع .. الخوارزميات التي كتبتوها هي O(N) .. يجب أن يكون هناك افضل من هذا ..

مساعدة : فكرو بتوزع الأشكال على لوحة الرسم ومواضعها وكيف يمكن تصميم data structure مناسب لها :)

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

الحلول ممكن أن تكون بأي لغة سي ، سي++، سي# ، psuedo code ، ...

سأختار الـ ... :lol:

فكرت -ويحتمل الخطأ بنسبه كبيييييييييره- أن ننشئ Binary Search Tree ، تحتوي على مؤشر لعقده باليمين واليسار ومؤشر للشكل Shape ،ومعروف أن العقده التي في اليسار تحمل قيمه أقل من الأب ، والعقد التي في اليمين تحمل عقده أكبر ..

class Node
{
public :
Shape* sp;
Node* leftNode;
Node* rightNode;
};

الفكره تكون كالتالي :

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

insert(int id,Shape* s);

الأن عند الضغط بالماوس نستطيع الحصول على الشكل الحالي وذلك بالبحث في الشجره عن الid وسيرجع بسرعه كبيره جدا (تقريبا شجره البحث الثنائيه يكون لها تعقيد O(log N) )

المشكله الأن في نوعيه هاid كيف يمكن أختياره ؟

يمكن أن نجمع أحد الأبعاد في الشكل ، يعني لو لدى البعد : 10.10.100.100 أجمع 10+100 ويصبح لدى 110 .

وهكذا أدخل هذا الشكل في الشجره بالرقم 110 (ويكون هو root) .

أيضا :

200.200.250.250

يكون الId هو 450 وسوف يكون في الجهه اليمني من الشجره ..

الأن في حال ضغط المستخدم في المكان 50.50 ، أجمع الرقمين ويخرج 100 ، وبالتالي البحث سوف يكون مقتصر في الجهه اليسري من الشجره .. واذا ضغط المستخدم على 150.150 يكون 300 وبالتالي البحث في الجهه اليمني ..

وهنا في حال كان شكلين فوق بعض سوف يخرج الشكل الأول :) لأنه الأول في الشجره ..

أخيرا المعذره على هذه الفكره ، ربما تكون بعييييييده جدا عن ما تريد ، لكن حبيت المشاركه :) .

وحمد لله على سلامتك أخ هاني الأتاسي .. وبراحه علينا ، اذا كان هذا أول سؤال ترحيبي كده الباقي بيكون كيف :( ..

بالتوفيق ،

تم تعديل بواسطه Wajdy Essam
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

عجبني متل ما بقولو تفكيرك خارج الصندوق :)

فكرتك قريبة من الحل بس فيها مشكلة .. الاحداثيات 10,100 غير 100,10 وبالتالي وضعها في الشجرة لا يكون بشكل صحيح ..

المفروض يمكنك استخدام احداثيات x و y على حدا في الشجرة من غير الجمع .. كيف يمكن هذا؟ الأسهل فكر كيف يمكن ان تستخدم x فقط ومن بعدها كيف تستفيد من y ..

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أنا كنت قاصد أن 10.10.100.100 وهي تمثل x1,y1,x2,y2 وأقوم جمع x1+y2 ...

وممكن أيضا أن يكون الid اللى تكلمت عنه هو القيمه الكبيره من هذه الأحداث ، وبالتالي لو المستخدم دق على 20.50 (ناخذ القيمه الكبيره هنا) ونبحث في جهه الشمال ..

لكن يبدوا من حديثك أنك تريد اختبار الx,y مع بعض ،،بالتالى ربما العقد يجب أن تحتوي على أكثر من متغير لحفظ القيمه يعني تصبح 2-3 Tree ..

على العموم نجرب ان شاء الله ونعود ،،

ولو في Hint بسيط بيكون أحسن :P

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

انسخ الكود
  1. using System;
  2. using System.Collections;
  3.  
  4. namespace ConsoleApplication1
  5. {
  6. class Shape
  7. {
  8. public string Shapename;
  9. public int x1, y1, x2, y2;
  10.  
  11. public bool IsInside(int x, int y)
  12. {
  13. if (x >= x1 && x <= x2 && y >= y1 && y <= y2)
  14. return true;
  15. return false;
  16. }
  17. }
  18.  
  19. class Screen
  20. {
  21. private const int xArr = 10, yArr = 10;
  22. private const int xLen = 128, yLen = 128;
  23. private Region[,] Regions = new Region[xArr, yArr];
  24. public static ArrayList Shapes = new ArrayList();
  25.  
  26. class Region
  27. {
  28. public int left, top, right, bottom;
  29. public ArrayList ShapeIndexs;
  30.  
  31. public bool Search(int x, int y)
  32. {
  33. if (ShapeIndexs.Count > 0)
  34. for (int n = (ShapeIndexs.Count - 1); n >= 0; n--)
  35. {
  36. Shape shape = ((Shape)Shapes[(int)ShapeIndexs[n]]);
  37. if (shape.IsInside(x, y) == true)
  38. {
  39. Console.WriteLine("({0}, {1}) Exist in Shape: {2}", x, y, shape.Shapename);
  40. return true;
  41. }
  42. }
  43.  
  44. Console.WriteLine("No shapes at ({0}, {1})", x, y);
  45. return false;
  46. }
  47. }
  48.  
  49. public Screen()
  50. {
  51. for (int x = 0; x < xArr; x++)
  52. for (int y = 0; y < yArr; y++)
  53. {
  54. Regions[x, y] = new Region();
  55. Regions[x, y].left = x * xLen;
  56. Regions[x, y].right = ((x + 1) * xLen) - 1;
  57. Regions[x, y].top = y * yLen;
  58. Regions[x, y].bottom = ((y + 1) * yLen) - 1;
  59.  
  60. Regions[x, y].ShapeIndexs = new ArrayList();
  61. }
  62. }
  63.  
  64. public void GetShapes()
  65. {
  66. string sName = "";
  67.  
  68. Console.WriteLine("nEnter Shapes... ");
  69. do
  70. {
  71. Console.Write("nEnter name: ");
  72. sName = Console.ReadLine();
  73. if (sName.Length > 0)
  74. {
  75. Shape shape = new Shape();
  76.  
  77. shape.Shapename = sName;
  78.  
  79. Console.Write("x1: ");
  80. shape.x1 = Convert.ToInt32(Console.ReadLine());
  81. Console.Write("y1: ");
  82. shape.y1 = Convert.ToInt32(Console.ReadLine());
  83. Console.Write("x2: ");
  84. shape.x2 = Convert.ToInt32(Console.ReadLine());
  85. Console.Write("y2: ");
  86. shape.y2 = Convert.ToInt32(Console.ReadLine());
  87.  
  88. InsertShape(ref shape);
  89. }
  90. else
  91. break;
  92. }
  93. while (sName.Length > 0);
  94. }
  95.  
  96. public bool InsertShape(ref Shape shape)
  97. {
  98. int x1 = shape.x1 / xLen;
  99. int y1 = shape.y1 / yLen;
  100. int x2 = shape.x2 / xLen;
  101. int y2 = shape.y2 / yLen;
  102. int ShapeIndex;
  103.  
  104. if (x2 < xArr && y2 < yArr)
  105. {
  106. ShapeIndex = Shapes.Add(shape);
  107.  
  108. for (int x = x1; x <= x2; x++)
  109. for (int y = y1; y <= y2; y++)
  110. {
  111. Regions[x, y].ShapeIndexs.Add(ShapeIndex);
  112. Console.WriteLine("Shape inserted at Regions[{0}, {1}]", x, y);
  113. }
  114. return true;
  115. }
  116. return false;
  117. }
  118.  
  119. public bool SearchShape(int xPos, int yPos)
  120. {
  121. int x = xPos / xLen;
  122. int y = yPos / yLen;
  123. if (x < xArr && y < yArr)
  124. {
  125. Console.WriteLine("Searching in Regions[{0}, {1}]", x, y);
  126. return Regions[x, y].Search(xPos, yPos);
  127. }
  128.  
  129. return false;
  130. }
  131. }
  132.  
  133. class Program
  134. {
  135. static void Main(string[] args)
  136. {
  137. int x, y;
  138. Screen scr = new Screen();
  139.  
  140. scr.GetShapes();
  141.  
  142. while (GetXY(out x, out y) == true)
  143. scr.SearchShape(x, y);
  144. }
  145.  
  146. static public bool GetXY(out int x, out int y)
  147. {
  148. Console.WriteLine("nCoordinates... ");
  149. Console.Write("Enter x: ");
  150. x = Convert.ToInt32(Console.ReadLine());
  151. Console.Write("Enter y: ");
  152. y = Convert.ToInt32(Console.ReadLine());
  153.  
  154. if (x >= 0 && y >= 0)
  155. return true;
  156. return false;
  157. }
  158. }
  159. }
  160.  
  161.  
  162.  
  163.  
  164.  

إذا كنت تريد أن يعرض لك أسماء جميع الاشكال أسفل النقطة مع الحفاظ على ترتيب ظهورهم على الشاشة (الأعلى أولاً، بأعتبار أن ما يدخل أولاً هو الاسفل وما يدخل بعده هو الأعلى)، أستبدل الكلاس Region الى:

انسخ الكود
  1. class Region
  2. {
  3. public int left, top, right, bottom;
  4. public ArrayList ShapeIndexs;
  5.  
  6. public bool Search(int x, int y)
  7. {
  8. bool bFound = false;
  9. if (ShapeIndexs.Count > 0)
  10. for (int n = (ShapeIndexs.Count - 1); n >= 0; n--)
  11. {
  12. Shape shape = ((Shape)Shapes[(int)ShapeIndexs[n]]);
  13. if (shape.IsInside(x, y) == true)
  14. {
  15. Console.WriteLine("({0}, {1}) Exist in Shape: {2}", x, y, shape.Sha
    pename);
  16. bFound = true;
  17. }
  18. }
  19.  
  20. if (bFound == false)
  21. Console.WriteLine("No shapes at ({0}, {1})", x, y);
  22. return bFound;
  23. }
  24. }
  25.  
  26.  
  27.  
  28.  

كلاس Shape تحتوى بيانات شكل واحد

الدالة IsInside: تحدد ما اذا كان الاحداثى داخل الشكل ام لا (t/f)

----------

كلاس Region تحتوى اشكال كل منطقة

الدالة Search تبحث عن النقطة (x, y) فى الاشكال داخل هذه المنطقة

المصفوفة ShapeIndexs وهى التى تحتفظ برقم (Index) الشكل فى داخل هذه المنطقة، وهذا الرقم يشير الى الشكل فى المصفوفة Shapes

left, top, right, bottom ، حدود المنطقة، يمكن الاستغناء عن (right, bottom) حالياً، ولكن يمكن ان يظهر لهم استخدام مستقبلى

----------

كلاس Screen تحتوى على الاشكال فى الشاشة، وتقسم الشاشة الى عدد من المناطق Regions فى بعدين

دالة Constractor يقوم بتجهيز المناطق

الدالة GetShapes استقبال بيانات شكل من لوحة المفاتيح، وارساله للدالة InsertShape

الدالة InsertShape تضيف الشكل الى المصفوفة Shapes وتحصل على رقمه Index، ثم تحدد المناطق التى يغطيها الشكل، ثم تضيف رقمه فى مصفوفة الرقام ShapeIndexs الخاصه بهذه المنطقة

عدد المناطق الافقية هو xArr وعرض كل منطقة هو xLen

عدد المناطق الرئيسة هو yArr وارتفاع كل منطقة هو yLen

المصفوفة ذات البعدين التى تحتفظ بهذه المناطق هى Regions

المصفوفة Shapes تحتوى على جميع الاشكال المدخلة (مصفوفة من كائنات كلاس Shape)

تم تعديل بواسطه دحدوح
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

دحدوح :) .. حلك كمان قريب .. بس في مشكلة أنا فرضا احب أضح آلاف الأشكال في قسم من الشاشاة .. وفرضا أيضا ممكن أعمل زوم على قسم معين وأرسم فيه كأنه الشاشة كلها ..

هل ممكن أن يكون تقسيمك للشاشة ديناميكي مثل binary search ...

أعتقد إذا لقيتو طريقة تدمجو طريقة بين حل دحدوح وحل وجدي يكون أفضل :)

تم تعديل بواسطه هاني الأتاسي
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

الحل بسيط اخي هاني

يمكنك وضع معرف لكل شكل

وكل ما أضفت شكل جديد يعيه رقم المعرف السابق +1

واذا تقاطع شكلان في نقطة تعطي الأولوية للذي معرفة رقم أعلى

وهذا بكون الموضوع أُغلق

والمخ شُغِّل

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .