What is an efficient way to check if any point of a contour is intersected by a line?

user_5381605 0
Viewed 495

Note: While this question Finding intersection between straight line and contour addresses a similar problem, my preference would be to not pull in another dependency if possible.

I have an image where I have detected multiple lines and multiple contours. As an example, the image below has three lines detected and two contours detected. My task is to find which contours have a line intersecting them. In this case, only one contour has a line intersecting it.

example

The collections that I have are below.

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

My original thought process was to calculate the distance of the centroid coordinates to the line, but there might be edge cases where there are very large contours, so that would be unreliable since the centroid would be too far away from the line.

Maybe find all possible coordinates in the contour, loop over each point and check if the distance of that point to the line is zero?

I wrote some code to calculate the distance between a point and a 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)

What is an efficient way to detect contours that have lines intersecting them?

If looping over each of the points inside of each contours is an efficient approach, how do I generate all points for a contour?

opencv python
1 Answers

The equation of a line in the plane is of the shape $ax+by+c=0$, where (x,y) is a point in the plane. The line separates the plane in two half-planes, and if we omit this boundary line, the (open) half planes are given by the equations:

ax + by + c > 0 ax + by + c < 0

I assume the domains to be crossed to be connected.

Then i would start a Monte-Carlo random generation of points, and record the sign of the function (x,y) -> ax + by + c each time. (Some error can be implemented.) After a first detection of both signs we have an intersection. Else, after a number of trials we stop and consider there is no intersection.

If the "domains" have only a few points, we loop of course, no Monte-Carlo is needed. (And we can restrict to boundary points, if we have them already.)

user_102425950
Related