CurveProximityQueries.jl - Finding collision or proximity between parametric curves and convex objects

#1

CurveProximityQueries.jl

This package provides efficient methods to compute the closest points, minimum distance, tolerance verification, and collision detection for parametric curves. This can be used in motion planning algorithms when the feasibility of a planned trajectory in obstacle-rich environments must be verified. By default, it handles parametric curves defined by Bernstein polynomials but it can be extended for any absolutely continuous parametric curve (PRs welcome :slight_smile:) .

A deeper analysis of the methods and their computational benefits can be found in our paper. In general, it is faster (and correct up to some numerical tolerance) than brute force approaches.

Example:

julia> curve = rand(Bernstein{2, 11})  # a tenth order Bernstein polynomial in R^2
a 10th order Bernstein polynomial with control points at:
([0.589371, 0.714336], [0.412222, 0.978291], [0.0227922, 0.853979], [0.100673, 0.79086], [0.886581, 0.111195], [0.258316, 0.182479], [0.455801, 0.74483], [0.749289, 0.181462], [0.406074, 0.0973739], [0.507534, 0.665799], [0.416049, 0.0165246])
with an arclength of 1.622728476731966

julia> poly = randpoly([0.0, 0.5], scale=0.5) # random decagon centered at 0.0, 0.5 and scaled down to roughly half the size of a unit square
ConvexPolygon{2,10,Float64}(SArray{Tuple{2},Float64,1,2}[[-0.117432, 0.964123], [-0.336266, 0.859416], [-0.422451, 0.614384], [-0.493171, 0.401837], [-0.246706, 0.11717], [-0.0651607, 0.176502], [0.192354, 0.297326], [0.309595, 0.679598], [0.315428, 0.720252], [0.0549531, 0.867691]])

julia> pts =  closest_points(curve, poly)
([0.309957, 0.660306], [0.230249, 0.630564])

julia> plot(curve); plot!(poly); plot!(pts)

example

14 Likes

#2

Very nice! A shout-out to the related https://github.com/arlk/ConvexBodyProximityQueries.jl as well, of which I was not aware before :clap:

1 Like

#3

wow! These animations oddly reminded me of DynamicalBilliards.jl !

I wonder if I could ever use something like this there…

1 Like

#4

Cool stuff! Related to ConvexBodyProximityQueries, I just wanted to point out that there’s also https://github.com/JuliaRobotics/EnhancedGJK.jl.

0 Likes