# Fast Robust Predicates for Computational Geometry: Something in Julia?
**URL:** https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807
**Category:** General Usage
**Created:** [September 10, 2017, 9:19am UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807 "2017-09-10T09:19:20Z")
**Posts on this page:** 7
**Page:** 1
### Author:  [@Datseris](https://discourse.julialang.org/u/Datseris)
#### Post date: [September 10, 2017, 9:19am UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807/1 "2017-09-10T09:19:20Z")
Hello all,
I am doing a lot of computations for a package ([`DynamicalBilliards.jl`](https://github.com/JuliaDynamics/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](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](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.
---
### Author:  [@yakir12](https://discourse.julialang.org/u/yakir12)
#### Post date: [September 10, 2017, 9:34am UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807/2 "2017-09-10T09:34:18Z")
Would this be helpful?
- Fast and robust 2D & 3D incircle/intriangle/etc. for Julia in [GeometricalPredicates.jl](https://github.com/JuliaGeometry/GeometricalPredicates.jl)
- Geometry types for Julia, based on FixedSizeArrays in [GeometryTypes.jl](https://github.com/JuliaGeometry/GeometryTypes.jl)
---
### Author:  [@Datseris](https://discourse.julialang.org/u/Datseris)
#### Post date: [September 10, 2017, 9:58am UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807/3 "2017-09-10T09:58:37Z")
@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 ☹
---
### Author:  [@yakir12](https://discourse.julialang.org/u/yakir12)
#### Post date: [September 10, 2017, 10:00am UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807/4 "2017-09-10T10:00:53Z")
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](https://github.com/JuliaGeometry/RayTraceEllipsoid.jl)…
---
### Author:  [@lairez](https://discourse.julialang.org/u/lairez)
#### Post date: [July 17, 2019, 9:47am UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807/5 "2019-07-17T09:47:56Z")
I had the same frustration that you had with [GeometricalPredicates.jl](https://github.com/JuliaGeometry/GeometricalPredicates.jl), so I developed and recently released [ExactPredicates.jl](https://github.com/lairez/ExactPredicates.jl). It is robust, extensible and provides similar performance than CGAL or Shewchuk’s library. I can easily add new predicates, just ask.
---
### Author:  [@chakravala](https://discourse.julialang.org/u/chakravala)
#### Post date: [July 17, 2019, 3:49pm UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807/6 "2019-07-17T15:49:55Z")
> [@Datseris](#):
>
> 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.
All of these are fairly simple using conformal geometric algebra, which I implemented in [Grassmann.jl](https://github.com/chakravala/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.
---
### Author:  [@loisel](https://discourse.julialang.org/u/loisel)
#### Post date: [July 18, 2019, 1:25am UTC](https://discourse.julialang.org/t/fast-robust-predicates-for-computational-geometry-something-in-julia/5807/7 "2019-07-18T01:25:49Z")
This may or may not be related, but problem number 2 in the [100 digit challenge](https://en.wikipedia.org/wiki/Hundred-dollar,_Hundred-digit_Challenge_problems) 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.