Line intersection algorithm optimization

[Bob Busby]

I am trying to heavily optimize a piece of code in C as well as MIPS assembly. Here is a link to my code: http://dl.dropbox.com/u/7264839/P1-3.c
http://dl.dropbox.com/u/7264839/P1-4-1%20new.asm

The problem is find the number of intersections between 1 pixel wide lines of different colors in a 64x64 matrix. An intersection does not count for T intersections. Also, line will always have at least 1 pixel of space in between them. Here is a picture of what an image might look like.

http://dl.dropbox.com/u/7264839/Pics/pile1.png

My basic algorithm is to look at every pixel (except ones on the perimeter) and if it is black, ignore it. If it is not black, check two of the sides and if they are the same color and not black, check the other sides, and if they are the same color, not black, and a different color from the other sides, there is an intersection. Also, if an intersection is found than the next pixel can be ignored.

I have found several optimizations but it still needs to be much much faster is terms of dynamic execution time. Do you guys have any tips on speeding it up or a better algorithm altogether. Thanks a bunch!

 

[KataKoniK]

Hello there,

I have taken a look at your code and I have a few suggestions for optimizing it further.

1. Use a more efficient data structure for storing the matrix. Instead of using a 2D array, consider using a bitmap or bitset. This will save memory and also make accessing and checking the pixels faster.

2. Instead of checking the two adjacent pixels, you can check all four sides at once using bitwise operations. For example, you can use the AND operator to check if the pixel to the left and right are the same color, and then use the XOR operator to check if the pixel above and below are different colors.

3. Consider using parallel processing techniques to speed up the execution time. You can divide the matrix into smaller sections and have multiple threads or processes checking for intersections simultaneously.

4. Use lookup tables for commonly used operations such as checking if a pixel is black or a certain color. This will eliminate the need for conditional statements and improve the overall performance.

5. Try to minimize the number of times you access the matrix. Instead of accessing the matrix for every pixel, you can store the results of previous checks and use them for future calculations.

Overall, I would recommend experimenting with different data structures and algorithms to find the most efficient solution for your problem. Also, consider using profiling tools to identify any bottlenecks in your code and focus on optimizing those sections. I hope this helps. Good luck with your optimization efforts!