I’m looking for geometry package, which has Euclidean point to point and point to line distances in 3D implemented.
Distances.jl?
1 Like
Use norm in LinearAlgebra (in the standard library) for point to point distance.
Point to line needs a touch of geometry and then use norm again, e.g. Distance from a point to a line - Wikipedia
2 Likes
I know how to do it from scratch. I was hoping that a basic computational geometry package is lurking somewhere. The closest I found is a highly experimental GitHub - rgcv/CGAL.jl: CGAL meets Julia
I agree that it seems to be missing.
Perhaps designing a good API is actually much more work than just reimplementing the algorithms each time!
1 Like
Here’s some simple code:
using StaticArrays
using LinearAlgebra
"Point in N dimensions"
struct Point{N,T}
x::SVector{N,T}
end
"Line in N dimensions. `p` is a point on the line and `u` is the direction vector
(not necessarily normalized). Parametrised as \$p + ut\$"
struct Line{N,T}
p::SVector{N,T}
u::SVector{N,T}
end
distance(p1::Point{N}, p2::Point{N}) where {N} = norm(p1.x - p2.x)
function distance(y::Point{N}, l::Line{N}) where {N}
p, u = l.p, l.u
t = (y.x - p) ⋅ u / (u ⋅ u)
x = Point(p + t*u)
return distance(x, y)
end
l = Line(SA[1.0, 2, 3], SA[1.0, 1.0, 1.0])
p = Point(SA[4., 6., 6.])
distance(p, l)
Of course it would be better to use GeometryBasics.jl.
Maybe this could / should be incorporated there.
4 Likes
This thing is beautiful and scary at the same time. Definitely an overkill for simple Euclidean 3D spaces. I’m leaning towards implementing some basic functionality using SIMD.jl package and represent 3D points/vectors as SIMD.Vec{4,Float32} for performance.
1 Like
Well hi there, sorry to barge in.
I knew deeming it highly experimental would prove difficult for someone to use it confidently. I’ve removed that notice since. Despite it still being somewhat experimental, as testing is performed in a terribly confined environment, I’m confident it can perform well when necessary. Luckily that will soon change as I aim to register the package in the General registry, hopefully birthing an influx of issues and requests, maybe even contributions, to the fold. It is a relatively daunting undertaking!
As it stands, there are a couple of functions and types exposed from CGAL. 3D Point-Point and Point-Line distances are indeed present in the package. They come in the form of squared distances since CGAL tends to promote robustness over potentially unnecessary inexact/costly computation, but if the absolute distance is needed, sqrt will work just fine.
1 Like
Thank you for working on this package. I think it may be of interest to many Julia users due to CGAL being a top-notch computational geometry library.
BTW, do you have any functions from 2D Polyline Simplification package wrapped up?
TL;DR: Thanks! Unfortunately, I’ve overlooked 2D Polyline Simplification. There’s some foundation for it in place, but it’s not a near future priority. I’ll bear it in mind though.
I’m glad to see someone has found interest in it.
I’m sorry to say that I haven’t looked at that package yet, no. However, some of the building blocks such as 2D Triangulations (bit finicky, but usable) and 2D Polygons have already been mapped. I will keep this in mind moving forward.
Be that as it may, I wouldn’t hold my breath as it is not an immediate priority to wrap that package. A bit of background: this package was born out of necessity to obtain a series of types, functions, and algorithms as a foundation for another potential geometric constraint library, allowing for the description of constrained geometry in a textual fashion. Yes, there are constraint solvers out there, even geometric ones. Regardless, I set out to try constructive approaches instead. Fundamentally, they’re an abstraction over numerical and algebraic solvers, but we can always boil it down to numbers.
Enough rambling! Sorry to take up your time ^^
2 Likes
Thanks for sharing your plans. Not rambling at all. 
1 Like
The Chapter 6 of Geometric Tools Engine by Schneider, Eberly is to my knowledge the best source on the subject. CGAL can get nerdy so quickly.
Authors have worked at walt disney, dec, magic software
The license is boost, eg. ~ mit.
Code has been written during more than two decades and is still updated!
A good basis for an interface / API
Let’s make a port (: !
1 Like
I used Geometric Tools for a prototype in C++ and I agree that it has fewer abstractions, which get in a way, compared with CGAL and especially with boost.geometry, which earns top nerdy honors. CGAL is much more comprehensive and has a real manual, though.
Eberly is close to releasing Geometric Tools Library (GTL), which will be a rewrite of Geometric Tools Engine.
Book and code have been delayed in reason of covid. Book was finally published in june 2020. And we are now waiting for code.
I bet it will be trapped in C++ land, and will certainly port some parts this year or next year since license will be boost too.
In general, I have interest in porting or developing high performance 2D and 3D basic computational geometry package. I don’t care about dimensions higher than 3 and accurate geometry. I will be fine with Float32 accuracy. Having an option of Float16 for faster compute on GPU would be nice.
I will know more in months to come. I have to learn more about Julia and specifics of my project, before I can contribute.
I intend to port a large bunch of work from Eberly, Ghali, Bostock starting in a couple of monthes.
Recent work of Eberly address robustness issues in CG. I am not so pro about this.
It remains to be determined how that will be handled.
I intend to contribute to https://github.com/JuliaGeometry/ https://github.com/JuliaGeo/
https://github.com/JuliaGraphics as much i can open source / we can pursue commons goal.
I work mainly in 2d/3d. Straight geometry, no bezier/spline curve, nurbs.
IMO, About the current state of
- CG in General : 2d does not belong to plot, 3d does not belong to mesh.
- GFX in Julia : Colors.jl is too tricky and GeometryBasis.jl too simple.
1 Like
Indeed, Grassmann could be used for this also, I haven’t specifically built in functionality for the distance of a line and a point, although you could efficiently express it with geometric algebra. Currently, I am also working on supporting differential geometric calculations on a discrete manifold in any number of dimensions (1D, 2D, 3D, 4D, 5D, etc). I would recommend trying out the algebra in my package, I am using it as a foundation for geometry, similar to GeometryBasics, but different design.
1 Like
Here is a solution using LazySets.jl:
using LazySets
# construct a line passing a point and the direction vector
l = Line([1.0, 2, 3], [1.0, 1.0, 1.0])
p = [4., 6., 6.]
distance(p, l)
0.816496580927726
# alternative constructor passing two points of the line
b = Line(from=[1.0, 2, 3], to=[2.0, 3, 4])
distance(p, b)
0.816496580927726
implementing some basic functionality […] for performance.
For performance consider using StaticArrays.jl as already suggested by @dpsanders,
using StaticArrays, BenchmarkTools
l = Line(SA[1.0, 2, 3], SA[1.0, 1.0, 1.0])
p = SA[4., 6., 6.]
@btime distance($p, $l)
7.105 ns (0 allocations: 0 bytes)
0.816496580927726
4 Likes
Using Grassmann.jl and a simple G(3,0,0) metric
julia> using Grassmann, BenchmarkTools
julia> basis"+++"
(⟨+++⟩, v, v₁, v₂, v₃, v₁₂, v₁₃, v₂₃, v₁₂₃)
julia> a,n = (1.0v1+2.0v2+3.0v3), (1.0v1+1.0v2+1.0v3)
(1.0v₁ + 2.0v₂ + 3.0v₃, 1.0v₁ + 1.0v₂ + 1.0v₃)
julia> p = 4.0v1+6.0v2+6.0v3
4.0v₁ + 6.0v₂ + 6.0v₃
julia> dist(a, n, p) = norm(((p-a)∧n)/n)
dist (generic function with 1 method)
julia> @btime dist($a,$n,$p)
10.874 ns (0 allocations: 0 bytes)
0.816496580927726
Note with Geometric Algebra you don’t need to normalize the line direction. A more fair comparison with the example using LazySets.jl should include Line construction.
julia> @btime distance($p, Line($a, $n))
39.027 ns (0 allocations: 0 bytes)
0.816496580927726
5 Likes