पॉलीटॉप मॉडल: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{for|physical models of polyhedra|बहुफलकीय प्रारूप}}
{{for|physical models of polyhedra|बहुफलकीय प्रारूप}}


बहुफलकीय प्रारूप उन प्रोग्रामों के लिए एक गणितीय ढांचा है जो बड़ी संख्या में संचालन करते हैं  स्पष्ट रूप से गणना करने के लिए बहुत बड़े सुसम्बद्ध प्रतिनिधित्व की आवश्यकता होती है। नीड़ित प्रविष्ट पाश कार्यक्रमों मे यह विशिष्ट हैं, और यह प्रारूप का सबसे सरल उपयोग कार्यक्रमों में पाश नीड अनुकूलीकरण के लिए है। बहुफलकीय विधि नीड़ित प्रविष्ट पाश के भीतर प्रत्येक पाश पुनरावृत्ति को बहुफलकीय नामक गणितीय वस्तुओं के अंदर जाली बिंदुओं के रूप में मानती है,यह [[affine परिवर्तन|सजातीय परिवर्तन]] या अधिक सामान्य गैर- सजातीय मे रूपांतरित करती है जैसे कि बहुफलकीय पर [[लूप टाइलिंग|पाश टाइलिंग]], और फिर रूपांतरित बहुतलीय को समतुल्य में परिवर्तित करती है, लेकिन बहुफलकीय रेखाचित्रण के माध्यम से पाश नीड अनुकूलित लक्षित अनुकूलन लक्ष्य पर निर्भर करती है।   
बहुफलकीय प्रारूप उन कार्यक्रमों के लिए एक गणितीय ढांचा है जो बड़ी संख्या में संचालन करते हैं  स्पष्ट रूप से गणना करने के लिए बहुत बड़े सुसम्बद्ध प्रतिनिधित्व की आवश्यकता होती है। नीड़ित प्रविष्ट पाश कार्यक्रमों मे यह विशिष्ट हैं, और यह प्रारूप का सबसे सरल उपयोग कार्यक्रमों में पाश नीड अनुकूलीकरण के लिए है। बहुफलकीय विधि नीड़ित प्रविष्ट पाश के भीतर प्रत्येक पाश पुनरावृत्ति को बहुफलकीय नामक गणितीय वस्तुओं के अंदर जाली बिंदुओं के रूप में मानती है,यह [[affine परिवर्तन|सजातीय परिवर्तन]] या अधिक सामान्य गैर- सजातीय मे रूपांतरित करती है जैसे कि बहुफलकीय पर [[लूप टाइलिंग|पाश टाइलिंग]], और फिर रूपांतरित बहुतलीय को समतुल्य में परिवर्तित करती है, लेकिन बहुफलकीय रेखाचित्रण के माध्यम से पाश नीड अनुकूलित लक्षित अनुकूलन लक्ष्य पर निर्भर करती है।   


== सरल उदाहरण ==
== सरल उदाहरण ==
Line 7: Line 7:
[[सी (प्रोग्रामिंग भाषा)]] में लिखे गए निम्नलिखित उदाहरण पर विचार करें:
[[सी (प्रोग्रामिंग भाषा)]] में लिखे गए निम्नलिखित उदाहरण पर विचार करें:


<वाक्यविन्यास प्रकाश लैंग = सी>
  const int n = 100;
कॉन्स्टेंट इंट एन = 100;
इंट आई, जे, ए [एन] [एन];


के लिए (i = 1; i <n; i++) {
int i, j, a[n][n];
  के लिए (जे = 1; जे <(आई + 2) && जे <एन; जे ++) {
    ए [आई] [जे] = ए [आई - 1] [जे] + ए [आई] [जे - 1];
for (i = 1; i < n; i++) {
  }
  for (j = 1; j < (i + 2) && j < n; j++) {
}
</वाक्यविन्यास हाइलाइट>


इस कोड के साथ आवश्यक समस्या यह है कि आंतरिक पाश के प्रत्येक पुनरावृत्ति पर <code>a[i][j]</code> आवश्यकता है कि पिछले पुनरावृत्ति के परिणाम, <code>a[i][j - 1]</code>, पहले से ही उपलब्ध हो। इसलिए, इस कोड को समानांतर या [[पाइपलाइन (कंप्यूटिंग)]] नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है।
    a[i][j] = a[i - 1][j] + a[i][j - 1];
 
इस कोड के साथ आवश्यक समस्या यह है कि [i] [j] पर आंतरिक पाश के प्रत्येक पुनरावृत्ति के लिए आवश्यक है कि पिछले पुनरावृत्ति का परिणाम, [i] [j - 1], पहले से ही उपलब्ध हो। इसलिए, इस कूट को समानांतर या पाइपलाइन नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है।


एफ़िन परिवर्तन के साथ बहुफलकीय प्रारूप   का एक अनुप्रयोग <math>(i',\, j') = (i+j,\, j)</math> और सीमाओं में उपयुक्त परिवर्तन, नेस्टेड छोरों को ऊपर में बदल देगा:
सजातीय परिवर्तन के साथ बहुतलीय प्रारूप का एक अनुप्रयोग <math>(i',\, j') = (i+j,\, j)</math> और सीमाओं में उपयुक्त परिवर्तन, नीड़ित प्रविष्ट छोरों को ऊपर में बदल देगा:


<वाक्यविन्यास प्रकाश लैंग = सी>
a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];
[आई - जे] [जे] = [आई - जे - 1] [जे] + [आई - जे] [जे - 1];
</वाक्यविन्यास हाइलाइट>


इस स्थिति में, आंतरिक   पाश का कोई पुनरावृत्ति पिछले पुनरावृत्ति के परिणामों पर निर्भर नहीं करता है; पूरे आंतरिक   पाश को समानांतर में निष्पादित किया जा सकता है। (हालांकि, बाहरी   पाश का प्रत्येक पुनरावृत्ति पिछले पुनरावृत्तियों पर निर्भर करता है।)
इस स्थिति में, आंतरिक पाश का कोई पुनरावृत्ति पिछले पुनरावृत्ति के परिणामों पर निर्भर नहीं करता है; पूरे आंतरिक पाश को समानांतर में निष्पादित किया जा सकता है।,यद्यपि बाहरी पाश का प्रत्येक पुनरावृत्ति पिछले पुनरावृत्तियों पर निर्भर करता है।


== विस्तृत उदाहरण ==
== विस्तृत उदाहरण ==


[[File:Polytope model unskewed.svg|thumb|right|की निर्भरताएँ <code>src</code>,  पाश  अनुकूलीकरण से पहले # कॉमन  पाश  रूपांतरण। लाल बिंदु से मेल खाता है <code>src[1][0]</code>; गुलाबी बिंदु से मेल खाता है <code>src[2][2]</code>.]]निम्नलिखित सी (प्रोग्रामिंग भाषा) कोड फ़्लॉइड-स्टाइनबर्ग [[तड़पना]]िंग के समान त्रुटि-वितरण डिथरिंग के एक रूप को लागू करता है, लेकिन शैक्षणिक कारणों से संशोधित किया गया है। द्वि-आयामी सरणी <code>src</code> रोकना <code>h</code> की पंक्तियों <code>w</code> पिक्सेल, प्रत्येक पिक्सेल का ग्रे[[स्केल]] मान 0 और 255 सहित के बीच होता है। दिनचर्या समाप्त होने के बाद, आउटपुट array <code>dst</code> मान 0 या मान 255 के साथ केवल पिक्सेल शामिल होंगे। गणना के दौरान, प्रत्येक पिक्सेल की डाइथरिंग त्रुटि को वापस जोड़कर एकत्र किया जाता है <code>src</code> सरणी। (नोटिस जो <code>src</code> और <code>dst</code> गणना के दौरान दोनों पढ़े और लिखे जाते हैं; <code>src</code> केवल-पढ़ने के लिए नहीं है, और <code>dst</code> केवल लिखने के लिए नहीं है।)
[[File:Polytope model unskewed.svg|thumb|right|की निर्भरताएँ <code>src</code>,  पाश  अनुकूलीकरण से पहले # कॉमन  पाश  रूपांतरण। लाल बिंदु से मेल खाता है <code>src[1][0]</code>; गुलाबी बिंदु से मेल खाता है <code>src[2][2]</code>.]]निम्नलिखित सी कूट फ़्लॉइड-स्टाइनबर्ग कटौती के समान त्रुटि-वितरण कटौती  के एक रूप को लागू करता है, लेकिन शैक्षणिक कारणों के लिए संशोधित किया गया है। द्वि-आयामी सरणी src में w पिक्सेल की h पंक्तियाँ होती हैं, प्रत्येक पिक्सेल में 0 और 255 के मध्य ग्रेस्केल मान होता है। दिनचर्या समाप्त होने के बाद, आउटपुट त्रुटि dst में मात्र 0 मान या 255 मान वाले पिक्सेल होंगे। गणना के समय, प्रत्येक पिक्सेल की डाइटिंग त्रुटि को वापस src सरणी में जोड़कर एकत्र किया जाता है। ध्यान दें कि गणना के दौरान src और dst दोनों पढ़े और लिखे जाते हैं; src मात्र  पढ़ने के लिए नहीं है, और dst मात्र  लिखने के लिए नहीं है।


आंतरिक पाश का प्रत्येक पुनरावृत्ति मूल्यों को संशोधित करता है <code>src[i][j]</code> के मूल्यों पर आधारित है <code>src[i-1][j]</code>, <code>src[i][j-1]</code>, और <code>src[i+1][j-1]</code>. (समान निर्भरताएं लागू होती हैं <code>dst[i][j]</code>.  पाश  अनुकूलीकरण # कॉमन  पाश  रूपांतरण के प्रयोजनों के लिए, हम सोच सकते हैं <code>src[i][j]</code> और <code>dst[i][j]</code> एक ही तत्व के रूप में।) हम निर्भरताओं को चित्रित कर सकते हैं <code>src[i][j]</code> ग्राफिक रूप से, जैसा कि दाईं ओर आरेख में है।
आंतरिक पाश का प्रत्येक पुनरावृत्ति src[i][j] के मानों के आधार पर src[i-1][j], src[i][j-1], और src[i+1] के मानों को संशोधित करता है। जे -1](समान निर्भरताएँ dst[i][j] पर लागू होती हैं। पाश  विषमन के प्रयोजनों के लिए, हम src[i][j] और dst[i][j] को एक ही तत्व के रूप में सोच सकते हैं। हम उदाहरण दे सकते हैं src[i][j] रेखांकन की निर्भरता, जैसा कि दाईं ओर आरेख में है


<!-- This table nonsense makes the page look slightly better in Firefox on Windows XP. Is there a more portable and self-explanatory way to get the code and images not to overlap with each other? --~~~~ -->
<!-- This table nonsense makes the page look slightly better in Firefox on Windows XP. Is there a more portable and self-explanatory way to get the code and images not to overlap with each other? --~~~~ -->
Line 61: Line 57:
|}
|}


[[File:Polytope model skewed.svg|thumb|right|की निर्भरताएँ <code>src</code>, पाश तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला ... क्रम में संसाधित किया जाएगा।]]एफ़िन परिवर्तन करना <math>(p,\, t) = (i,\, 2j+i)</math> मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को  पाश ऑन करने के लिए फिर से लिख सकते हैं <code>p</code> और <code>t</code> के बजाय <code>i</code> और <code>j</code>, निम्नलिखित तिरछी दिनचर्या प्राप्त करना।
[[File:Polytope model skewed.svg|thumb|right|की निर्भरताएँ <code>src</code>, पाश तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला ... क्रम में संसाधित किया जाएगा।]]एफ़िन परिवर्तन करना <math>(p,\, t) = (i,\, 2j+i)</math> मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को  पाश ऑन करने के लिए फिर से लिख सकते हैं <code>p</code> और <code>t</code> के अतिरिक्त  <code>i</code> और <code>j</code>, निम्नलिखित तिरछी दिनचर्या प्राप्त करना।


<!-- Please don't break this code. Test before committing! -->
<!-- Please don't break this code. Test before committing! -->

Revision as of 14:32, 17 March 2023

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

सरल उदाहरण

सी (प्रोग्रामिंग भाषा) में लिखे गए निम्नलिखित उदाहरण पर विचार करें:

 const int n = 100;
int i, j, a[n][n];

for (i = 1; i < n; i++) {
  for (j = 1; j < (i + 2) && j < n; j++) {
    a[i][j] = a[i - 1][j] + a[i][j - 1];
 

इस कोड के साथ आवश्यक समस्या यह है कि [i] [j] पर आंतरिक पाश के प्रत्येक पुनरावृत्ति के लिए आवश्यक है कि पिछले पुनरावृत्ति का परिणाम, [i] [j - 1], पहले से ही उपलब्ध हो। इसलिए, इस कूट को समानांतर या पाइपलाइन नहीं किया जा सकता जैसा कि वर्तमान में लिखा गया है।

सजातीय परिवर्तन के साथ बहुतलीय प्रारूप का एक अनुप्रयोग और सीमाओं में उपयुक्त परिवर्तन, नीड़ित प्रविष्ट छोरों को ऊपर में बदल देगा:

a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];

इस स्थिति में, आंतरिक पाश का कोई पुनरावृत्ति पिछले पुनरावृत्ति के परिणामों पर निर्भर नहीं करता है; पूरे आंतरिक पाश को समानांतर में निष्पादित किया जा सकता है।,यद्यपि बाहरी पाश का प्रत्येक पुनरावृत्ति पिछले पुनरावृत्तियों पर निर्भर करता है।

विस्तृत उदाहरण

की निर्भरताएँ src, पाश अनुकूलीकरण से पहले # कॉमन पाश रूपांतरण। लाल बिंदु से मेल खाता है src[1][0]; गुलाबी बिंदु से मेल खाता है src[2][2].

निम्नलिखित सी कूट फ़्लॉइड-स्टाइनबर्ग कटौती के समान त्रुटि-वितरण कटौती के एक रूप को लागू करता है, लेकिन शैक्षणिक कारणों के लिए संशोधित किया गया है। द्वि-आयामी सरणी src में w पिक्सेल की h पंक्तियाँ होती हैं, प्रत्येक पिक्सेल में 0 और 255 के मध्य ग्रेस्केल मान होता है। दिनचर्या समाप्त होने के बाद, आउटपुट त्रुटि dst में मात्र 0 मान या 255 मान वाले पिक्सेल होंगे। गणना के समय, प्रत्येक पिक्सेल की डाइटिंग त्रुटि को वापस src सरणी में जोड़कर एकत्र किया जाता है। ध्यान दें कि गणना के दौरान src और dst दोनों पढ़े और लिखे जाते हैं; src मात्र पढ़ने के लिए नहीं है, और dst मात्र लिखने के लिए नहीं है।

आंतरिक पाश का प्रत्येक पुनरावृत्ति src[i][j] के मानों के आधार पर src[i-1][j], src[i][j-1], और src[i+1] के मानों को संशोधित करता है। जे -1]। (समान निर्भरताएँ dst[i][j] पर लागू होती हैं। पाश विषमन के प्रयोजनों के लिए, हम src[i][j] और dst[i][j] को एक ही तत्व के रूप में सोच सकते हैं। हम उदाहरण दे सकते हैं src[i][j] रेखांकन की निर्भरता, जैसा कि दाईं ओर आरेख में है

#define ERR(x, y) (dst[x][y] - src[x][y])

void dither(unsigned char** src, unsigned char** dst, int w, int h)
{
    int i, j;
    for (j = 0; j < h; ++j) {
        for (i = 0; i < w; ++i) {
            int v = src[i][j];
            if (i > 0)
                v -= ERR(i - 1, j) / 2;
            if (j > 0) {
                v -= ERR(i, j - 1) / 4;
                if (i < w - 1)
                    v -= ERR(i + 1, j - 1) / 4;
            }
            dst[i][j] = (v < 128) ? 0 : 255;
            src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255;
        }
    }
}
की निर्भरताएँ src, पाश तिरछा करने के बाद। सरणी तत्वों को ग्रे, लाल, हरा, नीला, पीला ... क्रम में संसाधित किया जाएगा।

एफ़िन परिवर्तन करना मूल निर्भरता आरेख पर हमें एक नया आरेख मिलता है, जो अगली छवि में दिखाया गया है। फिर हम कोड को पाश ऑन करने के लिए फिर से लिख सकते हैं p और t के अतिरिक्त i और j, निम्नलिखित तिरछी दिनचर्या प्राप्त करना।

 void dither_skewed(unsigned char **src, unsigned char **dst, int w, int h)  
 {
     int t, p;
     for (t = 0; t < (w + (2 * h)); ++t) {
         int pmin = max(t % 2, t - (2 * h) + 2);
         int pmax = min(t, w - 1);
         for (p = pmin; p <= pmax; p += 2) {
             int i = p;
             int j = (t - p) / 2;
             int v = src[i][j];
             if (i > 0)
               v -= ERR(i - 1, j) / 2;
             if (j > 0)
               v -= ERR(i, j - 1) / 4;
             if (j > 0 && i < w - 1)
               v -= ERR(i + 1, j - 1) / 4;
             dst[i][j] = (v < 128) ? 0 : 255;
             src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255;
         }
     }
 }


यह भी देखें

बाहरी लिंक और संदर्भ

श्रेणी:संकलक अनुकूलन श्रेणी:सूडोकोड के उदाहरण वाले लेख श्रेणी:उदाहरण सी कोड वाले लेख