# Find simplex that contains point in triangulation

**URL:** <https://discourse.julialang.org/t/find-simplex-that-contains-point-in-triangulation/36181>\
**Category:** Numerics\
**Tags:** question\
**Created:** [March 19, 2020, 10:24am UTC](https://discourse.julialang.org/t/find-simplex-that-contains-point-in-triangulation/36181 "2020-03-19T10:24:28Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 19, 2020, 10:24am UTC](https://discourse.julialang.org/t/find-simplex-that-contains-point-in-triangulation/36181/1 "2020-03-19T10:24:28Z")

</div>

Suppose I have a triangulation on a domain in \mathbb{R}^n, where the element simplexes are given by their vertices.

What is the recommended approach for finding which simplex contains a given point? Naively, I would just test each with something like

```julia
function is_point_in_simplex(x, zs) # unoptimized, no checks, etc
    w = vcat(reduce(hcat, zs), ones(1, length(zs))) \ vcat(x, 1)
    all(w .≥ 0)
end

S = [[0, 0], [0, 1], [1, 0]]
is_point_in_simplex([0.3, 0.3], S) # true
is_point_in_simplex([1, 1], S) # false

```

but I am not sure if this is the right approach.

---

<div class="post-metadata">

**Author:** ![jlchan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlchan/32/10958_2.png) [@jlchan](https://discourse.julialang.org/u/jlchan)\
**Post date:** [March 19, 2020, 1:27pm UTC](https://discourse.julialang.org/t/find-simplex-that-contains-point-in-triangulation/36181/2 "2020-03-19T13:27:00Z")

</div>

Binning strategies like tree-based domain decomposition could reduce it further, but I don’t think there’s a much better approach (at least from a finite element toolbox).

This isn’t done often in FEM because relevant points in a simplex are usually mapped from a reference simplex explicitly.

---

<div class="post-metadata">

**Author:** ![cgeoga](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cgeoga/32/216186_2.png) [@cgeoga](https://discourse.julialang.org/u/cgeoga)\
**Post date:** [March 19, 2020, 1:52pm UTC](https://discourse.julialang.org/t/find-simplex-that-contains-point-in-triangulation/36181/3 "2020-03-19T13:52:23Z")

</div>

The package **[VoronoiDelaunay.jl](https://github.com/JuliaGeometry/VoronoiDelaunay.jl)** has a method `locate` whose source implementation seems quite similar to your example code, which seems like a reasonable indication that your approach is workable.

EDIT: looking at the code for a minute, their `findindex` function is a custom function (at a glance I assumed it was something in `Base`). It is slightly more clever and looks to use a tree-like method to search more efficiently. So a bit more thoughtful than a brute-force search.

---

<div class="post-metadata">

**Author:** ![PaulMatlashewski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/paulmatlashewski/32/3072_2.png) [@PaulMatlashewski](https://discourse.julialang.org/u/PaulMatlashewski)\
**Post date:** [March 19, 2020, 4:43pm UTC](https://discourse.julialang.org/t/find-simplex-that-contains-point-in-triangulation/36181/4 "2020-03-19T16:43:58Z")

</div>

There is also the [Jump and Walk Algorithm](https://hal.inria.fr/inria-00102194/document) which does not need any additional data structures beyond the triangulation itself.