Algorithm for finding intersections of straight li

Question

there's this problem about line crossings I saw somewhere and was trying to solve.

There's a 64x64 grid of 8 bit pixels and it has a bunch of 1 pixel wide vertical and horizontal lines of different colors on it. All parallel lines have at least one space between them. The problem is to find the number of line crossings that each set of colored lines makes (e.g. all green line crossings count towards one sum). And find which set of lines had the fewest amount of crossings. Also, all vertical lines of a color are the same size and all horizontal lines of the same color are the same size.

I had a few ideas but they all seem pretty inefficient. It would involve going through every pixel in the grid, if you run into a color determine if it's a vertical or horizontal line, and then go in the direction of the line all the while checking adjacent sides for different colors.

I'm trying to decide if first counting the length of the horizontal and vertical lines for each color would speed up the process. Do you guys have any brilliant ideas for how to do this?

Here are two examples. Notice that parallel lines always have a space in between them.

Answer 1

Simple way to find straight intersection

def straight_intersection(straight1, straight2):
    p1x = straight1[0][0]
    p1y = straight1[0][1]
    p2x = straight1[1][0]
    p2y = straight1[1][1]
    p3x = straight2[0][0]
    p3y = straight2[0][1]
    p4x = straight2[1][0]
    p4y = straight2[1][1]
    x = p1y * p2x * p3x - p1y * p2x * p4x - p1x * p2y * p4x + p1x * p2y * p3x - p2x * p3x * p4y + p2x * p3y * p4x + p1x * p3x * p4y - p1x * p3y * p4x
    x = x / (p2x * p3y - p2x * p4y - p1x * p3y + p1x * p4y + p4x * p2y - p4x * p1y - p3x * p2y + p3x * p1y)
    y = ((p2y - p1y) * x + p1y * p2x - p1x * p2y) / (p2x - p1x)
    return (x, y)

Answer 2

Scanning a pixel grid is actually very fast and efficient. It's standard for computer vision systems to do that kind of thing. A lot of these scans produce a FIR filtered versions of images that emphasize the kinds of details being searched for.

The main technical term is "convolution" (see http://en.wikipedia.org/wiki/Convolution). I think of it as a kind of weighted moving average, though weights can be negative. The animations on Wikipedia show convolution using a rather boring pulse (it could have been a more interesting shape), and on a 1D signal (like a sound) rather than a 2D (image) signal, but this is a very general concept.

It's tempting to think that something more efficient can be done by avoiding calculating that filtered version in advance, but the usual effect of that is that because you haven't precalculated all those pixels, you end up calculating each pixel several times. In other words, think of the filtered image as a lookup-table based optimisation, or a kind of dynamic programming.

Some particular reasons why this is fast are...

1. It is very cache-friendly, so accesses memory efficiently.
2. It is exactly the kind of thing that vector instructions (MMX, SIMD etc) are designed to support.
3. These days, you may even be able to offload the work onto your graphics card.

Another advantage is that you only need to write one image-filtering convolution function. The application-specific part is how you define the filter kernel, which is just a grid of weight values. In fact you probably shouldn't write this function yourself at all - various libraries of numeric code can supply highly optimised versions.

For handling the different colours of lines, I'd simply generate one greyscale image for each colour first, then filter and check each separately. Again, think of this as the optimisation - trying to avoid generating the separate images will likely result in more work, not less.

• On second thoughts, I may have understood the requirement. It may make more sense to generate a black-and-white image from the black-and-colours, filter that, and the find all intersections from that. Once you have the intersection points, then refer back to the original black-and-colours image to classify them for the counting. The filtering and intersection-finding remains very efficient per pixel. The classifying isn't so efficient per pixel, but is only done at a few points.

You could do a convolution that based on the following FIR filter kernel...

.*.
***
.*.

Dots are zeros (pixel irrelevant) or, possibly, negative values (prefer black). Asterisks are positive values (prefer white). That is, look for the three-by-three crosses at the intersections.

Then you scan the filtered result looking for greyscale pixels that are brighter than some threshold - the best matches for your pattern. If you really only want exact crossing points, you may only accept the perfect-match colour, but you might want to make allowances for T-style joins etc.

Answer 3

On the grid with your lines look for 2 types of 3x3 squares:

1).a.  2).a.
  bab    bbb
  .a.    .a.

"." represents background (always black?), "a" and "b" represent 2 different colors (also different from the background color). If found, bump up by 1 the counts for a-colored line intersections and b-colored line intersections.

Answer 4

Is your only input the 64x64 grid? If so, then you're looking at something with a 64x64 flavor, since there's no other way to ensure you've discovered all the lines. So I will assume you're talking about optimizing at the operation level, not asymptotically. I seem to remember the old "Graphics Gems" series had lots of examples like this, with an emphasis on reducing instruction count. I'm better at asymptotic questions myself, but here are a few small ideas:

The grid cells have the property that grid[i,j] is a green intersection if

(grid[i,j] == green)
&&
(grid[i+1,j]==green || grid[i-1,j]==green)
&&
(grid[i,j+1]==green || grid[i, j-1]==green)

So you can just scan the array once, without worrying about explicitly detecting horizontal and vertical lines ... just go through it using this relationship and tally up intersections as you find them. So at least you're just using a single 64x64 loop with fairly simple logic.

Since no two parallel lines are directly adjacent, you know you can bump your inner loop counter by 2 when you pass a populated cell. That'll save you a little work.

Depending on your architecture, you might have a fast way to AND the whole grid with offset copies of itself, which would be a cool way to compute the above intersection formula. But then you still have to iterate through the whole things to find the remaining populated cells (which are the intersection points).

Even if you don't have something like a graphics processor that lets you AND the whole grid, you can use the idea if the number of colors is less than half of your word size. For example, if you have 8 colors and a 64-bit machine, then you can cram 8 pixels into a single unsigned integer. So now you can do the outer loop comparison operation for 8 grid cells at a time. This might save you so much work it's worth doing two passes, one for a horizontal outer loop and one for a vertical outer loop.