Crop a polygon shape from an image without libraries except numpy

Question

I have a list of points let's say 5 points. I want to crop the area that this polygon is covering from the image. Here, red areas are the points and I want to crop inside of the white area from the black background.

I am able to do this with cv2.fillConvexPoly() function but I will run this code on GPU so I can not use cv2. I want to do this with only numpy arrays. I have the X and Y coordinates of the points and their orders to draw edges. I could not implement the code without using libraries like PIL or opencv so any advice would be helpful.

Answer 1

I don't think you could achieve a more optimized approach than cv2 by using only python. But if you're wondering what would a python + NumPy implementation of cv2.fillConvexPoly() look like, this is how I would do it:

1. For each pixel in an image, check if it is inside the polygon
2. If it is not inside, change the alpha value for that pixel to 0 (assuming the image has an alpha channel. Or you could just make that pixel black)

In order to know if a pixel is inside a polygon, you could use the Winding Number Algorithm / Nonzero-rule which states:

For any point inside the polygon the winding number would be non-zero. Therefore it is also known as the nonzero-rule algorithm.

And:

For a given curve C and a given point P: construct a ray (a straight line) heading out from P in any direction towards infinity. Find all the intersections of C with this ray. Score up the winding number as follows: for every clockwise intersection (the curve passing through the ray from left to right, as viewed from P) subtract 1; for every counter-clockwise intersection (curve passing from right to left, as viewed from P) add 1. If the total winding number is zero, P is outside C; otherwise, it is inside.

In my approach I won't be adding or subtracting 1, instead I'll think of it as the number of revolutions, meaning that if the sum of all the angles between the rays is 360, that means the point is inside the polygon

import numpy as np

def _angle_between_three_points(A, B, C):
    a, b, c = np.array(A), np.array(B), np.array(C)
    ba = a - b
    bc = c - b

    cosine_angle = np.dot(ba, bc) / (np.linalg.norm(ba) * np.linalg.norm(bc))
    angle = np.arccos(cosine_angle)  # in radians
    
    return np.degrees(angle)  # in degrees

def _get_edges_from_points(points):
    edges = []
    dist = lambda p1, p2: np.hypot(p2[0] - p1[0], p2[1] - p1[1])
    _p = points.copy()
    for i, p in enumerate(points):
        _p.pop(0)
        try:
            next_point = sorted(map(lambda pn: (pn, dist(p, pn)), _p), key=lambda x: x[1])[0][0]
        except IndexError:
            next_point = points[0]
        edges.append((p, next_point))
    return edges

def is_point_inside(point, polygon):
    point = [point[0], point[1]]
    angles = map(lambda edge: _angle_between_three_points(edge[0], point, edge[1]), _get_edges_from_points(polygon))
    return sum(angles) == 360

Now you can just apply the is_point_inside() to every pixel.

NOTE: It is worth checking out this article from Medium's Towards Data Science