Home » Algorithms » Scanning an arbitrarily rotated rectangular region

Scanning an arbitrarily rotated rectangular region

Quite often in image processing we need to scan a rectangular region in an image. The region is usually aligned to capture a specific feature in the image. You may be presented with a skewed image, necessitating that the region should also be skewed.

If it is not absolutely necessary to scan the region at the angle of skew, then the fastest way to interrogate the pixels is to scan the image horizontally.

As was shown in the previous post, the crossing points between two lines can be easily and efficiently determined.
By moving a reference line down across the region, the start and end x coordinates of each scan line can be found.
Only the y coordinate of the reference line is relevant, though it must have a length of at least 1 unit.

Of course, we must check every line in the rectangle, and every line in the rectangle may produce a crossing point.
The reference line shown below will identify points P1, P2, P3 and P4 as valid crossing points.

The solution is to compare the crossing coordinates against the bounds of the enclosing rectangle. In the example above this would eliminate points P1 and P4.

Vertical scans may be easily achieved by simply having a vertical reference line.
This technique can be applied to any convex hull.

John Wellbelove

John Wellbelove

Director of Aster Consulting Ltd
United Kingdom
I have been involved in technology and computer systems for all of my working life and have amassed considerable knowledge of designing and implementing systems that are both performant and correct. My role normally encompasses the entire project life-cycle, from specification to maintenance phase. Most systems I have worked on have required high speed and deterministic performance, often within a highly constrained platform. I am experienced in designing and adapting algorithms to solutions that are both space and time efficient, avoiding the normal overheads of standard solutions. Acting as a mentor for colleagues has often been a significant, though unofficial, part of my role.

I administer an open source project on Github.
See http://www.etlcpp.com/

Leave a comment

Your email address will not be published. Required fields are marked *