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.

CodePudding user response：

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.

CodePudding user response：

I'd go with a two-pass sweep-line algorithm.

The first pass would compute how far the horizontal lines extend to the right: sweep left to right keeping track of the active horizontal lines in a set sorted by y.

• When a vertical line V is encountered, for each active horizontal line H with y coordinate between V endpoints:
  • extend H up to the current x coordinate (note: keep the original unextended endpoints for the next pass).
  • remove H from the active set.
• When a horizontal line left end is encountered, add it to the active set.
• In the end, extend the unterminated active lines to infinity.

The second pass would compute how far the horizontal lines extend to the left, and emit the rectangles on the go: sweep right to left, again keeping track of the active horizontal lines sorted by y.

• When a vertical line V is encountered:
  • find the two nearest active horizontal lines H1, H2 that bound V from the top and the bottom: a line H bounds V if V.x is contained within the original unextended endpoints of H.
  • generate all the rectangles between the active horizontal lines between H1 and H2.
  • remove all the active lines between H1 and H2 with y coordinates contained within V endpoints (i.e. those that V terminates on the left).
• When a horizontal line extended-to-the-right end point is encountered, add that line to the active set.