एक सरणी में निकटतम निर्देशांक ढूँढना?

Question

मैं दो ArrayList, डबल डेटा प्रकार, 1.latitudes 2. देशांतर, प्रत्येक 200 से अधिक तत्वों

मैं एक यादृच्छिक परीक्षण निर्देशांक देते हैं, का कहना है कि कहना है (1.33, 103.4), प्रारूप [अक्षांश है , देशांतर]

क्या निकटतम बिंदु, आसानी से ढूंढने के लिए कोई एल्गोरिदम है या क्या मुझे हर संभव बिंदु की गणना करने के लिए बलपूर्वक बल देना है, hypotenuse ढूंढना है, और फिर निकटतम बिंदु को वापस करने के लिए 200 से अधिक hypotenuses की तुलना करना है? धन्यवाद

Answer 1

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

1) मान लीजिए आपके पास दो क्रमबद्ध सरणियों देशांतर के लिहाज से और अक्षांश के लिहाज से

2) आप पहले एक खोज और दो पास के अंक

3 लगता है) तो फिर तुम एक दूसरे के खोज और दो अधिक अंक पाते हैं

4) अब आप दो से चार अंक से है (परिणाम एक दूसरे को काटना हो सकता है)

5) ये अंक गंतव्य बिंदु के चारों ओर एक वर्ग बनेगी

6) निकटतम बिंदु

Answer 2

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

फिर, दोनों बिंदुओं में सरणी के साथ खोज करें जब तक कि इन बिंदुओं की दूरी अब तक का सबसे अच्छा परिणाम से अधिक न हो। सबसे छोटा दूरी बिंदु जवाब है।

इसके परिणामस्वरूप पूरे सरणी को खोजना पड़ सकता है, और Branch and bound का एक रूप है जो समस्या की ज्यामिति से बाधित है। यदि अंक उस बिंदु के आसपास समान रूप से वितरित किए जाते हैं, जिसे आप खोज रहे हैं, तो स्कैन को कई परीक्षणों की आवश्यकता नहीं होगी।

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

Answer 3

यह सच नहीं है कि निकटतम लेट (या लंबा) मान लंबे (या लेट) अक्ष पर खोजने के लिए चुना जाना चाहिए, वास्तव में आप एक लेट (या लंबी) रेखा पर रह सकते हैं लेकिन लंबे समय तक दूर (या अक्षां) मूल्य

तो सबसे अच्छा तरीका है सब दूरी की गणना और उन्हें