Homepage of Stefan Salewski
Ruby bindings for Constrained Delaunay Triangulation of CGAL library (2D)
For some areas of geometrical data processing, like topological routing, it is necessary to generate triangulations of a set of vertices. One popular triangulation is the Constrained Delaunay Triangulation (CDT), see wikipedia.org/wiki/Delaunay_triangulation. Generation is not trivial -- the GTS and CGAL library supports this type of triangulation, including dynamic insertion and removing of vertices and constraints. I started with the gts library. As it is written in C, it was not difficult writing bindings for Ruby. But there seems to be not much activity on the gts mailing list, and I was not able to fully understand its documentation.
So I started investigating the large CGAL C++ library. Indeed it was not difficult to write some basic bindings for Ruby. Actually the CGAL bindings needed less lines of code, and calling it from Ruby is simpler.
I have defined two data types, CGAL::CDT and CGAL::Vertex. t = CGAL::CDT.new creates an empty triangulation, and v = CGAL::Vertex.new(x, y) creates Vertices with coordinates x, y, which we can insert into the triangulation. You can extend your vertices as you do with other Ruby classes, v.x and v.y can be used to read the coordinates. Currently we have these methods defined:
t.each{|el| puts el.whatever}
t.insert(vertex)
t.insert_constraint(vertex1, vertex2)
t.neighbor_vertices(v) # returns array of all neighbour vertices of v
t.to_a # returns array of all vertices
# Installation (for Linux)
# You need a C compiler, installed CGAL library and Ruby interpreter (tested with 1.9.3)
cd RCGAL
ruby extconf.rb
make
# ruby test.rb
require_relative "rcgal_cdt"
t = CGAL::CDT.new
v1 = CGAL::Vertex.new(0, 0)
v2 = CGAL::Vertex.new(0, 10)
v3 = CGAL::Vertex.new(10, 0)
v4 = CGAL::Vertex.new(10, 10)
t.insert(v1)
t.insert(v2)
t.insert(v3)
t.insert(v4)
t.insert_constraint(v1, v4)
t.each{|el| print el.x, ", ", el.y, "\n"}
t.each{|el|
puts t.neighbor_vertices(el)
puts
}
puts (t.methods - Object.methods).sort
Please note that this is the initial release of these bindings, I have not done much testings. I am using it for my PCB topological router project, it seems to work fine. Adding more methods should be not too difficult -- maybe someone can manage to generate full bindings for Ruby, maybe by using SWIG? I know that there are some bindings/wrappers available for Python and Java, but I guess generation of full Ruby bindings is difficult due to all the C++ template stuff.