Even these calculations are going to take a while if you are comparing every line segment to every other one. The binary tree is a very cool way to do it, and this kind of thing is done quite a bit in 3D (Z-Sorting and use of trees, for example quad trees which will break down the rendering problem by dividing cubes of space into recursively smaller areas to cover). But maybe there is a quicker way.

I think you might be able to simplify this problem by preprocessing your data set. You shouldn't be trying to do some 200 million intersection tests. A (human generated) map is usually made of lots of relatively small line segments, mainly because it has to convey a good amount of information while remaining readable. I would start by giving every line segment an id number and put them in a database (or flat file, hash is fine). You should be able to quickly find what length line segment is most popular and what range of lengths around that covers say 80% of all the lines. Also, if you search starting with the longer ones, it should save you time, that is if long segments intersect more lines than do short segments.

This characterization would give you a guide to creating a grid of cells across the map, so that you can sort your segments by spatial distribution, in effect reducing the number of pairs. It is possible that you could define some bounding boxes of your own (say around cities?) which would do this efficiently for many of the longer line segments as well.

You can probably also do away with the bounding box calls and that epsilon stuff. You can also mark each segment in the database which has already been found to intersecting some other line, in effect taking that line segment out of circulation.

One thing to note is your definition of intersection. I think the algorithm below will find two lines which touch at their endpoints to be intersecting lines, but your example of the lake seems to indicate that such a pair of line segments should not be said to intersect. In that case you can eliminate a lot of computation by doing such a test first.

There is another approach which might be interesting. You could select a minimum resolution which would be needed to represent your map reasonably well, and provide a two dimensional array to represent this canvas. By drawing all the segments on this map with a routine which draws differently upon intersection, you can "download" the final answer by simply reading off the canvas at the end. Possibly you could do something with C-based drawing functions and various paint modes (and GIMP might be cool for that indeed, using an additive drawing mode) or collision detection functions (say in OpenGL), but I'm thinking here of just writing a line segment rendering function in Perl which "draws" to a data structure.

The neat part is that each "pixel", being an array element, could contain a list of the id numbers of all lines which crossed that pixel, which would provide a very rich output. You only have to execute the drawing code 14000 times, which sounds pretty good compared to 200 million of anything, but I'm not sure which approach is faster. Perhaps the most interesting thing is that you can run it at arbitrary resolutions, so you could for example run it once at a low resolution, then divide the canvas into an arbitrary number of cells and then perhaps use mathematical approach afterwards, or perhaps skip making cells and just use math to check the questionable pairs.

The pixel rendering approach is more interesting if you can grasp the entire image visually in a gestalt, for example by using colored filters. You might like to check out Gimp even just for fun since it is quite Perl-compatible.

Lastly I think there is one more approach to consider, if this is a one-shot job. If you just draw all the lines and open up the image in Gimp or Photoshop, you can use a combination of using the magic wand, paint bucket, and zoom tool to try solving this by hand.

You can also assign each line a unique RGB color combination and read its id with an eye-dropper (or Perl call if using Gimp).

Finding the exact point of intersection is too much work if
all we care about is whether two lines intersect at all. 
The intersection, if any, can be found by examining the 
signs of the two cross products 
(p2 - p0) × (p1 - p0) and (p3 - p0)× (p1 - p0).
The line_intersect() subroutine returns a simple true or
false value indicating whether two lines intersect:

# line_intersect( $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 )
# Returns true if the two lines defined by these points intersect.
# In borderline cases, it relies on epsilon to decide.
 sub line_intersect {
  my ( $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ) = @_;
  my @box_a = bounding_box( 2, $x0, $y0, $x1, $y1 );
  my @box_b = bounding_box( 2, $x2, $y2, $x3, $y3 );
  # If even the bounding boxes do not intersect, give up right now.
  return 0 unless bounding_box_intersect( 2, @box_a, @box_b );
  # If the signs of the two determinants (absolute values or lengths
  # of the cross products, actually) are different, the lines
  # intersect.
  my $dx10 = $x1 - $x0;
  my $dy10 = $y1 - $y0;
  my $det_a = determinant( $x2 - $x0, $y2 - $y0, $dx10, $dy10 );
  my $det_b = determinant( $x3 - $x0, $y3 - $y0, $dx10, $dy10 );
  return 1 if $det_a < 0 and $det_b > 0 or
  $det_a > 0 and $det_b < 0;
  if ( abs( $det_a ) < epsilon ) {
   if ( abs( $det_b ) < epsilon ) {
    # Both cross products are "zero".
    return 1;
   } elsif (abs($x3-$x2)<epsilon and abs($y3-$y2)<epsilon){
     # The other cross product is "zero" and
     # the other vector (from (x2,y2) to (x3,y3))
     # is also "zero".
    return 1;
   }
  } elsif ( abs( $det_b < epsilon ) ) {
  # The other cross product is "zero" and
  # the other vector is also "zero".
  return 1 if abs( $dx10 ) < epsilon and abs( $dy10 ) < epsilon;
 }
 return 0; # Default is no intersection.
}

# determinant( $x0, $y0, $x1, $y1 )    [from p. 432]
# Computes the determinant given the four elements of a matrix
# as arguments.
#
sub determinant { $_[0] * $_[3] - $_[1] * $_[2] }
[download]

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.