lw_dist3d_seg_seg()

int lw_dist3d_seg_seg	(	POINT3DZ *	s1p1,
		POINT3DZ *	s1p2,
		POINT3DZ *	s2p1,
		POINT3DZ *	s2p2,
		DISTPTS3D *	dl
	)

Finds the two closest points on two linesegments.

Definition at line 1139 of file measures3d.c.

{
        VECTOR3D v1, v2, vl;
        double s1k, s2k; /*two variables representing where on Line 1 (s1k) and where on Line 2 (s2k) a connecting line
                            between the two lines is perpendicular to both lines*/
        POINT3DZ p1, p2;
        double a, b, c, d, e, D;
 
        /*s1p1 and s1p2 are the same point */
        if ((s1p1->x == s1p2->x) && (s1p1->y == s1p2->y) && (s1p1->z == s1p2->z))
        {
                return lw_dist3d_pt_seg(s1p1, s2p1, s2p2, dl);
        }
        /*s2p1 and s2p2 are the same point */
        if ((s2p1->x == s2p2->x) && (s2p1->y == s2p2->y) && (s2p1->z == s2p2->z))
        {
                dl->twisted = ((dl->twisted) * (-1));
                return lw_dist3d_pt_seg(s2p1, s1p1, s1p2, dl);
        }
        /*s2p1 and s1p1 are the same point */
        if ((s2p1->x == s1p1->x) && (s2p1->y == s1p1->y) && (s2p1->z == s1p1->z))
        {
                dl->distance = 0.0;
                dl->p1 = dl->p2 = *s2p1;
                return LW_TRUE;
        }
 
        /*
                Here we use algorithm from softsurfer.com
                that can be found here
                http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm
        */
 
        if (!get_3dvector_from_points(s1p1, s1p2, &v1))
                return LW_FALSE;
 
        if (!get_3dvector_from_points(s2p1, s2p2, &v2))
                return LW_FALSE;
 
        if (!get_3dvector_from_points(s2p1, s1p1, &vl))
                return LW_FALSE;
 
        a = DOT(v1, v1);
        b = DOT(v1, v2);
        c = DOT(v2, v2);
        d = DOT(v1, vl);
        e = DOT(v2, vl);
        D = a * c - b * b;
 
        if (D < 0.000000001)
        { /* the lines are almost parallel*/
                s1k =
                    0.0;   /*If the lines are parallel we try by using the startpoint of first segment. If that gives a
                              projected point on the second line outside segment 2 it wil be found that s2k is >1 or <0.*/
                if (b > c) /* use the largest denominator*/
                        s2k = d / b;
                else
                        s2k = e / c;
        }
        else
        {
                s1k = (b * e - c * d) / D;
                s2k = (a * e - b * d) / D;
        }
 
        /* Now we check if the projected closest point on the infinite lines is outside our segments. If so the
         * combinations with start and end points will be tested*/
 
        if (s1k <= 0.0 || s1k >= 1.0 || s2k <= 0.0 || s2k >= 1.0)
        {
                if (s1k <= 0.0)
                {
                        if (!lw_dist3d_pt_seg(s1p1, s2p1, s2p2, dl))
                                return LW_FALSE;
                }
                if (s1k >= 1.0)
                {
                        if (!lw_dist3d_pt_seg(s1p2, s2p1, s2p2, dl))
                                return LW_FALSE;
                }
                if (s2k <= 0.0)
                {
                        dl->twisted = ((dl->twisted) * (-1));
                        if (!lw_dist3d_pt_seg(s2p1, s1p1, s1p2, dl))
                                return LW_FALSE;
                }
                if (s2k >= 1.0)
                {
                        dl->twisted = ((dl->twisted) * (-1));
                        if (!lw_dist3d_pt_seg(s2p2, s1p1, s1p2, dl))
                                return LW_FALSE;
                }
        }
        else
        { /*Find the closest point on the edges of both segments*/
                p1.x = s1p1->x + s1k * (s1p2->x - s1p1->x);
                p1.y = s1p1->y + s1k * (s1p2->y - s1p1->y);
                p1.z = s1p1->z + s1k * (s1p2->z - s1p1->z);
 
                p2.x = s2p1->x + s2k * (s2p2->x - s2p1->x);
                p2.y = s2p1->y + s2k * (s2p2->y - s2p1->y);
                p2.z = s2p1->z + s2k * (s2p2->z - s2p1->z);
 
                if (!lw_dist3d_pt_pt(&p1, &p2, dl)) /* Send the closest points to point-point calculation*/
                {
                        return LW_FALSE;
                }
        }
        return LW_TRUE;
}

References DISTPTS3D::distance, DOT, get_3dvector_from_points(), lw_dist3d_pt_pt(), lw_dist3d_pt_seg(), LW_FALSE, LW_TRUE, DISTPTS3D::p1, DISTPTS3D::p2, DISTPTS3D::twisted, POINT3DZ::x, POINT3DZ::y, and POINT3DZ::z.

Referenced by lw_dist3d_ptarray_ptarray().

Here is the call graph for this function:

Here is the caller graph for this function: