# Delaunay Triangularization

**URL:** <https://discourse.julialang.org/t/delaunay-triangularization/36172>\
**Category:** Geo\
**Created:** [March 19, 2020, 2:04am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172 "2020-03-19T02:04:27Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Donald\_Lacombe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/donald_lacombe/32/13500_2.png) [@Donald\_Lacombe](https://discourse.julialang.org/u/Donald_Lacombe)\
**Post date:** [March 19, 2020, 2:04am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/1 "2020-03-19T02:04:27Z")

</div>

Hello!

I’d like to be able to obtain the following output from MATLAB but in Julia. Here is a toy example in MATLAB:

```julia
>> x = rand(5,1)

x =

    0.8147
    0.9058
    0.1270
    0.9134
    0.6324

>> y = rand(5,1)

y =

    0.0975
    0.2785
    0.5469
    0.9575
    0.9649

>> tri = delaunay(x,y)

tri =

     2 3 1
     5 3 2
     5 2 4

```

Is there any way to obtain the output (i.e. the tri variable) in Julia?

Any help would be greatly appreciated.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 19, 2020, 2:10am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/2 "2020-03-19T02:10:42Z")

</div>

Check out [GitHub - JuliaPDE/SurveyofPDEPackages: Survey of the packages of the Julia ecosystem for solving partial differential equations](https://github.com/JuliaPDE/SurveyofPDEPackages#grids)

---

<div class="post-metadata">

**Author:** ![Donald\_Lacombe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/donald_lacombe/32/13500_2.png) [@Donald\_Lacombe](https://discourse.julialang.org/u/Donald_Lacombe)\
**Post date:** [March 19, 2020, 2:40am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/3 "2020-03-19T02:40:43Z")

</div>

Thank you for the link. I tried the VoronoiDelaunay package but that doesn’t seem to do what I want (probably I don’t know how) and the MiniQhull package requires Linux unless I’m reading this wrong.

My ultimate goal is to complete a spatial econometrics package and I need to be able to build a contiguity based weight matrix.

---

<div class="post-metadata">

**Author:** ![fverdugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fverdugo/32/9446_2.png) [@fverdugo](https://discourse.julialang.org/u/fverdugo)\
**Post date:** [March 19, 2020, 9:37am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/4 "2020-03-19T09:37:30Z")

</div>

> [@Donald\_Lacombe](#):
>
> Thank you for the link. I tried the VoronoiDelaunay package but that doesn’t seem to do what I want (probably I don’t know how) and the MiniQhull package requires Linux unless I’m reading this wrong.

Yes, MiniQhull is designed for linux at this moment. Perhaps it also works for mac OS but we have not tested it in this scenario…

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [March 19, 2020, 9:50am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/5 "2020-03-19T09:50:48Z")

</div>

Have you looked at [GeoStats.jl](https://github.com/JuliaEarth/GeoStats.jl)? Depending on what exactly you’re trying to do, it might be there already or maybe an opportunity to combine efforts?

---

<div class="post-metadata">

**Author:** ![Donald\_Lacombe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/donald_lacombe/32/13500_2.png) [@Donald\_Lacombe](https://discourse.julialang.org/u/Donald_Lacombe)\
**Post date:** [March 20, 2020, 11:12pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/6 "2020-03-20T23:12:42Z")

</div>

I’ve looked at GeoStats and that currently doesn’t have what I need. I think what I need is very simple and the MiniQHull would work (theoretically) but I’m on Windows.

Like I mentioned earlier, my ultimate goal is to produce a spatial econometrics library for Julia. Most of the code is written (think alpha version) and I’d like to include other options for uses to create spatial weight matrices.

---

<div class="post-metadata">

**Author:** ![joa-quim](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joa-quim/32/227_2.png) [@joa-quim](https://discourse.julialang.org/u/joa-quim)\
**Post date:** [March 21, 2020, 1:26am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/7 "2020-03-21T01:26:21Z")

</div>

You can do it easily with GMT.jl, but it’s a non-negligible ovehead to have as a dependency

```julia
using GMT

triangulate(rand(5,2))
Array{GMT.GMTdataset,1} with 1 segments
First segment DATA
4×3 Array{Float64,2}:
 2.0 0.0 1.0
 4.0 3.0 1.0
 1.0 3.0 2.0
 4.0 1.0 0.0

```

---

<div class="post-metadata">

**Author:** ![Donald\_Lacombe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/donald_lacombe/32/13500_2.png) [@Donald\_Lacombe](https://discourse.julialang.org/u/Donald_Lacombe)\
**Post date:** [March 22, 2020, 7:19pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/8 "2020-03-22T19:19:18Z")

</div>

Thank you for the reply. I’m really looking for a native Julia “Dealunay” function if possible so that users can avoid installing extra software.

I may take a crack at coding one myself and given I can’t leave home, it may be sooner than later!

---

<div class="post-metadata">

**Author:** ![Donald\_Lacombe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/donald_lacombe/32/13500_2.png) [@Donald\_Lacombe](https://discourse.julialang.org/u/Donald_Lacombe)\
**Post date:** [March 22, 2020, 11:04pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/9 "2020-03-22T23:04:04Z")

</div>

FYI: I found the following implementation in Python:

[Delaunay in Python](http://code.activestate.com/recipes/579021-delaunay-i'mtriangulation/)

I do not know Python but this might be a good place to start.

---

<div class="post-metadata">

**Author:** ![Eben60](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/eben60/32/13475_2.png) [@Eben60](https://discourse.julialang.org/u/Eben60)\
**Post date:** [March 23, 2020, 11:48am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/10 "2020-03-23T11:48:12Z")

</div>

The link “Delaunay in Python” doesn’t work. However [Delaunay triangulation](https://docs.scipy.org/doc/scipy-1.4.1/reference/generated/scipy.spatial.Delaunay.html) is implemented in the SciPy package (using the Qhull library). For me, the simplest thing would be calling the SciPy from Julia.

---

<div class="post-metadata">

**Author:** ![Donald\_Lacombe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/donald_lacombe/32/13500_2.png) [@Donald\_Lacombe](https://discourse.julialang.org/u/Donald_Lacombe)\
**Post date:** [March 23, 2020, 4:02pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/11 "2020-03-23T16:02:49Z")

</div>

Thank you for taking a look at this code. I do know about SciPy, but I’d like to avoid having to call Python code. Nothing against Python, but I want to avoid the “you have to have additional stuff for Julia to work blah, blah”.

All I really need is a very simple 2D Delaunay routine that will take latitude and longitude coordinates and output the vertices like in my MATLAB example above.

If someone can point me to existing code that works, I can try and adapt to Julia. It may not be exhaustive but I think it’s valuable nonetheless.

---

<div class="post-metadata">

**Author:** ![uwechsler](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/uwechsler/32/5223_2.png) [@uwechsler](https://discourse.julialang.org/u/uwechsler)\
**Post date:** [March 23, 2020, 5:10pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/12 "2020-03-23T17:10:55Z")

</div>

> [@fverdugo](#):
>
> Yes, MiniQhull is designed for linux at this moment. Perhaps it also works for mac OS but we have not tested it in this scenario…

`MiniQhull` is a really nice package, thanks for the great work. But what is missing for it to work on Windows?

---

<div class="post-metadata">

**Author:** ![Pbellive](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pbellive/32/3604_2.png) [@Pbellive](https://discourse.julialang.org/u/Pbellive)\
**Post date:** [March 23, 2020, 9:16pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/13 "2020-03-23T21:16:52Z")

</div>

A bit late to this thread but I’m wondering why the VoronoiDelaunay doesn’t work for you, assuming you don’t need to do any 3D tetrahedralizations, just 2d Delaunay triangulations. At work we’ve been using VoronoiDelaunay to do triangulations of unstructured 2d point clouds. It’s worked great for us. Here’s a little code snippet:

```julia
using GeometricalPredicates, VoronoiDelaunay
mutable struct Point2DI <: AbstractPoint2D
  _x::Float64
  _y::Float64
  _i::Int64
end

Point2DI(x::Float64, y::Float64) = Point2DI(x, y, 0)

import GeometricalPredicates.getx
import GeometricalPredicates.gety
import VoronoiDelaunay.isexternal

getx(p::Point2DI) = p._x
gety(p::Point2DI) = p._y
geti(p::Point2DI) = p._i

function isexternal(p::Point2DI)
  getx(p) < VoronoiDelaunay.min_coord || getx(p) > VoronoiDelaunay.max_coord
end

x = randn(10); y = randn(10)

n = length(x)
d0 = VoronoiDelaunay.min_coord
dd = VoronoiDelaunay.max_coord - VoronoiDelaunay.min_coord
dn = VoronoiDelaunay.max_coord
x0,xn = extrema(x)
y0,yn = extrema(y)
dx = xn-x0
dy = yn-y0
u = d0 .+ ((x .- x0) ./ dx) .* dd
v = d0 .+ ((y .- y0) ./ dy) .* dd
P = Point2DI[Point2DI(ui, vi, i) for (ui, vi, i) in zip(u, v, 1:n)]
push!(DT, P)

```

That should give you a delaunay triangulation object `DT` that you can use for subsequent calculations such as interpolation etc.

---

<div class="post-metadata">

**Author:** ![fverdugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fverdugo/32/9446_2.png) [@fverdugo](https://discourse.julialang.org/u/fverdugo)\
**Post date:** [March 24, 2020, 6:29am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/14 "2020-03-24T06:29:15Z")

</div>

> [@uwechsler](#):
>
> `MiniQhull` is a really nice package, thanks for the great work. But what is missing for it to work on Windows?

Honestly, I don’t know… I have never used windows for technical computing. In any case, we are using cmake.jl to compile the C functions in the project. Thus, this compilation step should be portable. My doubt is about the mechanism we use to find the compiled C objects from Julia, I don’t know if it is portable…

We would be happy if someone is ready to help with the windows extension!

---

<div class="post-metadata">

**Author:** ![fverdugo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fverdugo/32/9446_2.png) [@fverdugo](https://discourse.julialang.org/u/fverdugo)\
**Post date:** [March 24, 2020, 7:22am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/15 "2020-03-24T07:22:46Z")

</div>

I have open an issue in MiniQhul about the windows and Mac OS extension  
[https://github.com/gridap/MiniQhull.jl/issues/5](https://github.com/gridap/MiniQhull.jl/issues/5)

---

<div class="post-metadata">

**Author:** ![magister-ludi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/magister-ludi/32/4003_2.png) [@magister-ludi](https://discourse.julialang.org/u/magister-ludi)\
**Post date:** [March 24, 2020, 11:03am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/16 "2020-03-24T11:03:59Z")

</div>

> [@Eben60](#):
>
> The link “Delaunay in Python” doesn’t work.

Probably not really important, but for what it’s worth, here is [the correct link](http://code.activestate.com/recipes/579021-delaunay-triangulation/).

---

<div class="post-metadata">

**Author:** ![Donald\_Lacombe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/donald_lacombe/32/13500_2.png) [@Donald\_Lacombe](https://discourse.julialang.org/u/Donald_Lacombe)\
**Post date:** [April 2, 2020, 4:11am UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/17 "2020-04-02T04:11:11Z")

</div>

I have been investigating this issue and it appears that the open source program Octave uses Qhull. I have performed my toy example above and it works as expected. The Octave code calls Qhull and in the MinGW64 bin folder it appears that the developers of Octave have compiled the Qhull code for use on Windows.

I’m not sure if this helps but I thought I’d bring it up. I can provide more information if anyone is interrested.

Thank you.

---

<div class="post-metadata">

**Author:** ![idontgetoutmuch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/idontgetoutmuch/32/321_2.png) [@idontgetoutmuch](https://discourse.julialang.org/u/idontgetoutmuch)\
**Post date:** [December 1, 2020, 4:00pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/18 "2020-12-01T16:00:40Z")

</div>

What is `DT`? I tried `DT = DelaunayTessellation()` but got

```julia
julia> push!(DT, P)
+ 
ERROR: MethodError: no method matching push!(::DelaunayTessellation2D{Point2D}, ::Array{Point2DI,1})
Closest candidates are:
  push!(::Any, ::Any, !Matched::Any) at abstractarray.jl:2252
  push!(::Any, ::Any, !Matched::Any, !Matched::Any...) at abstractarray.jl:2253
  push!(!Matched::Array{Any,1}, ::Any) at array.jl:940

```

---

<div class="post-metadata">

**Author:** ![lazarusA](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lazarusa/32/6571_2.png) [@lazarusA](https://discourse.julialang.org/u/lazarusA)\
**Post date:** [December 1, 2020, 4:16pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/19 "2020-12-01T16:16:48Z")

</div>

Hey,  
I used this one in a [paper](https://journals.aps.org/pre/abstract/10.1103/PhysRevE.100.062309): [just in case you want to see something more:]

```julia
using GR
n, tri = GR.delaunay(x, y)

```

A complete MWE is as follows:

```julia
using Random
using GR: delaunay
Random.seed!(123)
x, y = rand(10), rand(10)
n, tri = delaunay(x,y)
tri
13×3 Array{Int64,2}:
  2 3 6
  4 6 3
  2 6 1
  9 3 8
  9 4 3
  4 9 5
  5 9 8
  7 1 6
  7 5 1
  6 4 7
  4 5 7
 10 5 8
  1 5 10

```

---

<div class="post-metadata">

**Author:** ![Pbellive](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pbellive/32/3604_2.png) [@Pbellive](https://discourse.julialang.org/u/Pbellive)\
**Post date:** [December 1, 2020, 5:32pm UTC](https://discourse.julialang.org/t/delaunay-triangularization/36172/20 "2020-12-01T17:32:14Z")

</div>

Sorry about that. Looks like I left a line out of my example. The key line I left out was:

```julia
DT = DelaunayTessellation2D{Point2DI}(n)

```

My example is using a custom point type `Point2DI`. When using a custom point type you need to specify that point type when initialising the `DelaunayTessellation`. When you do `DT = DelaunayTessellation()` it returns a `DelaunayTessellation2D{Point2D}`, rather than a `DelaunayTessellation2D{Point2DI}`

Discourse won’t let me edit my original post so here’s the updated self-contained example that actually works now:

```julia
using GeometricalPredicates, VoronoiDelaunay
mutable struct Point2DI <: AbstractPoint2D
  _x::Float64
  _y::Float64
  _i::Int64
end

Point2DI(x::Float64, y::Float64) = Point2DI(x, y, 0)

import GeometricalPredicates.getx
import GeometricalPredicates.gety
import VoronoiDelaunay.isexternal

getx(p::Point2DI) = p._x
gety(p::Point2DI) = p._y
geti(p::Point2DI) = p._i

function isexternal(p::Point2DI)
  getx(p) < VoronoiDelaunay.min_coord || getx(p) > VoronoiDelaunay.max_coord
end

x = randn(10); y = randn(10)

n = length(x)
DT = DelaunayTessellation2D{Point2DI}(n)
d0 = VoronoiDelaunay.min_coord
dd = VoronoiDelaunay.max_coord - VoronoiDelaunay.min_coord
dn = VoronoiDelaunay.max_coord
x0,xn = extrema(x)
y0,yn = extrema(y)
dx = xn-x0
dy = yn-y0
u = d0 .+ ((x .- x0) ./ dx) .* dd
v = d0 .+ ((y .- y0) ./ dy) .* dd
P = Point2DI[Point2DI(ui, vi, i) for (ui, vi, i) in zip(u, v, 1:n)]
push!(DT, P)

```

Note that you’re not required to define your own point type, you can use the built in Point2D type. I just decided to illustrate using a custom point type in my example.

[Next page](https://discourse.julialang.org/t/delaunay-triangularization/36172.md?page=2)