I have a problem in which I am trying to find a way to detect all enclosed shapes on a canvas. For background, the only shapes which can be drawn are straight lines and rectangles. An example will get the point across:
There are two complete rectangles, one of which is contained within the larger outer rectangle. Note that the would-be rectangle at the bottom right is not counted as such, because it is not closed.
Normally I am reasonably good with algorithms, but when I look at this problem I see so many edge cases that I don't even know where to start.
For a solution, I would just be looking for a basic algorithm which can identify the two complete rectangles in the image. For implementation details, I will leave that up to me as a follow up assignment.
Possible answer (pseudocode):
I assume from the picture that the lines and rectangle edges are parallel to the coordinate axes.
Sweep from left to right, At each vertical lines look at the points where some horizontal line starts or ends or crosses.
A pair of points is potential left edge of a rectangle if it has two horizontal lines extending to its right. Save that pair.
If a horizontal line needed by some saved pair ends with matching point to complete a rectangle, delete that saved pair.
If a pair with lines extending to the left matches a previously saved pair, you have a complete rectangle.