lw_dist2d_seg_seg()

int lw_dist2d_seg_seg	(	const POINT2D *	A,
		const POINT2D *	B,
		const POINT2D *	C,
		const POINT2D *	D,
		DISTPTS *	dl
	)

Finds the shortest distance between two segments.

This function is changed so it is not doing any comparison of distance but just sending every possible combination further to lw_dist2d_pt_seg

Definition at line 1840 of file measures.c.

{
        double s_top, s_bot, s;
        double r_top, r_bot, r;
 
        /*A and B are the same point */
        if ((A->x == B->x) && (A->y == B->y))
        {
                return lw_dist2d_pt_seg(A, C, D, dl);
        }
 
        /*U and V are the same point */
        if ((C->x == D->x) && (C->y == D->y))
        {
                dl->twisted = ((dl->twisted) * (-1));
                return lw_dist2d_pt_seg(D, A, B, dl);
        }
 
        /* AB and CD are line segments */
        /* from comp.graphics.algo
 
        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.
 
        */
        r_top = (A->y - C->y) * (D->x - C->x) - (A->x - C->x) * (D->y - C->y);
        r_bot = (B->x - A->x) * (D->y - C->y) - (B->y - A->y) * (D->x - C->x);
 
        s_top = (A->y - C->y) * (B->x - A->x) - (A->x - C->x) * (B->y - A->y);
        s_bot = (B->x - A->x) * (D->y - C->y) - (B->y - A->y) * (D->x - C->x);
 
        if ((r_bot == 0) || (s_bot == 0))
        {
                if ((lw_dist2d_pt_seg(A, C, D, dl)) && (lw_dist2d_pt_seg(B, C, D, dl)))
                {
                        /* change the order of inputted geometries and that we notice by changing sign on dl->twisted*/
                        dl->twisted *= -1;
                        return ((lw_dist2d_pt_seg(C, A, B, dl)) && (lw_dist2d_pt_seg(D, A, B, dl)));
                }
                else
                        return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
        }
 
        s = s_top / s_bot;
        r = r_top / r_bot;
 
        if (((r < 0) || (r > 1) || (s < 0) || (s > 1)) || (dl->mode == DIST_MAX))
        {
                if ((lw_dist2d_pt_seg(A, C, D, dl)) && (lw_dist2d_pt_seg(B, C, D, dl)))
                {
                        /* change the order of inputted geometries and that we notice by changing sign on dl->twisted*/
                        dl->twisted *= -1;
                        return ((lw_dist2d_pt_seg(C, A, B, dl)) && (lw_dist2d_pt_seg(D, A, B, dl)));
                }
                else
                        return LW_FALSE; /* if any of the calls to lw_dist2d_pt_seg goes wrong we return false*/
        }
        else
        {
                /* If there is intersection we identify the intersection point and return it but only if we are looking
                 * for mindistance */
                if (dl->mode == DIST_MIN)
                {
                        POINT2D theP;
 
                        if (((A->x == C->x) && (A->y == C->y)) || ((A->x == D->x) && (A->y == D->y)))
                        {
                                theP.x = A->x;
                                theP.y = A->y;
                        }
                        else if (((B->x == C->x) && (B->y == C->y)) || ((B->x == D->x) && (B->y == D->y)))
                        {
                                theP.x = B->x;
                                theP.y = B->y;
                        }
                        else
                        {
                                theP.x = A->x + r * (B->x - A->x);
                                theP.y = A->y + r * (B->y - A->y);
                        }
                        lw_dist2d_distpts_set(dl, 0, &theP, &theP);
                }
                return LW_TRUE;
        }
}

References DIST_MAX, DIST_MIN, lw_dist2d_distpts_set(), lw_dist2d_pt_seg(), LW_FALSE, LW_TRUE, DISTPTS::mode, r, s, DISTPTS::twisted, POINT2D::x, and POINT2D::y.

Referenced by lw_dist2d_arc_arc(), lw_dist2d_ptarray_ptarray(), lw_dist2d_seg_arc(), and rect_leaf_node_distance().

Here is the call graph for this function:

Here is the caller graph for this function: