Алгоритм создания линии средней точки

Опубликовано: 20 Января, 2022

Дана координата двух точек A (x1, y1) и B (x2, y2), таких что x1 <x2 и y1 <y2. Задача найти все промежуточные точки, необходимые для рисования линии AB на экране пикселей компьютера. Обратите внимание, что каждый пиксель имеет целочисленные координаты.
Ниже мы обсудили алгоритмы решения этой задачи.

Алгоритм DDA для рисования линий
Введение в алгоритм Брезенхамса для рисования линий.

В этом посте обсуждается алгоритм рисования линии средней точки, который представляет собой другой способ представления алгоритма Брезенхэма, представленного в предыдущем посте.
Как обсуждалось в предыдущем посте, для любого заданного / вычисленного предыдущего пикселя P (X _p , Y _p ) есть два кандидата на следующий пиксель, ближайший к линии, E (X _p +1, Y _p ) и NE (X _p +1, Y _p +1) ( E означает восток, а NE означает северо-восток).
В алгоритме Mid-Point мы делаем следующее.

Найдите середину из двух возможных следующих точек. Середина E (X _p +1, Y _p ) и NE (X _p +1, Y _p +1) - это M (X _{p + 1} , Y _p +1/2).
Если M находится над линией, выберите E в качестве следующей точки.
Если M ниже линии, выберите NE в качестве следующей точки.

Как определить, находится ли точка над линией или под линией?
Ниже приведены некоторые предположения для упрощения алгоритма.

Проводим линию слева направо.
x1 <x2 и y1 <y2
Наклон линии составляет от 0 до 1. Проводим линию снизу слева направо.

Случаи, отличные от приведенных выше предположений, могут быть обработаны с помощью отражения.

 Рассмотрим прямую y = mx + B. 
Мы можем переписать уравнение как:
y = (dy / dx) x + B или 
(dy) x + B (dx) - y (dx) = 0
Пусть F (x, y) = (dy) x - y (dx) + B (dx) ----- (1)
Пусть даны две конечные точки прямой (под
выше предположения)
-> Для всех точек (x, y) на линии, 
      решение F (x, y) равно 0. 
-> Для всех точек (x, y) выше линии, 
      F (x, y) дает отрицательное число. 
-> И для всех точек (x, y) ниже линии, 
      F (x, y) дает положительное число.

Это соотношение используется для определения относительной
положение M
M = (X _{p + 1} , Y _{p +} 1/2)
Итак, наш параметр решения d :
d = F (M) = F (X _{p + 1} , Y _{p +} 1/2)
Как эффективно найти новое значение d из его старого значения?
Для простоты пусть as записывает F (x, y) как ax + by + c.
Где a = dy
b = -dx
с = B * dx
Мы получили эти значения из приведенного выше уравнения (1)
Случай 1: Если выбрано E, то для следующей точки:
dnew = F (X _p +2, Y _{p +} 1/2)
= a (X _p +2) + b (Y _{p +} 1/2) + c
dold = a (X _p +1) + b (Y _{p +} 1/2) + c
Разница (или дельта) двух расстояний:
DELd = dnew - жирный
= a (X _p +2) - a (X _p +1) + b (Y _{p +} 1/2) - b (Y _{p +} 1/2) + cc
= а (Х _р ) + 2а - а (Х _р ) - а
= а.
Следовательно, dnew = dold + dy. (как a = dy)

Случай 2: Если выбран NE, то для следующей точки:
dnew = F (X _p +2, Y _p +3/2)
= а (X _p +2) + b (Y _p +3/2) + c
dold = a (X _p +1) + b (Y _p +1/2) + c
Разница (или дельта) двух расстояний:
DELd = dnew -dold
= a (X _p +2) - a (X _p +1) + b (Y _p +3/2) - b (Y _p +1/2) + cc
= a (X _p ) + 2a - a (X _p ) - a + b (Y _p ) + 3 / 2b - b (Y _p ) -1 / 2b
= а + б
Следовательно, dnew = dold + dy - dx. (как a = dy, b = -dx)
Расчет Для начального значения параметра решения d0:
d0 = F (X1 + 1, Y1 + 1/2)
= a (X1 + 1) + b (Y1 + 1/2) + c
= aX1 + bY1 + c + a + b / 2
= F (X1, Y1) + a + b / 2
= a + b / 2 (поскольку F (X1, Y1) = 0)
d0 = dy - dx / 2. (как a = dy, b = -dx)
Алгоритм:

 Входные данные (X1, Y1) и (X2, Y2)
dy = Y2- Y1
dx = X2 - X1
// начальное значение 
// параметр решения d


if (dy <= dx) {
d = dy - (dx / 2)
х = Х1, у = Y1

// строим начальную заданную точку
Участок (x, y)

// перебираем значение X
в то время как (x <X2)
    х = х + 1

    // Выбрано 'E'
    если (d <0)
       d = d + dy

    // выбран NE
    еще
       d = d + dy - dx
       у = у + 1
    Участок (x, y)}

иначе, если (dx <= dy)
{
d = dx - (dy / 2)
х = Х1, у = Y1

// строим начальную заданную точку
Участок (x, y)

// перебираем значение X
в то время как (y <Y2)
    у = у + 1

    // Выбрано 'E'
    если (d <0)
       d = d + dx

    // выбран NE
    еще
       d = d + dx - dy
       х = х + 1
    Участок (x, y)
}

Below is the implementation of above idea:

C++

// C++ program for Mid-point line generation
#include<bits/stdc++.h>
using namespace std;
 
// Header file for including graphics functions
// #include<graphics.h>
 
// midPoint function for line generation
void midPoint(int X1, int Y1, int X2, int Y2)
{
    // calculate dx & dy
   
    int dx = X2 - X1;
    int dy = Y2 - Y1;
   
    if(dy<=dx){
    // initial value of decision parameter d
    int d = dy - (dx/2);
    int x = X1, y = Y1;
 
    // Plot initial given point
    // putpixel(x,y) can be used to print pixel
    // of line in graphics
    cout << x << "," << y << "
";
 
    // iterate through value of X
    while (x < X2)
    {
        x++;
 
        // E or East is chosen
        if (d < 0)
            d = d + dy;
 
        // NE or North East is chosen
        else
        {
            d += (dy - dx);
            y++;
        }
 
        // Plot intermediate points
        // putpixel(x,y) is used to print pixel
        // of line in graphics
        cout << x << "," << y << "
";
    }
    }
   
  else if(dx<dy)
  {
    // initial value of decision parameter d
    int d = dx - (dy/2);
    int x = X1, y = Y1;
 
    // Plot initial given point
    // putpixel(x,y) can be used to print pixel
    // of line in graphics
    cout << x << "," << y << "
";
 
    // iterate through value of X
    while (y < Y2)
    {
        y++;
 
        // E or East is chosen
        if (d < 0)
            d = d + dx;
 
        // NE or North East is chosen
        // NE or North East is chosen
        else
        {
            d += (dx - dy);
            x++;
        }
 
        // Plot intermediate points
        // putpixel(x,y) is used to print pixel
        // of line in graphics
        cout << x << "," << y << "
";
    }
  }
}
 
// Driver program
int main()
{
    // graphics driver and mode
    // used in graphics.h
    // int gd = DETECT, gm;
 
    // Initialize graphics function
    // initgraph (&gd, &gm, "");
 
    int X1 = 2, Y1 = 2, X2 = 8, Y2 = 5;
    midPoint(X1, Y1, X2, Y2);
    return 0;
}

Java

// Java program for Mid-point
// line generation
class GFG
{
// midPoint function for line generation
static void midPoint(int X1, int Y1,
                     int X2, int Y2)
{
    // calculate dx & dy
    int dx = X2 - X1;
    int dy = Y2 - Y1;
 
    // initial value of decision
    // parameter d
    int d = dy - (dx/2);
    int x = X1, y = Y1;
 
    // Plot initial given point
    // putpixel(x,y) can be used to
    // print pixel of line in graphics
    System.out.print(x +"," + y + "
");
 
    // iterate through value of X
    while (x < X2)
    {
        x++;
 
        // E or East is chosen
        if (d < 0)
            d = d + dy;
 
        // NE or North East is chosen
        else
        {
            d += (dy - dx);
            y++;
        }
 
        // Plot intermediate points
        // putpixel(x,y) is used to print
        // pixel of line in graphics
        System.out.print(x +"," + y + "
");
    }
}
 
// Driver code
public static void main (String[] args)
{
    int X1 = 2, Y1 = 2, X2 = 8, Y2 = 5;
    midPoint(X1, Y1, X2, Y2);
}
}
 
// This code is contributed by Anant Agarwal.

Python 3

# Python3 program for Mid-point
# line generation
 
 
# midPoint function for line generation
def midPoint(X1,Y1,X2,Y2):
    # calculate dx & dy
    dx = X2 - X1
    dy = Y2 - Y1
 
    # initial value of decision parameter d
    d = dy - (dx/2)
    x = X1
    y = Y1
 
    # Plot initial given point
    # putpixel(x,y) can be used to print pixel
    # of line in graphics
    print(x,",",y,"
")
    # iterate through value of X
    while (x < X2):
        x=x+1
        # E or East is chosen
        if(d < 0):
            d = d + dy
 
        # NE or North East is chosen
        else:
            d = d + (dy - dx)
            y=y+1
     
 
        # Plot intermediate points
        # putpixel(x,y) is used to print pixel
        # of line in graphics
        print(x,",",y,"
")
     
 
# Driver program
 
if __name__=="__main__":
    X1 = 2
    Y1 = 2
    X2 = 8
    Y2 = 5
    midPoint(X1, Y1, X2, Y2)
 
# This code is contributed by ash264

C#

// C# program for Mid-point
// line generation
using System;
 
class GFG {
     
    // midPoint function for line
    // generation
    static void midPoint(int X1, int Y1,
                         int X2, int Y2)
    {
         
        // calculate dx & dy
        int dx = X2 - X1;
        int dy = Y2 - Y1;
     
        // initial value of decision
        // parameter d
        int d = dy - (dx/2);
        int x = X1, y = Y1;
     
        // Plot initial given point
        // putpixel(x,y) can be used
        // to print pixel of line in
        // graphics
        Console.Write(x + "," + y + "
");
     
        // iterate through value of X
        while (x < X2)
        {
            x++;
     
            // E or East is chosen
            if (d < 0)
                d = d + dy;
     
            // NE or North East is chosen
            else
            {
                d += (dy - dx);
                y++;
            }
     
            // Plot intermediate points
            // putpixel(x,y) is used to print
            // pixel of line in graphics
            Console.Write(x + "," + y + "
");
        }
    }
     
    // Driver code
    public static void Main ()
    {
        int X1 = 2, Y1 = 2, X2 = 8, Y2 = 5;
        midPoint(X1, Y1, X2, Y2);
    }
}
 
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program for Mid-point
// line generation
 
// midPoint function for
// line generation
function midPoint($X1, $Y1,
                  $X2, $Y2)
{
     
    // calculate dx & dy
    $dx = $X2 - $X1;
    $dy = $Y2 - $Y1;
 
    // initial value of
    // decision parameter d
    $d = $dy - ($dx/2);
    $x = $X1;
    $y = $Y1;
 
    // Plot initial given point
    // putpixel(x,y) can be used
    // to print pixel of line
    // in graphics
    echo $x , "," , $y , "
";
 
    // iterate through
    // value of X
    while ($x < $X2)
    {
        $x++;
 
        // E or East is chosen
        if ($d < 0)
            $d = $d + $dy;
 
        // NE or North East
        // is chosen
        else
        {
            $d += ($dy - $dx);
            $y++;
        }
 
        // Plot intermediate points
        // putpixel(x,y) is used
        // to print pixel of
        // line in graphics
        echo $x , "," ,$y , "
";
    }
}
 
    // Driver Code
    $X1 = 2;
    $Y1 = 2;
    $X2 = 8;
    $Y2 = 5;
    midPoint($X1, $Y1, $X2, $Y2);
 
// This code is contributed by nitin mittal.
?>

Javascript

<script>
 
// JavaScript program for the above approach
 
// midPoint function for line generation
function midPoint(X1, Y1, X2, Y2)
{
 
    // calculate dx & dy
    let dx = X2 - X1;
    let dy = Y2 - Y1;
 
    // initial value of decision
    // parameter d
    let d = dy - (dx/2);
    let x = X1, y = Y1;
 
    // Plot initial given point
    // putpixel(x,y) can be used to
    // print pixel of line in graphics
    document.write(x +"," + y + "<br/>");
 
    // iterate through value of X
    while (x < X2)
    {
        x++;
 
        // E or East is chosen
        if (d < 0)
            d = d + dy;
 
        // NE or North East is chosen
        else
        {
            d += (dy - dx);
            y++;
        }
 
        // Plot intermediate points
        // putpixel(x,y) is used to print
      
            

                    
                                            Алгоритмы
                                            Компьютерная графика
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИРазница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2024. Все права защищены.