edge_intersects()

uint32_t edge_intersects	(	const POINT3D *	A1,
		const POINT3D *	A2,
		const POINT3D *	B1,
		const POINT3D *	B2
	)

Returns non-zero if edges A and B interact.

The type of interaction is given in the return value with the bitmask elements defined above.

Definition at line 3515 of file lwgeodetic.c.

{
        POINT3D AN, BN, VN;  /* Normals to plane A and plane B */
        double ab_dot;
        int a1_side, a2_side, b1_side, b2_side;
        int rv = PIR_NO_INTERACT;
 
        /* Normals to the A-plane and B-plane */
        unit_normal(A1, A2, &AN);
        unit_normal(B1, B2, &BN);
 
        /* Are A-plane and B-plane basically the same? */
        ab_dot = dot_product(&AN, &BN);
 
        /*
        * https://trac.osgeo.org/postgis/ticket/5765
        * Failure because the colinearity check was
        * triggering due to an overly loose equality
        * check here.
        * if ( FP_EQUALS(fabs(ab_dot), 1.0) )
        */
        if ( 1.0 - fabs(ab_dot) <= 10e-16 )
        {
                /* Co-linear case */
                if ( point_in_cone(A1, A2, B1) || point_in_cone(A1, A2, B2) ||
                     point_in_cone(B1, B2, A1) || point_in_cone(B1, B2, A2) )
                {
                        rv |= PIR_INTERSECTS;
                        rv |= PIR_COLINEAR;
                }
                return rv;
        }
 
        /* What side of plane-A and plane-B do the end points */
        /* of A and B fall? */
        a1_side = dot_product_side(&BN, A1);
        a2_side = dot_product_side(&BN, A2);
        b1_side = dot_product_side(&AN, B1);
        b2_side = dot_product_side(&AN, B2);
 
        /* Both ends of A on the same side of plane B. */
        if ( a1_side == a2_side && a1_side != 0 )
        {
                /* No intersection. */
                return PIR_NO_INTERACT;
        }
 
        /* Both ends of B on the same side of plane A. */
        if ( b1_side == b2_side && b1_side != 0 )
        {
                /* No intersection. */
                return PIR_NO_INTERACT;
        }
 
        /* A straddles B and B straddles A, so... */
        if ( a1_side != a2_side && (a1_side + a2_side) == 0 &&
             b1_side != b2_side && (b1_side + b2_side) == 0 )
        {
                /* Have to check if intersection point is inside both arcs */
                unit_normal(&AN, &BN, &VN);
                if ( point_in_cone(A1, A2, &VN) && point_in_cone(B1, B2, &VN) )
                {
                        return PIR_INTERSECTS;
                }
 
                /* Have to check if intersection point is inside both arcs */
                vector_scale(&VN, -1);
                if ( point_in_cone(A1, A2, &VN) && point_in_cone(B1, B2, &VN) )
                {
                        return PIR_INTERSECTS;
                }
 
                return PIR_NO_INTERACT;
        }
 
        /* The rest are all intersects variants... */
        rv |= PIR_INTERSECTS;
 
        /* A touches B */
        if ( a1_side == 0 )
        {
                /* Touches at A1, A2 is on what side? */
                rv |= (a2_side < 0 ? PIR_A_TOUCH_RIGHT : PIR_A_TOUCH_LEFT);
        }
        else if ( a2_side == 0 )
        {
                /* Touches at A2, A1 is on what side? */
                rv |= (a1_side < 0 ? PIR_A_TOUCH_RIGHT : PIR_A_TOUCH_LEFT);
        }
 
        /* B touches A */
        if ( b1_side == 0 )
        {
                /* Touches at B1, B2 is on what side? */
                rv |= (b2_side < 0 ? PIR_B_TOUCH_RIGHT : PIR_B_TOUCH_LEFT);
        }
        else if ( b2_side == 0 )
        {
                /* Touches at B2, B1 is on what side? */
                rv |= (b1_side < 0 ? PIR_B_TOUCH_RIGHT : PIR_B_TOUCH_LEFT);
        }
 
        return rv;
}

References dot_product(), dot_product_side(), PIR_A_TOUCH_LEFT, PIR_A_TOUCH_RIGHT, PIR_B_TOUCH_LEFT, PIR_B_TOUCH_RIGHT, PIR_COLINEAR, PIR_INTERSECTS, PIR_NO_INTERACT, point_in_cone(), unit_normal(), and vector_scale().

Referenced by circ_tree_contains_point(), circ_tree_distance_tree_internal(), lwpoly_intersects_line(), ptarray_contains_point_sphere(), ptarray_distance_spheroid(), and test_edge_intersects().

Here is the call graph for this function:

Here is the caller graph for this function: