Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

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