किसी दिए गए सेट और उसके बाउंडिंग बॉक्स से सबसे दूर बिंदु को कैसे ढूंढें

Question

मेरे पास एक बाउंडिंग बॉक्स है, और इसके अंदर कई बिंदु हैं। मैं एक और बिंदु जोड़ना चाहता हूं जिसका स्थान पहले से जोड़े गए बिंदुओं से दूर है, साथ ही बॉक्स के किनारों से बहुत दूर है।

क्या इस तरह की चीज के लिए कोई आम समाधान है? धन्यवाद!

Answer 1

यहां थोड़ा Mathematica प्रोग्राम है।

हालांकि यह कोड की केवल दो पंक्तियां हैं (!) आपको शायद एक पारंपरिक भाषा में और साथ ही गणित पुस्तकालय में अधिकतम कार्यों को खोजने में सक्षम होना चाहिए।

मुझे लगता है कि आप गणित में धाराप्रवाह नहीं हैं, इसलिए मैं रेखा से लाइन समझाऊंगा और टिप्पणी करूंगा।

सबसे पहले हम {0,1} x {0,1} में 10 यादृच्छिक बिंदुओं के साथ एक टेबल बनाते हैं, और इसे पी नाम दें।

p = Table[{RandomReal[], RandomReal[]}, {10}]; 

अब हम अधिकतम करने के लिए एक समारोह बनाने के लिए:

f[x_, y_] = Min[ x^2, 
       y^2, 
       (1 - x)^2, 
       (1 - y)^2, 
       ((x - #[[1]])^2 + (y - #[[2]])^2) & /@ p]; 

हा! सिंटेक्स मुश्किल हो गया! आइए समझाएं:

फ़ंक्शन आपको उस बिंदु से {0,1} x {0,1} न्यूनतम दूरी किसी भी बिंदु के लिए हमारे सेट पी और किनारों पर देता है। पहले चार शब्द किनारों के लिए दूरी हैं और अंतिम (पढ़ने के लिए मुश्किल, मुझे पता है) एक सेट है जिसमें सभी बिंदुओं की दूरी होती है।

हम आगे क्या करेंगे को अधिकतम करने वाला यह कार्य, इसलिए हम उस बिंदु को प्राप्त करेंगे जहां अधिकतम हमारे लक्ष्यों के लिए न्यूनतम दूरी होगी।

लेकिन सबसे पहले f [] पर एक नज़र डालें। यदि आप इसे गंभीर रूप से देखते हैं, तो आप देखेंगे कि यह वास्तव में दूरी नहीं है, लेकिन दूरी वर्ग है। मैंने इसे परिभाषित किया, क्योंकि इस तरह फ़ंक्शन को अधिकतम करने के लिए बहुत आसान है और परिणाम समान हैं।

यह भी ध्यान दें कि f [] एक "सुंदर" फ़ंक्शन नहीं है।

कारण है कि आप एक अच्छा गणित पैकेज की आवश्यकता होगी अधिकतम ढूँढ़ी जा सकती है कि: यदि हम {0,1} में यह साजिश है, हम की तरह कुछ मिलता है।

मेथेमेटिका इस तरह के एक अच्छा पैकेज है, कि हम बात सीधा अधिकतम कर सकते हैं:

max = Maximize[{f[x, y], {0 <= x <= 1, 0 <= y <= 1}}, {x, y}]; 

और वह यह है। अधिकतम कार्य बिंदु को वापस करता है, और इसकी निकटतम सीमा/बिंदु तक वर्ग दूरी।

HTH! अगर आपको किसी अन्य भाषा में अनुवाद करने में मदद की ज़रूरत है, तो एक टिप्पणी छोड़ दें।

एक उम्मीदवार पैकेज DotNumerics

आप का पालन करना चाहिए है:

संपादित

हालांकि मैं एक सी # व्यक्ति नहीं हूँ, इसलिए और googling में संदर्भ के लिए देखने के बाद, इस के लिए आया था

file: \DotNumerics Samples\Samples\Optimization.cs 
Example header: 

    [Category("Constrained Minimization")] 
    [Title("Simplex method")] 
    [Description("The Nelder-Mead Simplex method. ")] 
    public void OptimizationSimplexConstrained() 

HTH: पैकेज में प्रदान की जाती उदाहरण का पालन करना!

Answer 2

आपके द्वारा हल की जा रही समस्या का नाम the largest empty sphere problem है।

इसे आसानी से विमान में ओ (एन^4) समय में हल किया जा सकता है। बस बिंदुओं के सभी ओ (एन^3) ट्रिपल पर विचार करें और उनके circumcenter की गणना करें। इन बिंदुओं में से एक आपका वांछित बिंदु है। (ठीक है, आपके मामले में, आपको अपने तीन बिंदुओं में से एक के रूप में "एक पक्ष" पर भी विचार करना होगा, इसलिए आपको न केवल circumcenters बल्कि कुछ और सामान्य बिंदु मिलते हैं, जैसे दो बिंदुओं और एक तरफ से समतुल्य।)

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