Generate heatmap image of lines

Question

I have this graph, which contains a lot of lines defined by 2 points. Now I would like to generate a heatmap. The result should be something similar to http://docs.ggplot2.org/current/geom_raster.html, except the heat of each cell is defined as how many lines intersect it. The result should be a numpy array for PIL.

I considered two things so far, one would be to iterate over all lines and grids and calculate the distance from the two with this and if the distance is smaller than between two cells, it's in there. This is possible because in the actual data, the lines have a certain minimum length.

Another possibility to intersect each line with each grid cell and check if it's in there. But that sounds expensive, but more accurate. Along the lines that you check each horizontal/vertical line for intersection and check in which cell it is.

Data sample. It's an Array[Array[Int, Int]]. Every pair of sub-arrays designates a line.

Answer 1

This sounds like what you want:

How to test if a line segment intersects an axis-aligned rectange in 2D?

In particular the top answer: https://stackoverflow.com/a/293052/66349

In summary:

• check if both points of the line are to one side of the box (left, right, above, below) - if so, there is no intersection
• otherwise, check if all four corners of the box are on the same side of the line - if they are not, then you have an intersection

Generally speaking, it might be faster to iterate over the line segments and test only a subset of heat map boxes (perhaps boxes that fall into the larger box defined by the two points of the line); rather than iterating over the heat map boxes and checking every line for intersections.