सरलीकृत ब्रेसेनहम की लाइन एल्गोरिदम: यह * बिल्कुल * क्या करता है?

Question

Bresenham की लाइन एल्गोरिथ्म पर विकिपीडिया के लेख के आधार पर मैं क्रियान्वित किया है simplified version वहाँ वर्णित है, मेरे जावा कार्यान्वयन इस तरह दिखता है:

int dx = Math.abs(x2 - x1); 
int dy = Math.abs(y2 - y1); 

int sx = (x1 < x2) ? 1 : -1; 
int sy = (y1 < y2) ? 1 : -1; 

int err = dx - dy; 

while (true) { 
    framebuffer.setPixel(x1, y1, Vec3.one); 

    if (x1 == x2 && y1 == y2) { 
     break; 
    } 

    int e2 = 2 * err; 

    if (e2 > -dy) { 
     err = err - dy; 
     x1 = x1 + sx; 
    } 

    if (e2 < dx) { 
     err = err + dx; 
     y1 = y1 + sy; 
    } 
} 

अब मुझे समझ नहीं है कि err नियंत्रण x- अक्ष पर चरणों के बीच अनुपात की तुलना वाई-अक्ष पर कदम उठाने के लिए - लेकिन अब मुझे यह दस्तावेज करना है कि कोड क्या कर रहा है, मैं स्पष्ट रूप से व्यक्त करने में विफल रहता हूं, इसके लिए क्या है, और बिल्कुल if-statement हैं, वे कैसे हैं, और क्यों err कोड में दिखाई देने के तरीके में बदल दिया गया है।

विकिपीडिया किसी भी अधिक विस्तृत स्पष्टीकरण या सूत्रों को इंगित नहीं करता, तो मैं सोच रहा हूँ:

ठीक err क्या करता है और क्यों कर रहे हैं dx और dy वास्तव में पता चला तरह से इस्तेमाल किया सही अनुपात बनाए रखने के लिए क्या ब्रेसेनहम के लाइन एल्गोरिदम के इस सरलीकृत संस्करण का उपयोग कर क्षैतिज और लंबवत चरणों के बीच?

Answer 1

लाइन के लिए समीकरणों के विभिन्न रूप हैं, सबसे परिचित y=m*x+b में से एक परिचित है। अब अगर m=dy/dx और c = dx*b, तो dx*y = dy*x + c। f(x) = dy*x - dx*y + c लिखना, हमारे पास f(x,y) = 0 iff (x,y) दी गई रेखा पर एक बिंदु है।

यदि आप x एक इकाई, f(x,y)dy द्वारा परिवर्तन अग्रिम करते हैं; यदि आप y एक इकाई अग्रिम करते हैं, f(x,y)dx द्वारा परिवर्तन। अपने कोड में, err रैखिक कार्यात्मक f(x,y) के वर्तमान मूल्य का प्रतिनिधित्व करता है, और बयान

err = err - dy; 
    x1 = x1 + sx; 

और

err = err + dx; 
    y1 = y1 + sy; 

अनुक्रम का प्रतिनिधित्व (sx या sy दिशा में) x या y एक इकाई को आगे बढ़ाने, कार्य मूल्य पर परिणामी प्रभाव के साथ। जैसा कि पहले उल्लेख किया गया है, f(x,y) लाइन पर बिंदुओं के लिए शून्य है; यह रेखा के एक तरफ बिंदुओं के लिए सकारात्मक है, और दूसरे के लिए नकारात्मक है। if परीक्षण निर्धारित करते हैं कि xy, या इसके विपरीत, या दोनों को आगे बढ़ाने की तुलना में वांछित रेखा के करीब रहेगा।

आरंभिक err = dx - dy; ऑफसेट त्रुटि को कम करने के लिए डिज़ाइन किया गया है; यदि आप अपना प्लॉटिंग स्केल उड़ाते हैं, तो आप देखेंगे कि आपकी गणना की गई लाइन अलग-अलग प्रारंभिकताओं के साथ वांछित रेखा पर केंद्रित नहीं हो सकती है।

Answer 2

बस जवाप के उत्कृष्ट उत्तर में "क्यों" जानकारी को जोड़ना चाहते हैं।

f(x) = dy*x - dx*y + c फॉर्मूलेशन का उपयोग करने का बिंदु गणना को तेज करना है। यह फॉर्मूलेशन पूर्णांक अंकगणित (तेज़) का उपयोग करता है, जबकि पारंपरिक y = mx + b फॉर्मूलेशन फ़्लोटिंग पॉइंट अंकगणित (धीमी) का उपयोग करता है।