Line intersection algorithm optimization

  • Thread starter Bob Busby
  • Start date
  • #1
47
0
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 [Broken]
http://dl.dropbox.com/u/7264839/P1-4-1%20new.asm [Broken]

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 [Broken]

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!
 
Last edited by a moderator:

Answers and Replies

Related Threads on Line intersection algorithm optimization

Replies
2
Views
1K
  • Last Post
Replies
9
Views
1K
Replies
4
Views
2K
Replies
1
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
3K
Top