### Author:  [@jcook](https://discourse.julialang.org/u/jcook)
#### Post date: [October 2, 2018, 12:51pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/1 "2018-10-02T12:51:29Z")
Is there a tool out there that is able to find the locations of where two lines cross one another? By line I mean a vector of positions in the 2D plane, where the positions are connected by straight lines. I would prefer not to reinvent the wheel if at all possible.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 2, 2018, 1:28pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/2 "2018-10-02T13:28:45Z")
High school math. You can solve it by finding where two lines cross where lines are parametrised like y=a+bx.
---
### Author:  [@jcook](https://discourse.julialang.org/u/jcook)
#### Post date: [October 2, 2018, 1:41pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/3 "2018-10-02T13:41:13Z")
Thank you for your insightful comments.
I could indeed code up a \mathcal{O}(n^2) all-against-all check, and then spend more time writing it in \mathcal{O}(n\log n). However, I asked this question because hopefully someone else has done all this and put it in a package, which I know exist in python and matlab.
---
### Author:  [@xiaodai](https://discourse.julialang.org/u/xiaodai)
#### Post date: [October 2, 2018, 2:04pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/4 "2018-10-02T14:04:43Z")
Oh so u have n lines. And you want to look for a coded up package. Good luck with that.
I thought this would be straightforward enough to write something. Looks like you might want sort them by x coordinate and find overlaps and sort again by y coordinate to find overlaps at which point you should have m\
### Author:  [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)
#### Post date: [October 2, 2018, 2:47pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/5 "2018-10-02T14:47:08Z")
```julia
using GeometryTypes
a = LineSegment(Point2f0(0,0), Point2f0(1,0))
b = LineSegment(Point2f0(0.5,0.5), Point2f0(0.5,-0.5))
intersects(a,b)
#Output: (true, Point2f0(0.5,0.0))
```
---
### Author:  [@jcook](https://discourse.julialang.org/u/jcook)
#### Post date: [October 2, 2018, 3:00pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/6 "2018-10-02T15:00:28Z")
Many thanks!
---
### Author:  [@mohamed82008](https://discourse.julialang.org/u/mohamed82008)
#### Post date: [October 2, 2018, 3:23pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/7 "2018-10-02T15:23:06Z")
I now realize this is not what you are looking for, since you want a path of lines if I understand correctly, but at least your implementation can be made a PR in that package.
---
### Author:  [@jcook](https://discourse.julialang.org/u/jcook)
#### Post date: [October 2, 2018, 3:25pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/8 "2018-10-02T15:25:23Z")
Indeed, and I see that there are rectangle types in that package that know if they overlap one another. They can be used to avoid pair-wise comparisons with sections of the data.
---
### Author:  [@jcook](https://discourse.julialang.org/u/jcook)
#### Post date: [October 2, 2018, 6:29pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/9 "2018-10-02T18:29:13Z")
It appears that the linear crossings algorithm in `GeometryTypes` doesn’t cope well with exactly vertical lines. There’s an issue about it already.
---
### Author:  [@Orbots](https://discourse.julialang.org/u/Orbots)
#### Post date: [October 2, 2018, 6:53pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/10 "2018-10-02T18:53:39Z")
For reducing to n\*log(n) you could use something like this:
[https://github.com/krcools/CollisionDetection.jl](https://github.com/krcools/CollisionDetection.jl)
It’s 3D, but you can simply add a small ‘z’ extent and put everything else in the xy plane.
I believe there are other packages with BVH or spatial partitioning trees implemented in julia out there.
---
### Author:  [@Orbots](https://discourse.julialang.org/u/Orbots)
#### Post date: [October 2, 2018, 7:06pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/11 "2018-10-02T19:06:51Z")
Actually looks like CollisionDetection.jl does 2D and 3D spatial partitioning. Just looking at the code now.
---
### Author:  [@jcook](https://discourse.julialang.org/u/jcook)
#### Post date: [October 2, 2018, 7:17pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/12 "2018-10-02T19:17:19Z")
Thanks. That will come in useful!
---
### Author:  [@MA\_Laforge](https://discourse.julialang.org/u/MA_Laforge)
#### Post date: [July 25, 2019, 8:46pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/13 "2019-07-25T20:46:02Z")
### MDDatasets.jl
Hi, I’m not sure if I really understood the question correctly, but if I did, the answer is:
`MDDatasets.jl` can do this (Tools to manipulate Multi-Dimensional Datasets).
It was designed to post-process transient simulation data: signals that are functions of 1 argument (typically, that argument is time - at least for transient simulations).
### Here is a simple example
```julia-auto
using MDDatasets
using InspectDR #Just to observe results
t = DataF1(0:.1:10)
#OOPS: Forgot to implement x^2 (powers in general) in MDDatasets:
p2(x) = x * x #x^2
p3(x) = x * x * x #x^3
#"DataF1" is considered a function of 1 argument (not an array)
# -> so you do NOT do "dot" operations (ex: t .* t).
v1 = 2 * p2(t-5) + 8 #Quadratic
v2 = 0.1 * p3(t-7) + 18 #3rd order line
#Generate plot:
plot = InspectDR.transientplot(:lin, title="Crossings")
wfrm = add(plot, v1.x, v1.y)
wfrm = add(plot, v2.x, v2.y)
display(InspectDR.GtkDisplay(), plot)
#Display crossings:
println("\nFind all crossing points:")
xings = ycross(v1, v2)
println(xings)
println("\nOnly 2nd crossing:")
xing_2 = ycross1(v1, v2, n=2)
println(xing_2)
println("\nX value @ 2nd crossing:")
xing_2_x = xcross1(v1-v2, n=2)
println(xing_2_x)
```
### Here are the results you would get
```julia-auto
Find all crossing points:
DataF1(x=[3.37977, 7.23572],y=[13.2535, 18.0015])
Only 2nd crossing:
18.00147867720744
X value @ 2nd crossing:
7.235719853023049
```
---
### Author:  [@jcook](https://discourse.julialang.org/u/jcook)
#### Post date: [July 25, 2019, 8:49pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/14 "2019-07-25T20:49:19Z")
I’ve long since forgotten about this, and ended up submitting a fix to GeometryTypes. This would have been a good solution for me though. Nevertheless, thanks for letting me know.
---
### Author:  [@MA\_Laforge](https://discourse.julialang.org/u/MA_Laforge)
#### Post date: [July 25, 2019, 8:51pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/15 "2019-07-25T20:51:56Z")
Great. If you intend on using this in the future, here are a few things to note:
- There are more examples of using MDDatasets in a module called “SignalProcessing.jl”.
- You can find here: [https://github.com/ma-laforge/SignalProcessing.jl](https://github.com/ma-laforge/SignalProcessing.jl).
- Some sample plots: [https://github.com/ma-laforge/FileRepo/blob/master/SignalProcessing/sampleplots/README.md](https://github.com/ma-laforge/FileRepo/blob/master/SignalProcessing/sampleplots/README.md)
- MDDatasets.jl is not heavily used, so there are some features missing - and there are surely some bugs.
- MDDatasets.jl & SignalProcessing.jl are part of a larger suite called “CData.jl”:
- [https://github.com/ma-laforge/CData.jl](https://github.com/ma-laforge/CData.jl)
---
### Author:  [@levasco](https://discourse.julialang.org/u/levasco)
#### Post date: [March 8, 2022, 12:54pm UTC](https://discourse.julialang.org/t/finding-crossing-points-of-two-vectors-of-vertices/15786/16 "2022-03-08T12:54:32Z")
Sorry for reviving this old thread, but did you end up finding a good way to solve your problem? I have the same situation where I need to find the intersection of two vectors (of length n) of 2d coordinates (specifically two zero-isolines computed with Contour.jl). Thanks!
Edit: Not the most elegant, but if you don’t mind wrapping an R library, this works. A Julia solution would still be cool though!
```julia
using RCall
function intersectlines(ln1, ln2)
@rput ln1
@rput ln2
reval("library(sf)")
out = reval("as.double(st_intersection(st_linestring(ln1),st_linestring(ln2)))")
convert(Array{Float64}, out)
end
cr1 = [0. 0.5; 1 4; 9 9]
cr2 = [0 10.5; 2 5.5; 9 0]
intersectlines(cr1, cr2)
```