How can i find the intersecting rectangle grid in the given diagram?

Question

I have with me the polygon coordinates and the line coordinates for the horizontal and vertical lines? The intention is to find all the intersecting grid (rectangles) existing outside of the polygons?

Starting point is this :

(step-2)The blue and the red lines are formed by stretching each and every coordinate of the polygons in horiztonal and vertical direction until the nearest intersection.

I can find the intersections for sure but defining rectangles from it seems to be tricky.

Answer 1

Add grid lines on the border.

For every grid line, horizontal or vertical, list all the intersection points on it in left-to-right or top-to-bottom order.

Foe every intersection point, store its nearest neighbor along a grid line to the right, and its nearest neighbor along a grid line to the bottom.

For every intersection point A, if it has both neighbors, proceed to the right neighbor B until it has a bottom neighbor. Also, proceed to the bottom neighbor C until it has a right neighbor. The three points A, B, and C are three corners of a rectangle.

If necessary, for each rectangle, detect whether it is inside or outside one of the given polygons.