मैं सी

Question

मैं my gEDA fork पर काम कर रहा हूँ में एक स्थानिक सूचकांक की जरूरत है और एक वास्तविक स्थानिक सूचकांक के पक्ष में मौजूदा सरल टाइल आधारित प्रणाली से छुटकारा पाने के लिए चाहते हैं।

एक एल्गोरिदम जो प्रभावी रूप से अंक पाता है पर्याप्त नहीं है: मुझे गैर-शून्य सीमा वाले ऑब्जेक्ट्स ढूंढने की आवश्यकता है। आयताकार आय वाले ऑब्जेक्ट्स के संदर्भ में सोचें, जो इंडेक्स में मुझे आवश्यक विस्तार के स्तर को काफी हद तक कैप्चर करता है। एक खोज आयत को देखते हुए, मुझे उन सभी वस्तुओं को कुशलतापूर्वक खोजने में सक्षम होना चाहिए जिनके बाध्य आयताकार अंदर हैं, या जो छेद, खोज आयताकार है।

सूचकांक केवल पढ़ने के लिए नहीं किया जा सकता है: gschem एक योजनाबद्ध कैप्चर प्रोग्राम है, और इसका पूरा बिंदु योजनाबद्ध आरेख के आसपास चीजों को स्थानांतरित करना है। तो चीजें एक आदान-प्रदान होने जा रहे हैं। इसलिए जब मैं खोज से थोड़ा महंगा होने का सम्मिलन कर सकता हूं, तो यह भी अधिक महंगा नहीं हो सकता है, और हटाना भी संभव और उचित दोनों होना चाहिए। लेकिन सबसे महत्वपूर्ण आवश्यकता एसिम्प्टोटिक व्यवहार है: खोज ओ (लॉग एन) होना चाहिए यदि यह ओ (1) नहीं हो सकता है। सम्मिलन/हटाना अधिमानतः ओ (लॉग एन) होना चाहिए, लेकिन ओ (एन) ठीक रहेगा। मुझे निश्चित रूप से कुछ भी नहीं चाहिए> ओ (एन) (प्रति क्रिया; स्पष्ट रूप से ओ (एन लॉग एन) ऑल ऑब्जेक्ट ऑपरेशन के लिए अपेक्षित है)।

मेरे विकल्प क्या हैं? मुझे the various options का मूल्यांकन करने के लिए पर्याप्त चालाक नहीं लगता है। आदर्श रूप से कुछ सी लाइब्रेरी होगी जो मेरे लिए सभी चालाक सामान करेगी, लेकिन मैं यांत्रिक रूप से एक एल्गोरिदम लागू करूँगा, अगर मुझे करना है तो मैं पूरी तरह से समझ सकता हूं या नहीं। जीईडीए तरफ से ग्लिब का उपयोग करता है, अगर यह सिफारिश करने में मदद करता है।

फुटनोट:

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

एक वैध जवाब टाइलिंग सिस्टम के तत्वों को रखना होगा, लेकिन इसकी कमजोरियों को ठीक करने के लिए: पूरे स्थान को फैलाने के लिए इसे पढ़ाना, और आवश्यक होने पर उप-विभाजित करना। लेकिन मैं दूसरों को अपने दो सेंट जोड़ना चाहता हूं इससे पहले कि मैं स्वायत्तता से निर्णय लेता हूं कि यह सबसे अच्छा तरीका है।

Answer 1

अंक और रेखाओं के मिश्रण के लिए एक अच्छी डेटा संरचना एक आर-पेड़ या इसके डेरिवेटिव्स (जैसे आर *-ट्री या हिल्बर्ट आर-ट्री) होगी। यह देखते हुए कि आप यह सूचकांक गतिशील और क्रमिक होना चाहते हैं, मुझे लगता है कि SQLite's R*-Tree module का उपयोग करना एक उचित दृष्टिकोण होगा।

यदि आप सी ++, libspatialindex को सहन कर सकते हैं तो परिपक्व और लचीला आर-पेड़ कार्यान्वयन है जो गतिशील आवेषण/हटाना और क्रमबद्धता का समर्थन करता है।

Answer 2

यह एक क्वाड्री के लिए उपयुक्त एक आवेदन की तरह लगता है (मान लीजिए कि आप केवल 2 डी में रुचि रखते हैं।) quadtree पदानुक्रमित (खोज के लिए अच्छा है) और इसका स्थानिक संकल्प गतिशील है (उन क्षेत्रों में उच्च रिज़ॉल्यूशन की अनुमति है जो इसकी आवश्यकता है)।

मैं हमेशा अपने स्वयं के quadtrees उपलब्ध कराई गई है, लेकिन यहां एक पुस्तकालय है कि उचित प्रतीत होता है: http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

Answer 3

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

#include <iostream> 
#include <fstream> 
#include <map> 

using namespace std; 

typedef unsigned int UInt; 

class payLoad { 
public: 
    UInt starts; 
    UInt finishes; 
    bool isStart; 
    bool isFinish; 
    payLoad() 
    { 
     starts = 0; 
     finishes = 0; 
     isStart = false; 
     isFinish = false; 
    } 
}; 

typedef map<UInt,payLoad> ExtentMap; 

//============================================================================== 
class Extents 
{ 
    ExtentMap myExtentMap; 

public: 

    void ReadAndInsertExtents (const char* fileName) 
    { 
     UInt start, finish; 
     ExtentMap::iterator EMStart; 
     ExtentMap::iterator EMFinish; 

     ifstream efile (fileName); 
     cout << fileName << " filename" << endl; 

     while (!efile.eof()) { 
      efile >> start >> finish; 
      //cout << start << " start " << finish << " finish" << endl; 
      EMStart = myExtentMap.find(start); 
      if (EMStart==myExtentMap.end()) { 
       payLoad pay; 
       pay.isStart = true; 
       myExtentMap[start] = pay; 
       EMStart = myExtentMap.find(start); 
       } 
      EMFinish = myExtentMap.find(finish); 
      if (EMFinish==myExtentMap.end()) { 
       payLoad pay; 
       pay.isFinish = true; 
       myExtentMap[finish] = pay; 
       EMFinish = myExtentMap.find(finish); 
      } 
      EMStart->second.starts++; 
      EMFinish->second.finishes++; 
      EMStart->second.isStart = true; 
      EMFinish->second.isFinish = true; 

//   for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) 
//    cout << "| key " << EMStart->first << " count " << EMStart->second.value << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish << endl; 

     } 

     efile.close(); 

     UInt count = 0; 
     for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) 
     { 
       count += EMStart->second.starts - EMStart->second.finishes; 
       EMStart->second.starts = count + EMStart->second.finishes; 
     } 

//  for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) 
//   cout << "||| key " << EMStart->first << " count " << EMStart->second.starts << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish << endl; 

    } 

    void ReadAndCountNumbers (const char* fileName) 
    { 
     UInt number, count; 
     ExtentMap::iterator EMStart; 
     ExtentMap::iterator EMTemp; 

     if (myExtentMap.empty()) return; 

     ifstream nfile (fileName); 
     cout << fileName << " filename" << endl; 

     while (!nfile.eof()) 
     { 
      count = 0; 
      nfile >> number; 
      //cout << number << " number "; 

      EMStart = myExtentMap.find(number); 
      EMTemp = myExtentMap.end(); 

      if (EMStart==myExtentMap.end()) {   // if we don't find the number then create one so we can find the nearest number. 
       payLoad pay; 
       myExtentMap[ number ] = pay; 
       EMStart = EMTemp = myExtentMap.find(number); 
       if ((EMStart!=myExtentMap.begin()) && (!EMStart->second.isStart)) 
       { 
        EMStart--; 
       } 
      } 

      if (EMStart->first < number) { 
       while (!EMStart->second.isFinish) { 
        //cout << "stepped through looking for end - key" << EMStart->first << endl; 
        EMStart++; 
        } 
       if (EMStart->first >= number) { 
        count = EMStart->second.starts; 
        //cout << "found " << count << endl; 
        } 
      } 
      else if (EMStart->first==number) { 
       count = EMStart->second.starts; 
       } 

      cout << count << endl; 

      //cout << "| count " << count << " key " << EMStart->first << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish<< " V " << EMStart->second.value << endl; 

      if (EMTemp != myExtentMap.end()) 
      { 
       myExtentMap.erase(EMTemp->first); 
      } 
     } 
     nfile.close();  
    } 

}; 

//============================================================================== 

int main (int argc, char* argv[]) { 
    Extents exts; 

    exts.ReadAndInsertExtents ("..//..//extents.txt"); 
    exts.ReadAndCountNumbers ("..//../numbers.txt"); 

    return 0; 
} 

एक्सेंट्स परीक्षण फ़ाइल 1 थी।के 5MB: की तरह

0 200000 
1 199999 
2 199998 
3 199997 
4 199996 
5 199995 
.... 
99995 100005 
99996 100004 
99997 100003 
99998 100002 
99999 100001 

संख्या फ़ाइल था:

102731 
104279 
109316 
104859 
102165 
105762 
101464 
100755 
101068 
108442 
107777 
101193 
104299 
107080 
100958 
..... 

भी डिस्क से दो फ़ाइलों को पढ़ने, विस्तार 1.5MB थे और संख्या 780k और मूल्यों और लुकअप की वास्तव में बड़ी संख्या में, इस थे एक सेकंड के एक अंश में चलाता है। अगर स्मृति में यह जल्दी बिजली होगी।

Answer 4

आपकी ज़रूरतें गेम और भौतिकी सिमुलेशन के लिए टक्कर पहचान एल्गोरिदम में उपयोग की जाने वाली चीज़ों के समान ही ध्वनि की तरह हैं। कई खुले स्रोत सी ++ पुस्तकालय हैं जो इसे 2-डी (Box2D) या 3-डी (Bullet physics) में संभालते हैं। यद्यपि आपका प्रश्न सी के लिए है, लेकिन आप उनके दस्तावेज और कार्यान्वयन उपयोगी पा सकते हैं।

आम तौर पर इस एक two phases में विभाजित है:

1. एक तेज व्यापक चरण है कि उनके अक्ष गठबंधन सीमांकन बॉक्स (AABB) द्वारा वस्तुओं का अनुमान लगाती है, और कहा कि स्पर्श AABBs या ओवरलैप के जोड़े के निर्धारित करता है।
2. एक धीमी संकीर्ण चरण जो वस्तुओं के जोड़े के लिए ज्यामितीय ओवरलैप के बिंदुओं की गणना करता है जिनके एएबीबी स्पर्श या ओवरलैप होते हैं।

भौतिकी इंजन तुलनात्मक वस्तुओं की जोड़ी को कम करने के लिए स्थानिक समेकन का भी उपयोग करते हैं, लेकिन यह अनुकूलन शायद आपके आवेदन में सहायता नहीं करेगा।

ब्रॉडफ़ेज आमतौर पर ओ (एन लॉग एन) एल्गोरिदम के साथ Sweep and prune के साथ कार्यान्वित किया जाता है। आप वर्तमान टाइल दृष्टिकोण (one of Nvidia's GPUGems इस संकर दृष्टिकोण का वर्णन करते हुए) के संयोजन के साथ इसका उपयोग करके इसे तेज करने में सक्षम हो सकते हैं। संकीर्ण चरण प्रत्येक जोड़ी के लिए काफी महंगा है, और आपकी आवश्यकताओं के लिए अधिक हो सकता है। GJK algorithm अक्सर इस चरण में उत्तल वस्तुओं के लिए उपयोग किया जाता है, हालांकि अधिक विशिष्ट मामलों (जैसे: बॉक्स/सर्कल और बॉक्स/गोलाकार टकराव) के लिए तेज़ एल्गोरिदम मौजूद हैं।