Как эффективный способ проверить, пересекается ли какая-либо точка контура линией?

Question

Примечание: Хотя этот вопрос Поиск пересечения между прямой и контуром решает аналогичную проблему, я предпочел бы не использовать другую зависимость, если это возможно.

---

У меня есть изображение, где я обнаружил несколько линий и несколько контуров. В качестве примера, изображение ниже имеет три обнаруженные линии и два обнаруженных контура. Моя задача - найти, какие контуры имеют линию, пересекающую их. В этом случае только один контур имеет линию, пересекающую его.

Ниже приведены коллекции, которые у меня есть.

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

Мой первоначальный мыслительный процесс состоял в том, чтобы вычислить расстояние координат центроида до линии, но могут быть крайние случаи, когда есть очень большие контуры, так что это будет ненадежным, поскольку центроид будет слишком далеко от линии.

Может быть, найти все возможные координаты в контуре, зациклить каждую точку и проверить, равно ли расстояние от этой точки до линии?

Я написал некоторый код для вычисления расстояния между точкой иline:

  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 ax + by + c <0 </p>

Я предполагаю, что домены, которые должны быть пересечены, связаны между собой.

Затем я бы начал случайную генерацию точек по методу Монте-Карло и записал бы знак функции (x, y) -> топор + на + с каждый раз. (Некоторые ошибки могут быть реализованы.) После первого обнаружения обоих признаков у нас есть пересечение. Иначе, после ряда испытаний мы останавливаемся и считаем, что пересечения нет.

Если у «доменов» есть только несколько точек, мы, конечно, делаем цикл, Монте-Карло не нужен. (И мы можем ограничиться граничными точками, если они у нас уже есть.)