0
$\begingroup$

I have a canvas. On this canvas, I want to position 1, 2 or 3 images. The images can be positioned anywhere on the canvas just as long as they're within the canvas. The images move by their top-left corner. To make sure that the images do not leave the canvas, I am doing this:

image_topLeft_x_position = random.randint(0, (canvas_width - logo_width))

image_topLeft_y_position = random.randint(0, (canvas_height - logo_height))

I can save these locations in a list of tuples like this:

locations = [(image_topLeft_x_position, image_topLeft_y_position)]

After saving a location, I want to generate new locations within the canvas that don't overlap with the previous ones. However, I've been stuck on this problem for well over a day. Any help is appreciated.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

If there is a place for the new image to fit, there must be a place where the left edge of the new image is aligned with either the left edge of the canvas or of some previous image. The same true for the top edge of the new image. So, if you've already placed 2 images, you only have to try 3 possibilities for the left edge and 3 possibilities for the top edge, or a total of 9 candidate positions in total. Given a candidate position, you should be easily able to test whether a new image can be placed there without overlapping any prior image.

$\endgroup$
6
  • $\begingroup$ Sorry, this is confusing. Can you break it down? $\endgroup$ Jan 23, 2021 at 3:18
  • $\begingroup$ @oo92, No, thanks, I think it is clear enough. I suggest you spend some time working through some examples. This is your task, you will need to put in some effort of your own to work through it. This site is not designed for interactive back-and-forth interaction. $\endgroup$
    – D.W.
    Jan 23, 2021 at 3:22
  • 1
    $\begingroup$ Suppose that you can fit a new image to the canvas. Move the image to the left as far as possible. You either reach the left edge of the canvas or the right edge of an existing image. Similarly, if you move the image up as far as possible, you either hit the top edge of the canvas or the bottom edge of an existing image. This implies that if there is a place for a new image, then one such place is where the left edge is either the left edge of the canvas or the right edge of an existing image, and similarly for the top edge. $\endgroup$ Jan 24, 2021 at 9:05
  • 1
    $\begingroup$ You can find out whether the image fits by trying out all such locations. If there are $n$ existing images, there are only $(n+1)^2$ positions to try. For each, you need to check overlap with the existing images, leading to an $O(n^3)$ algorithm. This can probably be improved significantly, but when $n = 2$ there is no reason to bother. $\endgroup$ Jan 24, 2021 at 9:06
  • 1
    $\begingroup$ If you want to place as many images on a given canvas, that's a much harder problem (two-dimensional knapsack), though in practice it might also be feasible. $\endgroup$ Jan 24, 2021 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.