पॉलीगॉन जाल

Question

से अद्वितीय खोज किनारों के लिए एल्गोरिदम मैं एक अच्छा एल्गोरिदम खोज रहा हूं जो मुझे बहुभुज डेटा के सेट से अद्वितीय किनारों को दे सकता है। इस मामले में, बहुभुज दो सरणी द्वारा परिभाषित किया जाता है। एक सरणी प्रति पॉलीगॉन के अंक की संख्या है, और अन्य सरणी वर्टेक्स सूचकांक की एक सूची है।

मेरे पास एक संस्करण है जो काम कर रहा है, लेकिन 500,000 से अधिक polys तक पहुंचने पर प्रदर्शन धीमा हो जाता है। मेरा संस्करण प्रत्येक चेहरे पर चलता है और प्रत्येक किनारे के क्रमबद्ध शिखर को एक stl :: सेट में जोड़ता है। मेरा डेटा सेट मुख्य रूप से त्रिभुज और चौकोर polys होगा, और अधिकांश किनारों को साझा किया जाएगा।

क्या इसके लिए कोई स्मार्ट एल्गोरिदम है?

Answer 1

हाँ
डबल हैश मानचित्र का उपयोग करें।
प्रत्येक किनारे में दो इंडेक्स ए, बी हैं। आइए कहें कि ए> बी
पहला, शीर्ष स्तर हैश-नक्शा नक्शा ए एक अन्य हैश-मैप जो बदले में बी को कुछ मान देता है जो हर किनारे के बारे में जानकारी को दर्शाता है। (या सिर्फ एक बूल अगर आपको किनारों के लिए जानकारी रखने की आवश्यकता नहीं है)।
अनिवार्य रूप से यह हैश मैप्स से बना दो स्तर का पेड़ बनाता है।

इस संरचना में किनारे को देखने के लिए आप बड़ी अनुक्रमणिका लेते हैं, इसे शीर्ष स्तर पर देखते हैं और एक हैश मानचित्र के साथ समाप्त होते हैं। फिर छोटी अनुक्रमणिका लें और इसे इस दूसरे हैश मानचित्र में देखें।

Answer 2

बस स्पष्ट करने के लिए, आप चाहते हैं, इस तरह एक बहुभुज सूची के लिए:

A +-----+ B 
    \ |\ 
    \ 1 | \ 
    \ | \ 
     \ | 2 \ 
     \| \ 
     C +-----+ D 

फिर किनारों के बजाय इस तरह

:

A - B -+ 
B - C +- first polygon 
C - A -+ 

B - D -+ 
D - C +- second polygon 
C - B -+ 

तो आप डुप्लिकेट बी निकालना चाहते हैं - सी बनाम सी - बी एज और इसे साझा करें?

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

Answer 3

आप दोनों सही हैं। एक अच्छा हैशसेट का उपयोग करके आवश्यक स्तरों से परे प्रदर्शन को अच्छी तरह से प्राप्त किया गया है। मैं अपना खुद का छोटा हैश सेट रोलिंग समाप्त कर दिया।

किनारों की कुल संख्या जाल में अद्वितीय शीर्षकों की संख्या एन/2 और एन एन के बीच होगी। सभी साझा किनारे एन/2 होंगे, और सभी अद्वितीय किनारे एन होंगे। वहां से मैं uint64 के बफर आवंटित करता हूं और इन मानों में अपने सूचकांक पैक करता हूं। अद्वितीय तालिकाओं के एक छोटे से सेट का उपयोग करके मैं अद्वितीय किनारों को तेजी से पा सकता हूं!

Answer 4

सबसे पहले आपको यह सुनिश्चित करना होगा कि आपके शिखर अद्वितीय हैं। ऐसा है कि आप एक निश्चित स्थिति पर केवल एक किनारे चाहते हैं। तब मैं इस डेटा संरचना

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

एज शिखर सूचकांक कि क्रमबद्ध क्रम में बढ़त बनाने में शामिल है का उपयोग करें। इसलिए यदि नमूना एज सूचकांक संख्या 12 और 5 के साथ चरम से बना किनारा है, sampleEdge.first = 5 और sampleEdge।12

तो फिर तुम सिर्फ सभी किनारों के लिए

uniqueEdges[sampleEdge] = true;

कर सकते हैं। अद्वितीय एज सभी अद्वितीय किनारों को पकड़ेंगे।

Answer 5

चेहरे से किनारों को जल्दी से बनाने के उद्देश्य से ब्लेंडर में किनारे के किनारे का उपयोग करने के लिए सी सी कार्यान्वयन है, दूसरों के लिए स्वयं को बनाने के लिए कुछ संकेत दे सकते हैं।

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/edgehash.c

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_edgehash.h

यह BLI_mempool का उपयोग करता है, https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_mempool.h