Point to line distance in GeometryBasics or another geometry package

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. https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

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 https://github.com/rgcv/CGAL.jl

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!

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.

3 Likes

Can it be easily calculated with Grassman?

1 Like

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. :smiley:

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 (: !

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.

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
4 Likes