# Software for triangulating a point set (with restrictions)

I want to triangulate a point-set like the one below.

I would like the triangulation of the point-set to have the following properties

1. The triangles must have as vertices the black and orange points

2. The triangles should be nicely shaped (like in Delaunay triangulations) ie not to skinny.

3. I would like to enforce the condition that each black segments should be the edge of some triangle in the triangulation.

4. The other edges of the triangulation must lie within the polygonal region indicated by black segments joining orange points to orange points or orange points to the black points.

CGAL can probably do this but it has been a nightmare to install CGAL on Windows 7. I am looking for any freely available, robust and easily installable MATLAB, Python, C++ (Visual Studio 2012 or Cygwin) solution to this problem on the Windows 7 platform.

• Have you tried Triangle or gmsh? – nicoguaro Mar 22 '15 at 4:29
• Conversion from gmsh to Python is quite easy, as gmsh can export as text. – sebix Mar 22 '15 at 9:06
• Would just Delaunay triangulation work, if you then removed the zero area triangles from the convex hull outline? For computing it, I recommend qhull "qhull.org" or its octave wrapper, but there are other choices. I think qhull might even be able to automatically remove the zero area triangles if you give the right options. – Zsbán Ambrus Mar 23 '15 at 7:19
• A normal Delaunay triangulation will work for any set of points where your enforced edges form the convex hull of the point set (as they do in this case). Matlab has it built in, and uses the Qhull algorithm, which was suggested above. If you need to move the triangulation between languages/programs, gmsh has a very flexible file format that is easy to parse in any high-level language (or you could just write your own text format, which isn't hard for a mesh of only triangles). – Tyler Olsen Mar 23 '15 at 17:00
• I've added a solution in Python/SciPy below, but if you'd like to install CGAL and are content with using the Python bindings, you can find binaries at lfd.uci.edu/~gohlke/pythonlibs/#cgal-bindings. – cfh Mar 27 '15 at 1:25

Scipy already comes with Delaunay triangulation via Qhull, and is easy to install on Windows. Here's an example. As mentioned by Tyler Olsen in a comment above, "[a] normal Delaunay triangulation will work for any set of points where your enforced edges form the convex hull of the point set (as they do in this case)".

In [1]: %pylab
Using matplotlib backend: TkAgg
Populating the interactive namespace from numpy and matplotlib

In [2]: X = rand(50,2)

In [3]: from scipy.spatial import Delaunay

In [5]: D = Delaunay(X)

In [6]: triplot(X[:,0], X[:,1], D.simplices)

In [7]: plot(X[:,0], X[:,1], 'o')

In [8]: show()