तेजी से ज्यामितीय निकटता

Question

मेरे पास 3 अंक (ए, बी और एक्स) और एक दूरी (डी) है। मुझे एक ऐसा फ़ंक्शन बनाना होगा जो परीक्षण करता है कि यदि बिंदु एक्स रेखा खंड एबी पर किसी बिंदु पर दूरी डी से करीब है।

सवाल सबसे पहले है, मेरा समाधान सही है और फिर बेहतर (तेज़) समाधान के साथ आना है।

मेरी पहली पास के रूप में

AX = X-A 
BX = X-B 
AB = A-B 

    // closer than d to A (done squared to avoid needing to compute the sqrt in mag) 
If d^2 > AX.mag^2 return true 

    // closer than d to B 
If d^2 > BX.mag^2 return true 

    // "beyond" B 
If (dot(BX,AB) < 0) return false 

    // "beyond" A 
If (dot(AX,AB) > 0) return false 

    // find component of BX perpendicular to AB 
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 < d^2 

इस प्रकार है इस कोड को पी के एक बड़े सेट और सभी पी कि पास खोजने के इरादे से ए/बी/डी तीनो के एक बड़े सेट के लिए रन किया जा रहा है खत्म हो जाएगा कम से कम एक ए/बी/डी के लिए मुझे संदेह है कि उस पर आधारित कुल लागत को कम करने का एक तरीका है लेकिन मैंने अभी तक उसमें ध्यान नहीं दिया है।

(BTW:। मुझे पता है कि कुछ पुनर्व्यवस्था, कुछ अस्थायी मूल्यों और कुछ बीजीय पहचान से ऊपर की लागत कम हो सकता है कर रहा हूँ मैं सिर्फ उन्हें स्पष्टता के लिए छोड़े गए।)

---

संपादित करें: यह एक है 2 डी समस्या (लेकिन समाधान जो 3 डी को सामान्यीकृत करता है

संपादित करें: आगे प्रतिबिंब पर, मुझे उम्मीद है कि हिट दर लगभग 50% हो। एक्स पॉइंट को घोंसले पदानुक्रम में बनाया जा सकता है, इसलिए मैं सक्षम होने की उम्मीद करता हूं बड़ी सबट्री को सभी पास और सभी असफल होने के रूप में प्रक्षेपित करने के लिए। ए/बी/डी ट्रिपलेट्स को सीमित करने से अधिक tr ick।

संपादित करें: डी एबी के रूप में परिमाण के समान क्रम में है।

---

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

• पहले Artelius 'सा, पूर्व cacluate एक मैट्रिक्स एबी केंद्रित करेंगे कि मूल खाया और X- अक्ष के साथ गठबंधन किया। (2 कहते हैं, 4 muls और 2 कहते हैं)
• यह सब गुना 1 वृत्त का चतुर्थ भाग में (2 पेट) एक्स & में
• पैमाने Y एक इकाई वर्ग में क्षेत्र के मध्य भाग बनाने के लिए (2 mul)
• परीक्षण करता है, तो मुद्दा यह है कि वर्ग (2 परीक्षण) में है, इसलिए छोड़ दी है
• परीक्षण अंत टोपी (बगैर माप मूल्यों
  • एक्स में अनुवाद मूल (1 जोड़ने पर अंत जगह के लिए वापस जाओ)
  • वर्ग और जोड़ें (2 मिली, 1 जोड़ें)
  • ^2 (1 सीएमपी)

घ की तुलना मैं काफी यकीन है कि यह मेरी समाधान धड़कता हूँ।

(यदि कुछ भी नहीं बेहतर सोने साथ आता है Artelius "पुरस्कार" हो जाता है :)

Answer 1

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

trans = - ((A + B)/2)  // translate midpoint of AB to origin 

rot.col1 = AB/AB.mag   // unit vector in AB direction 

         0 -1  
rot.col2 = rot.col1 * ( ) // unit vector perp to AB 
         1 0 

rot = rot.inverse()   // but it needs to be done in reverse 

तो फिर तुम बस प्रत्येक एक्स लेने के लिए और rot * (X + trans) कार्य करें:

मुझे लगता है कि इस मैट्रिक्स के निर्माण के लिए एक आसान तरीका है।

प्रश्न में क्षेत्र वास्तव में एक्स और वाई अक्ष दोनों में सममित है, इसलिए आप एक्स समन्वय, और वाई समन्वय का पूर्ण मूल्य ले सकते हैं।

तो फिर तुम सिर्फ जांच करने की आवश्यकता:

y < d && x < AB.mag/2   //"along" the line segment 
|| (x - AB.mag/2)^2 + y^2 < d^2 // the "end cap". 

आप किसी अन्य चाल कर सकते हैं; मैट्रिक्स AB.mag/2 के कारक द्वारा स्केल कर सकता है (याद रखें कि मैट्रिस केवल एक बार प्रति (ए, बी) की गणना की जाती है जिसका अर्थ है कि यह बेहतर है कि उन्हें ढूंढना वास्तविक जांच से धीमा है)। इसका मतलब यह है कि आपका चेक हो जाता है:

y < 2*d/AB.mag && x < 1 
|| (x - 1)^2 + y^2 < (2*d/AB.mag)^2 

निरंतर 1 के साथ AB.mag/2 के दो उदाहरणों प्रतिस्थापित करने के बाद, यह एक स्पर्श तेजी से हो सकता है। और निश्चित रूप से आप 2*d/AB.mag और (2*d/AB.mag)^2 को भी सटीक कर सकते हैं।

चाहे यह अन्य विधियों की तुलना में तेज़ी से काम करेगा, यह आपके द्वारा दिए गए इनपुट पर निर्भर करता है। लेकिन यदि एबी की लंबाई डी की तुलना में लंबी है, तो मुझे लगता है कि यह आपके द्वारा पोस्ट की गई विधि से काफी तेज हो जाएगा।

Answer 2

hmmmmmmm .... हिट दर क्या है? बिंदु "एक्स" कितनी बार निकटता आवश्यकताओं को पूरा करता है?

मुझे लगता है कि आपका मौजूदा एल्गोरिदम अच्छा है, और कोई भी अतिरिक्त अनुकूलन वास्तविक डेटा से ट्यूनिंग से आएगा। उदाहरण के लिए, यदि "एक्स" बिंदु निकटतम परीक्षण 99% समय से मिलता है, तो मुझे लगता है कि आपकी अनुकूलन रणनीति काफी अलग होनी चाहिए, अगर यह केवल समय के परीक्षण को पास करती है।

---

संयोग से, जब आप बिंदु है जहां आप अंक के हजारों के साथ इस एल्गोरिथ्म चला रहे हैं करने के लिए मिलता है, तो आप एक K-आयामी ट्री (या KDTree) में सभी बिंदुओं का आयोजन करना चाहिए। यह "निकटतम पड़ोसी" की गणना को बहुत आसान बनाता है।

आपकी समस्या मूल निकटतम पड़ोसी से थोड़ा अधिक जटिल है (क्योंकि आप निकटता-से-एक-बिंदु के बजाय निकटता-से-एक-रेखा-सेगमेंट की जांच कर रहे हैं) लेकिन मुझे अभी भी लगता है कि केडीटी आसान हो

Answer 3

यह कोड कम से कम एक ए/बी/डी के लिए पास होने वाले सभी पी के खोजने के इरादे से पी के बड़े सेट और ए/बी/डी ट्रिपलेट्स का एक बड़ा सेट चलाने के लिए समाप्त हो जाएगा। संदेह है कि उस पर आधारित कुल लागत को कम करने का एक तरीका है लेकिन मैंने अभी तक इसमें ध्यान नहीं दिया है।

किसी दिए गए बिंदु एक्स के लिए डी ~ एबी के मामले में, आप पहले परीक्षण कर सकते हैं कि एक्स त्रिज्या डी और केंद्र एआई या बीआई के कई क्षेत्रों में से एक है। चित्र को देखो:

 ......  ..... 
    ........... ........... 
........................... 
.......A-------------B....... 
........................... 
    ........... ........... 
    .....   ..... 

पहले दो परीक्षणों

If d^2 > AX.mag^2 return true 
If d^2 > BX.mag^2 return true 

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

Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2

Answer 4

यदि मैं यह सही ढंग से पढ़ा है, तो इस रूप में इस्तेमाल किया क्लासिक रे/क्षेत्र चौराहे परीक्षण के रूप में लगभग एक ही है 3 डी रे-ट्रेसिंग में।

इस मामले में आपके पास त्रिज्या डी के स्थान एक्स पर एक क्षेत्र है, और आप यह पता लगाने की कोशिश कर रहे हैं कि रेखा एबी क्षेत्र को छेड़छाड़ करता है या नहीं। रे-ट्रेसिंग के साथ एक अंतर यह है कि इस मामले में आपको एक विशिष्ट लाइन एबी मिल गई है, जबकि रे-ट्रेसिंग रे में सामान्य रूप से origin + distance * direction के रूप में सामान्यीकृत किया जाता है, और आपको परवाह नहीं है कि अनंत रेखा AB+ के साथ कितनी दूर है । ।

अपने ही रे-ट्रेसर से छद्म कोड में() "रे-ट्रेसिंग के लिए एक परिचय" (ईडी Glassner में दिए गए एल्गोरिथ्म पर आधारित

Vector v = X - A 
Vector d = normalise(B - A) // unit direction vector of AB 
double b = dot(v, B - A) 
double discrim = b^2 - dot(v, v) + d^2 
if (discrim < 0) 
    return false   // definitely no intersection 

आप इस मिल गया है, तो अब तक, । फिर वहाँ कुछ मौका है कि अपने शर्त पूरी होती है तुम बस पता लगाएँ कि क्या चौराहे (रों) लाइन पर है अटल बिहारी लगाने की है:

discrim = sqrt(discrim) 
double t2 = b + discrim 
if (t2 <= 0) 
    return false    // intersection is before A 

double t1 = b - discrim 

result = (t1 < length(AB) || (t2 < length(AB)) 

Answer 5

यदि ए/बी/डी के सेट # बड़े हैं, और आप निश्चित रूप से 2 डी में हैं, तो R-trees (या उनके अष्टकोणीय समकक्ष) का उपयोग करने पर विचार करें जहां आर-पेड़ में प्रत्येक प्रविष्टि न्यूनतम बाध्यकारी बॉक्स है ए/बी/डी ट्रिपल। यह आपको ए/बी/डी ट्रिपल के बहुत से परीक्षण करने के लिए खत्म करने देगा & केवल अपनी सीपीयू पावर को उन लोगों पर केंद्रित करें जहां प्रत्येक बिंदु एक्स ए/बी/डी ट्रिपल के बाध्यकारी बक्से के भीतर है। फिर आपके द्वारा उल्लेख किए गए एक और विस्तृत परीक्षण करें।