Intersection of 2 polylines

Hi all,
I wonder if there is a more efficient way (than the following) to detect if 2 polylines intersect.

the basic way would be to test for each line segment of pline1 , all the line segments of pline2 sequentially. but this seems slow.

thank you

depends on how much points you have in the polyline, but generally if both have less then 100 or so points it should go pretty fast. complexity is 0(n²) so if n small it should be ok.

you can also check the inside() method for polylines.
First, use getResampledBySpacing(1) on one polyline, iterate over all points and test if they are inside the other polygon. When it goes from true to false or vica versa you have an intersection point approximation. You might get an improvement over the above solution depending on the implementation of the inside function.

hi there,
thank you for the info.
my polylines are unfortunately not closed so this will not work.
Additionally the polylines have more than 100 points , which is why I was looking for a mathematically efficient way to do this.

Collision detection is a large topic - maybe you could be more specific as to what your situation is. Do your polylines exist in 2D or 3D? How many polylines are there on the screen at one time? How close are the polylines on average?

This article from Gamasutra might help give you some ideas for tackling your situation. There might already be some addons with implementations of these collision detection algorithms.

hi @mikewesthad
I have an svg drawing with a few polylines 9 - 10 scattered on my screen, the “paths” . these are mostly horizontal and vertical straight lines. Some of them have a few (2-5) 90degree corners. they are generally , just 2D polylines. and overall they are very few vertices involved.

I also have outlines from object tracking (also a 2D polyline). The outlines have an upper limit of 150 vertices each.

I want my outline to interact with the paths (basically modify the paths but inserting some outline vertices in the path).

I am not sure if by “how close” you mean if their boundBoxes interact often or not. If this is the case , then yes I expect my outline to affect a minimum of 1 path and possibly 2 or even 3 at any given time.