1

I'm working on an algorithm that randomly plots objects on a large image. Here is the workflow of what I currently have.

  1. I define a space that represents the dimensions of the image and initiate an empty array (restrictList)
  2. Using the genLoc function, I randomly pick a point (x,y). restrictList is empty when the first point is picked.
  3. I then calculate all points that will be occupied by the object. These points are added to the array(restrictList)
  4. I then call genLoc again, to pick another random (x,y). If (x,y) exists is restrictList, the function calls itself again.
  5. This will continue until we pick a random point that is not in restrict list.

The problem is as follows, as more objects are plotted, the size of the array - restrictList increases. With each iteration, it takes longer to pick a valid random point. The biggest flaw that I can see here is that I'm wasting processing power by repeatedly picking a random coordinate from the image space. One alternative that I tried was using an array - [x for x in AllPossiblePoints if x not in restrictList] and picking a random index. This takes even longer because the array AllPossiblePoints is very large. I think I need a way to make sure that the (x,y) coordinates that are in restrictList, do not get randomly generated in the first place.

def genLoc(x,y, restrictList):

Valx = randint(0, x)
Valy = randint(0, y)

point = (Valx, Valy)
if point in restrictList:
    return genLoc(dimx, dimy, restrictList)

elif point not in restrictList:
    return point
Saad Malik
  • 99
  • 2
  • 7
  • 2
    One common solution I have seen is to randomly shuffle `AllPossiblePoints` then just peel items off the end. – wwii Jul 13 '20 at 23:05
  • Does this answer your question? [What is the most pythonic way to pop a random element from a list?](https://stackoverflow.com/questions/10048069/what-is-the-most-pythonic-way-to-pop-a-random-element-from-a-list) – wwii Jul 13 '20 at 23:08
  • Otherwise use `random.sample` with the entire point space. `points = random.sample(AllPossiblePoints,nbr_of_objects_being_placed)` - [How do you pick “x” number of unique numbers from a list in Python?](https://stackoverflow.com/questions/6494508/how-do-you-pick-x-number-of-unique-numbers-from-a-list-in-python) – wwii Jul 13 '20 at 23:26
  • I'd say that would be a good way only if x and y didn't have significant size. Is this the case? – Ecto Jul 14 '20 at 00:02
  • Use a set instead of a list to hold the restricted points. that should help, – wwii Jul 14 '20 at 02:36

1 Answers1

1

REVISED

This solution will require you to generate all possible coordinates in advance. It uses sets and set logic to remove possibilities as they are used. random.sample is used to choose a point from the possibles. My mre is contrived to illustrate that - (everything is linear).

import random

# fake function that identifies
# unusable points after placing an object
def calc_objectspace(point,obj=None):
    objdims = range(-5,5)
    # linear all the same size
    objspace = set(point+n for n in range(-5,5))
    objspace.add(point)    # as needed
    return objspace

# make all the points as a set
allthestuff = set(range(10000))

# iterate over the objects getting placed
for obj in range(10):
    # random.choice won't work with a set
    point = random.sample(allthestuff,1)[0]
    # determine occupied points
    obj_space = calc_objectspace(point)
    # reduce the possible points
    allthestuff.difference_update(obj_space)
    print(len(allthestuff))

The time complexity of s.difference_update(t) is O(len(t)).

This solves the problem of hunting for a random coordinate that isn't already used.

Cannot assess the cost of creating all the coordinates up front. If it is too costly then probably have to revert to hunting for a usable coordinate. Using a set to hold all the restricted points will reduce the time for the membership testing.

wwii
  • 23,232
  • 7
  • 37
  • 77
  • Thanks for the answer, the issue is that when a point is selected, a certain amount of points (x,y) around it are no longer valid for selection. This is based on the largest object we are plotting. I did this so there is no overlap when plotting. For example, we select (10,5) first and use it to plot object (y), assume the largest object is (z). All points in the following rectangle are invalid (10-length(z), 5-height(z), 10+length(y), 5+height(y). In my solution, these points go in the restrictList array. – Saad Malik Jul 14 '20 at 02:23