How to check for array intersection?

Question

I have two arrays, each containing a few thousand Vector2s.

I want to find out if they intersect, but don't care about the intersection itself.

Currently, I do it this way.

func intersects(array1, array2):
    var intersect = false
    for item in array1:
        if item in array2:
            intersect = true
            break
    return intersect

I do not feel like this is the most optimal way to do it. In fact, I am experiencing performance issues doing it this way.

What is the fastest way to check arrays for intersection?

I am open to using a different data type, like dictionaries. I am even open to using a different type of object for my elements, for example, using subarrays rather than Vector2s.

Answer 1

A way you could do it is like this:

func intersect(array1, array2):
  var intersection = false
  for item in array1:
    if array2.has(item):
      intersection = true
      break
  return intersection

A little different from your code. The has() method may speed things up.

You could even get more sophisticated, and return the elements which do intersect:

func intersect(arra1, array2):
  var intersection = []
    for item in array1:
      if array2.has(item):
        intersection.append(item)
  return intersection

Hope this helps.