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?


  • 2
    $\begingroup$ What distribution do you want the crops to have? How critical is it to have the right distribution? Is there something wrong with rejection sampling, i.e., pick a random crop, and check whether it has at least n points inside? That will certainly have the right distribution and be easy to implement, but might be slower than optimal. Have you tried that first, to see whether it's fast enough for your needs, before trying to invent something fancier? $\endgroup$ – D.W. May 19 '17 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.