如何比较两条折线是否相等？
How to compare two poly lines for equality?
我有两条折线（路径），每条线都由一个二维点数组表示。我想计算两者之间的距离或相似度分数。每个阵列中可能有不同数量的点。如果您要绘制折线并且它们直接在彼此之上，则距离应该为零。
p1 = np.array([[0,0], [5,5], [9,9]])
p2 = np.array([[0,0], [3,3], [6,6], [9,9]])
p3 = np.array([[0,0], [3,4], [6,7], [9,9]])
p4 = np.array([[0,0], [0,9]])
polyline_dist(p1, p2) # Should be 0 since the plots are identical
polyline_dist(p1, p3) # Should be small since the plots are close
polyline_dist(p1, p4) # Should be larger since the plots are much different
我尝试了一种方法，计算数组 1 中的每个点到数组 2 中的线段的距离并取最小距离，然后取所有点的平均值。这行得通，但对于具有数百个点的较长数组来说速度很慢。
欢迎提出任何建议！
您可以尝试找出每个绘图投射到 x 轴和 y 轴上的区域，然后比较该区域的交集。与具有两条曲线 f(x) 和 g(x) 的微积分类似，您可以使用从 (f(x) - g(x)) 的下限到上限的积分找到曲线之间的区域dx。如果您的行没有重叠 domains/codomains，您可能需要添加一些惩罚并从 p1[0] 和 p2[0] 的最大值开始，到 p1[-1] 和 p2[ 的最小值结束-1]。相同的多段线彼此之间的距离为 0，因此每条多段线之间的面积为 0.You 将检查 x 轴和 y 轴以检查多段线区域高度垂直的情况。我写了下面的代码减去 sample_at_point 部分，因为它来晚了，所有这部分需要做的是找到给定轴的 p1 中 p 的上下边界点，然后定义一个线方程并找到在哪里通过的点 p 位于该线方程和 return 值上。我明天会编辑这个答案，但我想我会 post 我现在拥有的。此解决方案适用于您在上面显示的多段线，但如果多段线与基本曲线不相似（例如：circle/any 曲线，其中 f(x) 可能有两个不同的值），它将失败。
def polydist(p1, p2):
x_area = area_between_squared(p1, p2, axis=0, value=1)
y_area = area_between_squared(p1, p2, axis=1, value=0)
return (x_area + y_area)**0.5
def sample_at_point(p1, p, axis, value):
"""
# There should be a fast way to do this,
# Finnd the bounding points that p is between,
# the bounding points are the max point < p and the min point > p
# these points form a line,
# find the value of p applied to that line formula.
"""
def area_between_squared(p1, p2, axis, value):
start = max(p1[0][axis], p2[0][axis])
start_penalty = start - min(p1[0][axis], p2[0][axis])
end = min(p1[-1][axis], p2[-1][axis])
end_penalty = max(p1[-1][axis], p2[-1][axis]) - end
# Getting late, may edit this later tomorrow with the code for this to work but feel free to implement the following idea below:
axis_points = [x[axis] for x in p1]
axis_points.extend([x[axis] for x in p2])
axis_points.sort()
prev_p1_v = sample_at_point(p1, axis_points[0], axis, value)
prev_p2_v = sample_at_point(p2, axis_points[0], axis, value)
prev_axis_point = axis_points[0]
axis_points.pop(0) # remove the first item
sum = 0
for e in axis_points:
p1_v = sample_at_point(p1, e, axis, value)
p2_v = sample_at_point(p2, e, axis, value)
point_c = p1_v - p2_v
point_b = prev_p1_v - prev_p2_v
area = 0.5 * (point_c + point_b) * (e - prev_axis_point)
sum += area
prev_p1_v = p1_v
prev_p2_v = p2_v
prev_axis_point = e
sum *= sum # square the result value, add the penalties since this difference should be positive
sum += start_penalty + end_penalty
return sum
感谢您的评论和回答。他们实际上引导我找到了一个使用 OpenCV 函数 pointPolygonTest 的好解决方案，它比我写得不好的 numpy 代码优化得更多。
方法是通过以相反顺序附加点将多段线变成等高线，然后遍历第一个数组的点并调用 pointPolygonTest 来获取距离。我发现平方距离有助于放大较小的差异。然后我取所有点的平均值。
代码如下：
import cv2
import numpy as np
def point_to_polyline_dist(p, polyline):
cnt = np.concatenate((polyline, polyline[::-1]))
return np.abs(cv2.pointPolygonTest(cnt, (int(p[0]),int(p[1])), True))
def polyline_dist(polyline1, polyline2):
return np.mean([point_to_polyline_dist(p, polyline2)**2 for p in polyline1])
p1 = np.array([[0,0], [5,5], [9,9]])
p2 = np.array([[0,0], [3,3], [6,6], [9,9]])
p3 = np.array([[0,0], [3,4], [6,7], [9,9]])
p4 = np.array([[0,0], [0,9]])
print(polyline_dist(p1, p2)) # 0.0
print(polyline_dist(p1, p3)) # 0.1666666666666667
print(polyline_dist(p1, p4)) # 35.333333333333336
这对我来说效果很好，因为我的折线有很多短线段。计算两个阵列之间的距离并添加距离可能更稳健，如下所示：
def polyline_dist_better(polyline1, polyline2):
dist_1to2 = np.mean([point_to_polyline_dist(p, polyline2)**2 for p in polyline1])
dist_2to2 = np.mean([point_to_polyline_dist(p, polyline1)**2 for p in polyline2])
return dist_1to2 + dist_2to1
希望对外面的人有所帮助！
我有两条折线（路径），每条线都由一个二维点数组表示。我想计算两者之间的距离或相似度分数。每个阵列中可能有不同数量的点。如果您要绘制折线并且它们直接在彼此之上，则距离应该为零。
p1 = np.array([[0,0], [5,5], [9,9]])
p2 = np.array([[0,0], [3,3], [6,6], [9,9]])
p3 = np.array([[0,0], [3,4], [6,7], [9,9]])
p4 = np.array([[0,0], [0,9]])
polyline_dist(p1, p2) # Should be 0 since the plots are identical
polyline_dist(p1, p3) # Should be small since the plots are close
polyline_dist(p1, p4) # Should be larger since the plots are much different
我尝试了一种方法，计算数组 1 中的每个点到数组 2 中的线段的距离并取最小距离，然后取所有点的平均值。这行得通，但对于具有数百个点的较长数组来说速度很慢。
欢迎提出任何建议！
您可以尝试找出每个绘图投射到 x 轴和 y 轴上的区域，然后比较该区域的交集。与具有两条曲线 f(x) 和 g(x) 的微积分类似，您可以使用从 (f(x) - g(x)) 的下限到上限的积分找到曲线之间的区域dx。如果您的行没有重叠 domains/codomains，您可能需要添加一些惩罚并从 p1[0] 和 p2[0] 的最大值开始，到 p1[-1] 和 p2[ 的最小值结束-1]。相同的多段线彼此之间的距离为 0，因此每条多段线之间的面积为 0.You 将检查 x 轴和 y 轴以检查多段线区域高度垂直的情况。我写了下面的代码减去 sample_at_point 部分，因为它来晚了，所有这部分需要做的是找到给定轴的 p1 中 p 的上下边界点，然后定义一个线方程并找到在哪里通过的点 p 位于该线方程和 return 值上。我明天会编辑这个答案，但我想我会 post 我现在拥有的。此解决方案适用于您在上面显示的多段线，但如果多段线与基本曲线不相似（例如：circle/any 曲线，其中 f(x) 可能有两个不同的值），它将失败。
def polydist(p1, p2):
x_area = area_between_squared(p1, p2, axis=0, value=1)
y_area = area_between_squared(p1, p2, axis=1, value=0)
return (x_area + y_area)**0.5
def sample_at_point(p1, p, axis, value):
"""
# There should be a fast way to do this,
# Finnd the bounding points that p is between,
# the bounding points are the max point < p and the min point > p
# these points form a line,
# find the value of p applied to that line formula.
"""
def area_between_squared(p1, p2, axis, value):
start = max(p1[0][axis], p2[0][axis])
start_penalty = start - min(p1[0][axis], p2[0][axis])
end = min(p1[-1][axis], p2[-1][axis])
end_penalty = max(p1[-1][axis], p2[-1][axis]) - end
# Getting late, may edit this later tomorrow with the code for this to work but feel free to implement the following idea below:
axis_points = [x[axis] for x in p1]
axis_points.extend([x[axis] for x in p2])
axis_points.sort()
prev_p1_v = sample_at_point(p1, axis_points[0], axis, value)
prev_p2_v = sample_at_point(p2, axis_points[0], axis, value)
prev_axis_point = axis_points[0]
axis_points.pop(0) # remove the first item
sum = 0
for e in axis_points:
p1_v = sample_at_point(p1, e, axis, value)
p2_v = sample_at_point(p2, e, axis, value)
point_c = p1_v - p2_v
point_b = prev_p1_v - prev_p2_v
area = 0.5 * (point_c + point_b) * (e - prev_axis_point)
sum += area
prev_p1_v = p1_v
prev_p2_v = p2_v
prev_axis_point = e
sum *= sum # square the result value, add the penalties since this difference should be positive
sum += start_penalty + end_penalty
return sum
感谢您的评论和回答。他们实际上引导我找到了一个使用 OpenCV 函数 pointPolygonTest 的好解决方案，它比我写得不好的 numpy 代码优化得更多。
方法是通过以相反顺序附加点将多段线变成等高线，然后遍历第一个数组的点并调用 pointPolygonTest 来获取距离。我发现平方距离有助于放大较小的差异。然后我取所有点的平均值。
代码如下：
import cv2
import numpy as np
def point_to_polyline_dist(p, polyline):
cnt = np.concatenate((polyline, polyline[::-1]))
return np.abs(cv2.pointPolygonTest(cnt, (int(p[0]),int(p[1])), True))
def polyline_dist(polyline1, polyline2):
return np.mean([point_to_polyline_dist(p, polyline2)**2 for p in polyline1])
p1 = np.array([[0,0], [5,5], [9,9]])
p2 = np.array([[0,0], [3,3], [6,6], [9,9]])
p3 = np.array([[0,0], [3,4], [6,7], [9,9]])
p4 = np.array([[0,0], [0,9]])
print(polyline_dist(p1, p2)) # 0.0
print(polyline_dist(p1, p3)) # 0.1666666666666667
print(polyline_dist(p1, p4)) # 35.333333333333336
这对我来说效果很好，因为我的折线有很多短线段。计算两个阵列之间的距离并添加距离可能更稳健，如下所示：
def polyline_dist_better(polyline1, polyline2):
dist_1to2 = np.mean([point_to_polyline_dist(p, polyline2)**2 for p in polyline1])
dist_2to2 = np.mean([point_to_polyline_dist(p, polyline1)**2 for p in polyline2])
return dist_1to2 + dist_2to1
希望对外面的人有所帮助！