Fast Robust Predicates for Computational Geometry: Something in Julia?


#1

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.


#2

Would this be helpful?


#3

@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:


#4

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