Fast Robust Predicates for Computational Geometry: Something in Julia?

General Usage
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: Fast Robust Predicates for Computational Geometry
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 Likes
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:

1 Like
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…

5

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
6

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.

1 Like
7

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.

1 Like