PostGIS  2.5.0dev-r@@SVN_REVISION@@
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 753 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().

754 {
755  POINT3D vcp, vs, ve, vp;
756  double vs_dot_vcp, vp_dot_vcp;
757  geog2cart(&(e->start), &vs);
758  geog2cart(&(e->end), &ve);
759  /* Antipodal case, everything is inside. */
760  if ( vs.x == -1.0 * ve.x && vs.y == -1.0 * ve.y && vs.z == -1.0 * ve.z )
761  return LW_TRUE;
762  geog2cart(p, &vp);
763  /* The normalized sum bisects the angle between start and end. */
764  vector_sum(&vs, &ve, &vcp);
765  normalize(&vcp);
766  /* The projection of start onto the center defines the minimum similarity */
767  vs_dot_vcp = dot_product(&vs, &vcp);
768  LWDEBUGF(4,"vs_dot_vcp %.19g",vs_dot_vcp);
769  /* The projection of candidate p onto the center */
770  vp_dot_vcp = dot_product(&vp, &vcp);
771  LWDEBUGF(4,"vp_dot_vcp %.19g",vp_dot_vcp);
772  /* If p is more similar than start then p is inside the cone */
773  LWDEBUGF(4,"fabs(vp_dot_vcp - vs_dot_vcp) %.39g",fabs(vp_dot_vcp - vs_dot_vcp));
774 
775  /*
776  ** We want to test that vp_dot_vcp is >= vs_dot_vcp but there are
777  ** numerical stability issues for values that are very very nearly
778  ** equal. Unfortunately there are also values of vp_dot_vcp that are legitimately
779  ** very close to but still less than vs_dot_vcp which we also need to catch.
780  ** The tolerance of 10-17 seems to do the trick on 32-bit and 64-bit architectures,
781  ** for the test cases here.
782  ** However, tuning the tolerance value feels like a dangerous hack.
783  ** Fundamentally, the problem is that this test is so sensitive.
784  */
785 
786  /* 1.1102230246251565404236316680908203125e-16 */
787 
788  if ( vp_dot_vcp > vs_dot_vcp || fabs(vp_dot_vcp - vs_dot_vcp) < 2e-16 )
789  {
790  LWDEBUG(4, "point is in cone");
791  return LW_TRUE;
792  }
793  LWDEBUG(4, "point is not in cone");
794  return LW_FALSE;
795 }
void normalize(POINT3D *p)
Normalize to a unit vector.
Definition: lwgeodetic.c:580
double y
Definition: liblwgeom.h:339
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
double x
Definition: liblwgeom.h:339
double z
Definition: liblwgeom.h:339
static double dot_product(const POINT3D *p1, const POINT3D *p2)
Convert cartesion coordinates on unit sphere to lon/lat coordinates static void cart2ll(const POINT3D...
Definition: lwgeodetic.c:411
#define LW_FALSE
Definition: liblwgeom.h:76
GEOGRAPHIC_POINT start
Definition: lwgeodetic.h:58
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
GEOGRAPHIC_POINT end
Definition: lwgeodetic.h:59
void geog2cart(const GEOGRAPHIC_POINT *g, POINT3D *p)
Convert spherical coordinates to cartesion coordinates on unit sphere.
Definition: lwgeodetic.c:369
void vector_sum(const POINT3D *a, const POINT3D *b, POINT3D *n)
Calculate the sum of two vectors.
Definition: lwgeodetic.c:430
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88

Here is the call graph for this function:

Here is the caller graph for this function: