علامات شيء جيد. مفيدة بكميات معقولة. عندما يكون هناك الكثير منهم ، تختفي الفوائد. ماذا تفعل إذا كنت تريد وضع علامة على نتائج البحث على الخريطة ، والتي بها عشرات الآلاف من الكائنات؟ سأخبرك في المقالة كيف نحل هذه المشكلة على بطاقة WebGL دون المساس بمظهرها وأدائها.

الخلفية

في عام 2016 ، أطلقت 2GIS مشروع WebGL الأول ، Floors: 3D floor floor of Buildings.

طوابق نوفوسيبيرسك مركز التسوق هالة

مباشرة بعد إصدار Floors ، بدأ فريقنا في تطوير محرك رسومي ثلاثي الأبعاد كامل على WebGL. تم تطوير المحرك بالتزامن مع الإصدار الجديد 2gis.ru وهو الآن في حالة تجريبية عامة .

مربع أحمر مرسوم على WebGL. تم دمج خطط البناء الآن مباشرةً في الخريطة.

مهمة تعميم التوقيع

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

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

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

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

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

جميع متاجر موسكو على الخريطة. لا توجد طريقة للقيام دون التعميم

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

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

النهج العام للتعميم

1. عرض كل علامة على مستوى الشاشة وحسابها ملزمة - المنطقة المستطيلة التي تشغلها على الشاشة.
2. فرز علامات حسب الأولوية.
3. قم بفحص كل علامة بالتتابع ووضعها على الشاشة إذا لم تتقاطع مع العلامات الأخرى الموضوعة أمامها.

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

تكمن المشكلة الرئيسية في الفقرة 3: يمكن أن يعتمد وقت حساب التعميم إلى حد كبير على كيفية تنفيذه.

للبحث عن التقاطعات بين العلامات ، نحتاج إلى بعض بنية البيانات التي:

1. يخزن حدود العلامات المضافة إلى الشاشة.
2. لديه طريقة insert(marker) لإضافة علامة إلى الشاشة.
3. لديها طريقة collides(marker) للتحقق من علامة التقاطع مع تلك المضافة بالفعل إلى الشاشة.

النظر في العديد من التطبيقات لهذا الهيكل. سيتم كتابة جميع الأمثلة الإضافية في TypeScript ، والتي نستخدمها في معظم مشاريعنا. في جميع الأمثلة ، سيتم تمثيل العلامات بواسطة كائنات من النموذج التالي:

 interface Marker { minX: number; maxX: number; minY: number; maxY: number; } 

جميع الأساليب التي تم النظر فيها ستكون تطبيقات للواجهة التالية:

 interface CollisionDetector { insert(item: Marker): void; collides(item: Marker): boolean; } 

لمقارنة الأداء ، سيتم قياس وقت تنفيذ الكود التالي:

 for (const marker of markers) { if (!impl.collides(marker)) { impl.insert(marker); } } 

سوف تحتوي مجموعة markers على 100،000 عنصر 30x50 موضوعة بشكل عشوائي على طائرة بحجم 1920 × 1080.

سيتم قياس الأداء على جهاز Macbook Air 2012.

كما يتم نشر الاختبارات وأمثلة التعليمات البرمجية الواردة في المقالة على جيثب .

تنفيذ ساذج

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

 class NaiveImpl implements CollisionDetector { private markers: Marker[]; constructor() { this.markers = []; } insert(marker: Marker): void { this.markers.push(marker); } collides(candidate: Marker): boolean { for (marker of this.markers) { if ( candidate.minX <= marker.maxX && candidate.minY <= marker.maxY && candidate.maxX >= marker.minX && candidate.maxY >= marker.minY ) { return true; } } return false; } } 

مدة حساب التعميم لـ 100،000 علامة: 420 مللي ثانية . كثير جدا حتى إذا تم حساب التعميم في أحد العاملين على الويب ولا يحجب الخيط الرئيسي ، فسيكون هذا التأخير ملحوظًا بالعين ، خاصة وأن هذه العملية يجب أن تتم بعد كل حركة بطاقة. علاوة على ذلك ، على الأجهزة المحمولة التي تحتوي على معالج ضعيف ، يمكن أن يكون التأخير أكبر.

تنفيذ R- شجرة

نظرًا للتطبيق الساذج في كل علامة يتم التحقق من تقاطعها مع جميع العلامات السابقة ، وفي أسوأ الحالات ، يكون تعقيد هذه الخوارزمية من الدرجة الثانية. يمكنك تحسينه عن طريق تطبيق بنية بيانات R-tree. كتطبيق لـ R-tree ، خذ مكتبة RBush :

 import * as rbush from 'rbush'; export class RTreeImpl implements CollisionDetector { private tree: rbush.RBush<Marker>; constructor() { this.tree = rbush(); } insert(marker: Marker): void { this.tree.insert(marker); } collides(candidate: Marker): boolean { return this.tree.collides(candidate); } } 

مدة حساب التعميم لـ 100،000 علامة: 173 مللي ثانية . أفضل بكثير. استخدمنا هذا النهج في الطوابق (تم ذكر ذلك في مقالتي السابقة ).

تصور لتخزين النقاط في شجرة R. يتيح لك التقسيم الهرمي للمستوى إلى مستطيلات تضييق نطاق البحث بسرعة وعدم الفرز بين جميع الكائنات

تنفيذ الاصطدام العازلة

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

عندما بدأنا في تطوير خريطة WebGL ، بدأنا في التفكير: هل لا يزال من الممكن تسريع التعميم. لقد قدّم لنا stellarator فكرة مثيرة للاهتمام: بدلاً من شجرة R ، استخدم مخزنًا مؤقتًا لتخزين حالة كل بكسل من الشاشة (مشغول أو غير مشغول). عند إدخال علامة على الشاشة ، "املأ" المكان المقابل في المخزن المؤقت ، وعند التحقق من إمكانية اللصق ، تحقق من قيم البيكسل في المنطقة المطلوبة.

 class CollisionBufferByteImpl implements CollisionDetector { private buffer: Uint8Array; private height: number; constructor(width: number, height: number) { this.buffer = new Uint8Array(width * height); this.height = height; } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { buffer[i * this.height + j] = 1; } } } collides(candidate: Marker): boolean { const { minX, minY, maxX, maxY } = candidate; for (let i = minX; i < maxX; i++) { for (let j = minY; j < maxY; j++) { if (buffer[i * this.height + j]) { return true; } } } return false; } } 

مدة حساب التعميم لـ 100،000 علامة: 46 مللي ثانية .

لماذا سريع جدا؟ يبدو هذا النهج ساذجًا للوهلة الأولى ، كما أن الحلقات المتداخلة في كلا الطريقتين لا تشبه الكود السريع. ومع ذلك ، إذا ألقيت نظرة فاحصة على الكود ، فستلاحظ أن وقت تنفيذ كلا الطريقتين لا يعتمد على العدد الإجمالي للعلامات. وبالتالي ، للحصول على حجم ثابت من علامات WxH ، نحصل على التعقيد O (W * H * n) ، أي خطي!

الأمثل نهج الاصطدام العازلة

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

 export class CollisionBufferBitImpl implements CollisionDetector { private width: number; private height: number; private buffer: Uint8Array; constructor(width: number, height: number) { this.width = Math.ceil(width / 8) * 8; this.height = height; this.buffer = new Uint8Array(this.width * this.height / 8); } insert(marker: Marker): void { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; if (start === end) { buffer[start] = buffer[start] | (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { buffer[start] = buffer[start] | (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { buffer[i] = 255; } buffer[end] = buffer[end] | (255 << (8 - (maxX & 7))); } } } collides(marker: Marker): boolean { const { minX, minY, maxX, maxY } = marker; const { width, buffer } = this; for (let j = minY; j < maxY; j++) { const start = j * width + minX >> 3; const end = j * width + maxX >> 3; let sum = 0; if (start === end) { sum = buffer[start] & (255 >> (minX & 7) & 255 << (8 - (maxX & 7))); } else { sum = buffer[start] & (255 >> (minX & 7)); for (let i = start + 1; i < end; i++) { sum = buffer[i] | sum; } sum = buffer[end] & (255 << (8 - (maxX & 7))) | sum; } if (sum !== 0) { return true; } } return false; } } 

مدة حساب التعميم لـ 100،000 علامة: 16 مللي ثانية . كما ترون ، فإن تعقيد المنطق يبرر نفسه ويسمح لنا بتسريع حساب التعميم بمقدار ثلاث مرات تقريبًا.

حدود الاصطدام العازلة

من المهم أن نفهم أن المخزن المؤقت للتصادم ليس بديلاً كاملاً لشجرة R. لديها ميزات أقل بكثير والمزيد من القيود:

1. لا يمكنك فهم ما تتقاطع به العلامة بالضبط. المخزن المؤقت فقط بتخزين البيانات حول أي بكسل مشغولة والتي ليست كذلك. لذلك ، من المستحيل تنفيذ عملية تقوم بإرجاع قائمة العلامات التي تتقاطع مع المحدد.
2. لا يمكن حذف العلامة المضافة سابقًا. لا يقوم المخزن المؤقت بتخزين البيانات على عدد العلامات بالبكسل المحدد. لذلك ، من المستحيل تطبيق عملية إزالة علامة من المخزن المؤقت بشكل صحيح.
3. حساسية عالية لحجم العناصر. إذا حاولت إضافة علامات تشغل الشاشة بأكملها إلى المخزن المؤقت للتصادم ، فإن الأداء سينخفض ​​بشكل كبير.
4. يعمل في منطقة محدودة. يتم تعيين حجم المخزن المؤقت عند إنشائه ، ومن المستحيل وضع علامة فيه تتجاوز هذا الحجم. لذلك ، عند استخدام هذا الأسلوب ، من الضروري تصفية العلامات التي لا تظهر على الشاشة يدويًا.

كل هذه القيود لم تتداخل مع حل مشكلة تعميم العلامة. الآن يتم استخدام هذه الطريقة بنجاح للعلامات في الإصدار التجريبي من 2gis.ru.

ومع ذلك ، لتعميم التوقيعات الرئيسية على الخريطة ، فإن المتطلبات أكثر تعقيدًا. على سبيل المثال ، بالنسبة لهم ، من الضروري التأكد من أن أيقونة POI لا يمكنها "قتل" توقيعها الخاص. نظرًا لأن المخزن المؤقت للتصادم لا يميز بالضبط ما حدث مع التقاطع ، فإنه لا يسمح بتنفيذ هذا المنطق. لذلك ، كان عليهم ترك حل مع RBush.

استنتاج

توضح المقالة المسار الذي سلكناه من أبسط الحلول إلى الحل المستخدم الآن.

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

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

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