Find Intersection of 2 curves

Garry K

Does anyone have a simple solution to finding an intersection between 2 curves?

Currently I am traversing each edge of one of the curves and testing intersection on each edge of the other curve.

CAUL

You can use a simple space hash. I attached a piece of code in this thread solving the similar problem of finding intersecting faces. The principle is the same.

Garry K

The curves I am talking about do not have many edges. Also I already know which end of the curves is closest to the intersection from an iteration point of view.

This works quickly - I was hoping to reduce the compexity.


  # finds the intersection between 2 curves
  # returns [pt,cout_1,count_2] if there is a point
  # returns [nil,-1,-1] if there isn't a point
  # 
  # for best performance consider the following
  # array_1 should have the most points
  # caller could reverse array_1 if intersection is more likely at the end
  # caller could reverse array_2 if intersection is more likely at the end
  # --------------------------
  #           intersect_curves
  # --------------------------
  def intersect_curves(array_1, array_2)
      count_1 = 0
      loops = 0
      last_1 = []

      array_1.each {|pt_1|
        if (count_1 > 0) # second iteration - last_1 will have a value
          count_2 = 0
          last_2 = []

          array_2.each {|pt_2|
              if ( count_2 > 0 )  # second iteration - last_2 will have a value
                # now we can check intersection
                loops += 1
                line_1 = [pt_1, last_1]
                line_2 = [pt_2, last_2]
                pt = Geom.intersect_line_line(line_1, line_2)

                # if point is on BOTH edges then we have a true intersection
                if(point_on_line(pt,line_1) && point_on_line(pt,line_2))
                  return [pt,count_1, count_2, loops] 
                end
              end

            count_2 += 1
            last_2 = pt_2
          }
        end

        count_1 += 1
        last_1 = pt_1
      }

      [nil,-1,-1, loops]
  end

CAUL

From a time complexity perspective I think the problem is inherently O(n^2) (which means that your code can't be any simpler), also, if the curves have few segments and you already know enough to throw away half of them, then I would say your code is probably close to optimal. In general, the simplest way to gain speed is to use bounding boxes in various ways like reducing the input to segments in the bounding box intersection between the curves and so on, however, there are constant costs associated with this so it may not be a gain on small inputs.