Sign in for more options. Each user starts with 1,000 free credits.
Pathfinding
Pathfinding w/ obstacles¶
In [1]:
# CrossCompute
obstacle_table_path = 'obstacles.csv'
source_x = 0
source_y = 0
target_x = 9
target_y = 9
target_folder = '/tmp'
In [2]:
%pylab inline
In [4]:
try:
import cairosvg
except ImportError:
import pip
pip.main(['install', 'cairosvg'])
import cairosvg
In [3]:
import itertools
import math
import networkx as nx
from os.path import join
from pandas import read_csv
from shapely import wkt
from shapely.geometry import MultiPolygon, GeometryCollection, Point, LineString
source_xy = int(source_x), int(source_y)
target_xy = int(target_x), int(target_y)
obstacle_table = read_csv(obstacle_table_path)
obstacle_polygons = [wkt.loads(x) for x in obstacle_table['WKT']]
mp = MultiPolygon(obstacle_polygons)
mp
Out[3]:
In [8]:
target_path = join(target_folder, 'obstacles.png')
cairosvg.svg2png(bytestring=mp._repr_svg_(), write_to=target_path)
print('obstacles_image_path = %s' % target_path)
In [9]:
def get_points(pointa, pointb, obstacles):
''' returns all nodes for coordinate grid
params:
@pointa: starting point, (int, int)
@pointb: end point, (int, int)
@obstacles: group of polygons, shapely.geometry.MultiPolygon
'''
bounds = list(itertools.chain(pointa, pointb, obstacles.bounds))
minimum, maximum = int(min(bounds)), int(max(bounds))
coords = itertools.product(range(minimum, maximum + 1), range(minimum, maximum + 1))
points = []
for i in coords:
point = Point(*i)
if all([(
not obstacle.contains(point)) for obstacle in obstacles.geoms]):
points.append(point)
return points
In [10]:
points = get_points(source_xy, target_xy, mp)
In [11]:
G = GeometryCollection(obstacle_polygons + points)
G
Out[11]:
In [19]:
target_path = join(target_folder, 'grid.png')
cairosvg.svg2png(bytestring=G._repr_svg_(), write_to=target_path)
print('grid_image_path = %s' % target_path)
In [13]:
nodes = [(c.coords.xy[0][0], c.coords.xy[1][0]) for c in points]
nodes[:10]
Out[13]:
In [14]:
graph = nx.Graph()
for n in nodes:
adj_nodes = [(n[0] + 1, n[1]), (n[0], n[1] + 1), (n[0] - 1, n[1]), (n[0], n[1] - 1)]
adj_nodes = filter(lambda c: c in nodes, adj_nodes)
for i in adj_nodes:
graph.add_edge(n, i, weight=1)
dnodes = [(n[0] + 1, n[1] + 1),
(n[0] - 1, n[1] + 1), (n[0] - 1, n[1] - 1), (n[0] + 1, n[1] - 1)]
d_nodes = filter(
lambda c: c in nodes and all([
not obstacle.contains(
LineString([n, c])
) for obstacle in obstacle_polygons
]), dnodes)
for i in d_nodes:
graph.add_edge(n, i, weight=math.sqrt(2))
In [15]:
nx.draw_networkx(graph, with_labels=False)
from shapely.geometry import LineString
line = LineString([
(0, 0),
(5, 0),
(5, 5),
(3, 5),
(3, 9),
(9, 9),
])
line
In [16]:
# !!! Put a pathfinding algorithm here
path = nx.algorithms.dijkstra_path(graph, source_xy, target_xy)
line = LineString(path)
line
Out[16]:
In [20]:
target_path = join(target_folder, 'line.png')
cairosvg.svg2png(bytestring=line._repr_svg_(), write_to=target_path)
print('line_image_path = %s' % target_path)
In [21]:
gc = GeometryCollection(obstacle_polygons + [
Point(source_xy),
Point(target_xy),
line,
])
In [22]:
target_path = join(target_folder, 'collection.png')
cairosvg.svg2png(bytestring=gc._repr_svg_(), write_to=target_path)
print('collection_image_path = %s' % target_path)
In [23]:
from pandas import DataFrame
waypoint_table = DataFrame(path, columns=['x', 'y'])
waypoint_table
Out[23]:
In [24]:
waypoint_table_path = join(target_folder, 'waypoints.csv')
waypoint_table.to_csv(waypoint_table_path, index=False)
In [25]:
print('optimal_path_table_path = %s' % waypoint_table_path)