TransWikia.com

Using shapely to scatter points in an equidistant manner around a MultiPolygon in a Box?

Geographic Information Systems Asked by Justin Cabot-Miller on December 31, 2020

I have a box bounded by min_x, min_y, max_x, max_y, I also have a multipolygon = poly contained in that box. I’m trying to equidistantly scatter points throughout that box, outside of that multipolygon, for the eventual purpose of using a modified A* algorithm to find a route between two points.
Right now, I can generate points as such:

from shapely.geometry import Point
x_range = np.linspace(min_y,max_y,round((max_y - min_y)*2.5),False)
y_range = np.linspace(min_x,max_x,round((max_x - min_x)*2.5),False)
points = []
point_dict = dict()
i = 0
for x in x_range:
    j = 0
    for y in y_range:
        p = Point(y,x)
        if not poly.contains(p):
            points.append(p)
            point_dict[i,j] = p
        j+=1
    i+=1

They’re in an x-y grid along the map, but I think a more efficient way to generate points for a path would be to create this grid then add a repulsion factor so they’re all pushed away from each other inversely proportional to their distance from one another AND from the multipolygon and the bounding box. Eventually I imagine this would end up in some solid state equilibrium.

Right now I maintain a list of reference for each of the 8 nearest points to each point as follows:

edge_list = []
for point in point_dict:
    for i in [point[0]-1, point[0], point[0]+1,point[0]+2,point[0]-2]:
        for j in [point[1]-1, point[1], point[1]+1,point[1]+2,point[1]-2]:
            try: #we already excluded points s.t. poly.contains(point)
                if not point_dict[point].distance(point_dict[i,j]) == 0:
                    edge_list.append([point, (i,j), point_dict[point].distance(point_dict[i,j])])
            except:
                pass
            j+=1
        i+=1

Right now I use this edge list so that I can construct a graph and run djikstra’s algorithm on it. By constraining it to the <= 8 nearest points, I reduce the number of edges that need to be checked foreach point.

My problem here is two-fold:

  1. I have little idea how I would accomplish this repulsion addition computationally
  2. I don’t know how I would maintain a reference for the n-nearest points to each point after the equilibrium is reached.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP