Search code examples
algorithmgraphicsdetectionpixelintersection

Algorithm to find the coordinates of a corner in a simple image

I have a bitmap where two large blocks of colors intersect, and I would like to find the intersection of these two blocks.

enter image description here

Note that I do not know the actual geometry of the two shapes, because this is all just raw pixel data.

Is there any algorithm I could use to do this?

Solution

  • If you have all the pixel data in memory (which I'd assume you do, but this is a major sticking point) and there are only two distinct colours, all you should need to do is run a horizontal scanline to find the point where RGB changes from colour X to colour Y (note that you may need to run this scanline a few times, but in any case it's no worse than O(height)).
    A simple graph traversal (BFS or DFS) will then continue to walk you down that line (you should only need 3 points and then you'll be able to form a geometric line with equation a*x + b*y + c = 0 (assuming it's not a curve)).
    Repeat this scanline vertically (again, worst case it's O(width)). Find 3 points and you'll then have two lines with d*x + e*y + f = 0. Using a little bit of comp. geom, the intersection of these two lines will give you your point.