एक लाइन पर सभी ग्रिड वर्ग कैसे खोजें?

Question

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

मूल विचार बहुत सरल है। स्यूडोकोड में:

function LineOfSight(point1, point2): boolean 
    squares = GetListOfSquaresOnLine(point1, point2) 
    for each square in squares 
    if square.IsOpaque then return false 
    return true 

GetListOfSquaresOnLine होगा (धारणात्मक) अंक 2 पर ग्रिड वर्ग के केंद्र के लिए point1 पर ग्रिड वर्ग के केंद्र से एक सीधी रेखा खींचना, और सभी वर्गों है कि इस लाइन से होकर गुजरता है की एक सूची प्रदान । लेकिन यह वह हिस्सा है जिसे मुझे नहीं पता कि इसे कैसे कार्यान्वित किया जाए। क्या कोई जानता है कि इसे कैसे करना है? डेल्फी या सी उदाहरण पसंद करते हैं, लेकिन आवश्यक नहीं है।

Answer 1

उत्तरों की

दोनों मिलते हैं। यहां पूर्ण चित्र पर आलेख दिया गया चित्र है। ध्यान दें कि रेखा ग्रिड वर्गों से गुज़रती है जो हाइलाइट नहीं की जाती हैं, इसलिए ब्रेसनहेम का एल्गोरिदम केवल वही चीज़ देता है जो आप चाहते हैं।

जब से तुम "दृष्टि की रेखा" का उल्लेख है, यह लगता है कि आप एक एल्गोरिथ्म है कि ग्रिड वर्गों है कि लाइन के माध्यम से चला जाता है के सभी विश्लेषण करता है चाहता हूँ। इस सेट को कभी-कभी सुपर कवर (लाइन के), और one algorithm is described here के रूप में जाना जाता है।

this question के उत्तरों में दिए गए कुछ अन्य दृष्टिकोण भी हैं।

अद्यतन:Here's another reference

Answer 2

Bresenham's Algorithm क्या आप देख रहे हैं?

Answer 3

Bresenhams के एल्गोरिथ्म पर एक विकिपीडिया लेख के लिए अब तक बिंदु http://en.wikipedia.org/wiki/Bresenham's_line_algorithm

Answer 4

यहाँ an implementation I wrote in C है।