Detecting Line Intersection

Home Forums Problems and solutions in GDL Object design Detecting Line Intersection

This topic contains 5 replies, has 2 voices, and was last updated by  Péter Baksa 6 months ago.

  • Author
  • #4588

    James Goode


    I’ve recently received this bit of code regarding line intersection but I’m not quite sure how to implement it into my object.

    (px1, py1, px2, py2 are coordinates of points on each segments, vx1, vy1, vx2, vy2 are the direction vectors for the segments)

                  Scalar = ( (vx1*vx2) + (vy1*vy2) )
                  if abs(abs(Scalar) - 1) < EPS then
                                ! no intersection, parallel lines
                                ipx = 0
                                ipy = 0
                                state = 0
                                ! Calculate A1, B1 and C1 parameter
                                ! A1, B1 are equal to normal vector
                                A1 = -vy1
                                B1 = vx1
                                C1 = -(A1*px1) - (B1*py1)
                                ! Calculate A2, B2 and C2 parameter
                                ! A2, B2 are equal to normal vector
                                A2 = -vy2
                                B2 = vx2
                                C2 = -(A2*px2) - (B2*py2)
                                ! Calculate coordinates of intersection point
                                ipy = ((A1*C2) - (C1*A2)) / ((B1*A2) - (A1*B2))
                                if abs(A1) < EPS then
                                              ipx = (-B2*ipy - C2) / A2
                                              ipx = (-B1*ipy - C1) / A1
                                state = 1
    Specific to my object my line points would be something along the lines of 

    line2 x[1], y[1], x[2], y[2]
    line2 x[2], y[2], x[3], y[3]`

    How can I implement my parameters into the example code I’ve been given

  • #4593

    Péter Baksa

    Hi James,

    The direction vectors are unit vectors along the lines, their length have to be exactly 1 (meter). Compute the length of the vector between the two points on the line, and to set the vector length to 1, multiply its end coordinates by 1/length.

    If you use an EPS value that is common in GS libparts, this code has a small bug, the lines are treated parallel (no intersections) when their angle is smaller than 0.81°, which is still quite noticable. Using EPS = 0.00000001 will set the limit to 0.0081°

    Péter Baksa
    Software Engineer, Library Team

  • #4600

    James Goode

    Do you have any sort of examples for this by any chance?


  • #4603

    Péter Baksa

    Yes, have a look at “basicStairTread_m” 3D script.

    Péter Baksa
    Software Engineer, Library Team

  • #4611

    James Goode

    So I’ve taken a look at the basicStairTread_m 3d script but I don’t really understand what I’m supposed to be looking at. I wish there was an object which was an example purely for line intersection like there are for a few other objects in the help centre. Without being able to detect and stop line intersections in my object, it becomes unusable.

  • #4618

    Péter Baksa


    There is a call (gosub) to “LineLineIntersection” in the 3D script. The input variables are set up before the call.

    vx, vy is computed from two points (_intersectEdge[1] and _intersectEdge[2]) on the line, divided by the distance of the two points:

    	! line 1
    	vx1 = (_intersectEdge[2][1] - _intersectEdge[1][1]) / _intersectEdgeLength
    	vy1 = (_intersectEdge[2][2] - _intersectEdge[1][2]) / _intersectEdgeLength

    px, py is any point on the line:

    	px1 = _intersectEdge[1][1]
    	py1 = _intersectEdge[1][2]

    This is done again for the second line:

    	! line 2
    	vx2 = (_intersectEdgeLeft[2][1] - _intersectEdgeLeft[1][1]) / _intersectEdgeLeftLength
    	vy2 = (_intersectEdgeLeft[2][2] - _intersectEdgeLeft[1][2]) / _intersectEdgeLeftLength
    	px2 = _intersectEdgeLeft[1][1]
    	py2 = _intersectEdgeLeft[1][2]

    The result intersection is ipx, ipy, when state = 1 (otherwise the lines are parallel):

    	gosub "LineLineIntersection"	! returns ipx, ipy, state
    	if state <> 0 then
    		_intersectPtLeft[1] = ipx
    		_intersectPtLeft[2] = ipy

    Péter Baksa
    Software Engineer, Library Team

You must be logged in to reply to this topic.