python - 检查轮廓的任何点是否与一条线相交的有效方法是什么？

Question

注意:虽然这个问题Finding intersection between straight line and contour解决了类似的问题，我的偏好是尽可能不要引入另一个依赖项。

---

我有一张图像，其中检测到多条线和多个轮廓。例如，下图检测到三条线和两个轮廓。我的任务是找出哪些轮廓有一条线与它们相交。在这种情况下，只有一个轮廓与一条线相交。

我的收藏如下。

lines = cv2.HoughLines(img,1,np.pi/180, 200)
contours, _ = cv2.findContours(edges,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)

我最初的想法是计算质心坐标与直线的距离，但可能存在轮廓非常大的边缘情况，因此这不可靠，因为质心距离直线太远。

也许找到轮廓中所有可能的坐标，遍历每个点并检查该点到直线的距离是否为零？

我写了一些代码来计算点和线之间的距离:

  def shortest_distance_to_line(point, line):
      x, y = point
      rho, theta = line
      a = np.cos(theta)
      b = np.sin(theta)
      x0 = a*rho
      y0 = b*rho
      x1 = int(x0 + 10000*(-b))
      y1 = int(y0 + 10000*(a))
      x2 = int(x0 - 10000*(-b))
      y2 = int(y0 - 10000*(a))

      if theta == 0: # vertical line
          return abs(x - x1)
      else:
          c = (y2 - y1) / (x2 - x1)
          return abs(a*x + b*y + c) / math.sqrt(a**2 + b**2)

检测具有相交线的轮廓的有效方法是什么？

如果遍历每个轮廓内的每个点是一种有效的方法，我该如何生成轮廓的所有点？

Answer 1

平面中直线方程的形状为 $ax+by+c=0$，其中 (x,y) 是平面中的一个点。这条线将平面分成两个半平面，如果我们省略这条边界线，(开放的)半平面由以下方程式给出:

ax + by + c > 0斧 + 通过 + c < 0

我假设要跨越的域是连接的。

然后我将开始蒙特卡罗随机生成点，并每次记录函数 (x,y) -> ax + by + c 的符号。 (可能会出现一些错误。)在第一次检测到两个标志后，我们就有了一个交叉点。否则，经过多次试验后，我们会停下来并认为不存在交集。

如果“域”只有几个点，我们当然会循环，不需要蒙特卡洛。 (如果我们已经有了边界点，我们可以限制它们。)