'त्रिभुज-सूप' से अद्वितीय शिखर खोजें

Question

मैं दो पुस्तकालयों (ओपनकास्केड और डीडब्ल्यूएफ टूलकिट) के शीर्ष पर एक सीएडी फ़ाइल कनवर्टर बना रहा हूं।

को देखते हुए:

मैं त्रिकोणीय चेहरे की एक सूची के रूप में एक जाल जेनरेट किया है एक मॉडल अपने आवेदन के माध्यम से निर्माण के लिए फार्म

हालांकि, मेरे सवाल का plattform नास्तिक है। प्रत्येक त्रिभुज को तीन चरमों के माध्यम से परिभाषित किया जाता है, जिसमें तीन फ्लोट (x, y & z समन्वय) शामिल होते हैं। चूंकि त्रिकोण एक जाल बनाते हैं, इसलिए अधिकांश कोष्ठक एक त्रिकोण से अधिक साझा किए जाते हैं।

लक्ष्य:

मैं अद्वितीय कोने की सूची प्राप्त करने के लिए, और इस सूची में तीन सूचकांकों की tuples से मिलकर चेहरे की एक सरणी उत्पन्न करने के लिए की जरूरत है।

//step 1: build a list of unique vertices 
for each triangle 
    for each vertex in triangle 
     if not vertex in listOfVertices 
     Add vertex to listOfVertices 

//step 2: build a list of faces 
for each triangle 
    for each vertex in triangle 
     Get Vertex Index From listOfvertices 
     AddToMap(vertex Index, triangle) 

जब मैं एक कार्यान्वयन जो इस, चरण 1 (अद्वितीय कोने की सूची की पीढ़ी) करता है वास्तव में हे के क्रम में धीमी है (एन:

यह क्या मैं करना चाहता हूँ है !), चूंकि प्रत्येक चरम सूची की सूची में पहले से मौजूद सभी शीर्षकों से तुलना की जाती है। मैंने सोचा "अरे, std :: मैप का उपयोग करके मेरे शिखर के घटकों के एक हैशप को बनाने दें, जो चीजों को गति देना चाहिए!", केवल यह पता लगाने के लिए कि तीन फ़्लोटिंग पॉइंट मानों से एक अनूठी कुंजी उत्पन्न करना एक छोटा काम नहीं है।

यहां, स्टैक ओवरफ्लो के विशेषज्ञ खेल में आते हैं: मुझे किसी प्रकार का हैश-फ़ंक्शन चाहिए जो 3 फ्लोट्स पर काम करता है, या कोई अन्य फ़ंक्शन 3 डी-वर्टेक्स स्थिति से अद्वितीय मूल्य उत्पन्न करता है।

Answer 1

किसी सरणी में सभी कोष्ठक डंप करें, फिर unique(sort(array)) करें। यह ओ (के एन लॉग (एन) होना चाहिए), जहां के त्रिभुजों की औसत संख्या है जो वर्टेक्स साझा करते हैं, आमतौर पर के < 7।

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

distance(vertex1, vertex2) < threshold 

लेकिन यह प्रतीत हो रहा है चाहता हूँ OK।

Answer 2

तीन समाधान। निश्चित रूप से अन्य

1. हैश मानचित्र का उपयोग करें। यह केवल तभी काम करेगा यदि "समान" का अर्थ बिल्कुल
2. अंक
3. को विभाजित करने के लिए बाइनरी स्पेस विभाजन का उपयोग करें, अपने बिंदुओं को विभाजित करने के लिए नियमित ग्रिड का उपयोग करें।

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

Answer 3

हैश प्राप्त करने का सामान्य विचार prime के साथ एक फ्लोट के प्रत्येक बिटपटल को गुणा करना है और उन्हें एक साथ जोड़ना है। ऐसा ही कुछ:

unsigned int hash_point(float x, float y, float z) 
{ 
    unsigned int* px = (unsigned int*)&x; 
    unsigned int* py = (unsigned int*)&y; 
    unsigned int* pz = (unsigned int*)&z; 

    return (*px)*PRIME1 + (*py)*PRIME2 + (*pz)*PRIME3; 
} 

आपको लगता है कि sizeof (अहस्ताक्षरित int) को ध्यान देना चाहिए sizeof (नाव) यहाँ के बराबर माना जाता है। यहां नमूना केवल मुख्य विचार को चित्रित करने के लिए है, आपको इसे अपनी आवश्यकताओं के लिए ट्यून करना चाहिए।