Fast Robust Predicates for Computational Geometry: Something in Julia?

Hello all,

I am doing a lot of computations for a package (DynamicalBilliards.jl) where I very often compute dot products, differences, multiplications and sums of floating point numbers that are very small (order of 1e-12 to 1e-16) and also very close with each other. Of course this is bad computationally and I have noticed that it is extremely hard to control the precision of the outputs, since the results of these computations are always compared with numbers of order 1… Normally I get deviations from the “theoretically expected” calculations of order of 1e-10 instead of 1e-16.

In essence, there are some things that I compute all the time, but could maybe be done better. What I need in the most fundamental level are methods to deduce:

  1. Whether a point is inside or outside of a circle.
  2. Whether a point is to the left or to the right of a straight line
  3. The distance of a point from a straight line.

At all of these cases the point is extremely close to the circle/line. I have found online that there exists a resource written by Jonathan Richard Shewchuk here: https://www.cs.cmu.edu/~quake/robust.html
with a short paper giving the algorithms here: https://people.eecs.berkeley.edu/~jrs/papers/robust-predicates.pdf

The problem is, I don’t understand the paper since I am not a computer scientist. So I am asking here, is there something similar implemented in Julia? Or in general are there any methods to calculate my 3 points without having to subtract numbers that are close to 1e-16 all the time?

Example: to calculate whether a point is inside of a circle or not I calculate d = norm(pos - a.c) - a.r with a.c the center of the circle and a.r the radius. If d>0 the particle is outside the circle.

1 Like

Would this be helpful?

@yarik12 The first link is super promising, and would be what I was looking for. Unfortunately the limitation 1<=x <= 2 is very extreme and makes the package unusable :frowning:

1 Like

Not sure, but I think you could easily normalize your grid to that, but haven’t looked at it in greater detail. If you’re looking for intersections and reflections etc you could take a look at RayTraceEllipsoid.jl

I had the same frustration that you had with GeometricalPredicates.jl, so I developed and recently released ExactPredicates.jl. It is robust, extensible and provides similar performance than CGAL or Shewchuk’s library. I can easily add new predicates, just ask.

8 Likes

All of these are fairly simple using conformal geometric algebra, which I implemented in Grassmann.jl package. Computing intersections of things or determening whether something is inside or outside, or computing distances is all built in to the algebra.

This may or may not be related, but problem number 2 in the 100 digit challenge consists essentially of simulating billiards with circular obstacles. The normal way of solving this is to use large or arbitrary precision arithmetic. I am not aware of a way of doing this correctly in the usual floating point arithmetic.