How to check intersection of rectangle and polygon?-CodePudding

I have multiple rectangles on a x-y plane which are not rotated. How do I check if these rectangles intersect with a n-sized polygon?

I drew a picture here for clarity.

In the image above, the purple shape is the polygon and I have a bunch of black rectangles.

I've looked at the line-sweeping methods however from what I understand that would only work if my polygon was also a non-rotated rectangle. So I'm kinda stumped as to what type of algorithm I could use here. Thanks

CodePudding user response：

The Sutherland-Hodgman algorithm is your best friend.

First solve an easier problem: clipping a polygon by a half plane. This is done by scanning all sides in turn and detecting intersections with the border (green line). Keep the pieces on the desired half-plane. After this, you get a new polygon, the original polygon or... empty.

Repeat for all four sides of the rectangles.

This solution is not optimal, especially if there are several rectangles. A better but more complicated one is by line-sweeping.

CodePudding user response：

Not sure whether you are expecting an analytical solution, or something else, but it can be done quite simply graphically using the following method:

Create a 16-bit black canvas (or image) sized large enough for all your rectangles and the vertices of your polygon. You can use PIL, or OpenCV or scikit-image or wand, It doesn't need to be a 3-channel RGB colour image, a single greyscale channel is adequate. The canvas will be a PIL Image if you use PIL, or a Numpy array if you use the other libraries. Because the canvas is black, it will be full of zeroes.
Draw your first rectangle filled with greyscale value 1, your second rectangle filled with greyscale value 2 and so on
Draw your filled polygon on a new black canvas (or Numpy array) and fill it with 32768
Add the two canvases together with np.add()
Now use np.unique() to find a list of all the unique colours in the image.

That's the setup complete!

If there are no intersections, the unique colours (or shades of grey actually) in the image will be:

the background, i.e. 0
each of the rectangle colours, i.e. 1, 2, 3
the filled polygon colour, i.e. 32768

If the polygon intersects with the first rectangle, you will find the grey value 1 32768, if it intersects with the second rectangle, you will find 2 32768.

You can find the number of intersections by subtracting 2 from the length of the list of unique colours - one for the background and one for the polygon. And you can use np.where() to find the coordinates of where the polygon intersects with any rectangle.

The code will look something like this:

#!/usr/bin/env python3

import numpy as np
import cv2

# Make canvas, and copy for polygon canvas
canvas = np.zeros((480,640), np.uint16)
PolygonCanvas = canvas.copy()

# Draw first 3 rectangles using Numpy slicing
# We'll draw with 5000, 9000 and 25000 so you can see them
canvas[10:100, 40:180] = 5000
canvas[120:300, 150:400] = 9000
canvas[400:450, 80:600] = 25000

# Draw polygon on its canvas
# https://docs.opencv.org/4.x/d6/d6e/group__imgproc__draw.html#ga311160e71d37e3b795324d097cb3a7dc
vertices = np.array([[100,150], [280,200], [170,408]])
cv2.fillPoly(PolygonCanvas, pts = [vertices], color =32768)

# Add canvases
canvas  = PolygonCanvas
cv2.imwrite('DEBUG-overlaid.png', canvas)   # just debug

# Get list of unique colours
result = np.unique(canvas)
print(result)

# Print locations where polygon (32768) intersects with rectangle 25000
print(np.where(canvas == 32768 25000))

The output is this:

[    0  5000  9000 25000 32768 41768 57768]

These are the black background (0), the three rectangles (5000, 9000 and 25000), the polygon on its own (32768) and the polygon intersecting with rectangles 9000 and 25000.

These are the coordinates of all the points where the polygon intersects with rectangle 25000.

(array([400, 400, 400, 400, 400, 400, 400, 401, 401, 401, 401, 401, 401,
   401, 402, 402, 402, 402, 402, 402, 403, 403, 403, 403, 403, 404,
   404, 404, 404, 405, 405, 405, 405, 406, 406, 406, 407, 407, 408]), array([168, 169, 170, 171, 172, 173, 174, 168, 169, 170, 171, 172, 173,
   174, 168, 169, 170, 171, 172, 173, 169, 170, 171, 172, 173, 169,
   170, 171, 172, 169, 170, 171, 172, 169, 170, 171, 170, 171, 170]))

If you want to see all the intersections, just threshold the values above 32768 like this:

# Threshold at 32768 to get all intersections
_, allIntersections = cv2.threshold(canvas, 32768, 65535, cv2.THRESH_BINARY)
cv2.imwrite('DEBUG-intersections.png', allIntersections)   # just debug