JuliaGeometry/DelaunayTriangulation.jl

Awesome to see a new package for this!

Closed this issue · 7 comments

juliohm commented

We are advancing geometric processing in Julia with the Meshes.jl umbrella. Would it make sense to port this code over there? We can always integrate code using dependencies, but many things like exact predicates and other low-level functions are already available there, which makes ExactPredicates.jl and other dependencies not necessary.

DanielVandH commented

Hi @juliohm, thanks for your comment!

I'm not against combining the codes, although I plan to keep updating this package with other features and my limited time may make it a bit difficult to do these updates through a separate package (which I imagine has much higher standards than me!). What would the process be like for porting the code and then maintaining it?

This package was initially built on the Meshes interface actually, but I needed the features I describe in my Customisation section of the README / my Gmsh code for some of my research.

but many things like exact predicates and other low-level functions are already available there

I remember looking and I wasn't able to find any exact predicates. I had assumed it used e.g. GeometricalPredicates.jl which isn't as robust / easy to extend with new robust predicates.

juliohm commented

What would the process be like for porting the code and then maintaining it?

We could start with a PR that defines the interface (set of function names and data structures) for tessellation. I noticed that you used the term "triangulate" in the package but that term is often associated with what we call "discretize" and "simplexify" in Meshes.jl. These operations take a region as input and split it into elements. Tessellation on the other hand takes a set of points as input and fills the space with elements.

Regarding maintenance, you would be leading the development of these tessellation features. We have maintainers leading other initiatives in Meshes.jl like @dorn-gerhard who has contributed many intersection algorithms.

which I imagine has much higher standards than me!

We do have high standards, but that is a good thing! :) In the long run we can achieve much more with picky reviews and careful tests. Working on a coherent experience for end-users is one of the greatest things we can do for the community.

This package was initially built on the Meshes interface actually, but I needed the features I describe in my Customisation section of the README

I scanned the section quickly and couldn't find exactly what features were missing. I think that this is an opportunity to improve Meshes.jl even further if something is not there that could accommodate your tessellation algorithms. We are constantly evolving the Meshes.jl internals to make it more general, and that is why we are still v0.x.z. There are plans of more breaking changes to accommodate use cases in industrial applications.

DanielVandH commented

I see. This does seem interesting, although I don't currently have the time for starting that. I'd be happy to think more about this in the new year, since I would agree that having some of these features available in Meshes.jl would be useful for more people - though I also like the idea of having a separate package for tessellations since I have other packages in development that only need tessellations.

We do have high standards, but that is a good thing! :) In the long run we can achieve much more with picky reviews and careful tests. Working on a coherent experience for end-users is one of the greatest things we can do for the community.

I agree - one (of many) flaw I regularly notice about working individually is that I often come up with design ideas that are clearly bad in hindsight. The code would greatly benefit from other input.

I scanned the section quickly and couldn't find exactly what features were missing.

Maybe I missed them. The main issue I had with Meshes was that I could not move away from a specific definition of a Point or a Triangle and I wanted to easily use ExactPredicates.jl. My own research requires custom points with other information in them, e.g.

struct Cell{L, C}
  x::Float64
  y::Float64
  label::L
  color::C
end

and similarly for triangles I might need

struct Triangles{L1, L2, L3}
  i::Int64
  j::Int64
  k::Int64
  ij_edge_class::L1
  jk_edge_class::L2
  ki_edge_class::L3
end

Does Meshes support this? Basically what I need is to not have to be so devoted to a particular definition of a geometric primitive.

We could talk over Zulip if you wanted to talk some more about this, or e.g. about an interface or other parts of the code.

juliohm commented

My own research requires custom points with other information in them, e.g.

struct Cell{L, C}
  x::Float64
  y::Float64
  label::L
  color::C
end

and similarly for triangles I might need

struct Triangles{L1, L2, L3}
  i::Int64
  j::Int64
  k::Int64
  ij_edge_class::L1
  jk_edge_class::L2
  ki_edge_class::L3
end

Does Meshes support this? Basically what I need is to not have to be so devoted to a particular definition of a geometric primitive.

We do :) We implemented a different design that splits metadata from the geometry itself because then we can do more performant updates using the Tables.jl API. You can attach data to geometries using the meshdata function:

https://juliageometry.github.io/Meshes.jl/stable/meshdata.html

There is an example in the quickstart here:

https://juliageometry.github.io/Meshes.jl/stable/index.html#Mesh-data

And if you would like to understand why we adopted this design, the following video shows how you can easily manipulate metadata stored in faces, vertices, etc at a high level:

https://www.youtube.com/watch?v=1opCT2lId88

This Discourse post has a more reproducible example:

https://discourse.julialang.org/t/ann-geostats-jl-v0-36/90708

We could talk over Zulip if you wanted to talk some more about this, or e.g. about an interface or other parts of the code.

Sure, let's hangout in the #meshes.jl channel over Zulip or using direct messages if you prefer :)

juliohm commented

@DanielVandH can we get back to this issue and try to slim down the dependencies of DelaunayTriangulation.jl so that it can become a dependency of Meshes.jl?

DanielVandH commented

Hi @juliohm: My apologies, been so incredibly busy that I completely forgot about this issue.

Currently the dependencies are:

DataStructures = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
ElasticArrays = "fdbdab4c-e67f-52f5-8c3f-e7b388dad3d4"
EnumX = "4e289a0a-7415-4d19-859d-a7e5c4648b56"
ExactPredicates = "429591f6-91af-11e9-00e2-59fbe8cec110"
MakieCore = "20f20a25-4f0e-4fdf-b5d1-57303727442b"
Random = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"
SimpleGraphs = "55797a34-41de-5266-9ec1-32ac4eb504d3"

Not sure why I have ElasticArrays there actually, so that could definitely be removed. Not sure that Random is needed.

Are you thinking about the ExactPredicates and MakieCore dependencies? I'd like to keep the ExactPredicates dependency since, by default, I'd want predicates to be exact of course. Maybe the MakieCore could be removed and a recipe instead defined in something like MeshViz.

juliohm commented