Delaunay Triangularization

Specific Domains Geo
13

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:

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.

2 Likes