Lets assume I have an image which only has white background and black points, all same size. I need to randomly sample crops with a hardcoded size. The condition is that all the crops need to contain at least n points inside. Also, ideally the crops can be rotated any number of degrees. In the following sample image I have manually drawn what it would be considered as valid crops (green) and non-valid crops (red). The condition in this example is that a valid crop must have at least 5 points inside.
Note that I have made the image with paint so the crops are not exactly same size (they should), an also there are only two rotations (there should be any type of rotation)
I am looking for an efficient algorithm for doing this and my idea is to implement it in Python. Any suggestions?