Получить все точки прямой линии в python

Question

Очень просто, учитывая точку A (x, y) и другую точку B (m, n), мне нужна функция, которая может возвращать в любом итерируемом объекте список [k, z] всех точек между ними.

Меня интересуют только целые точки, поэтому нет необходимости в поплавках.

Мне нужен наилучший возможный пифонический путь, потому что эта «маленькая» функция будет сильно запущена и является ключевым столпом более крупной системы.

EDIT:

@roippi, спасибо, указывая вне Гоча относительно целых чисел. Из моего кода ниже вы можете увидеть, что я пытаюсь перейти по оси x и получить соответствующий y, а затем сделать то же самое для y. Мой набор точек, не будет иметь никакой недискретную координатную точку, так что на данный момент я могу позволить себе упустить из вида, что небольшой недостаток

import itertools 
#Vars 
origin = {'x':0, 'y':0} 

def slope(origin, target): 
    if target['x'] == origin['x']: 
     return 0 
    else: 
     m = (target['y'] - origin['y'])/(target['x'] - origin['x']) 
     return m 

def line_eqn(origin, target): 
    x = origin['x'] 
    y = origin['y'] 
    c = -(slope(origin, target)*x - y) 
    c = y - (slope(origin, target)*x) 
    #return 'y = ' + str(slope(target)) + 'x + ' + str(c) 
    m = slope(origin, target) 
    return {'m':m, 'c':c} 

def get_y(x, slope, c): 
    # y = mx + c  
    y = (slope*x) + c 
    return y 

def get_x(y, slope, c):  
    #x = (y-c)/m 
    if slope == 0: 
     c = 0 #vertical lines never intersect with y-axis 
    if slope == 0: 
     slope = 1 #Do NOT divide by zero 
    x = (y - c)/slope 
    return x 

def get_points(origin, target): 
    coord_list = [] 
    #Step along x-axis 
    for i in range(origin['x'], target['x']+1):  
     eqn = line_eqn(origin, target) 
     y = get_y(i, eqn['m'], eqn['c'])   
     coord_list.append([i, y]) 

    #Step along y-axis 
    for i in range(origin['y'], target['y']+1): 
     eqn = line_eqn(origin, target) 
     x = get_x(i, eqn['m'], eqn['c']) 
     coord_list.append([x, i]) 

    #return unique list  
    return list(k for k,_ in itertools.groupby(sorted(coord_list))) 

origin = {'x':1, 'y':3} 
target = {'x':1, 'y':6} 

print get_points(origin, target) 

Answer 1

def get_line(x1, y1, x2, y2): 
    points = [] 
    issteep = abs(y2-y1) > abs(x2-x1) 
    if issteep: 
     x1, y1 = y1, x1 
     x2, y2 = y2, x2 
    rev = False 
    if x1 > x2: 
     x1, x2 = x2, x1 
     y1, y2 = y2, y1 
     rev = True 
    deltax = x2 - x1 
    deltay = abs(y2-y1) 
    error = int(deltax/2) 
    y = y1 
    ystep = None 
    if y1 < y2: 
     ystep = 1 
    else: 
     ystep = -1 
    for x in range(x1, x2 + 1): 
     if issteep: 
      points.append((y, x)) 
     else: 
      points.append((x, y)) 
     error -= deltay 
     if error < 0: 
      y += ystep 
      error += deltax 
    # Reverse the list if the coordinates were reversed 
    if rev: 
     points.reverse() 
    return points 

Answer 2

Я посмотрел на это как проект, чтобы узнать с. Целые значения прямой линии следуют этой схеме. Большое число по горизонтали, по одному на одно повторение n раз, за ​​которым следует небольшое число по горизонтали по одному. Младший номер - это больше или меньше основного номера. Основное число - это градиент, а второстепенное число - округление.

Answer 3

Давайте предположим, что вы знаете, как работать уравнение линии, так что у вас есть m : ваш градиент, c : ваша постоянная

у вас также есть свои 2 очка: a и b, с х-значение ниже, чем значения х Ь

for x in range(a[0], b[0]): 
    y = m*x + c 
    if isinstance(y, int) and (x,y) not in [a,b]: 
     print (x, y) 

Answer 4

сегмент Bresenham линии, или их варианты связана с параметрическим уравнением

X = X0 + t.Dx 
Y = Y0 + t.Dy, 

где Dx = X1-X0 и Dy = Y1-Y0, а t - параметр в [0, 1].

Оказывается, что это уравнение может быть записано для целочисленной решетки, так как

X = X0 + (T.Dx) \ D 
Y = Y0 + (T.Dy) \ D, 

, где \ обозначает целочисленное деление, D = Max (| Dx |, | Dy |) и т представляет собой целое число в диапазон [0, D].

Как вы можете видеть, в зависимости от того, какая из Dx и Dy имеет наибольшую абсолютную величину и какие знаки она имеет, одно из уравнений можно упростить как X = X0 + T (допустим теперь Dx> = Dy> = 0).

Для реализации этого, у вас есть три варианта:

чисел с плавающей запятой

• использования для уравнения Y, Y = Y0 + T.dy, где ау = Dy/D, предпочтительно округляя результат для лучшая симметрия; по мере увеличения T, обновить с помощью Y + = dy;

• использовать фиксированное представление наклона, выбирая мощность 2 для масштабирования, пусть 2^B; множество Y '= Y0 < < B, Dy' = (Dy < < B) \ D; и каждый раз, когда вы выполняете Y '+ = D', извлекайте Y = Y '>> B.

• использование чистой целочисленной арифметики.

В случае целочисленной арифметики, вы можете получить эффект округления легко путем вычисления Y0 + (T.Dy + D/2) \ D вместо Y0 + (T.Dy \ D). Действительно, поскольку вы делите на D, это эквивалентно Y0 + T.dy + 1/2.

Отдел является медленной операцией. Вы можете обменять его для сравнения с помощью простого трюка: Y увеличивается на 1 каждый раз, когда T.Dy увеличивается на D. Вы можете сохранить переменную «остаток», равную (T.Dy) по модулю D (или T.Dy + D/2, для округления), и уменьшить его на D каждый раз, когда она превышает D.

Y= Y0 
R= 0 
for X in range(X0, X1 + 1): 
    # Pixel(X, Y) 
    R+= Dy 
    if R >= D: 
    R-= D 
    Y+= 1 

для хорошо оптимизированной версии, вы должны рассмотреть отдельно девяти случаев, соответствующих комбинации признаков Dx и Dy (-, 0, +).