Return to Answer

added 2155 characters in body

edited May 17, 2024 at 14:10

d) I would optimise the stepping to the next point by doing two things. Firsly I would start in the topbottom left corner and traverse north easterlyup and south westerlydown moving right at the boundary. Secondly when I stepped to a new point I would run a fast check that the same disc that covered the preceding point did not also cover that new point, becuase it is likely that a disc close by will cover multiple points. Once you find an uncovered point keep adding discs until it is covered and then move on.

This will most likely take a fraction of the time than it is currently taking for your code to run.

Example

The following code does exactly what I described above and it will measure upto 50,000 discs in about 1 second. It also follows the statistical analysis described above, giving me confidence it is free from bugs. I hope this skeletal structrue helps.

import numpy as np SQRT_N = 100.0 # length of side RV_DISC_CENTRES = np.random.rand(80000, 2) * SQRT_N GRID_SIZE = 0.01 def get_next_gridpoint(current, direction): "Traverse the grid up and down moving to a new point" if direction == "up": if current[1] >= SQRT_N: return (current[0] + GRID_SIZE, SQRT_N), "down" else: return (current[0], current[1] + GRID_SIZE), "up" else: if current[1] <= 0.0: return (current[0] + GRID_SIZE, 0.0), "up" else: return (current[0], current[1] - GRID_SIZE), "down" def is_gridpoint_in_disc(gridpoint, discpoint): """Ensure the euclidean distance between points is less than disc radius""" return ((gridpoint[0] - discpoint[0])**2 + (gridpoint[1] - discpoint[1])**2) < 1.0 def search_until_covered(gridpoint): """Iterate through all discs until the gridpoint is covered and return the disc num""" for i in range(RV_DISC_CENTRES.shape[0]): if is_gridpoint_in_disc(gridpoint, RV_DISC_CENTRES[i, :]): return True, i return False, None curr_gridpoint, direction = (0.0, 0.0), "up" disc_num, num_discs = None, 0.0 while curr_gridpoint[0] <= SQRT_N and curr_gridpoint[1] <= SQRT_N: if disc_num and is_gridpoint_in_disc(curr_gridpoint, RV_DISC_CENTRES[disc_num, :]): curr_gridpoint, direction = get_next_gridpoint(curr_gridpoint, direction) else: is_covered, disc_num = search_until_covered(curr_gridpoint) if not is_covered: raise ValueError(f"Gridpoint {curr_gridpoint} cannot be covered.") if disc_num > num_discs: num_discs = disc_num curr_gridpoint, direction = get_next_gridpoint(curr_gridpoint, direction) print(f"Number of discs required for coverage: {num_discs}")

Profiling

Notice that the exhaustive search is only called 99 times for the 10000 gridpoints:

d) I would optimise the stepping to the next point by doing two things. Firsly I would start in the top left corner and traverse north easterly and south westerly. Secondly when I stepped to a new point I would run a fast check that the same disc that covered the preceding point did not also cover that new point, becuase it is likely that a disc close by will cover multiple points. Once you find an uncovered point keep adding discs until it is covered and then move on.

This will most likely take a fraction of the time than it is currently taking for your code to run.

d) I would optimise the stepping to the next point by doing two things. Firsly I would start in the bottom left corner and traverse up and down moving right at the boundary. Secondly when I stepped to a new point I would run a fast check that the same disc that covered the preceding point did not also cover that new point, becuase it is likely that a disc close by will cover multiple points. Once you find an uncovered point keep adding discs until it is covered and then move on.

This will most likely take a fraction of the time than it is currently taking for your code to run.

Example

import numpy as np SQRT_N = 100.0 # length of side RV_DISC_CENTRES = np.random.rand(80000, 2) * SQRT_N GRID_SIZE = 0.01 def get_next_gridpoint(current, direction): "Traverse the grid up and down moving to a new point" if direction == "up": if current[1] >= SQRT_N: return (current[0] + GRID_SIZE, SQRT_N), "down" else: return (current[0], current[1] + GRID_SIZE), "up" else: if current[1] <= 0.0: return (current[0] + GRID_SIZE, 0.0), "up" else: return (current[0], current[1] - GRID_SIZE), "down" def is_gridpoint_in_disc(gridpoint, discpoint): """Ensure the euclidean distance between points is less than disc radius""" return ((gridpoint[0] - discpoint[0])**2 + (gridpoint[1] - discpoint[1])**2) < 1.0 def search_until_covered(gridpoint): """Iterate through all discs until the gridpoint is covered and return the disc num""" for i in range(RV_DISC_CENTRES.shape[0]): if is_gridpoint_in_disc(gridpoint, RV_DISC_CENTRES[i, :]): return True, i return False, None curr_gridpoint, direction = (0.0, 0.0), "up" disc_num, num_discs = None, 0.0 while curr_gridpoint[0] <= SQRT_N and curr_gridpoint[1] <= SQRT_N: if disc_num and is_gridpoint_in_disc(curr_gridpoint, RV_DISC_CENTRES[disc_num, :]): curr_gridpoint, direction = get_next_gridpoint(curr_gridpoint, direction) else: is_covered, disc_num = search_until_covered(curr_gridpoint) if not is_covered: raise ValueError(f"Gridpoint {curr_gridpoint} cannot be covered.") if disc_num > num_discs: num_discs = disc_num curr_gridpoint, direction = get_next_gridpoint(curr_gridpoint, direction) print(f"Number of discs required for coverage: {num_discs}")

Profiling

Notice that the exhaustive search is only called 99 times for the 10000 gridpoints:

Source Link

answered May 17, 2024 at 13:04

Attack68

Analytical problem

This is a an analytical problem and it may be best to solve it first before coding to have an idea how best to structure your code.

If I understand you correctly:

each disc has radius one,
the square is of dimensions: $$ \sqrt{n} \times \sqrt{n} $$
discs are placed sequentially at random and must cover the entire square.

If you assume, for simplicity, that the treatment of discs placed near the perimeter is to repeat/mirror rather than to truncate, then the probability that any point z=(x,y) in the square is covered by a single disc is the area of the disc divided by the area of the square:

$$ P(z \in Disc) = 1 - P(z \notin Disc) = \frac{\pi}{n} $$

Adding discs to reach a total of m discs independently and randomly means that,

$$ P(z \in \cup Discs) = 1 - P(z \notin \cup Discs) = 1 - \left ( P(z \notin Disc_1) ... P(z \notin Disc_m) \right ) = 1 - (1-\frac{\pi}{n})^m $$

This is a stochastic problem. Technically you could keep adding discs and might never cover the square but that is unlikely. If you estimated to a 99.99% likelihood that the square was covered, i.e. all points z are in the union of the discs, you can express the expected number of required discs relative to the dimension, n:

$$ m = \frac{ln(0.0001)}{ln(1-\frac{\pi}{n})} $$

Structuring code

I will ignore the disc chaining becuase that is a second task with not dissimilar concerns as here.

What is the optimal solution to ensure that the square is covered given some discs?

a) Don't exhaustively search every point every time you add a sphere. Once a point is covered it will be covered indefinitely. You do not need to check that point again.

b) To achieve the same 99.99% probability of coverage you need to create 10,000 gridpoints, i.e. 100 x 100.

c) Once you have discovered just one point that is not covered you need to add a disc and keep adding until that exact single point is covered, Once it is move on to check the next point.

This will most likely take a fraction of the time than it is currently taking for your code to run.