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:
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP