Line intersection ??

Maybe this will help

Line intersection

Good luck

Thank you my fellow dane ?

That''s quite slow algo, though. It needs 8 divs!

The following algo needs 0-6 muls and no divs at all.

(xa1=1st x-coordinate for line A,
yb2=2nd y-coordinate for line B..)

bool 2dintersect(int xa1,int ya1,int xa2,int ya2,int xb1,int yb1,int xb2,int yb2) { int jako,luku; //just some temp variables //trivial cases if (ya1 < ya2) { if (yb1 < ya1 && yb2 < ya1) return 0; if (yb1 > ya2 && yb2 > ya2) return 0; } else { if (yb1 > ya1 && yb2 > ya1) return 0; if (yb1 < ya2 && yb2 < ya2) return 0; } if (xa1 < xa2) { if (xb1 < xa1 && xb2 < xa1) return 0; if (xb1 > xa2 && xb2 > xa2) return 0; } else { if (xb1 > xa1 && xb2 > xa1) return 0; if (xb1 < xa2 && xb2 < xa2) return 0; } jako = (xa2 - xa1) * (yb2 - yb1) - (xb2 - xb1) * (ya2 - ya1); //parallel or point if (jako == 0) return 0; luku = (xb2 - xb1) * (ya1 - yb1) - (yb2 - yb1) * (xa1 - xb1); if (jako > 0) { if (luku >= 0 && luku <= jako) { luku = (xa2 - xa1) * (ya1 - yb1) - (ya2 - ya1) * (xa1 - xb1); if (luku >= 0 && luku <= jako) return 1; } } else { if (luku <= 0 && luku >= jako) { luku = (xa2 - xa1) * (ya1 - yb1) - (ya2 - ya1) * (xa1 - xb1); if (luku <= 0 && luku >= jako) return 1; } } return 0; }

I''m not 100% sure if it works. I wrote that one day but never tested it .



-Hans [home page] [e-mail]

My first instinct was to test if both points of one line lie on the same side of the other line, then swap the lines and repeat. This resulted in a method requiring 4 or 8 mul's, listed below. Hans, perhaps you can explain your method?

bool Intersect(int a, int b, int c, int d, int e, int f, int g, int h) { // Precalculations. int ac = a-c; int ae = a-e; int ag = a-g; int bd = b-d; int bf = b-f; int bh = b-h; int ce = c-e; int df = d-f; int eg = e-g; int fh = f-h; // The two lines of working. if((fh*ae > eg*bf) == (fh*ce > eg*df)) return false; if((ac*bf > bd*ae) == (ac*bh > bd*ag)) return false; // Enh. return true; }

You should probably add a bit to test if the boxes surrounding the lines intersect in the first place; Hans has already covered that.

EDIT: fixed an error in the code.

Edited by - Beer Hunter on December 6, 2000 6:42:03 PM

Is it a mathematical line or a line with two ends? If it is a proper line (one that is infinite), just solve their simultaneous equation using the elimination method and you get a nice little formula.

Trying is the first step towards failure.

I was thinking of a line with two ends...


Beer hunter:
>My first instinct was to test if both points of one line lie on >the same side of the other line, then swap the lines and >repeat.

Yeah that was my solution too at first. I just thought that there might be a better method.

I got my algo from comp.graphics.algorithms faq, I just optimized it a bit and added the trivial cases. It''s really basic vector math.

The following is copied from the faq:

Subject 1.03: How do I find intersections of 2 2D line segments?

    This problem can be extremely easy or extremely difficult depends
    on your applications.  If all you want is the intersection point,
    the following should work:

    Let A,B,C,D be 2-space position vectors.  Then the directed line
    segments AB & CD are given by:

        AB=A+r(B-A), r in [0,1]
        CD=C+s(D-C), s in [0,1]

    If AB & CD intersect, then

        A+r(B-A)=C+s(D-C), or

        Ax+r(Bx-Ax)=Cx+s(Dx-Cx)
        Ay+r(By-Ay)=Cy+s(Dy-Cy)  for some r,s in [0,1]

    Solving the above for r and s yields

            (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
        r = -----------------------------  (eqn 1)
            (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

            (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
        s = -----------------------------  (eqn 2)
            (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)

    Let P be the position vector of the intersection point, then

        P=A+r(B-A) or

        Px=Ax+r(Bx-Ax)
        Py=Ay+r(By-Ay)

    By examining the values of r & s, you can also determine some
    other limiting conditions:

        If 0<=r<=1 & 0<=s<=1, intersection exists
            r<0 or r>1 or s<0 or s>1 line segments do not intersect

        If the denominator in eqn 1 is zero, AB & CD are parallel
        If the numerator in eqn 1 is also zero, AB & CD are collinear.

    If they are collinear, then the segments may be projected to the x- 
    or y-axis, and overlap of the projected intervals checked.

    If the intersection point of the 2 lines are needed (lines in this
    context mean infinite lines) regardless whether the two line
    segments intersect, then

        If r>1, P is located on extension of AB
        If r<0, P is located on extension of BA
        If s>1, P is located on extension of CD
        If s<0, P is located on extension of DC

    Also note that the denominators of eqn 1 & 2 are identical.

 

-Hans [home page] [e-mail]

bool Intersects(int m1, int b1, int m2, int b2) { if (m1==m2) { if (b1==b2) return(true); else return(false); } else return(true); }

That is of course infinite lines. To test if two line segments are equal you calculate x where they intersect with (b1-b2)/(m2-m1) then check if x is between the start and end x of both segments. As near as I can tell that is one division.

Oh yeah, if the slopes are the same, i.e. m2-m1 = 0, you check whether the start or end x of one line is between the start and end x of the other.

An approach that works for 2D and 3D line segments is presented in the first Graphics Gems book. It gives the point that is the closest point between two lines, so you have to do extra checks to see if it is a true intersection. The book doesn't have an implementation and as presented doesn't deal with parallel lines (which have a locus of nearest points-----a new line halfway between the two parallel lines-----instead of just one nearest point). It is also presented for infinite lines not finite length segments. It is straightforward to expand to deal with these cases in an implementation. The post by Hans quoting from the comp.graphics.algorithms FAQ gives an example (for 2D) of how to deal with the special cases.

Here's a link to sources of object/object intersection algorithms, including this one:

http://www.realtimerendering.com/int/

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Edited by - grhodes_at_work on December 7, 2000 10:27:12 AM

LilBudyWeiser: From the eight co-ordinates, it will require several calculations to find the gradients and y-intercepts of the lines. Besides, gradients are not integers. This will require extra work and isn''t all that efficient in the long run.

I don''t know.

bool Intersects(Line l1, Line l2) { Vector d1 = l1.end - l1.start; Vector d2 = l2.end - l2.start; int t = ((l2.start.x - l1.start.x) * (d1.x*d2.x))/(d1.y*d2.x - d2.x*d1.x); if (t > d1.x || t > d2.x) return(false); else return(true); }

It seems to me that it should work and only uses three multiplications, one division and no floating point, but I could be wrong.

I tried the code as it is, but got a division by zero error. Perhaps you can test it and fix it up...

I should have just stayed out of the discussion. I can''t imagine how you could make practical use of so many lines in 2D at one time that optimization an intersect test would make any real performance impact. Practically speaking you would most likely save a great deal more not checking the same lines over and over for intersection. Since I don''t see it as worth a great deal of effort I didn''t put much effort into it, but that is also a good reason to not both getting in it.

Yes, if the slopes are equal you will get a divide by zero error. You should check if the divisor is zero before doing any division and that includes this case. I believe it should also be l2.start.y - l1.start.y not x. The idea was to use a parametric equation for a line since you complained about having to calculate the intercept, i.e. y = t*m + start.y and x = t + start.x. For the line segment t ranges from 0 to end.x - start.x. It isn''t much differant than y = x*m + b, except you don''t need the intercept. Since you complained about having to calculate the slope the idea was to use dy/dx. m1 - m2 = (dy1*dx2 - dy2*dx1)/(dx1*dx2). Since that is the divisor in the equation you can multiply by (dx1*dx2)/(dy1*dx2 - dy2*dx2) instead thus replacing a division with a multiplication. If end.x - start.x is negative then if the segements intersect then I believe t will be negative as well. As long as we are optimizing though we should always make sure start.x is less than end.x when we create the line so we don''t have to check that condition over and over. Finally to be precisely right you need a floating point, but to the nearest pixel should be good enough. It truncates instead of rounds so you need a shift left 1 before the divide and a shift right 1 after to round it.

That all said intuitively it seems to still be wrong. The range for t cannot be the same for the two segments unless they have the same dx. So t would have to be for one of the lines, but which line is it. Since it isn''t clear to me which one it is it seems the whole thing must be wrong. And with that note I''m out of this conversation. Should I ever need to draw a thousand lines on the screen at once and test if which other lines each intersects with then perhaps I will regret having not pursued this further.