Integration of other packages in JuliaGeometry

[sjkelly]

First off, great job on this package, I'm looking forward to testing it out. This is a followup to the discussion in https://github.com/JuliaGeometry/GeometricalPredicates.jl/issues/36 .

I maintain a few packages that use Mesh and Polytope types heavily:

• [x] PolygonOps.jl
• [x] TriangleIntersect.jl
• [ ] Meshing.jl
• [ ] Contour.jl
• [ ] DistMesh.jl
• [ ] Descartes.jl

The current integrations are GeometryTypes and GeometryBasics. To add the Meshes.jl interface it seem like the preferred approach is to copy paste the code here as a mono-repo. After discussions in https://github.com/JuliaGeometry/GeometricalPredicates.jl/issues/36 I agree this is a good approach for rallying contributions and improvements. Do these packages seem reasonable to integrate into Meshes.jl?

[juliohm]

Thank you for testing the package and for joining the effort @sjkelly. Your expertise is much needed to improve the situation we currently face in JuliaGeometry.

Regarding the packages listed, I think we can start working on the migration of the basic building blocks like PolygonOps.jl. As I mentioned in that issue, we may already have the operations in Meshes.jl but we can certainly double check and improve if something is not optimal or robust. After we finish with PolygonOps.jl, we can mark the package as maintenance mode, and point to Meshes.jl so that current users become aware of the broader initiative.

Having finished the migration of PolygonOps.jl, I think the next building block is GeometricalPredicates.jl. Are you also familiar with the package internals and BigInt representations needed? If we manage to merge these two packages, we will then be able to start the migration of more advanced routines like your isosurface extraction algorithms in Meshing.jl, and other meshing algorithms in DistMesh.jl, VoronoiDelaunay.jl, etc.

Do you think this is a good plan? Let me know how we can help with the migration of PolygonOps.jl and if something needs to be adapted here to accommodate additional features. I will edit your issue to make the bullet points check-able, to keep track of what is missing.

Thank you again for considering the proposal. Looking forward to exchanging knowledge.

[sjkelly]

I have not looked into GeometricalPredicates in a while, but have taken a few stabs at porting it to GT/GB in the past, with not good results. I think a more modern approach is to use Interval math for predicates in floating point, with fallbacks. I did some experiments in the past and intervals were faster with modern SIMD optimizations and rounding modes. Would be good to double check (code example below). This similar to what TetGen and GMsh do for predicates also.

"""
Experimental method for incircle using interval arithmetic.
determine if d is in the circumcircle of a,b,c
"""
function incircle(a,b,c,d)
    T = promote_type(eltype(a),eltype(b),eltype(c),eltype(d))
    # pow uses Big Float. See what happens if we don't
    ai = SVector{length(a),Interval{T}}(a)
    bi = SVector{length(b),Interval{T}}(b)
    ci = SVector{length(c),Interval{T}}(c)
    di = SVector{length(d),Interval{T}}(d)
    m = @SMatrix [ai[1]-di[1] ai[2]-di[2] (ai[1]*ai[1]-di[1]*di[1])+(ai[2]*ai[2]-di[2]*di[2]);
                  bi[1]-di[1] bi[2]-di[2] (bi[1]*bi[1]-di[1]*di[1])+(bi[2]*bi[2]-di[2]*di[2]);
                  ci[1]-di[1] ci[2]-di[2] (ci[1]*ci[1]-di[1]*di[1])+(ci[2]*ci[2]-di[2]*di[2])]
    detm = det(m)
    # det is positive is d is inside
    delta = detm.hi - detm.lo
    @show delta, (delta/2)+detm.lo
    detm
end

[juliohm]

We have a professor at our institute that works actively with interval math. I have never used it myself, but it is good to know that it works well with these predicates. We also have JuliaIntervals at our disposal if we decide that some of these predicates are better implemented with interval math.

Regarding PolygonOps.jl, I see you have two methods implemented for point in polygon queries. Should we start migrating them? #100 is related, but based on winding numbers. If we migrate these two methods, I think we can check the box for PolygonOps.jl.

[mdmaas]

Hi! Good job on this package. I'm interested in joining efforts, if the very long-term idea is to create a pure-julia version of CGAL ;-). I'm not an expert in Computational Geometry, but always liked the field.

For what is worth, ExactPredicates.jl looks more promising than GeometricalPredicates.jl. It implements robust predicates with Interval arithmetic and code generation. It looks like the version in Julia's Pkg registry is outdated, tough.

And for PolygonOps, there is another very interesting package with fast algorithms for points-in-polygons: PolygonInbounds.jl. It is based on a very recent paper.

I'll see what I can do about this, and get back to you.

Regards!

[juliohm]

Amazing @mdmaas , looking forward to your contributions 😃 The ExactPredicates.jl package indeed looks very interesting and self-contained 💯 Appreciate if you can compare our current method for point \in polygon with PolygonInBounds.jl, and if the latter method has major benefits, we can figure out how to incorporate it here.

[mdmaas]

Hi @juliohm. Indeed, ExactPredicates.jl could be integrated at no cost, just by using ExactPredicates. As for PolygonInBounds.jl, I believe the package is a port of a matlab code which is the "simple" version of a state-of-the-art algorithm to solve massive multiple-points-in-multiple-polygons problems, like the ones we often face in geospatial data. I haven't checked which algorithm was implemented in point \in polygon, so maybe a benchmark could be useful.

[juliohm]

@sjkelly we have ray-triangle intersection now. The algorithm was implemented by @HaoxuanGuo and it seems to be slightly faster than TriangleIntersect.jl. I've added the package to the list above and checked it as done 👍🏽

[sjkelly]

Great! DistMesh and Descartes are now registered as well, so it would be nice to add compatibility to those as well.

[juliohm]

Hi @sjkelly, I am closing this issue given the lack of activity from your side. We are open to review PRs if you submit any in the future.