在公差范围内,确定两个线段是否属于同一线段的最有效方法是什么？

Question

编辑:更改了标题.我不太感兴趣的是两个部分是相同的,而是,如果它们彼此共线,在一定的容差范围内.如果是这样,那么这些行应该作为单个段聚集在一起.

编辑:我想这是一个简短的说法:我试图以有效的方式将类似的线段聚集在一起.

说我有线段f (fx0, fy0)和(fx1, fy1)和g (gx0, gy0)和(gx1, gy1)

它们来自计算机视觉算法边缘检测器,在某些情况下,两条线基本相同,但由于像素容差而被计为两条不同的线.

有几种情况

• f并g分享完全相同的端点,例如:f = (0,0), (10,10) g = (0,0), (10,10)
• f并g分享大致相同的端点,大致相同的长度,例如:f = (0,0.01), (9.95,10) g = (0,0), (10,10)
• f是一个子集g,意味着它的端点属于g段并与段具有相同的斜率g.想象一下粗略绘制的线条,其中笔来回移动以使其变厚.例如:f = (4.00, 4.02), (9.01, 9.02) g = (0,0), (10,10)

以下不会被视为相同:

• f并且g有一个超过一定的斜率差异tolerance
• f并且g可以具有相同的斜率但是相隔一段距离tolerance,即平行线
• f并且g在同一平面和相同的斜率上,但根本不重叠...即虚线内的一组段.

判断它们是否相同的最简单方法是if gx1 - fx1 <= tolerance(重复其他三个点),但在某些情况下,line f可能比line短g(再次,因为像素差异和/或差的照片扫描).

那么将两个段转换为极坐标并比较角度会更好吗？在这种情况下,两个rho将在容差范围内.但是你必须确保两个线段具有相同的"方向",这在笛卡尔坐标或极坐标中计算是微不足道的.

所以这很容易找到一种方法,但我只是想知道是否有一种更清洁的方式,基于我早已忘记的线性代数？

Answer 1

您的问题有两个：您想要比较长度差异和角度差异。要计算长度差，您需要将第一行的长度除以第二行的长度。

要获取角度差异，您可以使用atan我最喜欢的 or ：

angle = acos(abs((u dot v)/(u.length * v.length)))

希望这有帮助。抱歉之前的错误回答。

旧答案：

这里有一个想法：为什么不将两条线段的起点和终点的差异与其中一条线的总长度进行比较？那么你的差异函数将类似于：

def difference(Line l1, Line l2):
    # Distance between first point on first line and first point on second line
    first_point_diff = (Line(l1.x1, l2.x1, l1.y1, l2.y1).length())

    # Distance between first point on first line and first point on second line
    second_point_diff = (Line(l1.x2, l2.x2, l1.y2, l2.y2).length())

    return (first_point_diff + second_point_diff)/l1.length()

此函数将返回两条线之间的“差异”作为第一条线总长度的一部分。