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

**URL:** <https://discourse.julialang.org/t/curveproximityqueries-jl-finding-collision-or-proximity-between-parametric-curves-and-convex-objects/22813>\
**Category:** Package Announcements\
**Created:** [April 5, 2019, 6:56pm UTC](https://discourse.julialang.org/t/curveproximityqueries-jl-finding-collision-or-proximity-between-parametric-curves-and-convex-objects/22813 "2019-04-05T18:56:37Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![arlk](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/arlk/32/2465_2.png) [@arlk](https://discourse.julialang.org/u/arlk)\
**Post date:** [April 5, 2019, 6:56pm UTC](https://discourse.julialang.org/t/curveproximityqueries-jl-finding-collision-or-proximity-between-parametric-curves-and-convex-objects/22813/1 "2019-04-05T18:56:37Z")

</div>

[CurveProximityQueries.jl](https://github.com/arlk/CurveProximityQueries.jl)

 ![](https://global.discourse-cdn.com/julialang/original/3X/4/1/41a1b2d44c994872bcb12559fc90546872bc6f3b.gif) ![](https://global.discourse-cdn.com/julialang/original/3X/7/d/7d8804374bc97cfd7dd8d9e4e37ed0ded28a189e.gif)

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 🙂) .

A deeper analysis of the methods and their computational benefits can be found in [our paper](https://arxiv.org/abs/1902.05027). In general, it is faster (and correct up to some numerical tolerance) than brute force approaches.

### Example:

```julia
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](https://global.discourse-cdn.com/julialang/original/3X/2/b/2bc993866f460c2feae4701112bf4966eb44fd12.png)

---

<div class="post-metadata">

**Author:** ![leethargo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leethargo/32/6004_2.png) [@leethargo](https://discourse.julialang.org/u/leethargo)\
**Post date:** [April 5, 2019, 7:44pm UTC](https://discourse.julialang.org/t/curveproximityqueries-jl-finding-collision-or-proximity-between-parametric-curves-and-convex-objects/22813/2 "2019-04-05T19:44:37Z")

</div>

Very nice! A shout-out to the related [GitHub - arlk/ConvexBodyProximityQueries.jl: A fast module for computing proximity queries between convex bodies in 2D/3D](https://github.com/arlk/ConvexBodyProximityQueries.jl) as well, of which I was not aware before 👏

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [April 5, 2019, 7:59pm UTC](https://discourse.julialang.org/t/curveproximityqueries-jl-finding-collision-or-proximity-between-parametric-curves-and-convex-objects/22813/3 "2019-04-05T19:59:11Z")

</div>

wow! These animations oddly reminded me of [DynamicalBilliards.jl](https://juliadynamics.github.io/DynamicalBilliards.jl/dev/) !

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

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [April 6, 2019, 3:22am UTC](https://discourse.julialang.org/t/curveproximityqueries-jl-finding-collision-or-proximity-between-parametric-curves-and-convex-objects/22813/4 "2019-04-06T03:22:05Z")

</div>

Cool stuff! Related to ConvexBodyProximityQueries, I just wanted to point out that there’s also [GitHub - JuliaRobotics/EnhancedGJK.jl: GJK signed distance algorithm for convex bodies in Julia](https://github.com/JuliaRobotics/EnhancedGJK.jl).