मेरे पास एक नक्शा है और उस पर बहुत सारे मार्कर प्रदर्शित हैं। कभी-कभी मार्कर एक-दूसरे के इतने करीब होते हैं कि वे ओवरलैप हो जाते हैं। इस स्थिति को मापने के लिए, मैंने इस स्थिति को मापने के लिए एक स्पाइडरफियर लाइब्रेरी लागू की है।
यह विचार है कि मार्कर को स्क्रीन पर (नीचे की ओर गणितीय रूप से) करीब-करीब इस तरह से समूहबद्ध किया जाए कि वे एक-दूसरे को प्रतिच्छेद न करें।
मार्करों को आयतों के रूप में प्रदर्शित किया जाता है।
कार्यान्वयन:
- मार्करों और मार्करों को ट्रेस करता है जो प्रतिच्छेद करते हैंप्रत्येक-दूसरे को ((minX + maxX) / 2, maxY) के केंद्र के साथ एक समूह में शामिल किया गया है और त्रिज्या एक-दूसरे को प्रतिच्छेद किए बिना परिधि पर मार्करों को प्रदर्शित करने के लिए बस पर्याप्त-पर्याप्त है
- जब अर्ध-मंडलियां होती हैं, जो एक-दूसरे को काटती हैं, तो हम उन्हें एक बड़े अर्ध-वृत्त में मिला देते हैं
- हम एक तुलनित्र द्वारा मार्करों को क्रमबद्ध करते हैं, "छोटे" मार्करों को उनके "अधिक" समकक्षों की तुलना में सर्कल की परिधि पर बाईं ओर रखते हैं।
- हम शीर्ष-आधे वृत्त पर मार्कर प्रदर्शित करते हैं, लेकिन हम उनके संशोधित स्थान से उनके वास्तविक स्थान तक एक पंक्ति प्रदर्शित करते हैं
अब तक सब ठीक है।
समस्या: ये रेखाएँ एक-दूसरे को बहुत बार काटती हैं और हमें एक तुलनित्र फ़ंक्शन की आवश्यकता होती है जिसके साथ मार्कर लाइन चौराहे की संख्या कम से कम हो जाती है।
कोशिश करता है:
P1.x <= P2.x => P1 <= P2
arctan ((P1.y - Cy) / (R * (P1.x - Cx))) <= arctan ((P2.y - Cy) / (R * (P2.x - Cx)) => 1 < = पी 2
मुझे दूसरी कोशिशों से बहुत उम्मीदें थीं, लेकिन थीयह स्वीकार करने के लिए कि यह एक अच्छा विचार नहीं है, चूंकि ट्रांसलेशन लाइन और वास्तविक स्थान के बीच की रेखा और सर्कल के केंद्र के बीच में आवश्यक रूप से मिलीभगत नहीं होती है, वास्तव में, उनका कोण काफी बड़ा हो सकता है यदि उनके वास्तविक स्थान पर कई मार्कर हों। इस उप-क्षेत्र को छोड़कर आधे-घेरे की सतह के बराबर, एक-दूसरे के बहुत करीब, इसलिए, यह चौराहों तक भी जाता है और यह पहली कोशिश की तुलना में बहुत अधिक जटिल है। मुझे विश्वास है कि जावास्क्रिप्ट है। Math.atan के साथ लागू किया गया है टेलर श्रृंखला या फोरियर श्रेणी, जिसमें पहले मामले में डेरिवेटिव शामिल हैऔर दूसरे मामले में अभिन्न। या, एक तीसरा दृष्टिकोण हो सकता है, जो अत्यधिक जटिल भी है। मैं इस तरह के अनुकूलन और सामान के बारे में सोचूंगा कि अगर यह दूसरा दृष्टिकोण चौराहों की संख्या को काफी कम कर देता, लेकिन चूंकि सुधार मुश्किल से अवलोकन योग्य है, अगर सभी पर, मैं पहले दृष्टिकोण पर लौट आया।
मैं निम्नलिखित दृष्टिकोण के बारे में सोच रहा हूं:
- परिधि पर मार्कर स्लॉट के स्थानों की गणना करें
- सभी मार्करों को उनके निकटतम संभावित स्लॉट में अनुवाद करने का प्रयास करें
- परस्पर विरोधी समूहों को ढूंढें और इष्टतम का पता लगाकर सभी संघर्षों को हल करें, जो कि सबसे छोटे कुल अनुवाद के साथ अनुवाद-सेट है
क्या यह विचार एक राज्य के लिए अग्रणी है जहां मकड़ी लाइन चौराहे की संख्या कम से कम है और यदि नहीं, तो मैं ऐसे चौराहों की संख्या को कैसे कम कर सकता हूं?
उत्तर:
उत्तर № 1 के लिए 1यह एक कठिन समस्या है, लंबे समय से अध्ययन किया गया है। इसे कभी-कभी कहा जाता है स्वचालित लेबल प्लेसमेंट। नीचे दिए गए काम साहित्य में उपलब्ध है की विशिष्ट है।
/>
/>
वैन क्रेवेल्ड, मार्क, टाइको स्ट्रीज और अलेक्जेंडर वोल्फ। "प्वाइंट सेट लेबलिंग विथ स्लाइडिंग लेबल।" कम्प्यूटेशनल ज्यामिति पर चौदहवें वार्षिक संगोष्ठी की कार्यवाही। एसीएम, 1998। एसीएम लिंक.