3

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?

binarymason
  • 1,351
  • 1
  • 14
  • 31
  • Are you looking for an analytical solution or does it have to have pixel precision? – norok2 Oct 11 '19 at 11:35
  • 1
    Possible duplicate of [Finding intersection between straight line and contour](https://stackoverflow.com/questions/22232311/finding-intersection-between-straight-line-and-contour) – norok2 Oct 11 '19 at 11:39
  • @norok2 Ideally, out of list of contours, I could return a list of indices of contours that have an intersection. – binarymason Oct 11 '19 at 11:39

1 Answers1

2

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.)

dan_fulea
  • 541
  • 3
  • 5
  • 2
    Instead of checking random points on the interior, just check all the vertices of the contour's boundary; if they have the same sign, the shape is not intersected by the line. (This works even if the contour is not convex.) – alexis Oct 11 '19 at 11:52
  • 1
    @alexis yes, if we have a boundary, then it is enough to check only that boundary. If we have moreover a convex set with known vertices, then it is enough to check these extremal points only. (+1 for your comment.) – dan_fulea Oct 11 '19 at 12:02
  • Nice, I think what I can do is just get the bounding box for each contour so I'm only checking four points against the line. Will experiment with this and report back. Thank you, dan_fulea and alexis! – binarymason Oct 11 '19 at 13:22
  • 1
    @binarymason note that the bounding box could give you false positives (it's easy to draw an example where the boundary box overlaps, but the contour does not); but it will never miss a true positive. – alexis Oct 14 '19 at 07:51
  • This answer (and follow-up) is all basic analytic geometry, by the way, so if you have more tasks along these lines, grab a book. It's amazing (and very satisfying :-)) how much geometry can be captured in numbers. – alexis Oct 14 '19 at 07:53
  • @alexis I'll take you up on that! You have any geometry books you would recommend? – binarymason Oct 14 '19 at 20:47
  • @binarymason Can't say I do, sorry. Really it depends on your own "mathematical maturity", and on whether you're prepared to spring for a real book (recommended) or just hope for an online resource. – alexis Oct 17 '19 at 10:03