Keith Hair

[...] uses the “lineIntersectLine” function of the earlier [...]

Thanks Keith, for the solution. Saved my time.

thanks kaith for this solution i was thinking on this thing from last few days u help me so much

Thanks Keith, that is a nice one. Any thoughts on intersection of *rotated* lines? The example here considers that the planes of both the lines are same. What will happen if any one or both the lines are rotated? How to get the intersection in that case? Any help will be much appreciated. ~ Shiyaz

Shiyaz,

This link might be helpful on the subject of planes and intersections. It has C++ implementations and pseudo code to help make it easier to create an AS3 implementation or into some other language, hope it helps.

http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm

Thanks Keith. The links were helpful. I required the intersections of rotating planes to find the reflection of a point across a moving mirror line. However, the links threw more light on the concept. I did solve my problem by using *midpoint formula* approach. Would share the pseudo code after some cleanup. ~ Shiyaz

[...] sources sinon: la fonction d’intersection de segments vient de chez Keith Hair: http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/ on doit pouvoir accélérer le test sur les segment notes [...]

[...] the way: the segment intersection function comes from Keith Hair’s blog (pretty nice job ): http://keith-hair.net/blog/2008/08/04/find-intersection-point-of-two-lines-in-as3/ I think something can be done to accelerate the ‘as_seg’ section [...]

Thanks a million.

This was really useful, thanks a million

[...] intersections that have saved me more than a few hours of headbanging. In particular, his line intersection function is a marvelous paste-and-go solution, and I really feel like posting a small optimisation that [...]

Thank you!

Thank you! It was quite useful

Hi there,
thanks for the great piece of code! Just wanted to suggest that you don’t use Point.distance for the “as_sec” part – because I think calculating the distance always uses the square-root – which is calculated slowly.

If you only want to check whether something is nearer than another, it’s enough to compare (a^2 + b^2) for both distances.

Hope I made clear what I mean
(if you want to reply, please also drop a short mail)

Cheers,
Dennis

Thanks Dennis and everyone else who have been pointing out the as_seg part of the function.
Since it’s only comparing if the value is greater, the actual distance by using square root is not important.

if(as_seg){
if(Math.pow((ip.x – B.x) + (ip.y – B.y), 2) > Math.pow((A.x – B.x) + (A.y – B.y), 2)){
return null;
}
if(Math.pow((ip.x – A.x) + (ip.y – A.y), 2) > Math.pow((A.x – B.x) + (A.y – B.y), 2)){
return null;
}

if(Math.pow((ip.x – F.x) + (ip.y – F.y), 2) > Math.pow((E.x – F.x) + (E.y – F.y), 2)){
return null;
}
if(Math.pow((ip.x – E.x) + (ip.y – E.y), 2) > Math.pow((E.x – F.x) + (E.y – F.y), 2)){
return null;
}
}

Thanks to Chris B-B for making it clear to me about a bug in the as_seg part, and preventing future headaches this might have caused me.

[...] again I’ve built on a handy function written by Keith Hair that finds the point of intersection between two lines. Using his lineIntersectLine() function and my getPerpDistanceFromLine() function you can calculate [...]

Thank you very much for the fine code!

I will use it under OpenCV.

i had another approach at this (by rotating vectors), but your code is like twenty times faster. thank you so much for sharing!

thank u!!! very useful………

Hi Keith,

thanks a lot for this piece of code. Works perfectly

I’m using it to determine intersections during graphs display. I have to check lots of segments, thus I optimized the “as_seg” part a little. I removed Math.pow, which is quite slow, and didn’t repeat any multiplication/subtraction. I thought I might post it (approx 1.78 times faster):

if ( as_seg ) {
var n0:Number, n1:Number, n2:Number, n3:Number, n4:Number, n5:Number, n6:Number, n7:Number, v0:Number, v1:Number, vr0:Number, vr1:Number;
n0 = ip.x – p_a1.x;
n1 = ip.y – p_a1.y;
v0 = p_a0.y – p_a1.y;
vr0 = b1 * b1 + v0 * v0;
if ( n0 * n0 + n1 * n1 > vr0 ) return null;
n2 = ip.x – p_a0.x;
n3 = ip.y – p_a0.y;
if ( n2 * n2 + n3 * n3 > vr0 ) return null;
n4 = ip.x – p_b1.x;
n5 = ip.y – p_b1.y;
v1 = p_b0.y – p_b1.y;
vr1 = b2 * b2 + v1 * v1;
if ( n4 * n4 + n5 * n5 > vr1 ) return null;
n6 = ip.x – p_b0.x;
n7 = ip.y – p_b0.y;
if ( n6 * n6 + n7 * n7 > vr1 ) return null;
}

Kind regards and thanks again

Excellent – Thanks!

Great work!

Any idea how it works with coinciding lines that are intersecting?
I know that there might be multiple points that will intersect, but let’s assume that we only return the upper left point.

I’ve been looking for this kind of function for an hour, thank you so much! Great code that can easily be copied and pasted and with a nice demo.

Thanks a ton!!!
You saved me a looot of work!!!

The as_seg check can be optimized still further if you consider you’re just checking to see that the intersection falls between A.x and B.x, between A.y and B.y, between E.x and F.x, and between E.y and F.y:

if ( as_seg ) {
    if (  ( ip.x – A.x ) * ( ip.x – B.x ) > 0
      ||  ( ip.y – A.y ) * ( ip.y – B.y ) > 0
      ||  ( ip.x – E.x ) * ( ip.x – F.x ) > 0
      ||  ( ip.y – E.y ) * ( ip.y – F.y ) > 0
    ) return null ;
}

Great topic !

El verde’s solution is fine but…
I ran into a little problem when i tried to implement it :
A, B… are POINT and their x/y properties are NUMBER, and somehow NUMBER is not precise enough.
So comparing the intersection x/y with A.x…F.y could trigger a “false” positive (eg : 1.23e-31 > 0).
Keith’s solution (using “math.pow”) seems to cop with this precision issue… But it’s slower.

Using INT (or rounding numbers) could be another solution

Do you have a donation button somewhere that I’m missing?

There are no plans to add a donation button to this blog. Hope you’ve found interesting or useful content here. Comments on optimizing script are welcome.