Efficient Algorithms for Counting Line Crossings on a Grid

[Bob Busby]

Hello, 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?

 

[MarcoD]

I would use a mask to first find out what the lines are, and then a second mask to find the intersections. That would give a O(2n) algorithm, which isn't nice, but at least linear. I doubt you'll find anything faster, though you can probably get rid of the 2 factor by merging the two approaches.

(This is with the assumption that it is mostly a simple problem with vertical and horizontal lines and other space only.)

 

[Bob Busby]

Can you give me an example of these masks? The only kind of masking I know of is bit masking and I'm not following how to use them here. Thanks for the idea, though!

EDIT: By the way, there are only 7 different colors.

 

[schip666!]

I did this a long time ago and remember that the actual algorithm was impenetrable...

If you can deal with Java, the Line.java:intersect() method is what you want:
http://www.etantdonnes.com/DATA/vecmap.zip

Otherwise the original information was from:
O'Rourke "Computational Geometry"
http://cs.smith.edu/~orourke/books/ftp.html

 

[LudusRex]

I am familiar with a variety of algorithms and techniques that can be used to solve problems such as this one. One approach that may be useful in this scenario is the Bresenham's line algorithm, which is commonly used in computer graphics to draw straight lines efficiently. This algorithm works by calculating the points along a line and checking if they intersect with any other lines on the grid. By using this algorithm, you could potentially reduce the number of checks needed and improve efficiency in finding line crossings.

Another approach could be to use a data structure, such as a grid or a graph, to store information about the lines and their intersections. This would allow for faster access and manipulation of the data, making the process more efficient.

In addition, as you mentioned, counting the length of the lines for each color could also help in speeding up the process. This information could be used to determine the starting and ending points of each line, making it easier to check for intersections.

Overall, there are many possible solutions to this problem and it would be helpful to consider the specific goals and constraints of the project in order to determine the most suitable algorithm. I hope these suggestions provide some insight and help you in finding a solution to this problem.