python - 查找栅格方向变化的算法

Question

我有一个包含 0 和 1 作为 numpy 数组的栅格，所有带有 1 的像素连接形成一条线。这条线在所有地方都是 1 像素粗。使用寻路算法，我得到了所有点(列、行)的坐标列表，包括起点和终点。 我的线的形状是缺少顶部的方形 U/矩形。

我想找到线的方向在较长时间内发生变化的点。比如从下到右，或者从右到上。

我看过Finding the point of a slope change as a free parameter- Python ;然而，由于我的点都是水平、垂直或对角连接的，所以这是行不通的。此外，我的 u 形可以在阵列中成对角线，因此我正在寻找连接类型变化超过 2 个像素的点。下面是我的数据示例，我想找到 (5,3)/(6,4) 和 (6,7)/(5,8)

a = np.array([[0,0,1,0,0,0,0,0,1],
              [0,0,1,0,0,0,0,0,1],
              [0,0,0,1,0,0,0,0,1],
              [0,0,0,1,0,0,0,1,0],
              [0,0,0,1,0,0,0,0,1],
              [0,0,0,1,0,0,0,0,1],
              [0,0,0,0,1,1,1,1,0],
              [0,0,0,0,0,0,0,0,0]])

list_of_points = [(0,2),(1,2),(2,3),(3,3),(4,3),(5,3),(6,4),(6,5),(6,6),(6,7),(5,8),(4,8),(3,7),(2,8),(1,8),(0,8)]

Answer 1

U 形有 3 个方向:向下、向右和向上。您可以使用下一个规则跟随线条和方向，其中 O 是当前位置，X 是可能的下一个像素:

1. 向下

...
.0.
XXX

1. 对

..X
.0X
..X

1. 向上

XXX
.0.
...

并遵循下一个算法(伪代码)

while next move can be down:
    move down
// here ends down line

while next move can be right:
    move right
// here ends right line

while next move can be up:
    move up
// here ends up line

如果U形可以这样对角:

.......
...1...
....1..
1....1.
.1.11..
..1....

您可以为向下、向右和向上的含义定义不同的矩阵。 即

// down
...
.0X
.XX

// right
.XX
.0X
...

// up
XX.
X0.
...