在Python中获取直线的所有点

Question

简单来说，给定一个点A(x,y)和另一个点B(m,n)，我需要一个函数，在任何可迭代对象中返回所有中间点的列表[k,z]。

我只对整数点感兴趣，因此不需要浮点数。

我需要最好的Pythonic方法，因为这个“小”函数将被大量运行，并且是更大系统的关键支柱。

编辑：

@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)

- user1048839

---

你目前尝试了什么？你知道如何解线性方程吗？你无法在范围内生成点吗？你卡在哪里了？ - Cory Kramer

你需要计算出直线的斜率，将其化为最简分数，并使用分子/分母作为x和y的增量。 - Emanuele Paolini

嗯...很多段落可能只有极少数或没有点，其中k和z都是整数。即使有整数，有些段落只有几个精确的整数对，而其他段落则有很多 - 使得稀疏性高度可变。我认为你还没有完全考虑清楚这个整数问题。 - roippi

你所寻找的对我来说有点不清楚。你能否给出一些简单输入的例子输出？例如，对于 A = (0, 0) 和 B = (17, 19) ，输出应该是什么？ - Anton

(a) 做好数学计算，确定你想要实现的算法。(b) 尝试去实现它。(c) 如果在编程过程中遇到困难，请回到这里。 - alexis

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

- user1048839

---

一个简单的说明会更有帮助，而不是只有代码。 - KCK

Answer 2

假设您知道如何计算一条直线的方程，因此您有 m ：斜率， c ：常数

您还有两个点：a和b，其中a的x值小于b的x值

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)

- Chris Clarke

---

虽然m可以很容易地得到，但对于人类大脑来说建立c可能是微不足道的，但是当需要为明显永远不会与y相交的垂直线制定例外时，情况变得更加复杂，因此c = ∞，还有水平线的特殊情况，其中c = y。 - user1048839

在这些情况下，您可以添加异常处理，其中a [0] == b [0]或a [1] == b [1]，诚然这不是最好的方法，但相当简单。 - Chris Clarke

Answer 3

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|)，t 是一个在 [0, D] 范围内的整数。

正如您所看到的，取决于 Dx 和 Dy 中哪个具有最大的绝对值以及它们的符号，其中一个方程可以简化为 X = X0 + T（现在假设 Dx >= Dy >= 0）。

要实现这一点，您有三个选项：

• 使用浮点数进行 Y 方程，Y = Y0 + T.dy，其中 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。

除法是一种缓慢的操作。您可以通过一个简单的技巧将其换成比较：每当 T.Dy 增加 D 时，Y 就会增加 1。您可以维护一个“余数”变量，等于 (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、+）。

- user1196549

---

我知道直线的数学概念，也可以编写伪代码来演示这个概念。但是正如问题所述，我需要一个可工作的函数代码。请参考我上面的代码片段。 - user1048839

你这么懒吗？你甚至没有意识到我已经提供了Python代码。 - user1196549

Answer 4

def getLine(x1,y1,x2,y2):
    if x1==x2: ## Perfectly horizontal line, can be solved easily
        return [(x1,i) for i in range(y1,y2,int(abs(y2-y1)/(y2-y1)))]
    else: ## More of a problem, ratios can be used instead
        if x1>x2: ## If the line goes "backwards", flip the positions, to go "forwards" down it.
            x=x1
            x1=x2
            x2=x
            y=y1
            y1=y2
            y2=y
        slope=(y2-y1)/(x2-x1) ## Calculate the slope of the line
        line=[]
        i=0
        while x1+i < x2: ## Keep iterating until the end of the line is reached
            i+=1
            line.append((x1+i,y1+slope*i)) ## Add the next point on the line
        return line ## Finally, return the line!

- nerdguy

Answer 5

以下是C++版本的user1048839的答案，供有兴趣的人参考：

std::vector<std::tuple<int, int>> bresenhamsLineGeneration(int x1, int y1, int x2, int y2) {
std::vector<std::tuple<int, int>> points;
bool                              issteep = (abs(y2 - y1) > abs(x2 - x1));
if (issteep) {
    std::swap(x1, y1);
    std::swap(x2, y2);
}
bool rev = false;
if (x1 > x2) {
    std::swap(x1, x2);
    std::swap(y1, y2);
    rev = true;
}
int deltax = x2 - x1;
int deltay = abs(y2 - y1);
int error  = int(deltax / 2);
int y      = y1;
int ystep;
if (y1 < y2) {
    ystep = 1;
} else {
    ystep = -1;
}

for (int x = x1; x < x2 + 1; ++x) {
    if (issteep) {
        std::tuple<int, int> pt = std::make_tuple(y, x);
        points.emplace_back(pt);
    } else {
        std::tuple<int, int> pt = std::make_tuple(x, y);
        points.emplace_back(pt);
    }

    error -= deltay;
    if (error < 0) {
        y += ystep;
        error += deltax;
    }
}
// Reverse the list if the coordinates were reversed
if (rev) {
    std::reverse(points.begin(), points.end());
}
return points;
}

- brad

Answer 6

我将其作为学习C语言的项目进行了研究。一条直线的整数值遵循以下模式：主要数字水平，横向一个单位，纵向一个单位，重复n次，然后是次要数字水平，横向一个单位，纵向一个单位。次要数字比主要数字多或少1。主要数字实际上是斜率，而次要数字则修正了四舍五入。

- phil

---

这可能是我见过的最糟糕的直线定义了 - y=mx+c 有什么问题吗？ - Tony Suffolk 66

除了我所描述的内容之外，屏幕上绘制一条线的方式没有其他的。而y=mx+c所做的是准确地描述它的几何特征。 - phil

你能否用人类可读的方式重新表达一下你的解释？ - user1196549

是的，@Yves Daust 抱怨是正确的。抱歉，他的回答很好，我唯一的辩护是我试图描述他回答中描述的数学实际上是什么样子的可视化。 - phil