如何用Python统计Android风格滑动密码的线段交点数量？

这里的“滑动密码”指连接3x3网格（数字0-8排列如下）中长度为9的路径元组所形成的线段：

0  1  2
3  4  5
6  7  8

我已编写如下代码用于可视化特定的9元组路径：

def coords(number):
    y, x = divmod(number, 3)
    return x, y

def draw_arrow(i, j):
    x1, y1 = coords(i)
    x2, y2 = coords(j)
    dx = x2 - x1
    dy = y2 - y1
    plt.arrow(x1, y1, dx, dy, 
          head_width = 0.04,
          width = 0.01,
          ec ='green')

def draw(path):
    # 默认输入是长度为9的元组
    plt.clf()
    for i in range(0,3):
        for j in range(0,3):      
            plt.scatter(i, j, s=200, c='black',  edgecolors='black') 
    plt.ylim(2.1, -0.1)
    for i in range(len(path)-1):
        draw_arrow(path[i], path[i+1])
    plt.show()

注：为简化问题，不会考虑例如2到8或0到2这类跨中间点的路径。以下是部分滑动密码示例：

draw((2, 7, 5, 0, 3, 6, 4, 8, 1))

draw((0, 4, 6, 3, 7, 2, 5, 8, 1))

请问如何统计这类滑动密码中的线段交点数量？

解决方案 #

要统计线段交点数量，可按以下三步实现：

1. 提取路径中的所有线段
   从输入路径元组中生成所有连续点对对应的线段，每条线段用两个端点的坐标表示，同时记录线段索引用于后续排除相邻线段。

2. 判断两条线段是否为内部相交
   实现线段相交判断函数，需满足：

   • 排除共享端点的线段（包括路径中相邻的线段，以及非相邻但端点重合的情况）
   • 仅统计两条线段在内部交叉的情况（交点不是任何线段的端点）

3. 遍历线段对统计有效交点
   遍历所有非相邻的线段对，用判断函数检查是否相交，累计符合条件的交点数量。

完整实现代码

import matplotlib.pyplot as plt

def coords(number):
    y, x = divmod(number, 3)
    return x, y

def draw_arrow(i, j):
    x1, y1 = coords(i)
    x2, y2 = coords(j)
    dx = x2 - x1
    dy = y2 - y1
    plt.arrow(x1, y1, dx, dy, 
          head_width = 0.04,
          width = 0.01,
          ec ='green')

def draw(path):
    plt.clf()
    for i in range(0,3):
        for j in range(0,3):      
            plt.scatter(i, j, s=200, c='black',  edgecolors='black') 
    plt.ylim(2.1, -0.1)
    for i in range(len(path)-1):
        draw_arrow(path[i], path[i+1])
    plt.show()

def orientation(p, q, r):
    # 计算三点方向：0=共线，1=顺时针，2=逆时针
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    return 1 if val > 0 else 2

def segments_intersect(s1, s2):
    # s1、s2格式为((x1,y1), (x2,y2))
    p1, q1 = s1
    p2, q2 = s2

    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)

    # 一般交叉情况
    if o1 != o2 and o3 != o4:
        return True

    # 共线端点重合情况（按问题要求排除）
    return False

def count_intersections(path):
    # 生成所有线段
    segments = []
    for i in range(len(path)-1):
        p = coords(path[i])
        q = coords(path[i+1])
        segments.append((p, q))
    
    count = 0
    # 遍历所有非相邻线段对
    for i in range(len(segments)):
        for j in range(i+1, len(segments)):
            if j == i+1:
                continue
            if segments_intersect(segments[i], segments[j]):
                count +=1
    return count

# 测试示例
path1 = (2, 7, 5, 0, 3, 6, 4, 8, 1)
print(f"路径1的交点数量：{count_intersections(path1)}")
draw(path1)

path2 = (0, 4, 6, 3, 7, 2, 5, 8, 1)
print(f"路径2的交点数量：{count_intersections(path2)}")
draw(path2)

代码说明

• orientation：通过计算向量叉积判断三点相对位置，是线段相交判断的核心逻辑。
• segments_intersect：仅返回两条线段内部交叉的结果，符合问题简化条件。
• count_intersections：生成路径线段后，遍历所有非相邻线段对统计有效交点数。

内容的提问来源于stack exchange，提问作者Sanae Kochiya