Function Repository Resource:

# RegionFindShortestPath

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" True whether 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]:=
 Out[1]=

Find the shortest path in a star-shaped region:

 In[2]:=
 Out[2]=

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

 In[3]:=
 Out[3]=

### Scope (2)

Create a complex random region:

 In[4]:=
 Out[4]=

Generate a RegionShortestPathFunction[]:

 In[5]:=
 Out[5]=

Specify start and end points interactively:

 In[6]:=
 Out[6]=

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

 In[7]:=
 Out[7]=

Create a RegionShortestPathFunction[] instead and use that repeatedly:

 In[8]:=
 Out[8]=

Using the same start point repeated is slightly faster still:

 In[9]:=
 Out[9]=

### Options (2)

#### MonitorProgress (2)

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

 In[10]:=
 Out[10]=

Disable the progress bar:

 In[11]:=
 Out[11]=

Lukas Lang

## Version History

• 1.0.0 – 07 June 2021