मार्कर एक अच्छी चीज है। उचित मात्रा में उपयोगी। जब उनमें से बहुत सारे होते हैं, तो लाभ गायब हो जाते हैं। यदि आप मानचित्र पर खोज परिणामों को चिह्नित करना चाहते हैं, तो हजारों वस्तुओं का क्या करना है? लेख में मैं आपको बताऊंगा कि कैसे हम अपनी उपस्थिति और प्रदर्शन से समझौता किए बिना वेबजीएल कार्ड पर इस समस्या को हल करते हैं।

प्रागितिहास

2016 में, 2GIS ने अपनी पहली WebGL परियोजना, फर्श: इमारतों की 3 डी मंजिल योजना शुरू की।

नोवोसिबिर्स्क शॉपिंग सेंटर आभा के फर्श

फ़्लोरर्स की रिलीज़ के तुरंत बाद, हमारी टीम ने वेबगेल पर एक पूर्ण त्रि-आयामी कार्टोग्राफिक इंजन विकसित करना शुरू किया। इंजन को नए संस्करण 2gis.ru के साथ मिलकर विकसित किया गया था और अब वह सार्वजनिक बीटा स्थिति में है।

वेबजीएल पर लाल वर्ग खींचा गया। बिल्डिंग प्लान अब सीधे मैप में एकीकृत हो गए हैं।

हस्ताक्षर सामान्यीकरण कार्य

जो कोई भी अपना स्वयं का मानचित्र इंजन लिखना चाहता है, वह जल्द ही या बाद में मानचित्र पर हस्ताक्षर रखने की समस्या का सामना करेगा। मानचित्र पर बहुत सारी वस्तुएं हैं, और प्रत्येक को हस्ताक्षर करना असंभव है ताकि हस्ताक्षर ओवरलैप न हों।

यदि नोवोसिबिर्स्क में सभी वस्तुओं को एक बार में हस्ताक्षरित किया जाता है तो क्या होगा

इस समस्या को हल करने के लिए, हस्ताक्षर के सामान्यीकरण की आवश्यकता है। सामान्य अर्थों में सामान्यीकरण मानचित्र डेटा का परिवर्तन है ताकि यह छोटे पैमाने पर प्रदर्शन के लिए उपयुक्त हो। यह विभिन्न तरीकों से किया जा सकता है। हस्ताक्षर के लिए, आमतौर पर चयन विधि का उपयोग किया जाता है: कुल संख्या से, सबसे प्राथमिकता वाले हस्ताक्षर का एक सबसेट जो एक-दूसरे के साथ प्रतिच्छेद नहीं करते हैं, का चयन किया जाता है।

हस्ताक्षर की प्राथमिकता उसके प्रकार, साथ ही वर्तमान मानचित्र पैमाने द्वारा निर्धारित की जाती है। उदाहरण के लिए, छोटे पैमाने पर, शहरों और देशों के हस्ताक्षरों की आवश्यकता होती है, और बड़े पैमाने पर, सड़क हस्ताक्षर और मकान संख्या अधिक महत्वपूर्ण हो जाते हैं। अक्सर एक बस्ती के नाम की प्राथमिकता उसकी आबादी के आकार से निर्धारित होती है। यह जितना बड़ा है, हस्ताक्षर उतने ही महत्वपूर्ण हैं।

न केवल हस्ताक्षर के लिए, बल्कि मानचित्र पर खोज परिणामों को चिह्नित करने वाले मार्करों के लिए भी सामान्यीकरण आवश्यक है। उदाहरण के लिए, मॉस्को में "स्टोर" की खोज करते समय, 15,000 से अधिक परिणाम हैं। उन सभी को मानचित्र पर एक बार में चिह्नित करना स्पष्ट रूप से एक बुरा विचार है।

सभी मास्को नक्शे पर संग्रहीत करता है। सामान्यीकरण के बिना करने का कोई तरीका नहीं है

नक्शे के साथ किसी भी उपयोगकर्ता की बातचीत (चलती, ज़ूमिंग, मोड़ और झुकाव) स्क्रीन पर मार्करों की स्थिति में बदलाव की ओर ले जाती है, इसलिए आपको मक्खी पर सामान्यीकरण को पुन: गणना करने में सक्षम होने की आवश्यकता है। इसलिए, यह तेज होना चाहिए।

इस लेख में, मार्कर सामान्यीकरण के उदाहरण का उपयोग करते हुए, मैं इस समस्या को हल करने के लिए अलग-अलग तरीके दिखाऊंगा, जिन्हें हमारी परियोजनाओं में अलग-अलग समय पर उपयोग किया गया था।

सामान्यीकरण के लिए सामान्य दृष्टिकोण

स्क्रीन के विमान पर प्रत्येक मार्कर को प्रोजेक्ट करें और इसके लिए एक बाध्य गणना करें - आयताकार क्षेत्र जो इसे स्क्रीन पर रखता है।
मार्करों को प्राथमिकता से क्रमबद्ध करें।
क्रमिक रूप से प्रत्येक मार्कर की जांच करें और इसे स्क्रीन पर रखें, अगर यह उसके सामने रखे गए अन्य मार्करों के साथ प्रतिच्छेद नहीं करता है।

बिंदु 1 के साथ, सब कुछ स्पष्ट है - यह सिर्फ एक गणना है। आइटम 2 के साथ, हम भी भाग्यशाली थे: मार्करों की सूची जो बैकएंड से हमारे पास आती है, पहले से ही खोज एल्गोरिदम द्वारा प्राथमिकता के अनुसार क्रमबद्ध है। सबसे अधिक प्रासंगिक परिणाम जो उपयोगकर्ता के लिए सबसे अधिक रुचि रखते हैं वे परिणामों के शीर्ष पर हैं।

मुख्य समस्या पैराग्राफ 3 में है: सामान्यीकरण की गणना का समय बहुत हद तक इस बात पर निर्भर करता है कि इसे कैसे लागू किया जाता है।

मार्करों के बीच चौराहों की खोज करने के लिए, हमें कुछ डेटा संरचना की आवश्यकता है:

स्क्रीन पर जोड़े गए मार्करों की सीमा को संग्रहीत करता है।
स्क्रीन पर एक मार्कर जोड़ने के लिए एक insert(marker) विधि है।
स्क्रीन के साथ पहले से ही जोड़े गए लोगों के साथ चौराहे के लिए मार्कर की जांच करने के लिए यह एक collides(marker) विधि।

इस संरचना के कई कार्यान्वयनों पर विचार करें। सभी अन्य उदाहरण टाइपस्क्रिप्ट में लिखे जाएंगे, जिसका उपयोग हम अपनी अधिकांश परियोजनाओं में करते हैं। सभी उदाहरणों में, मार्करों को निम्नलिखित फ़ॉर्म की वस्तुओं द्वारा दर्शाया जाएगा:

 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 सरणी में 1920x1080 आकार के विमान में 100,000 30x50 तत्व बेतरतीब ढंग से रखे जाएंगे।

प्रदर्शन 2012 मैकबुक एयर पर मापा जाएगा।

लेख में दिए गए परीक्षण और कोड उदाहरण GitHub पर भी पोस्ट किए गए हैं ।

Naive कार्यान्वयन

शुरू करने के लिए, सबसे सरल विकल्प पर विचार करें, जब मार्कर को एक साधारण चक्र में दूसरों के साथ चौराहे के लिए जांचा जाता है।

 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- ट्री के कार्यान्वयन के रूप में, 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 एमएस । काफी बेहतर है। हमने फ्लोरर्स में इस दृष्टिकोण का उपयोग किया (यह मेरे पिछले लेख में उल्लेख किया गया था)।

आर-ट्री में अंकों के भंडारण का दृश्य। आयतों में विमान का पदानुक्रमित विभाजन आपको खोज क्षेत्र को जल्दी से संकीर्ण करने और सभी वस्तुओं के माध्यम से छाँटने की अनुमति नहीं देता है

टकराव बफर कार्यान्वयन

एक इमारत की एक योजना को चित्रित करने की तुलना में एक नक्शा खींचना बहुत अधिक जटिल कार्य है। यह भी सामान्यीकरण में ही प्रकट होता है। यहां तक कि दुनिया के सबसे बड़े शॉपिंग सेंटरों में, 1,000 संगठन शायद ही कभी एक ही मंजिल पर हों। इसी समय, एक बड़े शहर में एक सरल खोज क्वेरी हजारों परिणामों के दसियों को वापस कर सकती है।

जब हमने एक WebGL मैप विकसित करना शुरू किया, तो हमने सोचना शुरू किया: क्या अभी भी सामान्यीकरण को गति देना संभव है। एक दिलचस्प विचार हमारे लिए काम करने वाले तारकीय द्वारा पेश किया गया था: आर-ट्री के बजाय, एक बफर का उपयोग करें जिसमें स्क्रीन के प्रत्येक पिक्सेल की स्थिति को स्टोर करने के लिए (व्यस्त या व्यस्त नहीं)। स्क्रीन पर एक मार्कर डालते समय, बफर में संबंधित स्थान को "भरें", और चिपकाने की संभावना की जांच करते समय, आवश्यक क्षेत्र में पिक्सेल मूल्यों की जांच करें।

 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 मार्करों के एक निश्चित आकार के लिए, हम जटिलता ओ (डब्ल्यू * एच * एन) प्राप्त करते हैं, अर्थात् रैखिक!

अनुकूलित टकसाल बफर दृष्टिकोण

यदि आप सुनिश्चित करें कि एक पिक्सेल को एक बाइट द्वारा नहीं, बल्कि एक बिट से याद किया जाए, तो आप पहले के दृष्टिकोण को गति और कब्ज़ेदार मेमोरी में सुधार सकते हैं। इस अनुकूलन के बाद का कोड, हालांकि, काफी जटिल है और थोड़ा सा जादू के साथ बढ़ता है:

स्रोत कोड

 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 एमएस । जैसा कि आप देख सकते हैं, तर्क की जटिलता खुद को सही ठहराती है और हमें सामान्यीकरण की गणना में लगभग तीन गुना तेजी लाने की अनुमति देती है।

टकराव बफर सीमाएं

यह समझना महत्वपूर्ण है कि टक्कर बफर आर-ट्री के लिए पूर्ण प्रतिस्थापन नहीं है। इसमें बहुत कम विशेषताएं हैं और अधिक प्रतिबंध हैं:

आप समझ नहीं सकते कि वास्तव में मार्कर किसके साथ अंतर करता है। बफर केवल उन डेटा को संग्रहीत करता है जिनके बारे में पिक्सेल व्यस्त हैं और जो नहीं हैं। इसलिए, एक ऑपरेशन को लागू करना असंभव है जो मार्करों की एक सूची देता है जो दिए गए के साथ प्रतिच्छेद करता है।
पहले जोड़े गए मार्कर को हटा नहीं सकता। किसी दिए गए पिक्सेल में कितने मार्कर पर बफ़र डेटा संग्रहीत नहीं करता है। इसलिए, बफर से एक मार्कर को हटाने के संचालन को सही ढंग से लागू करना असंभव है।
तत्वों के आकार के लिए उच्च संवेदनशीलता। यदि आप मार्करों को जोड़ने की कोशिश करते हैं जो टकराव बफर में पूरी स्क्रीन पर कब्जा कर लेते हैं, तो प्रदर्शन नाटकीय रूप से गिर जाएगा।
एक सीमित क्षेत्र में काम करता है। इसे बनाते समय बफर का आकार निर्धारित किया जाता है, और इसमें एक मार्कर रखना असंभव है जो इस आकार से परे जाता है। इसलिए, इस दृष्टिकोण का उपयोग करते समय, मैन्युअल रूप से उन मार्करों को फ़िल्टर करना आवश्यक है जो स्क्रीन पर दिखाई नहीं देते हैं।

ये सभी प्रतिबंध मार्कर सामान्यीकरण की समस्या के समाधान में हस्तक्षेप नहीं करते थे। अब यह विधि 2gis.ru के बीटा संस्करण में मार्करों के लिए सफलतापूर्वक उपयोग की जाती है।

हालांकि, नक्शे पर मुख्य हस्ताक्षरों को सामान्य करने के लिए, आवश्यकताएं अधिक जटिल हैं। उदाहरण के लिए, उनके लिए यह सुनिश्चित करना आवश्यक है कि POI आइकन अपने स्वयं के हस्ताक्षर को "मार" नहीं सकता है। चूंकि टकराव बफर यह भेद नहीं करता है कि वास्तव में चौराहे के साथ क्या हुआ, यह इस तरह के तर्क को लागू करने की अनुमति नहीं देता है। इसलिए, उन्हें RBush के साथ एक समाधान छोड़ना पड़ा।

निष्कर्ष

लेख उस पथ को दिखाता है जो हम सबसे सरल समाधान से उपयोग किए गए अब तक गए थे।

आर-ट्री का उपयोग पहला महत्वपूर्ण कदम था जिसने हमें कई बार अनुभवहीन कार्यान्वयन में तेजी लाने की अनुमति दी। यह फर्श में बहुत अच्छा काम करता है, लेकिन वास्तव में हम इस डेटा संरचना की क्षमताओं का केवल एक छोटा सा अंश उपयोग करते हैं।

आर-ट्री को छोड़ दिया और इसे एक सरल द्वि-आयामी सरणी के साथ बदल दिया, जो वास्तव में हमें क्या चाहिए, और कुछ नहीं, हमें उत्पादकता में और भी अधिक वृद्धि हुई।

इस उदाहरण ने हमें दिखाया कि यह कितना महत्वपूर्ण है, उनमें से प्रत्येक की सीमाओं को समझने और महसूस करने के लिए, कई विकल्पों में से एक समस्या का समाधान चुनना। सीमाएं महत्वपूर्ण और उपयोगी हैं, और आपको उनसे डरना नहीं चाहिए: कुशलतापूर्वक अपने आप को कुछ तुच्छ लोगों तक सीमित करना, आपको बदले में भारी लाभ मिल सकते हैं जहां उन्हें वास्तव में जरूरत है। उदाहरण के लिए, किसी समस्या के समाधान को आसान बनाने के लिए, या कई बार उत्पादकता में सुधार के लिए, अपने आप को समस्याओं के एक पूरे वर्ग से बचाने के लिए, या, हमारे मामले में।

एक WebGL मानचित्र पर फास्ट मार्कर सामान्यीकरण