[ANN] Announcing Eikonal.jl

Package Announcements
1

Eikonal.jl implements solvers for Eikonal equations of the form:
\begin{align} &\qquad \left\Vert\nabla \tau\right\Vert = \sigma(x), &&\forall x\in\Omega\subset\mathbb{R}^N,\\ &\qquad\tau(x_0) = 0, &&\forall x_0\in\Gamma\subset\Omega,\end{align}
where one seeks the unknown field \tau, which can be interpreted as the time of first arrival of a (wave) front that originates in \Gamma and moves with slowness \sigma (i.e its speed is given by 1/\sigma).

Eikonal equations arise as a high-frequency approximation of waves propagation equations (much like geometric optics); they can also be interpreted as continuous shortest path problems.

Eikonal.jl implements two kinds of methods for solving the Eikonal equation:

  • Fast Sweeping Method (FSM) [1],
  • Fast Marching Method (FMM) [2].

(Please note that the FSM implementation has benefited from more work than the FMM. Only the FSM can handle problems in arbitrary dimension; FMM is (for now) limited to 2D problems. The API is also (for now) slightly inconsistent between FSM and FMM).

Previously existing packages allowing to handle such problems include FastMarching.jl which, as the name implies, implements only the FMM. Although there are many cases in which the FSM should be faster, even the FMM implementation of Eikonal.jl should be faster than that of FastMarching.jl (but the latter may be more accurate in complex cases).

Although a formal documentation is almost inexistant at this point, a few usage examples of Eikonal.jl are presented in its README.md. Maybe the two most interesting are (click on the images below to get all details):

  • computing the time of first arrival of a water wavefront passing through a small opening:
  • finding a shortest path to move an object in a complex environment (shamelessly and heavily inspired by James Sethian’s page):

Finally, the package has just been registered, so you can simply install and use it using the standard Pkg tooling:

import Pkg; Pkg.add("Eikonal")
using Eikonal

If you do play with it, please do not hesitate to report back!

  1. Zhao, Hongkai (2005-01-01). “A fast sweeping method for Eikonal equations”. Mathematics of Computation. 74 (250): 603–627. DOI: 10.1090/S0025-5718-04-01678-3 ↩︎

  2. J.A. Sethian. A Fast Marching Level Set Method for Monotonically Advancing Fronts, Proc. Natl. Acad. Sci., 93, 4, pp.1591–1595, 1996. PDF ↩︎

42 Likes
2

Impressive that the whole thing is only 400 lines of code. Nice usage of tuples, cartesian indices, and generated functions to get dimension-agnostic code.

19 Likes
3

What are other possible uses of it other than following listed in Eikonal equations Wikipedia ? :speech_balloon:

4

Note that the uses listed in Wikipedia already cover a broad field. For example,

  • I think seismologists sometimes use geometric optics models, which they solve either via ray-tracing methods or by solving Eikonal equations;
  • continuous shortest path problems have tons of applications in robotics
  • image segmentation / skeletonization also finds a lot of application in diverse fields such as medical imagery or (again) robotics.

James Sethian (who invented the Fast Marching method) also has a page that lists a lot of applications of the FMM:

https://math.berkeley.edu/~sethian/2006/Applications/Menu_Expanded_Applications.html

Not all of them are directly related to solving Eikonal equations, though; some are “tweaked” problems that can also be solved using Fast Marching-like methods, but are not necessarily exactly Eikonal equations (at least not in the form I describe above).

5 Likes
5

Actually less than 300 SLOC :wink:
(I love the piano example)

2 Likes
6

This looks very cool! I am wondering whether we could be using this in Agents.jl as an alternative to path finding in obstacle courses (we have A-star now)! cc @cryptic.ax !

1 Like
7

Just to advertise, PackageAnalyzer can be used to get a quantitative look at this beautiful package (or any other one :slight_smile:):

julia> using PackageAnalyzer

julia> analyze("Eikonal")
PackageV1 Eikonal:
  * repo: https://github.com/triscale-innov/Eikonal.jl.git
  * uuid: a6aab1ba-8f88-4217-b671-4d0788596809
  * version: 0.1.1
  * is reachable: true
  * tree hash: ac89a6cf8c89a741448deb8692aaacba745ecee0
  * Julia code in `src`: 303 lines
  * Julia code in `test`: 63 lines (17.2% of `test` + `src`)
  * documentation in `docs`: 891 lines (74.6% of `docs` + `src`)
  * documentation in README & docstrings: 67 lines (18.1% of README + `src`)
  * has license(s) in file: MIT
    * filename: LICENSE
    * OSI approved: true
  * number of contributors: 1 (and 1 anonymous contributors)
  * number of commits: 43
  * has `docs/make.jl`: true
  * has `test/runtests.jl`: true
  * has continuous integration: true
    * GitHub Actions

It comes up with 303 lines, but that includes the precompile script added in Eikonal v0.1.1 (analyze("Eikonal"; version=v"0.1") reports 280 lines).

10 Likes