Is it possible to check if a pixel is in a line generated by bresenham without generating a line?

Question

I have a pixel P on the grid. I want to know if this pixel on bresenham will be a generated line between P0 and P1 without actually generating the line. Is it possible to come up with such a determinant?

Answer 1

I write this as an answer, although this is only a very partial answer.

I think the answer is yes. However, writing proof of this is rather a bit of work, and, at a minimum, TeX support is required to be clear. Instead, here are the key ideas for developing evidence.

m 0 1. , . , 1. n, n + 1, n <= 1/m <= n + 1. , Brensenham 0 1. .

, , m. m - 1/(n + 1) . " " m 1/(n + 1). , , m. , . , 0/1 , .

, , m , , .

, . y- x-. x. , , ( ), , n <= a < b < + 1.

Answer 2

: (1,1) (11,5):

, :

Module Module1

    Dim chart(15, 9) As String

    Class Point
        Property X As Double
        Property Y As Double

        Sub New(x As Double, y As Double)
            Me.X = x
            Me.Y = y
        End Sub
        Sub New()
            ' empty constructor
        End Sub
    End Class

    Sub ClearChart()
        For i = 0 To 15
            For j = 0 To 9
                chart(i, j) = "·"
            Next
        Next
    End Sub

    Sub ShowChart(title As String)
        If title.Length > 0 Then
            Console.WriteLine(title)
        End If

        For j = 0 To 9
            For i = 0 To 15
                Console.Write(chart(i, j))
            Next
            Console.WriteLine()
        Next

        Console.WriteLine()

    End Sub

    Sub Plot(p As Point)
        Plot(p.X, p.Y)
    End Sub

    Sub Plot(x As Double, y As Double)
        chart(CInt(Math.Round(x, MidpointRounding.AwayFromZero)), CInt(Math.Round(y, MidpointRounding.AwayFromZero))) = "█"
    End Sub

    Sub DrawLine(p1 As Point, p2 As Point)
        ' use Bresenham line algorithm
        Dim Δx = p2.X - p1.X
        Dim Δy = p2.Y - p1.Y
        Dim err As Double = 0.0
        Dim Δerr = Math.Abs(Δy / Δx)
        Dim y As Integer = CInt(p1.Y)
        Dim yDirn = Math.Sign(p2.Y - p1.Y)
        For x = CInt(p1.X) To CInt(p2.X)
            Plot(x, y)
            err += Δerr
            While err >= 0.5
                Plot(x, y)
                y += yDirn
                err -= 1.0
            End While
        Next
    End Sub

    Function IsOnLine(p1 As Point, p2 As Point, testPoint As Point) As Boolean
        ' check for bounds
        If testPoint.X < p1.X - 0.5 OrElse testPoint.X > p2.X + 0.5 OrElse testPoint.Y < p1.Y - 0.5 OrElse testPoint.Y > p2.Y + 0.5 Then
            Return False
        End If

        Dim Δx = p2.X - p1.X
        Dim Δy = p2.Y - p1.Y
        Dim m = Δy / Δx
        Dim c = p1.Y - m * p1.X

        Return Math.Abs((m * Math.Round(testPoint.X, MidpointRounding.AwayFromZero) + c - Math.Round(testPoint.Y, MidpointRounding.AwayFromZero))) <= 0.5

    End Function

    Sub Main()
        ClearChart()

        ' end-points of the line
        Dim p1 = New Point(1, 1)
        Dim p2 = New Point(11, 5)

        DrawLine(p1, p2)

        ShowChart("Bresenham line:")

        ClearChart()

        For j = 0 To 9
            For i = 0 To 15
                Dim thisPoint = New Point(i, j)
                If IsOnLine(p1, p2, thisPoint) Then
                    Plot(thisPoint)
                End If
            Next
        Next

        ShowChart("Points on the line by brute-force:")

        ' a couple of points to go with the illustration on SO:
        Console.WriteLine(IsOnLine(p1, p2, New Point(7.51, 4.4)))
        Console.WriteLine(IsOnLine(p1, p2, New Point(7.51, 4.6)))

        Console.ReadLine()

    End Sub

End Module

, , , , , :

Bresenham line:
················
·██·············
···██···········
·····███········
········██······
··········██····
················
················
················
················

Points on the line by brute-force:
················
·██·············
···██···········
·····███········
········██······
··········██····
················
················
················
················

( ... .)

, , , .

, , (7.51, 4.4) (7.51, 4.6) , IsOnLine().

, , , , (4.51, 2.404) . IsOnLine() False .

Answer 3

(Dx > Dy > 0)

X = X0 + I
Y = Y0 + (I.Dy + R) / Dx

R - ( Dx / 2).

Y == Y0 + ((X - X0).Dy + R) / Dx

---

You can rewrite a criterion, for example

0 <= (X - X0).Dy + R - (Y - Y0).Dx < Dx

You need to adapt relationships for other octants.