Optimizations for intersections finding algorithm

Question

I am trying to heavily optimize a piece of code I wrote before I write it in MIPS assembly. Here is a link to my code: http://dl.dropbox.com/u/7264839/P1-3.c

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!

Sorry. This place is new to me. I didn't know you marked answers. — ballaw
– ballaw, Commented Oct 11, 2011 at 0:08
If there's an answer that answers your question fully, please do mark it using this check mark to the left of it. If there's an answer that doesn't answer the question fully, but is very close (gives you a good idea towards the solution of your problem) and is better than others, consider marking it too. This is a small reward that you can give others for helping you out. And it gives you a few points too. — Alexey Frunze
– Alexey Frunze, Commented Oct 11, 2011 at 0:18
Also, I don't want you to optimize my code. I just want some insight on how to make it faster. I only show my code for reference. — ballaw
– ballaw, Commented Oct 11, 2011 at 1:26
@ballaw: Does my answer solves your problem? If so please indicate it, see Alex comment... — Laurent Grégoire
– Laurent Grégoire, Commented Feb 28, 2012 at 8:02

Laurent Grégoire · Accepted Answer · 2012-02-04 14:35:39Z

1

You could optimize your algorithm on black zones: since to intersect lines will need to be at least 3 pixels long in both directions, you can check only 3 pixels per group of 9 using the following pattern:

X  .  .
.  X  .
.  .  X

If no pixel is non-black on every 3x3 squares, then skip square. If at least one is non black, fall back on original algorithm.

If you have a low colored/black ratio, it can improve your code by a factor ~3.

answered Feb 4, 2012 at 14:35

Laurent Grégoire

4,20633 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Optimizations for intersections finding algorithm

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related