edge_point_in_cone()

int edge_point_in_cone	(	const GEOGRAPHIC_EDGE *	e,
		const GEOGRAPHIC_POINT *	p
	)

Returns true if the point p is inside the cone defined by the two ends of the edge e.

Definition at line 784 of file lwgeodetic.c.

References dot_product(), GEOGRAPHIC_EDGE::end, geog2cart(), LW_FALSE, LW_TRUE, LWDEBUG, LWDEBUGF, normalize(), GEOGRAPHIC_EDGE::start, vector_sum(), POINT3D::x, POINT3D::y, and POINT3D::z.

Referenced by edge_contains_point().

{
        POINT3D vcp, vs, ve, vp;
        double vs_dot_vcp, vp_dot_vcp;
        geog2cart(&(e->start), &vs);
        geog2cart(&(e->end), &ve);
        /* Antipodal case, everything is inside. */
        if ( vs.x == -1.0 * ve.x && vs.y == -1.0 * ve.y && vs.z == -1.0 * ve.z )
                return LW_TRUE;
        geog2cart(p, &vp);
        /* The normalized sum bisects the angle between start and end. */
        vector_sum(&vs, &ve, &vcp);
        normalize(&vcp);
        /* The projection of start onto the center defines the minimum similarity */
        vs_dot_vcp = dot_product(&vs, &vcp);
        LWDEBUGF(4,"vs_dot_vcp %.19g",vs_dot_vcp);
        /* The projection of candidate p onto the center */
        vp_dot_vcp = dot_product(&vp, &vcp);
        LWDEBUGF(4,"vp_dot_vcp %.19g",vp_dot_vcp);
        /* If p is more similar than start then p is inside the cone */
        LWDEBUGF(4,"fabs(vp_dot_vcp - vs_dot_vcp) %.39g",fabs(vp_dot_vcp - vs_dot_vcp));

        /*
        ** We want to test that vp_dot_vcp is >= vs_dot_vcp but there are
        ** numerical stability issues for values that are very very nearly
        ** equal. Unfortunately there are also values of vp_dot_vcp that are legitimately
        ** very close to but still less than vs_dot_vcp which we also need to catch.
        ** The tolerance of 10-17 seems to do the trick on 32-bit and 64-bit architectures,
        ** for the test cases here.
        ** However, tuning the tolerance value feels like a dangerous hack.
        ** Fundamentally, the problem is that this test is so sensitive.
        */

        /* 1.1102230246251565404236316680908203125e-16 */

        if ( vp_dot_vcp > vs_dot_vcp || fabs(vp_dot_vcp - vs_dot_vcp) < 2e-16 )
        {
                LWDEBUG(4, "point is in cone");
                return LW_TRUE;
        }
        LWDEBUG(4, "point is not in cone");
        return LW_FALSE;
}

Here is the call graph for this function:

Here is the caller graph for this function: