0 votes

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.

asked Jun 7, 2018 in Engine by Diet Estus (1,496 points)

1 Answer

+1 vote

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.

answered Jun 7, 2018 by Ertain (1,257 points)
edited Jun 7, 2018 by Ertain
Welcome to Godot Engine Q&A, where you can ask questions and receive answers from other members of the community.

Please make sure to read How to use this Q&A? before posting your first questions.