Connect two points with line

[MrKris1224]

Hi, i have problem and i haven't any idea how to solve it.

Let's assume that. I have 2 points in 2D array marked as 1. other cells are 0. Now i wanna to connect these two points with line but there is problem because these two points are in array. Anyone have idea how to do it?



Simply, this picture is 2D array. Green squares are two points in array which i wanna to connect. The red line and red squares are line which i wanna to "draw" in array by some function. But how this function can looks?

Please help me. I am trying solve this for several weeks.

[JLogan3o13]

You've been trying for several weeks, how about posting your code rather than making us guess?

[jchd]

Google "Bresenham".

[odaylton]

This is matter of middle oak.
You need to apply the equation of the line Y = a * X + b where a = slope of the line.
Calculating the "a"
A = Δy / Δx or (Y - Yo) / (X - Xo) or (Yb - Ya) / (Xb - Xa)
Now simply substitute the coordinates of a point to define the "b".
B = y-ax
So just looping to define the values of y for the X components

[UEZ]

No need to reinvent the wheel -> quick search!

#include <Array.au3>

Global $aCanvas[25][12]

drawBresenhamLine($aCanvas, 1, 1, 10, 21)
_ArrayDisplay($aCanvas)

Func drawBresenhamLine(ByRef $aArray, $iX0, $iY0, $iX1, $iY1, $bSE = True)
    Local $iDx = Abs($iX1 - $iX0)
    Local $iSx = $iX0 < $iX1 ? 1 : -1
    Local $iDy = Abs($iY1 - $iY0)
    Local $iSy = $iY0 < $iY1 ? 1 : -1
    Local $iErr = ($iDx > $iDy ? $iDx : -$iDy) / 2, $e2
    Local $iSX = $iX0, $iEY = $iY0
    While $iX0 <= $iX1
        $aArray[$iY0][$iX0] = "*"
        If ($iX0 = $iX1) And ($iY0 = $iY1) Then ExitLoop
        $e2 = $iErr
        If ($e2 > -$iDx) Then
            $iErr -= $iDy
            $iX0 += $iSx
        EndIf
        If ($e2 < $iDy) Then
            $iErr += $iDx
            $iY0 += $iSy
        EndIf
    WEnd
    If $bSE Then
        $aArray[$iEY][$iSx] = "S"
        $aArray[$iY1][$iX1] = "E"
    EndIf
    Return 1
EndFunc   ;==>drawBresenhamLine

Edited November 24, 2016 by UEZ

[MrKris1224]

Thanks UEZ.

[Gianni]

.... also, from a quick search "Bresenham" within www.autoitscript.com -->

within above link there are function to plot lines, circles, ellipses and Bezier segments:

here a quick example of use:

expandcollapse popup

#cs
    The Beauty of Bresenham's Algorithm
    A simple implementation to plot lines, circles, ellipses and Bézier curves.
    http://members.chello.at/~easyfilter/bresenham.html
#ce
; ------------------------------------------
#include <array.au3>

Global $aArray[25][25] ; [x][y]  0 to 24
Global $aEmpty = $aArray

plotLine(0,0,24,24) ; start y, start x , end y, end x
_ArrayDisplay($aArray)
$aArray = $aEmpty

plotCircle(12, 12, 11) ; y center, x center, ray
_ArrayDisplay($aArray)
$aArray = $aEmpty

; plot an ellipse into a box
plotEllipseRect(3, 1, 15, 8) ; y upleft, x upleft, y downright, x downright
plotEllipseRect(1, 11, 23, 23) ; second ellipse in the same array
_ArrayDisplay($aArray)
$aArray = $aEmpty

; start point , curve point , end point
plotQuadBezierSeg(0,0, 0,24, 24,24) ; y,x,   y,x,   y,x
_ArrayDisplay($aArray)

; ------------------------------------------
; Line
Func plotLine($x0, $y0, $x1, $y1)
    Local $dx = Abs($x1 - $x0), $sx = $x0 < $x1 ? 1 : - 1
    Local $dy = -Abs($y1 - $y0), $sy = $y0 < $y1 ? 1 : - 1
    Local $err = $dx + $dy, $e2 ; /* error value e_xy */

    While 1 ;  /* loop */
        setPixel($x0, $y0)
        If($x0 = $x1 And $y0 = $y1) Then ExitLoop ; break
        $e2 = 2 * $err
        If($e2 >= $dy) Then ; /* e_xy + e_x > 0 */
            $err += $dy
            $x0 += $sx ; /* x step */
        EndIf
        If($e2 <= $dx) Then ; /* e_xy + e_y < 0 */
            $err += $dx
            $y0 += $sy ; /* y step */
        EndIf
    WEnd

EndFunc   ;==>plotLine

; Circle
Func plotCircle($xm, $ym, $r)
    Local $x = -$r, $y = 0, $err = 2 - 2 * $r ; /* II. Quadrant */
    While($x < 0); Do
        setPixel($xm - $x, $ym + $y); /*   I. Quadrant */
        setPixel($xm - $y, $ym - $x); /*  II. Quadrant */
        setPixel($xm + $x, $ym - $y); /* III. Quadrant */
        setPixel($xm + $y, $ym + $x); /*  IV. Quadrant */
        $r = $err;
        If($r <= $y) Then ;           /* e_xy+e_y < 0 */
            $y += 1
            $err += $y * 2 + 1
        EndIf
        If($r > $x Or $err > $y) Then ; /* e_xy+e_x > 0 or no 2nd y-step */
            $x += 1
            $err += $x * 2 + 1
        EndIf
    WEnd ; While ($x < 0);
EndFunc   ;==>plotCircle

; Ellipse
; This function plots an ellipse inside a specified rectangle.
Func plotEllipseRect($x0, $y0, $x1, $y1)
    Local $a = Abs($x1 - $x0), $b = Abs($y1 - $y0), $b1 = BitAND($b, 1) ;  $b1 = $b & 1; /* values of diameter */
    Local $dx = 4 * (1 - $a) * $b * $b, $dy = 4 * ($b1 + 1) * $a * $a ; /* error increment */
    Local $err = $dx + $dy + $b1 * $a * $a, $e2; /* error of 1.step */

    If($x0 > $x1) Then ; /* if called with swapped points */
        $x0 = $x1
        $x1 += $a
    EndIf
    If($y0 > $y1) Then $y0 = $y1 ; /* .. exchange them */
    $y0 += ($b + 1) / 2
    $y1 = $y0 - $b1 ;   /* starting pixel */
    $a *= 8 * $a;
    $b1 = 8 * $b * $b;

    While($x0 <= $x1) ; do [
        setPixel($x1, $y0); /*   I. Quadrant */
        setPixel($x0, $y0); /*  II. Quadrant */
        setPixel($x0, $y1); /* III. Quadrant */
        setPixel($x1, $y1); /*  IV. Quadrant */
        $e2 = 2 * $err;
        If($e2 <= $dy) Then
            $y0 += 1
            $y1 -= 1
            $dy += $a
            $err += $dy ; += $a; }  /* y step */
        EndIf
        If($e2 >= $dx Or 2 * $err > $dy) Then
            $x0 += 1
            $x1 -= 1
            $dx += $b1
            $err += $dx ; += $b1; } /* x step */
        EndIf
    WEnd ; while ($x0 <= $x1);

    While($y0 - $y1 < $b) ; [  /* too early stop of flat ellipses a=1 */
        setPixel($x0 - 1, $y0); /* -> finish tip of ellipse */

        $y0 += 1
        setPixel($x1 + 1, $y0) ; ++);

        setPixel($x0 - 1, $y1);

        $y1 -= 1
        setPixel($x1 + 1, $y1) ; --);
    WEnd
EndFunc   ;==>plotEllipseRect

; #cs
; Bézier curve
; This function plots a quadratic Bézier curve limited to gradients without sign change.
Func plotQuadBezierSeg($x0, $y0, $x1, $y1, $x2, $y2)

    Local $sx = $x2 - $x1, $sy = $y2 - $y1;
    Local $xx = $x0 - $x1, $yy = $y0 - $y1, $xy;         /* relative values for checks */
    Local $dx, $dy, $err, $cur = $xx * $sy - $yy * $sx;                    /* curvature */

    ; assert($xx * $sx <= 0 && $yy * $sy <= 0) ;  /* sign of gradient must not change */       <--------- ? ? ? ? what's this

    ;If ($sx * (long) $sx + $sy * (long) $sy > $xx * $xx + $yy * $yy) Then ; { /* begin with longer part */
    If($sx * $sx + $sy * $sy > $xx * $xx + $yy * $yy) Then ; { /* begin with longer part */    <--------- (Long) removed
        $x2 = $x0
        $x0 = $sx + $x1
        $y2 = $y0
        $y0 = $sy + $y1
        $cur = -$cur ;  /* swap P0 P2 */
    EndIf ; }
    If($cur <> 0) Then ;{ / * no straight line * /
        $xx += $sx
        ; **************************
        $sx = ($x0 < $x2 ? 1 : - 1)
        $xx *= $sx ; = $x0 < $x2 ? 1 : -1 ;           /* x step direction */

        $yy += $sy

        $sy = ($y0 < $y2 ? 1 : - 1)
        $yy *= $sy ; = $y0 < $y2 ? 1 : -1 ;           /* y step direction */
        ; **************************
        $xy = 2 * $xx * $yy
        $xx *= $xx
        $yy *= $yy ;          /* differences 2nd degree */
        If($cur * $sx * $sy < 0) Then ;{         /* negated curvature? */
            $xx = -$xx
            $yy = -$yy
            $xy = -$xy
            $cur = -$cur
        EndIf ; }
        $dx = 4.0 * $sy * $cur * ($x1 - $x0) + $xx - $xy;             /* differences 1st degree */
        $dy = 4.0 * $sx * $cur * ($y0 - $y1) + $yy - $xy;
        $xx += $xx
        $yy += $yy
        $err = $dx + $dy + $xy;                /* error 1st step */
        While($dy < $dx) ; do {
            setPixel($x0, $y0);                                     /* plot curve */
            ; If ($x0 == $x2 && $y0 == $y2) Then Return;  /* last pixel -> curve finished */
            If($x0 = $x2 And $y0 = $y2) Then Return;  /* last pixel -> curve finished */
            $y1 = 2 * $err < $dx;                  /* save value for test of y step */
            If(2 * $err > $dy) Then
                $x0 += $sx
                $dx -= $xy
                $dy += $yy
                $err += $dy ; += $yy;
            EndIf ; } /* x step */
            If($y1) Then
                $y0 += $sy
                $dy -= $xy
                $dx += $xx
                $err += $dx ; += xx;
            EndIf ; } /* y step */
        WEnd ;} while (dy < dx );           /* gradient negates -> algorithm fails */
    EndIf ; }
    plotLine($x0, $y0, $x2, $y2);               /* plot remaining part to end */
EndFunc   ;==>plotQuadBezierSeg

Func setPixel($x0, $y0); it draws a single pixel
    $aArray[$x0][$y0] = "*"
    Return
EndFunc   ;==>_setPixel