[ANN] Announcing CGAL.jl

Package Announcements
, , ,
1

Good evening,

I’m pleased to announce that I’ve just registered CGAL.jl, a package that aptly maps a series of types and functionality from CGAL (Computational Geometry Algorithms Library), a C++ library, to Julia.

I’ve been hammering away for quite a while now, trying to bring CGAL types, functions, and algorithms to julia for my sake. Henceforth, I’d like to make it easily available for anyone and everyone who would be interested in using it.

It currently makes available most, if not all, linear kernel objects, some circular/spherical functionality, and a few packages (2D Convex Hulls, 2D Triangulations, Voronoi Diagram adaptor, Principal Component Analysis), albeit some not entirely mapped due to some technical limitations, along with intellectual ones (I’m not that smart of a cookie). Documentation is relatively lacking, only having some reference docs available. Future work, I suppose.

Any and all feedback, criticism, and contributions are welcome!

38 Likes
2

Thanks a lot for this - I’ve had my eye on CGAL for a while, for CSG operations.

2 Likes
3

Do you know off hand if CGAL lets you obtain the centroidal voronoi tesselations? Or computer voronoi barycenters? if so this will be up on my list.

4

As far as I can tell, I can’t see an elegant way of obtaining such tessellations. However, there is a package in CGAL, namely 2D Conforming Triangulation and Meshes, that includes functionality to create Lloyd optimized meshes, which leads me to believe it is possible to create such a triangulation which can then be used to construct a 2D Voronoi Diagram.

Now I haven’t researched much, but from the little I gather, Lloyd’s optimization algorithm is used in computing Centroidal Voronoi Tesselations, which is why it leads me to believe this is viable. Of course, I’m a newblet when it comes to that kind of advanced geometrical algorithms, so don’t take my word for it.

Be that as it may, I can see it being a hindrance to try and make such a package available as it depends on a different parametric instantiation of the Constrained_delaunay_triangulation_2 class. My approach thus far involves creating instances of these types on the C++ side of things, making them opaquely available in julia. Arguably, this is a terrible approach since I could probably try and leverage the parametric mechanisms in CxxWrap to map these types near 1:1. However, this was a design choice made a while back in order to at least get something out of CGAL and make it relatively usable. I knew it would bite me in the ass eventually. Ever since, I’ve had to do some juggling to try and tame that beast of a library, but its complexity is abominable, beyond my capabilities, unfortunately.

That said, I’m not willing to necessarily call it quits. In the future, it would be nice to parameterize types properly, starting with providing many different kernels and numeric types, maybe even map such numeric types to already existing ones in julia (e.g. CGAL::Gmpq to Rational or CGAL::Exact_integer to BigInt). This would allow the user to more freely dial in the settings he’d like when using the library, opening a door to a wide range of new possibilities, instead of being confined to sensible defaults I’ve chosen…

Anyways, I’m rambling again at this point. Hope I made myself clear and helped you in any way, shape, or form.

1 Like
5

You can do it with GMT. I need to polish some of of the code to make some of the below look less cryptic

using GMT
d = [2.54 5.17 0; 2.48 6.27 1; 8.69 4.56 2; 4.11 7.79 3; 1.80 6.53 4; 7.17 3.82 5; 3.41 8.18 6; 8.35 1.43 7; 8.17 4.47 8; 5.28 1.15 9];

Dv = triangulate(d, voronoi=:n, limits=(0,10,0,10));		# Get the Voronoi polygons
Dc = gmtspatial(Dv, area=true);				# Computes also the baricenters
G = nearneighbor(GMT.GMTdataset(d), nearest=true, limits=(0,10,0,10), inc=0.05);	# Compute grid needed for image below
C = makecpt(cmap=:categorical, range=(0,10,1));		# A discrete colormap
grdimage(G, proj=:linear, title="Natural Nearest Neighbor Gridding", color=C)	# Plot image
plot!(Dv)			# Plot Voronoi polygons
plot!(Dc, marker=:circle, ms=0.2, mc=:black, fmt=:png, show=true)	# Plot Voronoi baricenters

GMTjl_tmp
GMTjl_tmp1572×1658 94.8 KB

2 Likes
6

Will GMT work for N-dim space or at least 3-space?

7

Nope, it’s only xy

1 Like
8

I’m a regular CGAL user and it’s great to see this.
For some reason Julia’s computational geometry side is lacking, in relation with other areas. But I won’t complain much about it or else someone will tell me to do the work myself.

2 Likes
9

I’m glad! Though I’m afraid this isn’t the full-fledged CGAL regular users like you know, much of the template instantiation is hidden away.

As I say this, there might hope for some of that in the future though. I just recently pushed a few changes that allow one to parameterize VoronoiDiagram2, allowing for the creation of Voronoi Delaunay and Power (Laguerre) Diagrams using DelaunayTriangulation2 and RegularTriangulation2 respectively. So who knows, maybe down the line I’ll parameterize the kernels… Though I fear the degree of complexity will spike as soon as such a change is attempted.

Regarding the Julia geometry ecosystem: It seems a bit lacking here and there, but GeometryBasics.jl is well on its way to replace its predecessor with flying colors. There are also other packages in the JuliaGeometry, as well as in the wild, that, combined, end up being a more than suitable replacement for CGAL.jl as it stands.

Of course, eventually, I’d like to polish the bindings and bring more and more things out of the daunting beast. Be that as it may, it’s starting to feel like a herculean effort here and there. Some things I just completely skip altogether since they involve more skill than the one I makeshift possess. That and I have a thesis to write! Should put that on the front seat someday… Oops :sweat_smile:

1 Like