Search code examples
pythonalgorithmcomputer-visiongeometrycomputational-geometry

Divide a region into parts efficiently Python

I have a square grid with some points marked off as being the centers of the subparts of the grid. I'd like to be able to assign each location within the grid to the correct subpart. For example, if the subparts of the region were centered on the black dots, I'd like to be able to assign the red dot to the region in the lower right, as it is the closest black dot.

enter image description here

Currently, I do this by iterating over each possible red dot, and comparing its distance to each of the black dots. However, the width, length, and number of black dots in the grid is very high, so I'd like to know if there's a more efficient algorithm.

My particular data is formatted as such, where the numbers are just placeholders to correspond with the given example:

black_dots = [(38, 8), (42, 39), (5, 14), (6, 49)]
grid = [[0 for i in range(0, 50)] for j in range(0, 50)]

For reference, in the sample case, I hope to be able to fill grid up with integers 1, 2, 3, 4, depending on whether they are closest to the 1st, 2nd, 3rd, or 4th entry in black_dots to end up with something that would allow me to create something similar to the following picture where each integer correspond to a color (dots are left on for show).

enter image description here

To summarize, is there / what is the more efficient way to do this?

Solution

  • You can use a breadth-first traversal to solve this problem.

    1. Create a first-in, first-out queue. (A queue makes a traversal breadth-first.)

    2. Create a Visited mask indicating whether a cell in your grid has been added to the queue or not. Set the mask to false.

    3. Create a Parent mask indicating what black dot the cell ultimately belongs to.

    4. Place all the black dots into the queue, flag them in the Visited mask, and assign them unique ids in the Parent mask.

    5. Begin popping cells from the queue one by one. For each cell, iterate of the cell's neighbours. Place each neighbour into the Queue, flag it in Visited, and set its value in Parent to be equal to that of the cell you just popped.

    6. Continue until the queue is empty.

    The breadth-first traversal makes a wave which expands outward from each source cell (black dot). Since the waves all travel at the same speed across your grid, each wave gobbles up those cells closest to its source.

    This solves the problem in O(N) time.