How to find the corner pixels of a rectangle?

Question

Given a simple monochrome bitmap that contains a single, randomly rotated rectangle. How can I find the left/top, left/bottom, right/bottom and right/top corner positions of the rectangle inside the bitmap?

For example, this is how the bitmap could look like, where the X marks the pixels in question:

......... ......... ......... .........
.X11111X. ....X.... ..X11.... ....11X..
.1111111. ...111... ..11111X. X111111..
.1111111. ..X111X.. ..111111. .111111..
.X11111X. ...111... .1111111. .1111111.
......... ....X.... .111111.. ..111111.
......... ......... .X11111.. ..11111X.
......... ......... ....11X.. ..X11....
......... ......... ......... .........

Please excuse the bad ascii art. For the second example, the corner pixel at the top could either be the rectangles left/top or right/top corner. Either is fine.

What steps are required to determine the corner pixels/positions in the above examples?

Answer 1

The corner pixels are the pixels the furthest apart. Find the top most row and the bottom most row. There will always be a corner pixel in those.

The corner pixel can only be the first or last pixel in this the topmost row row (or both if there's just the one).

So compare the distances between the first pixel in the topmost row and the last pixel in the bottom most row. And last pixel in topmost with the first in bottom most. The corners there are the the ones that are the furthest apart.

Since they are all the same distance in the Y you need the pixels with the greatest difference with regard to their x location. The corners are the pixels for which abs(x0-x1) is the greatest, where x0 is in the topmost row and x1 is in the bottom most.

Repeat this for the rightmost and leftmost rows.

If the topmost corner is on the left then the leftmost corner is on the bottom, the bottom most corner is on the right and the rightmost corner is on the top. Once you have the top, bottom, left, and right rows there's really just the two possibilities that can be solved in an if statement. But, due to the edge condition of having one pixel on the topmost row and two on the rightmost row, you're better off just running the algorithm again with transposed x and ys to solve for the other two corners rather than trying to spare yourself an if statement.