14

Is there some method to get a triangulation in 2D that is more ordered like Matlab Delaunay produces? Here is an example of Matlab's 2D Delaunay triangulation.

matlab delaunay

Using this code:

xPoints = np.arange(0,11,1)
yPoints = np.arange(0,11,1)
gridPoints = np.array([[x,y] for y in yPoints for x in xPoints])
tri = Delaunay(gridPoints)
plt.triplot(gridPoints[:,0],gridPoints[:,1],tri.simplices.copy())
plt.plot(gridPoints[:,0],gridPoints[:,1],'bo')
plt.title("Triangulation Visualization")

I get the triangulation below:

scipy delaunay

Notice how diagonal arcs in the Matlab result all have the same slope; but those in the scipy result are varying. Since Matlab and Scipy both use QHull internally, I presume there is some method to mimic the Matlab result.

Philippe Signoret
  • 13,299
  • 1
  • 40
  • 58
Vance T
  • 513
  • 2
  • 5
  • 15
  • 2
    Obviously both triangulations are "correct", since both kinds of diagonal have the same length. You might want to look at the `qhull_options=` parameter to `Delaunay`, which takes a string of options that are passed to `qdelaunay`. The various possible options are summarized [here](http://www.qhull.org/html/qh-optq.htm), although nothing obvious sticks out. Unfortunately it's not possible to see how MATLAB's `delaunay` function works since it's closed-source. – ali_m Apr 27 '15 at 11:25
  • Yes, both are correct, but since this is a uniform domain, matlab's triangulation allows some simplifications in the math to be taken. Thanks for that link, I hadn't found that one when searching before. – Vance T Apr 27 '15 at 14:08
  • Would it work, for your problem, to explicitly generate the triangulation yourself? This should be reasonable for a uniform rectangular domain. – Alex Szatmary May 04 '15 at 19:06
  • I in fact did go ahead and generate the triangulation myself and will post my code here soon. Unfortunately, the utility of the built-in functions of scipy are lost. – Vance T May 05 '15 at 12:15
  • 2
    [This old doc](http://matlab.izmiran.ru/help/techdoc/ref/delaunay.html) says that the Qhull options used by MATLAB are `'Qt','Qbb','Qc'`, however when I use those with `scipy` I don't get the result you want. I tried various combinations to no avail. Interestingly - on that linked page, a triangulation of a uniform "grid" using Matlab Delaunay (Example 2) does ***not*** show the regularity you seek. I wonder if your particular Matlab example (i.e a unit quare with 0.25 intervals) produced this by fluke? I haven't a Matlab with license to test any longer, unfortunately. – J Richard Snape May 21 '15 at 12:15
  • 1
    For your example, you can produce a nice triangulation by running `qdelaunay` on a linearly transformed set of input points. Adding a small amount of skew, e.g. `x = x + eps * y`, should be sufficient. – bfroehle May 31 '15 at 05:41
  • Do you just want a mesh like in the first image? If yes, you should just build it instead of using triangulation. I don't understand why you would want to use library functions if you /already have/ working code. Is it too slow because it's Python or what? If that's the case, use scipy.weave instead of wasting time on a slow triangulation algorithm. – Joonazan Jun 05 '15 at 14:39

1 Answers1

4

You could try Triangulation instead of Delaunay:

import matplotlib.tri as tri
import numpy as np
import matplotlib.pyplot as plt

xlen = 10
ylen = 16
xPoints = np.arange(0,xlen+1,1)
yPoints = np.arange(0,ylen+1,1)

gridPoints = np.array([[[x,y] for y in yPoints] for x in xPoints])
a = [[i+j*(ylen+1),(i+1)+j*(ylen+1),i+(j+1)*(ylen+1)] for i in range(ylen) for j in range(xlen)]
triang = tri.Triangulation(gridPoints[:,:,0].flatten(), gridPoints[:,:,1].flatten(),a)

plt.triplot(triang)
plt.plot(gridPoints[:,:,0],gridPoints[:,:,1],'bo')
plt.title("Triangulation Visualization")
plt.show()

enter image description here

joscao
  • 35
  • 7