python中不规则点之间的坐标列表

Question

想象一下，对于x和y，我们有两个随机选择的0到100之间的点。

例如：

(95,7), (35,6)

现在使用简单的pygame.draw.line（）函数，我们可以轻松地在这些点之间画一条线而没有任何间隙。

我的问题是，我们怎样才能找到两点之间单个像素粗线中所有坐标的列表，而且线上没有任何间隙？

其次，这甚至可能吗？

我正在使用这个像素列表用于裂缝迷宫算法，该算法需要“射击”另一个像素，同时考虑可能干扰其路径的任何阻挡墙。

http://www.astrolog.org/labyrnth/algrithm.htm

通过不规则，我指的是不会产生简单直线的点。

例如，很容易找到以下所有点：

（0,5）和（5,5）

这已经包含在这个问题中：

List coordinates between a set of coordinates

Answer 1

使用Bresenham's line algorithm。你可以找到一个简单的python实现here。这是该实现的修改版本，给定起点和终点，可以返回中间点列表：

def line(x0, y0, x1, y1):
        "Bresenham's line algorithm"
        points_in_line = []
        dx = abs(x1 - x0)
        dy = abs(y1 - y0)
        x, y = x0, y0
        sx = -1 if x0 > x1 else 1
        sy = -1 if y0 > y1 else 1
        if dx > dy:
            err = dx / 2.0
            while x != x1:
                points_in_line.append((x, y))
                err -= dy
                if err < 0:
                    y += sy
                    err += dx
                x += sx
        else:
            err = dy / 2.0
            while y != y1:
                points_in_line.append((x, y))
                err -= dx
                if err < 0:
                    x += sx
                    err += dy
                y += sy
        points_in_line.append((x, y))
        return points_in_line

Answer 2

也许这是一个矫枉过正，但我​​只是找到线方程并使用生成器表达式。要找到方程，你可以使用this example algorithm，它将返回类似的东西

lambda x: 2*x +1

有了这个，我们可以做到：

f = find_line_equation(A, B) #A B are tuples
points = [(x, f(x)) for x in range(min(A[0], B[0]), max(A[0], B[0]))]

这假设您只需要整数点。你也可以使用这个循环：

points = []
x = min(A[0], B[0])
increment = 0.1
while x <= max(A[0], B[0]):
    points.append((x, f(x))
    x += increment