Function Repository Resource:

RegionFindShortestPath

Source Notebook

Find the shortest paths between two points in 2D regions

Contributed by: Lukas Lang

ResourceFunction["RegionFindShortestPath"][region,start,end]

finds the shortest path from start to end that lies entirely within region.

ResourceFunction["RegionFindShortestPath"][region,start,All]

generates a RegionShortestPathFunction[] that can be applied repeatedly to different end.

ResourceFunction["RegionFindShortestPath"][region,All,end]

generates a RegionShortestPathFunction[] that can be applied repeatedly to different start.

ResourceFunction["RegionFindShortestPath"][region,All,All]

generates a RegionShortestPathFunction[] that can be applied repeatedly to different start and end.

Details and Options

ResourceFunction["RegionFindShortestPath"][region,start,end] gives the shortest path from start to end as a sequence of points.
ResourceFunction["RegionFindShortestPath"][region,start] is equivalent to ResourceFunction["RegionFindShortestPath"][region,start,All]
ResourceFunction["RegionFindShortestPath"][region] is equivalent to ResourceFunction["RegionFindShortestPath"][region,All,All]
ResourceFunction["RegionFindShortestPath"][region,] works only for 2D regions.
The following option can be given:
"MonitorProgress"Truewhether to show the progress of preprocessing region
With the default setting "MonitorProgress"True, ResourceFunction["MonitorProgress"] is used to display a progress bar during the preprocessing step.
When no path exists, ResourceFunction["RegionFindShortestPath"] returns {}.
If start or end or both are not within region, no path is found.
ResourceFunction["RegionFindShortestPath"] works only on MeshRegion objects. If a Region is given, it is first discretized using DiscretizeRegion. If a BoundaryMeshRegion is given, the region is triangulated using TriangulateMesh.
When searching for multiple paths in the same region, generating RegionShortestPathFunction[] once will give a significant performance improvement in most cases.
The algorithm used by ResourceFunction["RegionFindShortestPath"] is described in this Mathematica Stack Exchange post.
When evaluating ResourceFunction["RegionFindShortestPath"], parts of the function are precompiled. This results in a slow first run.

Examples

Basic Examples (3) 

Find the shortest path in a region with a hole:

In[1]:=
ring = Annulus[];
start = {-0.75, 0}; end = {0.5, 0.5};
Graphics[{
  LightGray, ring, Red, PointSize@Large, Point@{start, end},
  Green, Thick, Line@ResourceFunction["RegionFindShortestPath"][ring, start, end]
  }, ImageSize -> 250]
Out[1]=

Find the shortest path in a star-shaped region:

In[2]:=
star = Polygon@
   Table[(3 + 2 Cos[8 \[Theta]]) {Cos@\[Theta], Sin@\[Theta]}, {\[Theta], Subdivide[2 \[Pi], 16]}];
start = {-3, 0}; end = {0.1, 3.3};
Graphics[{
  LightGray, star, Red, PointSize@Large, Point@{start, end},
  Green, Thick, Line@ResourceFunction["RegionFindShortestPath"][star, start, end]
  }, ImageSize -> 250]
Out[2]=

If the region consists of multiple disjoint parts, a path might not always exist:

In[3]:=
disjoint = DiscretizeRegion@RegionUnion[Rectangle[{0, 0}], Rectangle[{2, 0}]];
start = {0.5, 0.5}; end = {2.5, 0.5};
Graphics[{
  LightGray, disjoint, Red, PointSize@Large, Point@{start, end},
  Green, Thick, Line@ResourceFunction["RegionFindShortestPath"][disjoint, start, end]
  }, ImageSize -> 250]
Out[3]=

Scope (2) 

Create a complex random region:

In[4]:=
SeedRandom[1];
mesh = (numdisks = 60; numpolys = 40; disks = MapThread[
   Disk[#, #2]& , {
RandomPoint[
Disk[], numdisks], 
RandomReal[1/5, numdisks]}]; translatePoly[
Pattern[poly, 
Blank[]], 
Pattern[pos, 
Blank[]]] := Polygon[
Map[# + pos& , 
Part[poly, 1]], 
Part[poly, 2]]; polygons = MapThread[translatePoly[#, #2]& , {
RandomPolygon[8, numpolys, DataRange -> {-0.15, 0.15}], 
RandomPoint[
Disk[], numpolys]}]; DiscretizeRegion[
RegionUnion[
Join[polygons, disks]], ImageSize -> 250])
Out[4]=

Generate a RegionShortestPathFunction[]:

In[5]:=
rspf = ResourceFunction["RegionFindShortestPath"][mesh]
Out[5]=

Specify start and end points interactively:

In[6]:=
Manipulate[
 Show[Region[mesh, BaseStyle -> {EdgeForm@None, LightGray}], Graphics[{Thick, Red, Dynamic@
     Line@rspf[p1, p2]}
   ]
  ],
 {{p1, {-0.4, 0.9}}, Locator},
 {{p2, {-0.8, -0.6}}, Locator}
 ]
Out[6]=

Calling RegionFindShortestPath repeatedly on the same region can be very slow:

In[7]:=
SeedRandom[1];
region = RandomPolygon[200];
points = RandomPoint[region, {2, 3, 4}];
AbsoluteTiming[
 TableForm@MapThread[
   With[
     {path = ResourceFunction["RegionFindShortestPath"][region, ##]},
     Graphics[{LightGray, region, Red, PointSize[Large], Point[{##}], Green, Thick, Line[path]}, ImageSize -> 100]
     ] &, points, 2]
 ]
Out[7]=

Create a RegionShortestPathFunction[] instead and use that repeatedly:

In[8]:=
SeedRandom[1];
region = RandomPolygon[200];
points = RandomPoint[region, {2, 3, 4}];
AbsoluteTiming[
 rspf = ResourceFunction["RegionFindShortestPath"][region];
 TableForm@MapThread[
   With[
     {path = rspf[##]},
     Graphics[{LightGray, region, Red, PointSize[Large], Point[{##}], Green, Thick, Line[path]}, ImageSize -> 100]
     ] &, points, 2]
 ]
Out[8]=

Using the same start point repeated is slightly faster still:

In[9]:=
SeedRandom[1];
region = RandomPolygon[200];
start = RandomPoint@region; ends = RandomPoint[region, {3, 4}];
AbsoluteTiming[
 rspf = ResourceFunction["RegionFindShortestPath"][region, start];
 TableForm@MapThread[
   With[
     {path = rspf[#]},
     Graphics[{LightGray, region, Red, PointSize[Large], Point[{start, #}], Green, Thick, Line[path]}, ImageSize -> 100]
     ] &, {ends}, 2]
 ]
Out[9]=

Options (2) 

MonitorProgress (2) 

With the default setting "MonitorProgress"True, a progress bar is shown during the preprocessing step:

In[10]:=
ResourceFunction["RegionFindShortestPath"][RandomPolygon[200]]
Out[10]=

Disable the progress bar:

In[11]:=
ResourceFunction["RegionFindShortestPath"][RandomPolygon[200], "MonitorProgress" -> False]
Out[11]=

Publisher

Lukas Lang

Version History

  • 1.0.0 – 07 June 2021

Related Resources

License Information