संभव डुप्लिकेट:
Greatest linear dimension 2d set of pointsअंक के एक सेट को देखते हुए, मैं दो बिंदुओं को कैसे प्राप्त करूं जो एक-दूसरे से सबसे दूर हैं?
मैं प्रत्येक बिंदु के बीच की दूरी की गणना और सबसे बड़ा ले लेकिन यह है कि एक बहुत ही कारगर तरीका की तरह ध्वनि नहीं करता है यह करने के लिए जब वहाँ एक हैं सकता है बड़ी (> 1000) अंक की संख्या।
नोट: यह आईफोन के लिए है इसलिए मेरे पास प्रोसेसिंग पावर का टन नहीं है।
आप सेट के व्यास की गणना करने के लिए कह रहे हैं। मानक तकनीक को पहले उत्तल ढक्कन की गणना करना है, जो एक उत्तल बहुभुज के व्यास को खोजने में समस्या को कम करता है। यहां तक कि उस मामले में जहां आप किसी भी अंक को खत्म नहीं करते हैं, यह अतिरिक्त जानकारी समस्या को हल करने के लिए वास्तव में आवश्यक है। हालांकि, एक उत्तल बहुभुज का व्यास खोजना पूरी तरह से तुच्छ नहीं है; इस कार्य के लिए एल्गोरिदम के साथ कई प्रकाशित कागजात गलत हो गए हैं।
कार्य के लिए एक सही ओ (एन) एल्गोरिदम का fairly readable discussion है (जहां एन उत्तल में हल की संख्या है)।
इसके अलावा, ध्यान दें कि आईफोन नहीं है सीमित; पूरी तरह से बेवकूफ एल्गोरिदम का ध्यान से लिखित कार्यान्वयन एक दूसरे के दसवें से भी कम में 1000 अंक संभाल सकता है। बेशक, सही एल्गोरिदम का उपयोग करने से आपको बहुत तेजी से जाना होगा =)
निम्नतम x-coord के साथ बिंदु के साथ प्रारंभ करें। (इसे प्वाइंट एक्स पर कॉल करें) "सीमा बिंदु" बिंदु बिंदु के साथ शुरू होता है, और बिंदु के माध्यम से लंबवत रेखा का निर्माण, पॉइंटएक्स के बाईं ओर कोई अन्य बिंदु नहीं होना चाहिए) धीरे-धीरे लाइन को दक्षिणावर्त घुमाकर सीमा में अगला बिंदु ढूंढें (या counterclockwise) जब तक लाइन किसी अन्य बिंदु को छूता है, (नीचे देखें)। उस बिंदु को सेट में जोड़ें और अगले बिंदु को पाने के लिए उस अगले बिंदु के साथ दोहराएं, जब तक आप अंततः मूल बिंदु x पर वापस न आएं। आप एनपीडब्ल्यू के पास पूर्ण सेट की सीमा बनाने वाले बिंदुओं का एक सेट है। इस जोड़ी को अलग-अलग जोड़ी को खोजने के लिए इस कम सेट में प्रत्येक जोड़ी के बीच दूरी की तुलना करें।
"रेखा को घुमाएं" (प्रत्येक अनुक्रमिक सीमा बिंदु को खोजने के लिए), उस बिंदु को ले जाएं जो पिछली सीमा बिंदु के लिए उपयोग की जाने वाली रेखा के लिए लंबवत दिशा में "सबसे दूर" है, और अंतिम सीमा के बीच एक नई रेखा का निर्माण बिंदु और वह "अगला" बिंदु। फिर सत्यापित करें कि उस नई लाइन द्वारा बनाई गई नई लंबवत दिशा में कोई अन्य बिंदु नहीं है। यदि इस रेखा या आखिरी पंक्ति के लिए लंबवत विच्छेदन में कोई अन्य बिंदु "फर्थथ आउट" नहीं है, तो अगली सीमा बिंदु के लिए यह सही सीजेहॉइस है, यदि ऐसा कोई बिंदु है, तो उस पर स्विच करें और पुनः प्रयास करें।
क्रिस के समान टिप्पणी। यदि बाहरी बाउंड पर बहुत कम अंक नहीं हैं तो आप कुछ भी आसान नहीं बनाते हैं। –
यह जटिल हल की गणना करने के लिए एक महंगी तरीका की तरह लगता है, इसके बाद क्रिस बंच के बाकी उत्तर के बाद। – PanCrit
मुझे नहीं पता था कि इसके लिए एक तकनीकी शब्द था ... (उत्तल हल) लेकिन यह एक रबड़ बैंड सीमा है। मैं इसकी गणना करने के लिए अन्य एल्गोरिदम की जांच करूंगा ... बिंदुओं की संख्या के अनुसार, अंक के किसी भी यादृच्छिक संग्रह के लिए, सीमा में बिंदुओं की संख्या ओ (एन) अंकों की कुल संख्या से कम होनी चाहिए। (सीमा एक आयामी रेखा है जो 2-आयामी क्षेत्र से घिरा हुआ है।) –
क्यों न केवल convex hull अंकों की गणना करें? algorithm पर निर्भर करते हुए, यह O(n) या O(n log n) समय लेता है और सभी आंतरिक बिंदुओं को विचार से हटा देता है। फिर, सबसे दूर दूर दो खोजने के लिए केवल इन बाहरी बिंदुओं की जांच करें।
इससे चीजों को आसान नहीं बनाया जाता है। यदि उत्तल ढक्कन में बिंदुओं की मात्रा ओ (एन) है, तो जटिलता वही रहती है। –
बहुत सच है। लेकिन आशा है कि यदि 1000 अंक हैं, तो उनमें से कई उत्तल हल के अंदर होंगे। –
ग्रेट उत्तर। मैं यह कहने जा रहा था। उत्तल-टॉसेंट हेरिस्टिक के साथ शुरू करें ताकि उत्तल ढक्कन को ढूंढने से पहले जितना संभव हो सके उतने अंक फेंक दें। – Nosredna
these pages देखें (एक लिंक से जुड़े हुए पृष्ठों और "अगले" लिंक पर क्लिक करके पहुंचने योग्य पृष्ठ) सेट के उत्तल झुकाव के व्यास की गणना करने पर अंक के
मेरे त्वरित सारांश: उत्तल पतवार में अंकों की
यह ओ (एन) केवल उत्तल हल ढूंढने के बाद है - यदि आपको केवल अंक का एक सेट दिया गया है तो यह पहले उत्तल होल खोजने के लिए ओ (एन लॉग एन) हो सकता है। – ShreevatsaR
@ श्रीवत्सरा: बेशक। मेरा जवाब स्पष्ट रूप से कहता है "जहां एन उत्तल हॉल में अंक की संख्या है", जो स्पष्ट करता है कि आपको पहले उत्तल हल ढूंढने की आवश्यकता है। –
हां, शायद यह करता है। स्पष्टता पाठक की आंखों में है। :-) (प्रश्न में कार्य के लिए एल्गोरिदम स्पष्ट रूप से ओ (एन) नहीं है जहां n उत्तल उत्थान में बिंदुओं की संख्या है; जैसा कि आप कहते हैं, यह दूसरा भाग है।) वैसे भी, मैंने सोचा कि यह उल्लेखनीय है , केवल पूर्णता के लिए: लोग बाद में खोज इंजन के माध्यम से इन उत्तरों पर पहुंच सकते हैं, सावधानीपूर्वक पढ़ नहीं सकते हैं, और भ्रमित हो सकते हैं, आदि – ShreevatsaR