Finding the cross points of vertical and horizontal lines (speeding up the loop)

I have a series of horizontal lines and vertical lines, and I need to find all the cross points of these lines. I do this with

$x_lines[$x][]=array($y1,$y2); // already sorted as $y1<$y2  $y_lines[$y][]=array($x1,$x2);    foreach($x_lines as $x=>$a){      foreach($a as $yy){          foreach($y_lines as $y=>$b){              foreach($b as $xx){                  if($x<$xx[0] || $x>$xx[1] || $y<$yy[0] || $y>$yy[1]){continue;}                  $crosses[]=array($x,$y);              }          }      }  }  

The problem is the performance/speed. There are thousands of lines to be tested, and we have four loops. I look for a tricky approach to find the cross points quickly.

The code is in PHP, but any solution in other programming language is sufficient. I look for the logic rather than the code.

https://stackoverflow.com/questions/66073217/finding-the-cross-points-of-vertical-and-horizontal-lines-speeding-up-the-loop February 06, 2021 at 11:06AM