2D三角网格中对齐及近似对齐线段的检测与合并方法咨询

我有结构为(x, y, index)的2D点云，示例如下：

pts = [[0,0,1],[0,1,2],[0,2,3],[1,0,4],[1,1,5],[1,2,6],[2,0,7],[2,1,8],[2,2,9]] 

另有结构为(index1, index2)的线段集合，用于两两连接点：

segs = [[1,2],[1,4],[1,5],[2,3],[2,5],[3,5],[3,6],[4,5],[4,7],[4,8],[5,6],[5,8],[5,9],[6,9],[7,8],[8,9]]

所有线段仅连接两个点，不会穿过第三个点。要求在每条线段仅使用一次的前提下，检测对齐的线段，合并为包含n个索引的长线段，预期输出示例如下：

aligned = [[1,2,3],[1,4,7],[1,5,9],[2,5,8],[3,6,9],[3,5],[4,5,6],[4,8],[7,8,9]]

如果点不是完全对齐的，点云示例如下：

pts = [[0.002,0.1,1],[0.0003,1.003,2],[-0.01,2.11,3],[1.01,0.101,4],[1.0005,1.2,5],[1.25,2.01,6],[2.007,-0.12,7],[1.996,1.1,8],[2.03,2.1,9]] 

此时需要根据自定义的角度容差（例如3°），将夹角接近0的近似对齐线段合并。该算法需要适配1万点以上的大规模网格，尝试了多种方法均未成功，以下是可复现示例的代码：

import numpy as np
import matplotlib.pyplot as plt

#pts = np.array([[0,0,1],[0,1,2],[0,2,3],[1,0,4],[1,1,5],[1,2,6],[2,0,7],[2,1,8],[2,2,9]])
pts = np.array([[0.002,0.1,1],[0.0003,1.003,2],[-0.01,2.11,3],[1.01,0.101,4],[1.0005,1.2,5],[1.25,2.01,6],[2.007,-0.12,7],[1.996,1.1,8],[2.03,2.1,9]])

indices = pts[:,2].astype(int)

seg = np.array([[1,2],[1,4],[1,5],[2,3],[2,5],[3,5],[3,6],[4,5],[4,7],[4,8],[5,6],[5,8],[5,9],[6,9],[7,8],[8,9]])

for s in seg:
    i1, i2 = s
    segment = np.array((pts[indices == i1][0], pts[indices == i2][0]))
    plt.plot(segment[:,0],segment[:,1],color="black")
plt.axis("equal")
plt.show()

aligned = np.array([[1,2,3],[1,4,7],[1,5,9],[2,5,8],[3,6,9],[3,5],[4,5,6],[4,8],[7,8,9]],dtype=object)

for a in aligned:
    p = []
    for index in a:
        p += [pts[indices == index][0]]
    p = np.array(p)
    print(p)
    plt.plot(p[:, 0], p[:, 1])

plt.axis("equal")
plt.show()

注：本问题表述比此前发布的内容更通用，请勿判定为重复问题。

内容的提问来源于stack exchange，提问作者adrienlucca.net