वोक्सेल स्पेस पर नियमित अभिव्यक्ति

Question

क्या 3 डी वोक्सेल ग्रिड में एक वस्तु (उदाहरण के लिए पैटर्न मिलान करने वाले परिमित ऑटोमाटा के माध्यम से) का वर्णन करने का कोई तरीका है, वैसे ही हम रेगेक्सपी के साथ एक-आयामी स्ट्रिंग में पैटर्न का वर्णन कर सकते हैं?

मान लें कि मैं "ए" प्रकार के voxels का वर्णन करना चाहता हूं, जिसमें "बी" या "सी" प्रकार voxels से बना 3 और चौड़ाई 5 के साथ कम पहलू हैं, और इस वर्णन को उदाहरण के लिए voxel फ़ील्ड से मिलान करें पैटर्न। मैं सटीक मॉडल (जैसे-बॉयर-मूर-इन-3 डी) के लिए कुछ खोज कर सकता हूं लेकिन मुझे कुछ ऑब्जेक्ट्स के लिए चर आयाम निर्दिष्ट करने की आवश्यकता है (जैसे उपरोक्त क्यूबॉयड के लिए चर लंबाई)।

Answer 1

मुझे 3 डी या वोक्सल्स के बारे में बहुत कुछ पता नहीं है, लेकिन यदि आप अपने 3 डी स्पेस को मार्कअप का उपयोग करके एक-आयामी प्रतिनिधित्व में बदल सकते हैं, तो आप उस पर एक रेगेक्स का उपयोग कर सकते हैं।

सरलीकृत उदाहरण:

एक नीले चेहरा, लाल चेहरा, हरे चेहरे के साथ एक घन के लिए, और 3 अन्य हम परवाह नहीं है के बारे में:

<object> 
    <cube> 
     <faces> 
      <face orientation="up" color="blue"> 
       <border neighborOrient="west"> 
       <border neighborOrient="south"> 
      <face orientation="west" color="red"> 
      <face orientation="south" color="green"> 
      ... 
     </faces> 
    </cube> 
</object> 

आपका रेगुलर एक्सप्रेशन से चेहरे के लिए दिखाई दे सकता है एक ही घन के भीतर जो सीमा साझा करता है। रेगेक्स टेक्स्ट के साथ सबसे अच्छा काम करते हैं, इसलिए आपका पहला कदम टेक्स्ट पर "फ़्लैट" करने का तरीका ढूंढना चाहिए।

Answer 2

नियमित अभिव्यक्तियां सीमित (और अभी भी अनंत) भाषाओं के सेट वाक्य के वाक्यविन्यास को व्यक्त करने के लिए एक कॉम्पैक्ट तरीका हैं। नियमित अभिव्यक्तियों के साथ आपको यह बताने की आवश्यकता नहीं है कि अगले प्रतीक को कहां देखना है, क्योंकि यह ज्ञात है कि आप एक स्ट्रिंग पर काम कर रहे हैं और अपने पात्रों को भाषा के प्रतीकों के रूप में लेते हुए ... लेकिन 3 डी में क्या रास्ता तय करने की जरूरत है।

आप इसे 3 डी ट्यूरिंग मशीन के रूप में सोच सकते हैं, यह एक ट्यूरिंग मशीन है जिसमें एक आंतरिक राज्य है और 3 डी "टेप" से प्रतीकों को पढ़ सकता है, क्योंकि हम केवल सत्यापित कर रहे हैं कि हम टेप को लिखने की अनदेखी करते हैं। फिर, यह ट्यूरिंग मशीन 3 डी "टेप" उर्फ ​​3 डी वोक्सेल ग्रिड चलाएगी और वोक्सल्स को प्रतीकों के रूप में पढ़ेगी, प्रत्येक प्रतीक को पढ़ने के बाद ट्यूरिंग मशीन की आंतरिक स्थिति कुछ कानूनों के अनुसार बदल जाएगी। एक बार मशीन की अंतिम स्थिति पर निष्पादन खत्म होने के बाद आपको बताएगा कि यह एक मैच था या नहीं। अब वॉन न्यूमैन आर्किटेक्चर में ये कानून टेप से डेटा के रूप में जानकारी की व्याख्या हैं, लेकिन हम हार्वर्ड आर्किटेक्चर चाहते हैं, यह है कि निर्देश डेटा से अलग किए गए हैं। अब आप जो चाहते हैं वह ट्यूरिंग मशीन के लिए उन निर्देशों का वर्णन करने का एक तरीका है। [आप इसे लोगो के कछुए के रूप में सोच सकते हैं लेकिन 3 डी में]।

नियमित अभिव्यक्तियों की भावना के बाद हम वास्तविक संरचना जैसा दिखने वाली भाषा पसंद करेंगे। यदि हम यह आधारित पाठ बनाने के लिए यह एक वर्णनात्मक भाषा रहेगा (क्योंकि एक जरूरी एक नहीं की तुलना में अपने पसंदीदा ट्यूरिंग एक को पूरा बेहतर है), यह कहना उदाहरण के लिए (अंग्रेजी में) करना होगा:

There is a voxel type A and then moving (x1, y1, z1) from that there is a voxel of type B or C and then moving (x2, y2, z3) from that there is a voxel type D 

यह वही है का वर्णन करता है ट्यूरिंग मशीन एक बैकट्रैकिंग एल्गोरिदम के साथ खोज रही है जो सभी संभावित मैचों का परीक्षण करती है, यह अपेक्षित के रूप में काम करेगी।

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

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

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

एक्स अक्ष पर तीन voxels प्रकार ए की एक पंक्ति मिलान करना:

(A1X){3} 

यहाँ मैं आंदोलन "1X", कोष्ठक का उपयोग के साथ 'ए' से मेल खाते intercalate "(" और ")" समूह और कर्ली कोष्ठक के लिए "{" और "}" अंदाजा लगाना।

A1XA1XA1X 

पिछले "1X" परिणाम को प्रभावित नहीं करता, तो यह रूप में अच्छी तरह हो सकता है::

A1XA1XA 

और यह स्पष्ट रूप से कहते हैं: A प्रकार का वॉक्सेल, इस कदम का मिलान करें यह इस लिए unrolls एक्स पर 1 और एक प्रकार ए वोक्सेल से मेल खाता है, एक्स पर 1 को ले जाएं और एक प्रकार ए वोक्सेल से मेल खाता है।

मिलान एक्स अक्ष या Z अक्ष पर तीन voxels ग्रुप ए की एक पंक्ति:

(A1X){3}|(A1Z){3} 

वैकल्पिक:

(A1[X|Z]){3} 

यहाँ मैं कोष्ठकों का उपयोग "[" और "]" बनाने के लिए एक 'वर्ग', इसका स्थान यह बताता है कि यह दिशा के बारे में है और इसमें केवल संभावित धुरी शामिल है, इसमें भ्रमित न हों:

[(A1X)|(A1Z)]{3} 

यह तीन voxels प्रकार ए से मेल खाएगा लेकिन वे एक ही अक्ष पर नहीं हो सकते हैं, वे केवल संगत होने के साथ ही एक्स अक्ष या जेड अक्ष को पड़ोसी के साथ साझा करते हैं।

विमान एक्स से अधिक voxels प्रकार एक के एक 3x3 सेट मिलान, Y:

(((A1X){3})1Y){3} 

यह एक्स अक्ष पर एक लाइन और Y अक्ष एक और और इतने पर मैच के लिए अधिक चाल 1 मेल खाता है। इसका तात्पर्य है कि पुनरावृत्ति को समूहबद्ध करने के बाद "([(ए 1 एक्स)] {16})" हम पीछे हटते हैं जहां मैच निम्नलिखित कदम "1Y" निष्पादित करना शुरू कर देता है। उतारना करने के लिए यह होगा:

(A1XA1XA1X)1Y(A1XA1XA1X)1Y(A1XA1XA1X)1Y 

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

एक पर ध्यान नहीं दिया प्रकार का एक वॉक्सेल द्वारा अलग (किसी भी अक्ष से अधिक) voxels ग्रुप ए की जोड़ी मिलान: "।"

A1(X|Y|Z).1(X|Y|Z)A1(X|Y|Z) 

नियमित अभिव्यक्ति हम डॉट उपयोग से प्रभावित किसी भी प्रकार के voxel का प्रतिनिधित्व करने के लिए।

मैं अभी भी यह तय नहीं करता कि नकारात्मक अक्षों का उपयोग अन्य अक्षों के लिए अन्य अक्षरों का उपयोग करने के बजाय बेहतर है, तो मुझे लगता है कि संख्या 1 वैकल्पिक हो सकता है। नियमित अभिव्यक्तियों के वाक्यविन्यास के अन्य हिस्सों जैसे "+", "*", और "?" हालांकि अधिक सावधानी से बाहर होना चाहिए। किसी भी मात्रा के लिए "{" और "}" को लागू करना अच्छा हो सकता है जब तक कि साबित न हो कि कोई अस्पष्टता नहीं है।

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

(A1[X|Y|Z|W]){3} 

यह भी हो सकता है डॉट का उपयोग करने के लिए अच्छा "।"

(A1.){3} 

वहाँ जब निर्दिष्ट नहीं किया किसी भी दिशा संभालने के साथ एक समस्या है और वह यह है कि इस भाषा क्या एक दिशा है की पहचान करने और के अंदर स्थान पर आधारित वॉक्सेल प्रकार से उन्हें अलग करने के लिए परिभाषित किया गया है है: किसी भी दिशा का प्रतिनिधित्व करने के अभिव्यक्ति। तो "(ए 1 बी 1) {3}" मैप नहीं करेगा "(ए 1 बीबी।) {3}" क्योंकि यह "बी" को स्थानांतरित करने की दिशा के रूप में ले जाएगा, पीछे की संख्या से अर्थ का अनुमान लगाना संभव हो सकता है अंत, लेकिन मुझे नहीं पता कि यह अनौपचारिक होगा या नहीं।

अन्त में इस विमान एक्स में कोई मान्य tetris टुकड़े से मेल खाएगी, वाई voxels ग्रुप ए से बना:

(A1[X|Y]){4} 

अगर हम मान लेते हैं कि दुनिया केवल bidimensional है और है कि हम नंबर एक की अनदेखी करने के लिए अनुमति देते हैं, इससे यह कम हो जाता है:

(A.){4} 

और मैं इससे खुश हूं। फिर भी, आपको जटिल संरचनाओं के लिए एक अधिक जटिल, कम कॉम्पैक्ट और अधिक पठनीय नोटेशन पर विचार करना चाहिए।

और यह नियमित रूप से अभिव्यक्ति को दो, तीन या अधिक आयामों के सामान्यीकरण के लिए मेरा सिद्धांत है।

संपादित करें:

वॉक्सेल के प्रकार के जटिल है या अस्पष्टता मेरा प्रस्ताव है, कोणीय कोष्ठक "<" और ">" के साथ इसे लिखने के लिए तो उदाहरण के लिए आप कच्चे के हेक्स मान का उपयोग कर सकते हैं का कारण बनता है वोक्सेल डेटा:

(<0088FF>.){4}