Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Line intersection algorithm optimization

  1. Oct 10, 2011 #1
    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: May 5, 2017
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted