Finding crossing points of two vectors of vertices

Specific Domains Signal and Image Processing
1

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.

1 Like
2

High school math. You can solve it by finding where two lines cross where lines are parametrised like y=a+bx.

1 Like
3

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.

4

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<n points. Then apply the m^2 algorithm. I think the sorting to find intervals is how nlogn comes into it.

5 
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))
1 Like
6

Many thanks!

7

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.

8

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.

9

It appears that the linear crossings algorithm in GeometryTypes doesn’t cope well with exactly vertical lines. There’s an issue about it already.

10

For reducing to n*log(n) you could use something like this:
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.

11

Actually looks like CollisionDetection.jl does 2D and 3D spatial partitioning. Just looking at the code now.

12

Thanks. That will come in useful!

13

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

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

image
image639×501 23 KB

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
14

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.

15

Great. If you intend on using this in the future, here are a few things to note:

16

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!

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)
1 Like