3
$\begingroup$

I want to triangulate a point-set like the one below. enter image description here

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.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Have you tried Triangle or gmsh? $\endgroup$
    – nicoguaro ♦
    Mar 22, 2015 at 4:29
  • $\begingroup$ Conversion from gmsh to Python is quite easy, as gmsh can export as text. $\endgroup$
    – sebix
    Mar 22, 2015 at 9:06
  • $\begingroup$ 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. $\endgroup$
    – Zsbán Ambrus
    Mar 23, 2015 at 7:19
  • $\begingroup$ 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). $\endgroup$
    – Tyler Olsen
    Mar 23, 2015 at 17:00
  • $\begingroup$ 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. $\endgroup$
    – cfh
    Mar 27, 2015 at 1:25

1 Answer 1

Reset to default
4
$\begingroup$

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()

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.