检测两条曲线交点的上游和下游点

Question

我有两条曲线，由

定义

X1=[9, 10.5, 11, 12, 12, 11, 10, 8, 7, 7]
Y1=[-5, -3.5, -2.5, -0.7, 1, 3, 4, 5, 5, 5]
X2=[5, 7, 9, 9.5, 10, 11, 12]
Y2=[-2, 4, 1, 0, -0.5, -0.7, -3]

它们相互交叉

通过我正在使用的系统代码中编写的函数，我可以获得交点的坐标。

loop1=Loop([9, 10.5, 11, 12, 12, 11, 10, 8, 7, 7],[-5, -3.5, -2.5, -0.7, 1, 3, 4, 5, 5, 5])
loop2=Loop([5, 7, 9, 9.5, 10, 11, 12], [-2, 4, 1, 0, -0.5, -0.7, -3])
x_int, y_int = get_intersect(loop1,loop2)
Intersection = [[],[]]
Intersection.append(x_int)
Intersection.append(y_int)

对于两条曲线，我需要找到由 (x_int, y_int).

标识的交点的上游和下游点

我试过的是这样的：

for x_val, y_val, x, y in zip(Intersection[0], Intersection[1], loop1[0], loop1[1]):
    if  abs(x_val - x) < 0.5 and abs(y_val - y) < 0.5:
        print(x_val, x, y_val, y)

问题是结果受到我决定的增量（在本例中为 0.5）的极大影响，这给了我错误的结果，特别是如果我使用更多的小数（这实际上是我的情况）。

我怎样才能使循环更健壮并真正找到所有且仅找到交叉路口上游和下游的点？

非常感谢您的帮助

Answer 1

TL;TR: 遍历折线段并测试 if the intersection is betwwen the segment end points.

一种更稳健的（比 OP 中的“delta”）方法是找到包含交点（或一般给定点）的折线段。该细分市场应该是 IMO 的一部分 get_intersect 功能，但如果您无权访问它，则必须自己搜索该细分市场。

由于舍入误差，给定的点并不完全位于线段上，所以你仍然有一些 tol 参数，但结果应该是“almost-insensitive”到它的（非常低) 值。

该方法使用简单的几何，即点积和叉积及其几何意义：

a

b

dot product 除以 |a| 是 b 在 a 方向上的投影（长度） .再次除以 |a| 将值归一化到范围 [0;1]
cross product of a and b is the area of the parallelogram having a and b as sides。将它除以长度的平方使其成为距离的一些无量纲因子。如果一个点恰好位于线段上，则叉积为零。但是浮点数需要一个小的公差。

X1=[9, 10.5, 11, 12, 12, 11, 10, 8, 7, 7]
Y1=[-5, -3.5, -2.5, -0.7, 1, 3, 4, 5, 5, 5]
X2=[5, 7, 9, 9.5, 10, 11, 12]
Y2=[-2, 4, 1, 0, -0.5, -0.7, -3]

x_int, y_int = 11.439024390243903, -1.7097560975609765

def splitLine(X,Y,x,y,tol=1e-12):
    """Function
    X,Y ... coordinates of line points
    x,y ... point on a polyline
    tol ... tolerance of the normalized distance from the segment
    returns ... (X_upstream,Y_upstream),(X_downstream,Y_downstream)
    """
    found = False
    for i in range(len(X)-1): # loop over segments
        # segment end points
        x1,x2 = X[i], X[i+1]
        y1,y2 = Y[i], Y[i+1]
        # segment "vector"
        dx = x2 - x1
        dy = y2 - y1
        # segment length square
        d2 = dx*dx + dy*dy
        # (int,1st end point) vector
        ix = x - x1
        iy = y - y1
        # normalized dot product
        dot = (dx*ix + dy*iy) / d2
        if dot < 0 or dot > 1: # point projection is outside segment
            continue
        # normalized cross product
        cross = (dx*iy - dy*ix) / d2
        if abs(cross) > tol: # point is perpendicularly too far away
            continue
        # here, we have found the segment containing the point!
        found = True
        break
    if not found:
        raise RuntimeError("intersection not found on segments") # or return None, according to needs
    i += 1 # the "splitting point" has one higher index than the segment
    return (X[:i],Y[:i]),(X[i:],Y[i:])

# plot
import matplotlib.pyplot as plt
plt.plot(X1,Y1,'y',linewidth=8)
plt.plot(X2,Y2,'y',linewidth=8)
plt.plot([x_int],[y_int],"r*")
(X1u,Y1u),(X1d,Y1d) = splitLine(X1,Y1,x_int,y_int)
(X2u,Y2u),(X2d,Y2d) = splitLine(X2,Y2,x_int,y_int)
plt.plot(X1u,Y1u,'g',linewidth=3)
plt.plot(X1d,Y1d,'b',linewidth=3)
plt.plot(X2u,Y2u,'g',linewidth=3)
plt.plot(X2d,Y2d,'b',linewidth=3)
plt.show()

结果：

检测两条曲线交点的上游和下游点

Detect points upstream and downstream of an intersection between two curves

python

loops

intersection

pycharm

set-intersection