What's the easiest way to check if two of any lines in a big array of lines intercept?
Context: Im trying to implement a path finding algorithm, and to generate the nodes and lines, i'm generating random nodes, then lines between these nodes. But i want a new node to be created at any point that two lines intercept.
Obviously i could just loop through the array of lines every time i create a new line and do a collision detection on every item in the array, but that would be quite slow. So wondering if anyone has a better solution.
The best solution depends on how big your array is and how static it is.
Looping over the array each time can actually be reasonably fast if you exploit parallelism. Up to a certain size.
The go to data structure for collision detection between large numbers of objects is an Axis Aligned Bounding Box Tree. AABB Tree. You'll find lots of examples and code online for all languages. https://en.wikipedia.org/wiki/Bounding_volume_hierarchy